Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!lll-crg!mordor!sri-spam!nike!ucbcad!ucbvax!LBL-CSAM.ARPA!van
From: van@LBL-CSAM.ARPA (Van Jacobson)
Newsgroups: mod.protocols.tcp-ip
Subject: Re: Setting Initial Round-trip time
Message-ID: <8610311813.AA04616@lbl-csam.arpa>
Date: Fri, 31-Oct-86 13:13:01 EST
Article-I.D.: lbl-csam.8610311813.AA04616
Posted: Fri Oct 31 13:13:01 1986
Date-Received: Mon, 3-Nov-86 19:47:52 EST
Sender: daemon@ucbvax.BERKELEY.EDU
Organization: The ARPA Internet
Lines: 54
Approved: tcp-ip@sri-nic.arpa

I've got a little bit of hard data and a simple change that may improve
things for 4.[23]bsd.  About six months ago I instrumented our Internet
gateway to record a timestamp, src & dst address and port and data & ack
sequence numbers for each tcp packet.  I reduced two days worth of
this trace data and found

  . the distribution of number of data packets sent on a connection
    was roughly exponential with a mean of 4 (e.g., a lot of mail
    traffic).

  . between 7am and 5pm, PDT, the mean number of retransmissions per
    data packet was 8.  The distribution was bi-modal, with traffic
    through the "mail bridges" in one lobe (with a mode of ~11) and
    all other traffic in the other lobe (a mode of ~2).  Both lobes
    were approximately Poisson, possibly due to the long "learning
    time" of round trip timers on the connections.

  . For a particular connection, round trip times varied about an
    order of magnitude.  Over all connections, round trip times
    varied three orders of magnitude.  (With the large number of
    retransmissions, there is some ambiguity in which packets one
    uses to estimate RTT.  I generally used the time from the first
    use of a sequence number to its first ack, with some ad hoc
    hackery to accomodate the 50% packet loss through the mail
    bridges.  Given this ambiguity, the uncertainty in any RTT
    estimate is at least a factor of two.)

  . The next hop Internet gateway was strongly correlated with the RTT
    in the following sense:  the average RTT of all packets through a
    gateway is within a factor of three of the average RTT of each
    connection through that gateway.

It is not hard to convince yourself that no reasonable setting of the
RTT initial value & filter constants is going to accomodate a factor
of 1000 variation in four packets worth of learning time.  I mentioned
the problem to Mike O'Dell & he suggested using the kernel's routing
entry to cache the RTT.  I made up a kernel that kept an RTT in each
route.  When a TCP connection was opened, it initialized its RTT from
the route.  When the connection closed, its RTT was used to update
the route's RTT with a weighted average
     Rt = A * Rt + (1-A) * Conn
(the 4.3bsd kernel changes for all this amount to about 20 lines of C).

I took 12 hours of trace data with the filter constant set to .5.
The average number of retransmissions *for traffic that originated at
the gateway* went down a factor of two (8 to 4).  I was going to take
more data and try tuning the connection and route filter constants.
Unfortunately, some local political changes intervened and I can no
longer make changes or take data on the gateway.  However, the initial
results were promising enough that I plan to try a similar scheme
for machines that sit behind the gateway (i.e., construct pseudo-route
entries to cache the RTT).

  - Van Jacobson, LBL