|
Previous
|
Content
|
Next
|
|
|
1.0.-
TCP Round-Trip Time Estimates |
|
 |
|
| Karn & Partridge studied the problem of
computing round-trip time estimates. They presented a work in 1.988
summarized
here: |
| TCP implementations attempt to predict future
round-trip times by sampling the behavior of packets sent over a connection
and averaging those samples into a "smoothed" round-trip time estimate SRTT.
When a packet is sent over a TCP connection, the sender times how long it
takes for it to be acked, producing a sequence of round-trip samples:
S(1), S(2), S(3), … With each new sample Si, the new SRTT is computed as: |
| |
SRTT(i+1) =
α * SRTT(i) + (
1-α ) * S(i) |
|
| Where α is a
constant between 0 and 1 that control how rapidly the SRTT adapts to
changes. The retransmission timeout RTO(i),
this means, the amount of time the sender will
wait for a given packet to be acked, is computed
from SRTT(i) as follows: |
|
|
|
Where β is a constant, greater then 1,
chosen such that there is an acceptably small probability that the
round-trip time for the packet will exceed RTO(i). In general having the RTT
samples S(1), S(2), S(3), …, S(i), we hope that the RTO computed from those
values will be a good bound on them. |
| Value of α |
| Mills has measured network round-trip times and
recommends that there be two values for α,
depending on the relative values of the sample S(i) and SRTT(i). He observed
that round-trip times are roughly Poisson distributed but with brief periods
of high delay. During these periods, he found that the standard way of
computing SRTT and RTO often did not adapt switly enough, and the TCP sender
would unnecessary retransmit packets because the RTO was set too low. As a
result, he suggested a nonlinear filter where α
is smaller when SRTT(i) < S(i), allowing the SRTT to adapt more
swiftly to sudden increase in network delay. |
| Value of
β |
| To minimize retransmissions,
β should be chosen such
that the RTO will be a high upper limit on the round-trip times. The TCP
specification recommends a value of
β=2 as
a reasonable balance. Another possibility suggested by Van Jacobson is to
vary β
based on the observed variance in measured round-trip times. |
|
|
|
Whenever a timeout occurs, virtually every TCP
implementation increases the RTO by some factor before retransmitting the
unacked data. Should the new, larger RTO expire yet again before the
retransmission is acked, it is increased still further. This technique is
known as back-off. When the overload condition disappears, packet loss stops
and the TCPs reduce their RTO to their normal SRTT based value. |
|
| When sampling round-trip times a key assumption
is that the sequence of round-trip time samples is an accurate measurement
of the true network round-trip times. Because retransmission problems, when
measuring you have three choices: a.- Measuring from the first transmission.
b.- Measuring from the most recent transmission. c.- Ignoring round-trip
times for packets that have been retransmitted. |
- When measuring from the first transmission may
cause the SRTT to grow without bound when there is loss on the networks.
Inflated round-trip time estimates may not be a problem if the original
reason for the high loss rate was network congestion. However if the path is
lossy the SRTT grows and throughput unnecessarily decreases to low levels.
- When measuring from last transmission things
can really be worst because acks from previous
transmissions may arrive after a retransmission. RTT and indeed RTO are
undervaluated. This reduction of the RTO value increases the likelihood that
a packet will be acked just after the RTO has expire. Unnecessary data
retransmissions ocurr constantly, useful throughput drop sharply, and
network bandwidth is wasted.
- When ignoring round-trip times samples by
retransmissions another problem can occur: if there is a sudden increase in
network round-trip time every packet will be retransmitted before the ack
come back; this case all samples will be discarded maintaining an erroneous
low RTO value been applied. In this case consequences are truly disastrous;
the sender is stuck with an unrealistic short RTO that it has little or no
chance to be corrected. Once again, there are numerous unnecessary
retransmissions, throughput drops sharply and network capacity is wasted.
|
| Karn's algoritm |
| The fundamental notion of Karn's algorithm is
to use RTO back-off (see above) to collect accurate round-trip time
measurements uncontaminated by retransmission ambiguity. The rule is as
follows: |
| When an ack arrives for a packet that has
been sent more than once (i.e. retransmitted at least once), ignore any
round-trip measurement based on this packet thus avoiding the retransmission
ambiguity problem; next apply the back-off algorithm and the backed-off RTO
for this packet is kept for the next packet. Only when it (or a succeeding
packet) is acked without an intervening retransmission, will the RTO be
calculated again from SRTT. |
| The last provision ensure that new and accurate
round-trip measurements will be taken and fed into the SRTT estimate
regardless of any sudden increase in round-trip delay. If the increase is
large, the RTO may oscillate between the backed-off value necessary to avoid
an unnecessary retransmission, and the value calculated from SRTT. However
the SRTT will converge to the correct value and unnecessary retransmission
will stop. |
|
|
|
|
|
Previous
|
Content
|
Next
|
