4.  The RTTM Mechanism

4.1.  Introduction

   One use of the Timestamps option is to measure the round-trip time
   (RTT) of virtually every packet acknowledged.  The RTTM mechanism
   requires a Timestamps option in every measured segment, with a TSval
   that is obtained from a (virtual) "timestamp clock".  Values of this
   clock MUST be at least approximately proportional to real time, in
   order to measure actual RTT.

   TCP measures the RTT, primarily for the purpose of arriving at a
   reasonable value for the RTO timer interval.  Accurate and current
   RTT estimates are necessary to adapt to changing traffic conditions,
   while a conservative estimate of the RTO interval is necessary to
   minimize spurious RTOs.

   These TSval values are echoed in TSecr values in the reverse
   direction.  The difference between a received TSecr value and the
   current timestamp clock value provides an RTT measurement.

   When timestamps are used, every segment that is received will contain
   a TSecr value.  However, these values cannot all be used to update
   the measured RTT.  The following example illustrates why.  It shows a
   one-way data flow with segments arriving in sequence without loss.
   Here A, B, C... represent data blocks occupying successive blocks of
   sequence numbers, and ACK(A),...  represent the corresponding
   cumulative acknowledgments.  The two timestamp fields of the
   Timestamps option are shown symbolically as <TSval=x,TSecr=y>.  Each
   TSecr field contains the value most recently received in a TSval
   field.

             TCP  A                                     TCP B

                             <A,TSval=1,TSecr=120> ----->

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

                             <B,TSval=5,TSecr=127> ----->

                  <---- <ACK(B),TSval=131,TSecr=5>

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

                             <C,TSval=65,TSecr=131> ---->

                  <---- <ACK(C),TSval=191,TSecr=65>

                                 (etc.)

   The dotted line marks a pause (60 time units long) in which A had
   nothing to send.  Note that this pause inflates the RTT, which B
   could infer from receiving TSecr=131 in data segment C.  Thus, in
   one-way data flows, RTTM in the reverse direction measures a value
   that is inflated by gaps in sending data.  However, the following
   rule prevents a resulting inflation of the measured RTT:

   RTTM Rule: A TSecr value received in a segment MAY be used to update
              the averaged RTT measurement only if the segment advances
              the left edge of the send window, i.e., SND.UNA is
              increased.

   Since TCP B is not sending data, the data segment C does not
   acknowledge any new data when it arrives at B.  Thus, the inflated
   RTTM measurement is not used to update B's RTTM measurement.

4.2.  Updating the RTO Value

   When [RFC1323] was originally written, it was perceived that taking
   RTT measurements for each segment, and also during retransmissions,
   would contribute to reduce spurious RTOs, while maintaining the
   timeliness of necessary RTOs.  At the time, RTO was also the only
   mechanism to make use of the measured RTT.  It has been shown that
   taking more RTT samples has only a very limited effect to optimize
   RTOs [Allman99].

   Implementers should note that with timestamps, multiple RTTMs can be
   taken per RTT.  The [RFC6298] RTT estimator has weighting factors,
   alpha and beta, based on an implicit assumption that at most one RTTM
   will be sampled per RTT.  When multiple RTTMs per RTT are available

   to update the RTT estimator, an implementation SHOULD try to adhere
   to the spirit of the history specified in [RFC6298].  An
   implementation suggestion is detailed in Appendix G.

   [Ludwig00] and [Floyd05] have highlighted the problem that an
   unmodified RTO calculation, which is updated with per-packet RTT
   samples, will truncate the path history too soon.  This can lead to
   an increase in spurious retransmissions, when the path properties
   vary in the order of a few RTTs, but a high number of RTT samples are
   taken on a much shorter timescale.

