karn_partridge.Improving_RTT_Estimates

Improving Round-Trip Time Estimates in Reliable Transport Protocol

Phil Karn (Bell Communications Research) and Craig Partridge (Harvard), 1991

Summary. The authors give a new method for improving RTT estimations that converges quickly to accurate estimated RTTs and, therefore, RTOs when RTTs change but does not modify the SRTT (smoothed round-trip time) due to retransmission ambiguity or congestion.

More Detail

The performance of TCP depends (among other things) on the successful estimation of the round-trip time (RTT). A smoothed round-trip time (SRTT) is calculated as a function of the current SRTT and an alpha term The alpha term determines how quickly the SRTT adapts to changes in the most recently measured RTT. The SRTT is multiplied by a beta factor (>1) to determine the retransmission time-out (RTO). Typical values for alpha and beta are .0875 & 2, respectively.

If the RTO is too large, bandwidth is wasted because time-outs are not detected quickly. It the RTO is too small, packets are erroneously retransmitted and can lead to congestion and, again, wasted bandwidth. It is especially critical to converge to accurate RTOs when the RTT has changed (perhaps the shortest link has gone down & an alternate route is now being used).

Retransmission ambiguity arises when retransmissions have been sent out and, when the ACK is received, it is not clear which packet (original or retransmission) is being acked. Retransmission ambiguity causes the inaccuracies in RTT estimation.

Previous algorithms to estimate RTT (and their drawbacks) include:

Measuring RTT from the last transmission: leads to underestimation of the RTT -> RTO too small -> unnecessary retransmissions.
Measure RTT from the first transmission: leads to overestimation of RTT -> RTO too big -> wasted bandwidth while waiting for ACKS that never come
Measure only RTTs of packets that aren't retransmitted: if the RTO is smaller than a new, larger RTT, the algorithm never has a chance to catch up: all the samples are discarded because they are retransmissions.

The Karn Algorithm measures only those packets that aren't .retransmitted plus more aggressive RTO backoff to enable the collection of accurate RTT measurements ``uncontaminated by retransmission ambiguity''. The algorithm is:

When an acknowledgement arrives for a datagram that has been sent more than once ... , ignore any RTT measurement based on this datagram thus avoiding the retransmission ambiguity problem. In addition, the backed-off RTO for this datagram is kept for the next datagram. Only when it (or a succeeding datagram) is acknowledged without an intervening retransmission will the RTO be recalculated ...

An implementation in a very lossy network (not congested -- so the RTT should *not* go up just because a datagram was lost -- only if the RTT time really goes up), extimated RTT times remained very stable changing in response only to true RTT changes.