Subject: Advancing RFC-1323
From: [email-masked] (Bob Braden)
To: [email-masked]
Date: Mon, 26 Apr 1993 17:16:18 -0700

Folks,

Comments on the RFC-1323 RTTM algorithm from Dave Borman and Tom Skibo
led me to believe that we need to tinker with RFC-1323 before it is
advance to Draft Standard.  Here is a summary of my ideas on what
ought to be changed.

Bob Braden

----- Begin Included Message -----

Date: Mon, 26 Apr 1993 17:14:47 -0700
From: braden (Bob Braden)
To: braden
Content-Length: 17053
X-Lines: 532

NSF/tcp.extend/newrfc.txt

Network Working Group                                          R. Braden
Internet Draft                                                       ISI
                                                          April 25, 1993

             TCP Extensions for High Performance: An Update

Status of This Memo

   This memo is for information only.

Abstract

   This memo presents some suggested modifications to RFC-1323, which
   defined TCP extensions to improve performance over large
   bandwidth*delay product paths and to provide reliable operation over
   very high-speed paths.  It is intended that these changes will be
   merged into the successor to RFC-1323.

1. INTRODUCTION

   RFC-1323 [Jacobson92] defined a set of extensions to the TCP protocol
   [Postel81] to improve performance over large bandwidth*delay product
   paths and to provide reliable operation over very high-speed paths.

   Specifically, RFC-1323 defined three new mechanisms.

   (1)  Window Scale Option

        A new TCP option, "Window Scale" allows windows larger than
        2**16 bytes.  This option defines an implicit scale factor,
        which is used to multiply the window size value found in a TCP
        header to obtain the true window size.

   (2)  RTTM: Round-Trip Time Measurement

        A new TCP option "Timestamps" is introduced, and a mechanism
        called "RTTM"  (Round Trip Time Measurement) uses this option to
        obtain improved measurement of round trip times (RTTs).

   (3)  PAWS: Protect Against Wrapped Sequence

        The Timestamps option is used by the PAWS mechanism to extend
        TCP reliability to transfer rates well beyond the foreseeable
        upper limit of network bandwidths, with reasonably large values
        of the Maximum Segment Lifetime (MSL).

Braden                                                          [Page 1]


Internet Draft     TCP Performance Extensions: Update         April 1993

   The present document summarizes several minor issues and
   clarifications that have accumulated since RFC-1323 was published.

2. MODIFICATIONS TO RFC-1323

   2.1  RTTM: When Make RTT Measurement?

      TCP requires that the RTO (retransmission timeout) values used for
      successive retransmissions of the same segment form an increasing
      sequence; this is known as "retransmission back-off".  TCP
      implementations have previously been required [RFC-1323] to use
      Karn's algorithm [Karn87], which states that (1) retransmission
      back-off will persist until the next ACK is received for a data
      segment that has never been retransmitted, and that (2) no RTT
      measurements will be made from acknowledgments for re-transmitted
      data segments.  Karn's algorithm was designed to allow reliable
      RTT estimates despite the ambiguity when an ACK is received for a
      retransmitted data segment: the ACK may have been created from
      either the original or the retransmission [Zhang86].

      However, as RFC-1323 implied but did not clearly state, the RTTM
      mechanism replaces Karn's algorithm.  The RTTM mechanism resolves
      the ambiguity in RTT measurement from an acknowledgment for a
      retransmitted data segment; the ACK segment will echo the
      timestamp from whichever data segment caused it be sent.
      Overriding the Karn algorithm was implied by the following
      statement on page 14 of RFC-1323, which was independent of whether
      or not the new data being acknowledged has been retransmitted:

           "A TSecr value received in a segment is used to update the
           averaged RTT measurement only if the segment acknowledges
           some new data, i.e., only if it advances the left edge of the
           send window."

      This RFC-1323 rule furthermore implies that duplicate
      acknowledgments will not contribute to measurement of the RTT,
      even with RTTM in use.  Suppose that exactly one segment is lost
      per window of N segments, resulting in N-1 duplicate ACKs.  RTTM
      will make a new RTT measurement only from the ACK triggered by
      retransmission of the (assuming it is successfully acknowledged);
      none of the N segments originally sent will be used.  Therefore,

      *    the discussion under bullet (B) on page 15 of RFC-1323 is
           gratuitous: no matter which timestamp is echoed in a
           duplicate ACK segment, it (the echoed timestamp) will be
           ignored; and

      *    with one lost segment per window, RTTM will result in only