4.3.  Which Timestamp to Echo

   If more than one Timestamps option is received before a reply segment
   is sent, the TCP must choose only one of the TSvals to echo, ignoring
   the others.  To minimize the state kept in the receiver (i.e., the
   number of unprocessed TSvals), the receiver should be required to
   retain at most one timestamp in the connection control block.

   There are three situations to consider:

   (A)  Delayed ACKs.

        Many TCPs acknowledge only every second segment out of a group
        of segments arriving within a short time interval; this policy
        is known generally as "delayed ACKs".  The data-sender TCP must
        measure the effective RTT, including the additional time due to
        delayed ACKs, or else it will retransmit unnecessarily.  Thus,
        when delayed ACKs are in use, the receiver SHOULD reply with the
        TSval field from the earliest unacknowledged segment.

   (B)  A hole in the sequence space (segment(s) has been lost).

        The sender will continue sending until the window is filled, and
        the receiver may be generating <ACK>s as these out-of-order
        segments arrive (e.g., to aid "Fast Retransmit").

        The lost segment is probably a sign of congestion, and in that
        situation the sender should be conservative about
        retransmission.  Furthermore, it is better to overestimate than
        underestimate the RTT.  An <ACK> for an out-of-order segment
        SHOULD, therefore, contain the timestamp from the most recent
        segment that advanced RCV.NXT.

        The same situation occurs if segments are reordered by the
        network.

   (C)  A filled hole in the sequence space.

        The segment that fills the hole and advances the window
        represents the most recent measurement of the network
        characteristics.  An RTT computed from an earlier segment would
        probably include the sender's retransmit timeout, badly biasing
        the sender's average RTT estimate.  Thus, the timestamp from the
        latest segment (which filled the hole) MUST be echoed.

   An algorithm that covers all three cases is described in the
   following rules for Timestamps option processing on a synchronized
   connection:

   (1)  The connection state is augmented with two 32-bit slots:

        TS.Recent holds a timestamp to be echoed in TSecr whenever a
        segment is sent, and Last.ACK.sent holds the ACK field from the
        last segment sent.  Last.ACK.sent will equal RCV.NXT except when
        <ACK>s have been delayed.

   (2)  If:

            SEG.TSval >= TS.Recent and SEG.SEQ <= Last.ACK.sent

        then SEG.TSval is copied to TS.Recent; otherwise, it is ignored.

   (3)  When a TSopt is sent, its TSecr field is set to the current
        TS.Recent value.

   The following examples illustrate these rules.  Here A, B, C...
   represent data segments occupying successive blocks of sequence
   numbers, and ACK(A),... represent the corresponding acknowledgment
   segments.  Note that ACK(A) has the same sequence number as B.  We
   show only one direction of timestamp echoing, for clarity.

   o  Segments arrive in sequence, and some of the <ACK>s are delayed.

      By case (A), the timestamp from the oldest unacknowledged segment
      is echoed.

                                                  TS.Recent
                <A, TSval=1> ------------------->
                                                      1
                <B, TSval=2> ------------------->
                                                      1
                <C, TSval=3> ------------------->
                                                      1
                         <---- <ACK(C), TSecr=1>
                (etc.)

   o  Segments arrive out of order, and every segment is acknowledged.

      By case (B), the timestamp from the last segment that advanced the
      left window edge is echoed until the missing segment arrives; it
      is echoed according to case (C).  The same sequence would occur if
      segments B and D were lost and retransmitted.

                                                  TS.Recent
                <A, TSval=1> ------------------->
                                                      1
                         <---- <ACK(A), TSecr=1>
                                                      1
                <C, TSval=3> ------------------->
                                                      1
                         <---- <ACK(A), TSecr=1>
                                                      1
                <B, TSval=2> ------------------->
                                                      2
                         <---- <ACK(C), TSecr=2>
                                                      2
                <E, TSval=5> ------------------->
                                                      2
                         <---- <ACK(C), TSecr=2>
                                                      2
                <D, TSval=4> ------------------->
                                                      4
                         <---- <ACK(E), TSecr=4>
                (etc.)

5.  PAWS - Protection Against Wrapped Sequences

5.1.  Introduction

   Another use for the Timestamps option is the PAWS mechanism.
   Section 5.2 describes a simple mechanism to reject old duplicate
   segments that might corrupt an open TCP connection.  PAWS operates
   within a single TCP connection, using state that is saved in the
   connection control block.  Section 5.8 and Appendix H discuss the
   implications of the PAWS mechanism for avoiding old duplicates from
   previous incarnations of the same connection.

