rfc1379.txt

RFC 的详细文档！

      The PAWS mechanism [RFC-1323] uses TCP "timestamps" as
      monotonically increasing integers in order to throw out old
      duplicate segments within the same incarnation.  Jacobson
      suggested the cacheing of these timestamps for bypassing 3-way
      handshakes [Jacobson90], i.e., that TCP timestamps be used for our
      common monotonic space M.  This idea is attractive since it would
      allow the same timestamp options to be used for RTTM, PAWS, and
      transactions.



Braden                                                         [Page 16]

RFC 1379              Transaction TCP -- Concepts          November 1992


      To obtain at-most-once service, the criterion for immediate
      acceptance of a SYN must be that SEG.M is strictly greater than
      the cached M value.  That is, to be useful for bypassing 3-way
      handshakes, the timestamp clock must tick at least once between
      any two successive transactions between the same pair of hosts
      (even if different ports are used).  Hence, the timestamp clock
      rate would determine TRmax, the maximum possible transaction rate.

      Unfortunately, the timestamp clock frequency called for by RFC-
      1323, in the range 1 sec to 1 ms, is much too slow for
      transactions.  The TCP timestamp period was chosen to be
      comparable to the fundamental interval for computing and
      scheduling retransmission timeouts; this is generally in the range
      of 1 sec. to 1 ms., and in many operating systems, much closer to
      1 second.  Although it would be possible to increase the timestamp
      clock frequency by several orders of magnitude, to do so would
      make implementation more difficult, and on some systems
      excessively expensive.

      The wraparound time for TCP timestamps, at least 24 days, causes
      no problem for transactions.

      The PAWS mechanism uses TCP timestamps to protect against old
      duplicate non-SYN segments from the same incarnation [RFC-1323].
      It can also be used to protect against old duplicate data segments
      from earlier incarnations (and therefore allow shortening of
      TIME-WAIT state) if we can ensure that the timestamp clock ticks
      at least once between the end of one incarnation and the beginning
      of the next.  This can be achieved by setting U = 2 seconds, i.e.,
      to twice the maximum timestamp clock period.  This value in
      formula [2] leads to an upper bound TRmax = 32K Tps between a host
      pair.  However, as pointed out above, old duplicate SYN detection
      using timestamps leads to a smaller transaction rate bound, 1 Tps,
      which is unacceptable.  In addition, the timestamp approach is
      imperfect; it allows old ACK segments to enter the new connection
      where they can cause a disconnect.  This happens because old
      duplicate ACKs that arrive during TIME-WAIT state generate new
      ACKs with the current timestamp [RFC-1337].

      We therefore conclude that timestamps are not adequate as the
      monotonic space M; see Table I.  However, they may still be useful
      to effectively extend some other monotonic number space, just as
      they are used in PAWS to extend the TCP sequence number space.
      This is discussed below.







Braden                                                         [Page 17]