Braden                                                          [Page 2]


Internet Draft     TCP Performance Extensions: Update         April 1993

           one RTT measurement per window.  However, this is still a
           significant improvement over a standard TCP without RTTM,
           which will make no measurements in the same circumstances.

      The diagram on the top of page 14 of RFC-1323 illustrates why
      TSecr can be accepted only if new data is acknowledged; otherwise,
      the RTT value may be artifically inflated.  We could consider an
      alternative criterion for accepting TSecr that would prevent
      inflation in the RFC-1323 example: only use TSecr if the
      transmitter has outstanding data, i.e., only if SND_NXT > SND_UNA.
      However, the following example, involving simultaneous data
      transmission from both sides, illustrates why this alternative
      criterion won't work.

         TCP  A                                          TCP B

       (TSrecent)                                      (TSrecent)

      1.         <A,TSval=1,TSecr=120>         ------>       (1)

      2.  (127)  <-----      <X,ACK(A),TSval=127,TSecr=1>    (1)

      3.  (127)  <ACK(X),TSval=5,TSecr=127>    ------>       (5)

             . . . . . . . . . . . . . . . . . . . . . .

      4.  (127)  <B,ACK(X),TSval=65,TSecr=127> --->  ...

      5.            ... <--- <Y,ACK(A),TSval=191,TSecr=5>    (5)

      4'.               <B,ACK(X),TSval=65,TSecr=127> --->  (65)

      5'.  (191)  <-- <Y,ACK(A),TSval=191,TSecr=5>

      6.            ... <--- <Y,ACK(B),TSval=195,TSecr=65>  (65)

      7.  (191)  <B,ACK(Y),TSval=68,TSecr=191> --->  ...

      In this symmetrical data transfer example, both sides send data
      simultaneously (lines 4 and 5) after a pause of roughly 60 time
      units.  When these segments arrive (lines 4' and 5') each side has
      outstanding data and therefore would use the TSecr to update its
      RTT estimate.  The result would be to inflate each RTT estimate by
      60 time units.  We believe that the only way to ensure the
      measured RTT is accurate is to accept TSecr only when new data is
      acknowledged, and accept that duplicate ACKs will not update the
      RTT estimate.

Braden                                                          [Page 3]


Internet Draft     TCP Performance Extensions: Update         April 1993

   2.2  RTTM: Which Timestamp to Echo?

      Step (2) of the algorithm to control which timestamp is echoed,
      given in RFC-1323 (see top of p. 16), is incorrect in two regards:
      (1) it will fail to update TSrecent for a retransmitted segment
      that resulted from a lost ACK, and (2) it will fail if SEG.LEN =
      0.

      The correct step (2) is actually simpler.  It is as follows:

           (2)  If: SEG.TSval >= TSrecent and SEG.SEQ <= Last.ACK.sent
                then SEG.TSval is copied to TS.Recent; otherwise, it is
                ignored.

      Observe that this algorithm explicitly constructs a monotonic
      sequence of TSrecent values.  The case SEG.TSval = TSrecent is
      included here for consistency with the PAWS test.  Note also that
      RFC-1323 correctly rendered this algorithm in Section 4.2.1
      discussing PAWS, and also incorrectly (!) on page 35.

   2.3  Implementation of TCP Options

      The hardest part of implementing RFC-1323 extensions is probably
      the modifications to allow TCP options in data segments while
      obeying the limits set by the MSS (maximum segment size) and by
      the connected network MTU (maximum transmission unit).  This issue
      has been widely misunderstood, perhaps partly due to a past
      imprecision in terminology (e.g., what is a "segment"?).  In
      addition, prior attempts to clarify these issues have been
      unfortunately obscure [RFC-1122].

      To send a segment, the general procedure for a TCP should be:

           (a) Get a packet buffer and copy a header template into it.

           (b) Format any required TCP options into the buffer.

           (c) Copy 'len' bytes of data into buffer, where:

                len = min( data_to_send, maxseg, maxoptdata - optlen );

      Here:

      *    data_to_send = Amount of data to be sent.

      *    maxseg = "Normal" data length in a segment.

      *    maxoptdata =  Largest <data + TCP options> area permitted.

