[ih] TCP RTT Estimator

[Craig Partridge]

Michael is right about capturing round-trip time measurements for segments
that were retransmitted -- that was Karn's algorithm.

The measurements go into the SRTT, which is in turn used to calculate the
RTO.  Jacobson created the updated algorithm for computing the RTO from the
SRTT.

Craig

On Tue, Mar 11, 2025 at 4:06 PM Michael Greenwald via Internet-history <
internet-history at elists.isoc.org> wrote:

> "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
> --
> 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.