RFC 1379              Transaction TCP -- Concepts          November 1992


   5.2 Current TCP Sequence Numbers

      It is useful to understand why the existing 32-bit TCP sequence
      numbers do not form an appropriate monotonic space for
      transactions.

      The sequence number sent in an initial SYN is called the Initial
      Sequence Number or ISN.  According to the TCP specification, an
      ISN is to be selected using:

      [3]      ISN = (R*T) mod 2**32

      where T is the real time in seconds (from an arbitrary origin,
      fixed when the system is started) and R is a constant, currently
      250 KBps.  These ISN values form a monotonic time sequence that
      wraps in 4.55 hours = 16380 seconds and has a granularity of 4
      usecs.  For transaction rates up to roughly 250K Tps, the ISN
      value calculated by formula [3] will be monotonic and could be
      used for bypassing the 3-way handshake.

      However, TCP sequence numbers (alone) could not be used to shorten
      TIME-WAIT state, because there are several ways that overlap of
      the sequence space of successive incarnations can occur (as
      described in Appendix to [RFC-1185]).  One way is a "fast
      connection", with a transfer rate greater than R; another is a
      "long" connection, with a duration of approximately 4.55 hours.
      TIME-WAIT delay is necessary to protect against these cases.  With
      the official delay of 240 seconds, formula [1] implies a upper
      bound (as RTT -> 0) of TRmax = 268 Tps; with our target MSL of
      2000 sec, TRmax = 32 Tps.  These values are unacceptably low.

      To improve this transaction rate, we could use TCP timestamps to
      effectively extend the range of the TCP sequence numbers.
      Timestamps would guard against sequence number wrap-around and
      thereby allow us to increase R in [3] to exceed the maximum
      possible transfer rate.  Then sequence numbers for successive
      incarnations could not overlap.  Timestamps would also provide
      safety with an MSL as large as 24 days.  We could then set U = 0
      in the TIME-WAIT delay calculation [2].  For example, R = 10**9
      Bps leads to TRmax <= 10**9 Tps. See 2(b) in Table I.  These
      values would more than satisfy our objectives.

      We should make clear how this proposal, sequence numbers plus
      timestamps, differs from the timestamps alone discussed (and
      rejected) in the previous section.  The difference lies in what is
      cached and tested for TAO; the proposal here is to cache and test
      BOTH the latest TCP sequence number and the latest TCP timestamp.
      In effect, we are proposing to use timestamps to logically extend



Braden                                                         [Page 18]

RFC 1379              Transaction TCP -- Concepts          November 1992


      the sequence space to 64 bits.  Another alternative, presented in
      the next section, is to directly expand the TCP sequence space to
      64 bits.

      Unfortunately, the proposed solution (TCP sequence numbers plus
      timestamps) based on equation [3] would be difficult or impossible
      to implement on many systems, which base their TCP implementation
      upon a very low granularity software clock, typically O(1 sec).
      To adapt the procedure to a system with a low granularity software
      clock, suppose that we calculate the ISN as:

      [4]      ISN = ( R*Ts*floor(T/Ts) + q*CC) mod 2**32

      where Ts is the time per tick of the software clock, CC is the
      connection count, and q is a constant.  That is, the ISN is
      incremented by the constant R*Ts once every clock tick and by the
      constant q for every new connection.  We need to choose q to
      obtain the required monotonicity.

      For monotonicity of the ISN's themselves, q=1 suffices.  However,
      monotonicity during the entire connection requires q = R*Ts.  This
      value of q can be deduced as follows.  Let S(T, CC, n) be the
      sequence number for byte offset n in a connection with number CC
      at time T:

          S(T, CC, n) = (R*Ts*floor(T/Ts) + q*CC + n) mod 2**32.

      For any T1 > T2, we require that: S(T2, CC+1, 0) - S(T1, CC, n) >
      0 for all n.  Since R is assumed to be an upper bound on the
      transfer rate, we can write down:

          R > n/(T2 - T1),  or  T2/Ts - T1/Ts > n/(R*Ts)

      Using the relationship:  floor(x)-floor(y) > x-y-1 and a little
      algebra leads to the conclusion that using q = R*Ts creates the
      required monotonic number sequence.  Therefore, we consider:

      [5]      ISN = R*Ts*(floor(T/Ts) + CC) mod 2**32

      (which is the algorithm used for ISN selection by BSD TCP).

      For error-free operation, the sequence numbers generated by [5]
      must not wrap the sign bit in less than MSL seconds.  Since CC
      cannot increase faster than TRmax, the safe condition is:

            R* (1 + Ts*TRmax) * MSL < 2**31.

      We are interested in the case: Ts*TRmax >> 1, so this relationship



Braden                                                         [Page 19]

