[ih] TCP RTT Estimator

Tue Mar 11 15:06:10 PDT 2025

"Are you speaking of estimating RTT or the value of the retransmission 
timer? They aren’t the same."

You are, of course, right that they are different. And it is totally 
possible that I was/am conflating the two in my recollection. And, I 
agree that I too had seen and used exponential decay to approximate a 
rolling average rate before I used it for RTT estimation in TCP. That 
was before the changes referred to here (which is why/how I remember 
that it differed from "standard" exponential decay -- I changed my 
code). My recollection, for what it's worth, was that this (separate 
mean and variance estimates, combined by weighted addition) was used for 
an estimation of round-trip-time, and a simple multiple of that estimate 
was used for the retransmission timer. But your question makes me 
seriously reconsider whether my recollection is accurate.

On 3/11/25 11:25 AM, John Day wrote:
> That could be. I have encountered it in other places (outside computing) prior to its use in TCP.
>
> Are you speaking of estimating RTT or the value of the retransmission timer? They aren’t the same.
>
> The variance is a mean variance, rather than a standard deviation for obvious reasons.
>
> John
>
>> On Mar 11, 2025, at 14:07, Michael Greenwald via Internet-history<internet-history at elists.isoc.org> wrote:
>>
>> 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$
>> -- 
>> Internet-history mailing list
>> Internet-history at elists.isoc.org
>> https://elists.isoc.org/mailman/listinfo/internet-history