[ih] TCP RTT Estimator

[Michael Greenwald]

If I am remembering correctly (I'm on the move, and don't have access to 
anything other than email to checkup anything at the moment), the RTT 
estimator is not exactly the standard algorithm for computing moving 
average. I think it separately estimated RTT average and RTT variance, 
and added the 2 together (which meant the estimate actually increased, 
briefly, if the RTT was dropping rapidly.)
Also, wasn't there some variation (Craig and MRose? or Van? or Lixia?) 
to eliminate individual round-trips that may have been computed by a 
duplicate or missing packet?

On 3/11/25 10:51 AM, John Day via Internet-history wrote:
> 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://urldefense.com/v3/__https://elists.isoc.org/mailman/listinfo/internet-history__;!!IBzWLUs!Qx0EPP3x4ywRB5-XWkp_6aP7r-BhO-BE73RdziAIZDXr0Nih4_6iMBhKd4qXnPQOeBDL7BYXBXqb1lrq54b1GG5X5Vfp1vceEvud$
>>>
>>
>> -- 
>> *****
>> Craig Partridge's email account for professional society activities and
>> mailing lists.
>> -- 
>> Internet-history mailing list
>> Internet-history at elists.isoc.org
>> https://urldefense.com/v3/__https://elists.isoc.org/mailman/listinfo/internet-history__;!!IBzWLUs!Qx0EPP3x4ywRB5-XWkp_6aP7r-BhO-BE73RdziAIZDXr0Nih4_6iMBhKd4qXnPQOeBDL7BYXBXqb1lrq54b1GG5X5Vfp1vceEvud$