5.2.  The PAWS Mechanism

   PAWS uses the TCP Timestamps option described earlier and assumes
   that every received TCP segment (including data and <ACK> segments)
   contains a timestamp SEG.TSval whose values are monotonically non-
   decreasing in time.  The basic idea is that a segment can be
   discarded as an old duplicate if it is received with a timestamp
   SEG.TSval less than some timestamps recently received on this
   connection.

   In the PAWS mechanism, the "timestamps" are 32-bit unsigned integers
   in a modular 32-bit space.  Thus, "less than" is defined the same way
   it is for TCP sequence numbers, and the same implementation
   techniques apply.  If s and t are timestamp values,

                       s < t  if 0 < (t - s) < 2^31,

   computed in unsigned 32-bit arithmetic.

   The choice of incoming timestamps to be saved for this comparison
   MUST guarantee a value that is monotonically non-decreasing.  For
   example, an implementation might save the timestamp from the segment
   that last advanced the left edge of the receive window, i.e., the
   most recent in-sequence segment.  For simplicity, the value TS.Recent
   introduced in Section 4.3 is used instead, as using a common value
   for both PAWS and RTTM simplifies the implementation.  As Section 4.3
   explained, TS.Recent differs from the timestamp from the last in-
   sequence segment only in the case of delayed <ACK>s, and therefore by
   less than one window.  Either choice will, therefore, protect against
   sequence number wrap-around.

   PAWS submits all incoming segments to the same test, and therefore
   protects against duplicate <ACK> segments as well as data segments.
   (An alternative non-symmetric algorithm would protect against old
   duplicate <ACK>s: the sender of data would reject incoming <ACK>
   segments whose TSecr values were less than the TSecr saved from the

   last segment whose ACK field advanced the left edge of the send
   window.  This algorithm was deemed to lack economy of mechanism and
   symmetry.)

   TSval timestamps sent on <SYN> and <SYN,ACK> segments are used to
   initialize PAWS.  PAWS protects against old duplicate non-<SYN>
   segments and duplicate <SYN> segments received while there is a
   synchronized connection.  Duplicate <SYN> and <SYN,ACK> segments
   received when there is no connection will be discarded by the normal
   3-way handshake and sequence number checks of TCP.

   [RFC1323] recommended that <RST> segments NOT carry timestamps and
   that they be acceptable regardless of their timestamp.  At that time,
   the thinking was that old duplicate <RST> segments should be
   exceedingly unlikely, and their cleanup function should take
   precedence over timestamps.  More recently, discussions about various
   blind attacks on TCP connections have raised the suggestion that if
   the Timestamps option is present, SEG.TSecr could be used to provide
   stricter acceptance tests for <RST> segments.

   While still under discussion, to enable research into this area it is
   now RECOMMENDED that when generating an <RST>, if the segment causing
   the <RST> to be generated contains a Timestamps option, the <RST>
   should also contain a Timestamps option.  In the <RST> segment,
   SEG.TSecr SHOULD be set to SEG.TSval from the incoming segment and
   SEG.TSval SHOULD be set to zero.  If an <RST> is being generated
   because of a user abort, and Snd.TS.OK is set, then a Timestamps
   option SHOULD be included in the <RST>.  When an <RST> segment is
   received, it MUST NOT be subjected to the PAWS check by verifying an
   acceptable value in SEG.TSval, and information from the Timestamps
   option MUST NOT be used to update connection state information.
   SEG.TSecr MAY be used to provide stricter <RST> acceptance checks.

