Re: A New TCP Retransmission Algorithm

Geof Cooper (imagen!apolling!geof@decwrl.DEC.COM)
Wed, 8 Apr 87 11:45:47 pst

> 1. If a segment being ACKed was sent only once, update the estimated round
> trip time and recompute the timeout interval. (This is standard behavior).
> 2. If a timeout occurs, back off the timeout timer interval (e.g., double
> it), retransmit the oldest unacknowledged segment, and restart the timeout
> timer. (Again, nothing unusual).
> 3. When an ACK comes in for a segment that was sent more than once (i.e.,
> retransmitted at least once) do NOT attempt to measure its round trip time;
> leave the smoothed estimate alone. FURTHERMORE, KEEP THE BACKED-OFF TIMER

Looks good. If it works, all the better!

I like the separation of the RTT estimate from the timeout computation.
I think it would help the description of the algorithm to make the
separation clearer. The RTT estimate is a particular metered value, so
it makes a lot of sense to not try to update it based on data that is
questionable. The timeout value is a function of the RTT estimate, but
need not be a simple function -- sometimes it might not depend on the RTT
estimate at all, as you cleverly suggest.

The possible problem is that the RTT might not be estimated for a long
time (if packets are lost frequently). It looks like the algorithm will
correctly play with the timeout in the absence of measured RTT values.
I'm not sure what you do in [1], though. If you compute something like
    RTTnew = (7*RTTold + RTTmeasured)/8
then your behavior may be bad when the RTT had become seriously out of
date and was then measured. You'll get a damped oscilatory response,
I think.

An example:

Say the RTT estimate is 1 second and the retransmission timer is 2 s.
Now imagine that the the network conditions change abruptly
so that the real network RTT is 10 seconds. For several segments,
you get spurious retransmissions and don't compute the RTT. Meanwhile
the retransmission timer is increased using normal backoff. Eventually,
it hits ~10 seconds or so, and you get a valid computation of RTT.
This gives you:
    RTTnew = (7*1 + 10)/8 = 2.125
Then you might compute
    timer = RTT * 2 = 4.25 s

This means that the next segment will also be retransmitted spuriously,
and the process repeats. Maybe my example is too severe when compared
with the real world (I don't think so, if you have both satnets, X.25
links and direct lines as alternate paths to each other).

I guess the moral of the story is to use a method of smoothing the RTT
estimate that converges very quickly, like
    RTTnew = (RTTold + RTTmeasured)/2
or even
    RTTnew = RTTold

One element of incompleteness in the algorithm is the turn-on transition.
You don't specify how to make the initial RTT and Timer guesses. In view
of the above, that sounds especially important in this algorithm.

- Geof Cooper

This archive was generated by hypermail 2.0b3 on Thu Mar 09 2000 - 14:38:07 GMT