Back to index
Improving Round-Trip Time Estimates in Reliable Transport Protocol
Phil Karn and Craig Partridge
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.
Back to index (Created by Yatin Chawathe)