5.3.  Basic PAWS Algorithm

   If the PAWS algorithm is used, the following processing MUST be
   performed on all incoming segments for a synchronized connection.
   Also, PAWS processing MUST take precedence over the regular TCP
   acceptability check (Section 3.3 in [RFC0793]), which is performed
   after verification of the received Timestamps option:

   R1)  If there is a Timestamps option in the arriving segment,
        SEG.TSval < TS.Recent, TS.Recent is valid (see later
        discussion), and if the RST bit is not set, then treat the
        arriving segment as not acceptable:

           Send an acknowledgment in reply as specified in Section 3.9
           of [RFC0793], page 69, and drop the segment.

           Note: it is necessary to send an <ACK> segment in order to
           retain TCP's mechanisms for detecting and recovering from
           half-open connections.  For an example, see Figure 10 of
           [RFC0793].

   R2)  If the segment is outside the window, reject it (normal TCP
        processing).

   R3)  If an arriving segment satisfies SEG.TSval >= TS.Recent and
        SEG.SEQ <= Last.ACK.sent (see Section 4.3), then record its
        timestamp in TS.Recent.

   R4)  If an arriving segment is in sequence (i.e., at the left window
        edge), then accept it normally.

   R5)  Otherwise, treat the segment as a normal in-window,
        out-of-sequence TCP segment (e.g., queue it for later delivery
        to the user).

   Steps R2, R4, and R5 are the normal TCP processing steps specified by
   [RFC0793].

   It is important to note that the timestamp MUST be checked only when
   a segment first arrives at the receiver, regardless of whether it is
   in sequence or it must be queued for later delivery.

   Consider the following example.

      Suppose the segment sequence: A.1, B.1, C.1, ..., Z.1 has been
      sent, where the letter indicates the sequence number and the digit
      represents the timestamp.  Suppose also that segment B.1 has been
      lost.  The timestamp in TS.Recent is 1 (from A.1), so C.1, ...,
      Z.1 are considered acceptable and are queued.  When B is
      retransmitted as segment B.2 (using the latest timestamp), it
      fills the hole and causes all the segments through Z to be
      acknowledged and passed to the user.  The timestamps of the queued
      segments are *not* inspected again at this time, since they have
      already been accepted.  When B.2 is accepted, TS.Recent is set to
      2.

   This rule allows reasonable performance under loss.  A full window of
   data is in transit at all times, and after a loss a full window less
   one segment will show up out of sequence to be queued at the receiver
   (e.g., up to ~2^30 bytes of data); the Timestamps option must not
   result in discarding this data.

   In certain unlikely circumstances, the algorithm of rules R1-R5 could
   lead to discarding some segments unnecessarily, as shown in the
   following example:

      Suppose again that segments: A.1, B.1, C.1, ..., Z.1 have been
      sent in sequence and that segment B.1 has been lost.  Furthermore,
      suppose delivery of some of C.1, ... Z.1 is delayed until *after*
      the retransmission B.2 arrives at the receiver.  These delayed
      segments will be discarded unnecessarily when they do arrive,
      since their timestamps are now out of date.

   This case is very unlikely to occur.  If the retransmission was
   triggered by a timeout, some of the segments C.1, ... Z.1 must have
   been delayed longer than the RTO time.  This is presumably an
   unlikely event, or there would be many spurious timeouts and
   retransmissions.  If B's retransmission was triggered by the "Fast
   Retransmit" algorithm, i.e., by duplicate <ACK>s, then the queued
   segments that caused these <ACK>s must have been received already.

   Even if a segment were delayed past the RTO, the Fast Retransmit
   mechanism [Jacobson90c] will cause the delayed segments to be
   retransmitted at the same time as B.2, avoiding an extra RTT and,
   therefore, causing a very small performance penalty.

   We know of no case with a significant probability of occurrence in
   which timestamps will cause performance degradation by unnecessarily
   discarding segments.