Braden                                                          [Page 4]


Internet Draft     TCP Performance Extensions: Update         April 1993

      *    optlen = length of options added in (b).

      Finally, we must define how to compute 'maxseg' and 'maxoptdata'.

          maxoptdata = min( Received_MSS, pathMTU - 40) -

                                      <max IP option length>

          maxseg = maxoptdata - <size of 'normal' TCP options>

      Here "Received_MSS" is the value received in an MSS option in a
      SYN segment, or 536 if none is received.  The MTU over the path,
      "pathMTU", may be found by MTU Discovery, or it may be determined
      by the following heuristic:  use "interface_MTU" if the
      destination is on the connected network, else use 576.  In normal
      usage today, there are no IP options to be considered.

      An MSS option is intended to specify ONLY a property of the remote
      host, independent of the path: the largest IP datagram that can be
      received and reassembled (less 40).  For those hosts that have no
      limit on datagram size, it would not be incorrect to specify
      "infinity" (65535) in its MSS option.  However, a more sensible
      choice would be "interface_MTU".

      Note also that 'maxseg' is also used by the SWS (silly-window
      syndrome) and congestion control algorithms of TCP [RFC-1122], and
      it should correspond to the "normal" data block size for a segment
      used in bulk transmission.

3. SUMMARY OF ALGORITHMS

   Appendix E of RFC-1323 defined the overall algorithm as modifications
   of the TCP Event Processing rules.  The following is a more concise
   and algorithmic description of the algorithms.

   We define the following symbols:

   Options

       WSopt:       TCP Window Scale Option
       TSopt:       TCP Timestamps Option

   Option Fields

       shift.cnt:   Window scale byte in WSopt.
       TSval:       32-bit Timestamp Value field in TSopt.
       TSecr:       32-bit Timestamp Reply field in TSopt.

Braden                                                          [Page 5]


