[ih] TCP RTT Estimator

[John Day]

This algorithm and variations of it are used throughout science in many different places, sometimes called convolution to compute a moving average.

It is far from unique to TCP or even networking.

Take care,
John

> On Mar 11, 2025, at 12:01, Craig Partridge via Internet-history <internet-history at elists.isoc.org> wrote:
> 
> Yes, informally known as the RSRE algorithm.
> 
> The other detail is the value for Alpha was chosen to be fast on computers
> of the time and so is a fraction of 1/8.
> 
> Craig
> 
> On Tue, Mar 11, 2025 at 8:05 AM David Finnigan via Internet-history <
> internet-history at elists.isoc.org> wrote:
> 
>> 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
>> --
>> Internet-history mailing list
>> Internet-history at elists.isoc.org
>> https://elists.isoc.org/mailman/listinfo/internet-history
>> 
> 
> 
> -- 
> *****
> Craig Partridge's email account for professional society activities and
> mailing lists.
> -- 
> Internet-history mailing list
> Internet-history at elists.isoc.org
> https://elists.isoc.org/mailman/listinfo/internet-history