Improving Round-Trip Time Estimates in Reliable Transport Protocol

Summary

• Basic round trip time estimation is not effective in the face of dropped packets and retransmissions. Accurate sampling of round trip times is problematic when a packet is retransmitted a number of times.
• Basic TCP algorithm for RTT estimation:
  • Use exponentially weighted average to estimate the "smoothed" RTT from past RTT samples:
    SRTT_i+1 = (alpha x SRTT_i) + (1 - alpha) x sample_i .... (0 < alpha < 1)
  • Retransmittion time-out (RTO) is Beta x SRTT . (Beta > 1)
  • Smaller alpha allows faster adaptation to changes in SRTT: one suggestion was to use a non-linear filter where alpha is smaller when SRTT < sample_i, so that the SRTT may adapt more swiftly to sudden increases in network delay.
  • For optimal throughput, beta should be just greater than 1; but this may lead to inefficient network utilization due to spurious retransmissions.
• Back-off: Increase the RTO by some factor whenever a timeout occurs. Various algorithms have been suggested: binary exponential back-off (double the RTO every time a timeout occurs), stepping through a table of arbitrary back-off factors, etc.
• Sampling RTT:
  • Measuring from first transmission: Whenever an ack is received, the RTT is computed from the first time the datagram was sent, regardless of how many times the acked datagram has been retransmitted. This can cause the SRTT to grow without bound when there is a loss in the network.
  • Measuring from the most recent transmission: Compute RTT from the most recent retransmission of the acked datagram. Implicit assumption here is that the RTO is accurate; if a packet has to be retransmitted, the previous packet has most certainly been lost. This is not always true; causes problems since the RTT samples obtained may end up being very close to zero (instead of the actual, pssibly larger, value). This will cause SRTT (and, hence, RTO) to reduce, increasing the likelihood that another datagram will be acked just after the RTO has expired.
  • Ignoring RTTs for datagrams that have been retransmitted: This fails to work if there is a sudden increase in network RTT; if the new RTT is larger than the RTO, then all samples will be discarded!
  • The paper's algorithm: When an ack for a datagram that has been retransmitted arrives, ignore any RTT measurement based on this datagram. In addition, the backed-off RTO for this datagram is kept for the next datagram. Only when it (or some later datagram) is acked without an intervening retransmission will the RTO be recalculated from SRTT.