[ih] TCP RTT Estimator

[David Finnigan]

About 2 weeks ago I finally began writing the Round Trip Time (RTT)
estimator for my TCP on the Mac. I had previously read many many
documents which described the small, evolutionary changes in this
important function of TCP:

SRTT = ( ALPHA * SRTT ) + ( (1-ALPHA) * RTT )

I was interested in knowing the reason behind why this particular
algorithm was selected. I found a reference to IEN 177, "Comments on
Action Items from the January [1981] Meeting" which stated:

"The algorithm described by RSRE at the October 80 meeting should be
implemented.  It will be included in the next edition of the TCP
specification.

The current best procedure for retransmission timeout is to measure the
time elapsed between sending a data octet with a particular sequence
number and receiving an ack that covers that sequence number (thus one
does not have to match sends and acks one for one)."

I continued looking back in older IEN documents and found in IEN 160, 7
November 1980, it was reported that

"Brian Davies discussed some suggestions for performance improvements
based on the experience at RSRE.

The use of an adaptive retransmission timeout seems to be very helpful.
RSRE has experimented with one based on the following:

1.  For each segment record the sequence number and time sent.

2.  For each acknowledgment determine the round trip time (RTT) of the
sequence number thereby acknowledged.

3.  Compute an Integrated Ack Time (IAT) as follows:

	IAT = ( ALPHA * IAT ) + RTT

4.  Compute a Retransmission Time Estimate (RTE) as follows:

	RTE = Min [ BOUND, ( BETA * IAT ) ]

Where BOUND is an upper bound on the retransmission time and BETA is an
adjustment to the IAT to account for variation in the delay.

RSRE currently uses  ALPHA = 31/32 and BETA = 1.33.

[Dave Clark noted that MIT-MULTICS uses the same algorithm but with
ALPHA = 4/5 and BETA = 1.5.]"



Going still further back to IEN 134 of 29 February 1980, it was reported
that
"Brian discussed some measurements of TCP conducted by RSRE to various
other places in the internet.  The performance is regular for round
trips from RSRE to various points at UCL, and is consistent with the
physical facilities.  Once the round trip path includes the SATNET,
however, the performance becomes irregular, with a few messages subject
to very high delay.  Also some unnecessary retransmissions are detected
in the tests form RSRE to ISIE and back, these may be due to a too low
retransmission threshold."

And the topic is discussed in IEN 121, 25 October 1979.

It looks like staff at RSRE (Royal Signals and Radar Establishment) took
the lead in experimenting with formulae and methods for dynamic
estimation of round trip times in TCP. Does anyone here have any further
insight or recollection into these experiments for estimating RTT, and
the development of the RTT formula?

-David Finnigan