5.4.  Timestamp Clock

   It is important to understand that the PAWS algorithm does not
   require clock synchronization between the sender and receiver.  The
   sender's timestamp clock is used as a source of monotonic non-
   decreasing values to stamp the segments.  The receiver treats the
   timestamp value as simply a monotonically non-decreasing serial
   number, without any connection to time.  From the receiver's
   viewpoint, the timestamp is acting as a logical extension of the
   high-order bits of the sequence number.

   The receiver algorithm does place some requirements on the frequency
   of the timestamp clock.

   (a)  The timestamp clock must not be "too slow".

        It MUST tick at least once for each 2^31 bytes sent.  In fact,
        in order to be useful to the sender for round-trip timing, the
        clock SHOULD tick at least once per window's worth of data, and
        even with the window extension defined in Section 2.2, 2^31
        bytes must be at least two windows.

        To make this more quantitative, any clock faster than 1 tick/sec
        will reject old duplicate segments for link speeds of ~8 Gbps.
        A 1 ms timestamp clock will work at link speeds up to 8 Tbps
        (8*10^12) bps!

   (b)  The timestamp clock must not be "too fast".

        The recycling time of the timestamp clock MUST be greater than
        MSL seconds.  Since the clock (timestamp) is 32 bits and the
        worst-case MSL is 255 seconds, the maximum acceptable clock
        frequency is one tick every 59 ns.

        However, it is desirable to establish a much longer recycle
        period, in order to handle outdated timestamps on idle
        connections (see Section 5.5), and to relax the MSL requirement
        for preventing sequence number wrap-around.  With a 1 ms
        timestamp clock, the 32-bit timestamp will wrap its sign bit in
        24.8 days.  Thus, it will reject old duplicates on the same
        connection if MSL is 24.8 days or less.  This appears to be a
        very safe figure; an MSL of 24.8 days or longer can probably be
        assumed in the Internet without requiring precise MSL
        enforcement.

   Based upon these considerations, we choose a timestamp clock
   frequency in the range 1 ms to 1 sec per tick.  This range also
   matches the requirements of the RTTM mechanism, which does not need
   much more resolution than the granularity of the retransmit timer,
   e.g., tens or hundreds of milliseconds.

   The PAWS mechanism also puts a strong monotonicity requirement on the
   sender's timestamp clock.  The method of implementation of the
   timestamp clock to meet this requirement depends upon the system
   hardware and software.

   o  Some hosts have a hardware clock that is guaranteed to be
      monotonic between hardware resets.

   o  A clock interrupt may be used to simply increment a binary integer
      by 1 periodically.

   o  The timestamp clock may be derived from a system clock that is
      subject to being abruptly changed by adding a variable offset
      value.  This offset is initialized to zero.  When a new timestamp
      clock value is needed, the offset can be adjusted as necessary to
      make the new value equal to or larger than the previous value
      (which was saved for this purpose).

   o  A random offset may be added to the timestamp clock on a per-
      connection basis.  See [RFC6528], Section 3, on randomizing the
      initial sequence number (ISN).  The same function with a different
      secret key can be used to generate the per-connection timestamp
      offset.

5.5.  Outdated Timestamps

   If a connection remains idle long enough for the timestamp clock of
   the other TCP to wrap its sign bit, then the value saved in TS.Recent
   will become too old; as a result, the PAWS mechanism will cause all
   subsequent segments to be rejected, freezing the connection (until
   the timestamp clock wraps its sign bit again).

   With the chosen range of timestamp clock frequencies (1 sec to 1 ms),
   the time to wrap the sign bit will be between 24.8 days and 24800
   days.  A TCP connection that is idle for more than 24 days and then
   comes to life is exceedingly unusual.  However, it is undesirable in
   principle to place any limitation on TCP connection lifetimes.

   We therefore require that an implementation of PAWS include a
   mechanism to "invalidate" the TS.Recent value when a connection is
   idle for more than 24 days.  (An alternative solution to the problem
   of outdated timestamps would be to send keep-alive segments at a very
   low rate, but still more often than the wrap-around time for
   timestamps, e.g., once a day.  This would impose negligible overhead.
   However, the TCP specification has never included keep-alives, so the
   solution based upon invalidation was chosen.)

   Note that a TCP does not know the frequency, and therefore the wrap-
   around time, of the other TCP, so it must assume the worst.  The
   validity of TS.Recent needs to be checked only if the basic PAWS
   timestamp check fails, i.e., only if SEG.TSval < TS.Recent.  If
   TS.Recent is found to be invalid, then the segment is accepted,
   regardless of the failure of the timestamp check, and rule R3 updates
   TS.Recent with the TSval from the new segment.

   To detect how long the connection has been idle, the TCP MAY update a
   clock or timestamp value associated with the connection whenever
   TS.Recent is updated, for example.  The details will be
   implementation dependent.