Internet Draft     TCP Performance Extensions: Update         April 1993

   Option Fields in Current Segment

       SEG.TSval:   TSval field from TSopt in current segment.
       SEG.TSecr:   TSecr field from TSopt in current segment.
       SEG.WSopt:   8-bit value in WSopt

   Clock Values

       my.TSclock:      Local source of 32-bit timestamp values
       my.TSclock.rate: Period of my.TSclock (1 ms to 1 sec per tick).

   Per-Connection State Variables

       TS.Recent:       Latest received Timestamp
       Last.ACK.sent:   Last ACK field sent

       Snd.TS.OK:       1-bit flag
       Snd.WS.OK:       1-bit flag

       Rcv.Wind.Scale:  Receive window scale power
       Snd.Wind.Scale:  Send window scale power

       Start.Time:      my.TSclock value when segment being timed was
                        sent (used by pre-1323 code).

   Procedure

       Update_SRTT( m ) Procedure to update the smoothed RTT and RTT variance
                        estimates, using the Jacobson algorithms [Jacobson88].
                        Here m is a new RTT measurement in seconds.

   PSEUDO-CODE SUMMARY:

   Create new TCB => {
         Rcv.wind.scale =
             MIN( 14, MAX( 0, floor(log2(receive buffer space)) - 15 ) );
         Snd.wind.scale = 0;
         Last.ACK.sent = 0;
         Snd.TS.OK = Snd.WS.OK = FALSE;
   }

   Send initial {SYN} segment => {

          SEG.WND = MIN( SND.WND, 65535 );
          Include in segment: TSopt(TSval=my.TSclock, TCecr=0);
          Include in segment: WSopt = Rcv.wind.scale;

Braden                                                          [Page 6]


Internet Draft     TCP Performance Extensions: Update         April 1993

   }

   Send {SYN, ACK} segment => {

          SEG.ACK = Last.ACK.sent = RCV.NXT;
          SEG.WND = MIN( SND.WND, 65535 );
          if (Snd.TS.OK) then
                 Include in segment: TSopt(TSval=my.TSclock, TSecr=TS.Recent);
          if (Snd.WS.OK) then
                 Include in segment: WSopt = Rcv.wind.scale;
   }

   Receive {SYN} or {SYN,ACK} segment => {

          if (Segment contains TSopt) then {
                 TS.Recent = SEG.TSval;
                 Snd.TS.OK = TRUE;
                 if (is {SYN,ACK} segment) then
                       Update_SRTT(
                            (my.TSclock - SEG.TSecr)*my.TSclock.rate ) ;
          }

          if Segment contains WSopt) then {
                 Snd.wind.scale = SEG.WSopt;
                 Snd.WS.OK = TRUE;
          }
          else
                 Rcv.wind.scale = Snd.wind.scale = 0;
   }

   Send non-SYN segment => {

          SEG.ACK = Last.ACK.sent = RCV.NXT;
          SEG.WND = MIN( SND.WND >> Rcv.wind.scale, 65535 );
          if (Snd.TS.OK) then
                 Include in segment: TSopt(TSval=my.TSclock, TSecr=TS.Recent);
   }

   Receive non-SYN segment in (state >= ESTABLISHED) => {

          Window = (SEG.WND << Snd.wind.scale);
                /* Use 32-bit 'Window' instead of 16-bit 'SEG.WND'
                 * in rest of processing.

Braden                                                          [Page 7]


Internet Draft     TCP Performance Extensions: Update         April 1993

                 */

          if (Segment contains TSopt) then {
                 if (SEG.TSval < TS.Recent) then {
                        if (Send.TS.OK
                            AND (Idle less than 25 hours)
                            AND (NOT RST) ) then {
                                 /* Timestamp too old =>
                                  *    segment is unacceptable.
                                  */
                              Send ACK segment;
                              Discard segment and return;
                        }
                 }
                 else {
                        if (SEG.SEQ =< Last.ACK.sent) then
                               TS.Recent = SEG.TSval;
                 }
          }

          if (SEG.ACK > SND.UNA) then {
                       /* (At least part of) first segment in
                        * retransmission queue has been ACKd
                        */
                 if (Segment contains TSopt) then
                        Update_SRTT(
                           (my.TSclock - SEG.TSecr)/my.TSclock.rate);
                 else
                        Update_SRTT( /* for compatibility */
                           (my.TSclock - Start.Time)/my.TSclock.rate);
          }
   }

4.  REFERENCES

      [Jacobson88] Jacobson, V., "Congestion Avoidance and Control",
      SIGCOMM '88, Stanford, CA., August 1988.

      [Jacobson92]  Jacobson, V., Braden, R., and D. Borman, "TCP
      Extensions for High Performance", RFC-1323, May 1992.

      [Karn87]  Karn, P. and C. Partridge, "Estimating Round-Trip Times
      in Reliable Transport Protocols", Proc. SIGCOMM '87, Stowe, VT,
      August 1987.

      [Postel81]  Postel, J., "Transmission Control Protocol - DARPA

Braden                                                          [Page 8]


Internet Draft     TCP Performance Extensions: Update         April 1993

      Internet Program Protocol Specification", RFC 793, DARPA,
      September 1981.

      [RFC-1122]  Braden, R., Ed., "Requirements for Internet Hosts --
      Communication Layers", RFC-1122, October 1989.

      [Zhang86]  Zhang, L., "Why TCP Timers Don't Work Well", Proc.
      SIGCOMM '86, Stowe, Vt., August 1986.

Security Considerations

   Security issues are not discussed in this memo.

Authors' Addresses

   Bob Braden
   University of Southern California
   Information Sciences Institute
   4676 Admiralty Way
   Marina del Rey, CA 90292

   Phone: (213) 822-1511
   EMail: [email-masked]

Braden                                                          [Page 9]


----- End Included Message -----

Date: Wed, 14 Apr 1993 12:43:05 -0700
From: [email-masked] (Bob Braden)
To: [email-masked]
Subject: SunOS 4.1.1 version

Hi.  I have a version of RFC-1323 changes for SunOS 4.1.1.  I recently
put together a set of context diffs that would allow someone else with
Sun sources to try my code.  If you are interested, drop me a line.

Bob Braden