RFC 1379              Transaction TCP -- Concepts          November 1992


      reduces to:

      [6]     R * Ts * TRmax * MSL < 2**31.

      This shows a direct trade-off among the maximum effective
      bandwidth R, the maximum transaction rate TRmax, and the maximum
      segment lifetime MSL.  For reasonable limiting values of R, Ts,
      and MSL, formula [6] leads to a very low value of TRmax.  For
      example, with MSL= 2000 secs, R=10**9 Bps, and Ts = 0.5 sec, TRmax
      < 2*10**-3 Tps.

      To ease the situation, we could supplement sequence numbers with
      timestamps.  This would allow an effective MSL of 2 seconds in
      [6], since longer times would be protected by differing
      timestamps.  Then TRmax < 2**30/(R*Ts).  The actual enforced MSL
      would be increased to 24 days.  Unfortunately, TRmax would still
      be too small, since we want to support transfer rates up to R ~
      10**9 Bps.  Ts = 0.5 sec would imply TRmax ~ 2 Tps.  On many
      systems, it appears infeasible to decrease Ts enough to obtain an
      acceptable TRmax using this approach.

   5.3 64-bit TCP Sequence Numbers

      Another possibility would be to simply increase the TCP sequence
      space to 64 bits as suggested in [RFC-1263].  We would also
      increase the R value for clock-driven ISN selection, beyond the
      fastest transfer rate of which the host is capable.  A reasonable
      upper limit might be R = 10**9 Bps.  As noted above, in a
      practical implementation we would use:

            ISN = R*Ts*( floor(T/Ts) + CC) mod 2**64

      leading to:

            R*(1 +  Ts * TRmax) * MSL < 2**63

      For example, suppose that R = 10**9 Bps, Ts = 0.5, and MSL = 16K
      secs (4.4 hrs); then this result implies that TRmax < 10**6 Tps.
      We see that adding 32 bits to the sequence space has provided
      feasible values for transaction processing.

   5.4 Connection Counts

      The Connection Count CC is well suited to be the monotonic
      sequence M, since it "ticks" exactly once for each new connection
      incarnation and is constant within a single incarnation.  Thus, it
      perfectly separates segments from different incarnations of the
      same connection and would allow U = 0 in the TIME-WAIT state delay



Braden                                                         [Page 20]

RFC 1379              Transaction TCP -- Concepts          November 1992


      formula [2].  (Strictly, U cannot be reduced below 1/R = 4 usec,
      as noted in Section 4.  However, this is of little practical
      consequence until the ultimate limits on TRmax are approached).

      Assume that CC is a 32-bit number.  To prevent wrap-around in the
      sign bit of CC in less than MSL seconds requires that:

           TRmax * MSL < 2**31

      For example, if MSL =  2000 seconds then TRmax < 10**6 Tp.  These
      are acceptable limits for transaction processing.  However, if
      they are not, we could augment CC with TCP timestamps to obtain
      very far-out limits, as discussed below.

      It would be an implementation choice at the client whether CC is
      global for all destinations or private to each destination host
      (and maintained in the per-host cache).  In the latter case, the
      last CC value assigned for each remote host could also be
      maintained in the per-host cache.  Since there is not typically a
      large amount of parallelism in the network connection of a host,
      there should be little difference in the performance of these two
      different approaches, and the single global CC value is certainly
      simpler.

      To augment CC with TCP timestamps, we would bypass a 3-way
      handshake if both SEG.CC > cache.CC[A] and SEG.TSval >=
      cache.TS[A].  The timestamp check would detect a SYN older than 2
      seconds, so that the effective wrap-around requirement would be:

           TRmax * 2 < 2**31

      i.e., TRmax < 10**9 Tps.  The required MSL would be raised to 24
      days.  Using timestamps in this way, we could reduce the size of
      CC.  For example, suppose CC were 16 bits.  Then the wrap-around
      condition TRmax * 2 < 2**15 implies that TRmax is 16K.

      Finally, note that using CC to delete old duplicates from earlier
      incarnations would not obviate the need for the time-stamp-based
      PAWS mechanism to prevent errors within a single incarnation due
      to wrapping the 32-bit TCP sequence space at very high transfer
      rates.

   5.5  Conclusions

      The alternatives for monotonic sequence are summarized in Table I.
      We see that there are two feasible choices for the monotonic
      space: the connection count and 64-bit sequence numbers.  Of these
      two, we believe that the simpler is the connection count.



Braden                                                         [Page 21]

RFC 1379              Transaction TCP -- Concepts          November 1992