5.6.  Header Prediction

   "Header prediction" [Jacobson90a] is a high-performance transport
   protocol implementation technique that is most important for high-
   speed links.  This technique optimizes the code for the most common
   case, receiving a segment correctly and in order.  Using header
   prediction, the receiver asks the question, "Is this segment the next
   in sequence?"  This question can be answered in fewer machine
   instructions than the question, "Is this segment within the window?"

   Adding header prediction to our timestamp procedure leads to the
   following recommended sequence for processing an arriving TCP
   segment:

   H1)  Check timestamp (same as step R1 above).

   H2)  Do header prediction: if the segment is next in sequence and if
        there are no special conditions requiring additional processing,
        accept the segment, record its timestamp, and skip H3.

   H3)  Process the segment normally, as specified in RFC 793.  This
        includes dropping segments that are outside the window and
        possibly sending acknowledgments, and queuing in-window,
        out-of-sequence segments.

   Another possibility would be to interchange steps H1 and H2, i.e., to
   perform the header prediction step H2 *first*, and perform H1 and H3
   only when header prediction fails.  This could be a performance
   improvement, since the timestamp check in step H1 is very unlikely to
   fail, and it requires unsigned modulo arithmetic.  To perform this
   check on every single segment is contrary to the philosophy of header
   prediction.  We believe that this change might produce a measurable
   reduction in CPU time for TCP protocol processing on high-speed
   networks.

   However, putting H2 first would create a hazard: a segment from 2^32
   bytes in the past might arrive at exactly the wrong time and be
   accepted mistakenly by the header-prediction step.  The following
   reasoning has been introduced in [RFC1185] to show that the
   probability of this failure is negligible.

      If all segments are equally likely to show up as old duplicates,
      then the probability of an old duplicate exactly matching the left
      window edge is the maximum segment size (MSS) divided by the size
      of the sequence space.  This ratio must be less than 2^-16, since
      MSS must be < 2^16; for example, it will be (2^12)/(2^32) = 2^-20
      for [a 100 Mbit/s] link.  However, the older a segment is, the
      less likely it is to be retained in the Internet, and under any

      reasonable model of segment lifetime the probability of an old
      duplicate exactly at the left window edge must be much smaller
      than 2^-16.

      The 16 bit TCP checksum also allows a basic unreliability of one
      part in 2^16.  A protocol mechanism whose reliability exceeds the
      reliability of the TCP checksum should be considered "good
      enough", i.e., it won't contribute significantly to the overall
      error rate.  We therefore believe we can ignore the problem of an
      old duplicate being accepted by doing header prediction before
      checking the timestamp.  [Note: the notation for exponentiation
      has been changed from how it appeared in RFC 1185.]

   However, this probabilistic argument is not universally accepted, and
   the consensus at present is that the performance gain does not
   justify the hazard in the general case.  It is therefore recommended
   that H2 follow H1.

5.7.  IP Fragmentation

   At high data rates, the protection against old segments provided by
   PAWS can be circumvented by errors in IP fragment reassembly (see
   [RFC4963]).  The only way to protect against incorrect IP fragment
   reassembly is to not allow the segments to be fragmented.  This is
   done by setting the Don't Fragment (DF) bit in the IP header.

   Setting the DF bit implies the use of Path MTU Discovery as described
   in [RFC1191], [RFC1981], and [RFC4821]; thus, any TCP implementation
   that implements PAWS MUST also implement Path MTU Discovery.

5.8.  Duplicates from Earlier Incarnations of Connection

   The PAWS mechanism protects against errors due to sequence number
   wrap-around on high-speed connections.  Segments from an earlier
   incarnation of the same connection are also a potential cause of old
   duplicate errors.  In both cases, the TCP mechanisms to prevent such
   errors depend upon the enforcement of an MSL by the Internet (IP)
   layer (see the Appendix of RFC 1185 for a detailed discussion).
   Unlike the case of sequence space wrap-around, the MSL required to
   prevent old duplicate errors from earlier incarnations does not
   depend upon the transfer rate.  If the IP layer enforces the
   recommended 2-minute MSL of TCP, and if the TCP rules are followed,
   TCP connections will be safe from earlier incarnations, no matter how
   high the network speed.  Thus, the PAWS mechanism is not required for
   this case.

   We may still ask whether the PAWS mechanism can provide additional
   security against old duplicates from earlier connections, allowing us
   to relax the enforcement of MSL by the IP layer.  Appendix B explores
   this question, showing that further assumptions and/or mechanisms are
   required, beyond those of PAWS.  This is not part of the current
   extension.