rfc1185.txt

来自「RFC 的详细文档！」· 文本 代码 · 共 1,179 行 · 第 1/4 页

      sensible receiver).  RFC-1072 defined a timestamp echo option for
      this purpose.

      It is vitally important to use the timestamp echo option with big
      windows; otherwise, the door is opened to some dangerous
      instabilities due to aliasing.  Furthermore, the option is
      probably useful for all TCP's, since it simplifies the sender.

   2.3  Avoiding Old Duplicate Segments

      Timestamps carried from sender to receiver in TCP Echo options can
      also be used to prevent data corruption caused by sequence number
      wrap-around, as this section describes.

      2.3.1  Basic Algorithm

         Assume that every received TCP segment contains a timestamp.
         The basic idea is that a segment received with a timestamp that
         is earlier than the timestamp of the most recently accepted
         segment can be discarded as an old duplicate.  More
         specifically, the following processing is to be performed on
         normal incoming segments:

         R1)  If the timestamp in the arriving segment timestamp is less
              than the timestamp of the most recently received in-
              sequence segment, treat the arriving segment as not
              acceptable:

                   If SEG.LEN > 0, send an acknowledgement in reply as
                   specified in RFC-793 page 69, and drop the segment;
                   otherwise, just silently drop the segment.*

_________________________
*Sending an ACK segment in reply is not strictly necessary, since  the
case  can  only  arise  when a later in-order segment has already been
received.   However,  for  consistency  and  simplicity,  we   suggest
treating  a  timestamp  failure  the  same  way  TCP  treats any other
unacceptable segment.




Jacobson, Braden & Zhang                                        [Page 6]

RFC 1185               TCP over High-Speed Paths            October 1990


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

         R3)  If an arriving segment is in-sequence (i.e, at the left
              window edge), accept it normally and record its timestamp.

         R4)  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 are the normal TCP processing steps specified by
         RFC-793, except that in R3 the latest timestamp is set from
         each in-sequence segment that is accepted.  Thus, the latest
         timestamp recorded at the receiver corresponds to the left edge
         of the window and only advances when the left edge moves
         [Jacobson88].

         It is important to note that the timestamp is checked only when
         a segment first arrives at the receiver, regardless of whether
         it is in-sequence or is queued.  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 highest in-sequence
              timestamp 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, the receivers's current timestamp is set to 2.

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

         In certain unlikely circumstances, the algorithm of rules R1-R4
         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



Jacobson, Braden & Zhang                                        [Page 7]

RFC 1185               TCP over High-Speed Paths            October 1990


              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 was delayed past the RTO, the selective
         acknowledgment (SACK) facility of RFC-1072 will cause the
         delayed packets 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.

      2.3.2  Header Prediction

         "Header prediction" [Jacobson90] is a high-performance
         transport protocol implementation technique that is 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 sequence for processing an arriving TCP segment:

         H1)  Check timestamp (same as step R1 above)

         H2)  Do header prediction: if 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.



Jacobson, Braden & Zhang                                        [Page 8]

RFC 1185               TCP over High-Speed Paths            October 1990


              This includes dropping segments that are outside the
              window and possibly sending acknowledgments, and queueing
              in-window, out-of-sequence segments.

         However, the timestamp check in step H1 is very unlikely to
         fail, and it is a relatively expensive operation since it
         requires interval arithmetic on a finite field.  To perform
         this check on every single segment seems like poor
         implementation engineering, defeating the purpose of header
         prediction.  Therefore, we suggest that an implementor
         interchange H1 and H2, i.e., perform header prediction FIRST,
         performing H1 and H3 only if header prediction fails.  We
         believe that this change might gain 5-10% in performance on
         high-speed networks.

         This reordering does raise a theoretical hazard: a segment from
         2**32 bytes in the past may arrive at exactly the wrong time
         and be accepted mistakenly by the header-prediction step.  We
         make the following argument 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 an FDDI 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.

      2.3.3  Timestamp Frequency

         It is important to understand that the receiver algorithm for
         timestamps does not involve clock synchronization with the
         sender.  The sender's clock is used to stamp the segments, and
         the sender uses this fact to measure RTT's.  However, the



Jacobson, Braden & Zhang                                        [Page 9]

RFC 1185               TCP over High-Speed Paths            October 1990


         receiver treats the timestamp as simply a monotone-increasing
         serial number, without any necessary connection to its clock.
         From the receiver's viewpoint, the timestamp is acting as a
         logical extension of the high-order bits of the sequence
         number.

         However, the receiver algorithm dpes place some requirements on
         the frequency of the timestamp "clock":

         (a)  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 RFC-1072 window
              extension, 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 ~2 Gbps;  a 1ms clock will work up to link
              speeds of 2 Tbps (10**12 bps!).

         (b)  Timestamp clock must not be "too fast".

              Its cycling time 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, since the sender is using the timestamp for RTT
              calculations, the timestamp doesn't need to have much more
              resolution than the granularity of the retransmit timer,
              e.g., tens or hundreds of milliseconds.

         Thus, both limits are easily satisfied with a reasonable clock
         rate in the range 1-100ms per tick.

         Using the timestamp option relaxes the requirements on MSL for
         avoiding sequence number wrap-around.  For example, with a 1 ms
         timestamp clock, the 32-bit timestamp will wrap its sign bit in
         25 days.  Thus, it will reject old duplicates on the same
         connection as long as MSL is 25 days or less.  This appears to
         be a very safe figure.  If the timestamp has 10 ms resolution,
         the MSL requirement is boosted to 250 days.  An MSL of 25 days
         or longer can probably be assumed by the gateway system without
         requiring precise MSL enforcement by the TTL value in the IP
         layer.




Jacobson, Braden & Zhang                                       [Page 10]

RFC 1185               TCP over High-Speed Paths            October 1990


3.  DUPLICATES FROM EARLIER INCARNATIONS OF CONNECTION

   We turn now to the second potential cause of old duplicate packet
   errors: packets from an earlier incarnation of the same connection.
   The appendix contains a review the mechanisms currently included in
   TCP to handle this problem.  These mechanisms depend upon the
   enforcement of a maximum segment lifetime (MSL) by the Internet
   layer.

   The MSL required to prevent failures due to an earlier connection
   incarnation does not depend (directly) upon the transfer rate.
   However, the timestamp option used as described in Section 2 can
   provide additional security against old duplicates from earlier
   connections.  Furthermore, we will see that with the universal use of
   the timestamp option, enforcement of a maximum segment lifetime would
   no longer be required for reliable TCP operation.

   There are two cases to be considered (see the appendix for more
   explanation):  (1) a system crashing (and losing connection state)
   and restarting, and (2) the same connection being closed and reopened
   without a loss of host state.  These will be described in the
   following two sections.

   3.1  System Crash with Loss of State