Subject: Re: [tcpm] Timestamp semantic change

From: Matt Mathis <[email-masked]>
Date: Mon, 19 Dec 2011 15:06:59 -0800

NO - this is not correct!   Sorry I did not catch this sooner.

On Fri, Nov 25, 2011 at 12:59 AM, Scheffenegger, Richard <[email-masked]>wrote:

>
> Hi Michael,
>
> You are absolutely correct. In the context of RFC1323,the sole purpose of
> Timestamps (to the sender) is to deliver a conservative lower bound of the
> RTT. This is again used for the single purpose of calculating the RTO on
> the sender side.
>

The sole purpose of 1323 timestamps was the Protection
Against Wrapped Sequence (PAWS) algorithm, which essentially treats the
timestamps as an extension to the MSB of the sequence number.  Other uses
are secondary.  (Furthermore it was known at the time that the PAWS
requirements reduce the usefulness for RTT measurement, and that this was
implicit from the requirements).

My mental model of PAWS is to compute longseq
= 4294967296*timestamp+seg.seq and enforce the standard in window checks on
both seq and longseq.  This requires the hard constraint that longseq be
absolutely monotonic, which in turn causes constraints on when you are
permitted to (or must) update the echoed timestamp.

I admit that I have never worked through the details of PAWS myself, so
your algorithm might still be ok.  However failing to meet the constraints
imposed by PAWS will cause odd TCP failures...

I believe that one of the important fixes in 1323bis was about some corner
case in exactly this area.

Dave, do you care to comment?

Also, as far as I know, nobody has worked though possible interactions
(or opportunities) between PAWS/timestamps and SACK (or FACK).  Or perhaps
you are the first!  :-)

Thanks,
--MM--

---

From: <[email-masked]>
Date: Tue, 20 Dec 2011 04:09:39 +0000

Sigh, You're both wrong. It's both.

> The sole purpose of 1323 timestamps was the Protection Against Wrapped Sequence (PAWS) algorithm,
> 

Read the expired RFC1323bis internet-draft:
http://www.kohala.com/start/tcplw-extensions.txt
     "However, as RFC-1323 implied but did not clearly state, the RTTM
      mechanism replaces Karn's algorithm."
[..]
      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."

On 19 Dec 2011, at 23:06, Matt Mathis wrote:

> On Fri, Nov 25, 2011 at 12:59 AM, Scheffenegger, Richard <[email-masked]> wrote:
> 
> Hi Michael,
> 
> * You are absolutely correct. In the context of RFC1323,the sole purpose of Timestamps (to the sender)
> * is to deliver a conservative lower bound of the RTT. This is again used for the single purpose of
> * calculating the RTO on the sender side.
> 
> The sole purpose of 1323 timestamps was the Protection Against Wrapped Sequence (PAWS) algorithm, which essentially treats the timestamps as an extension to the MSB of the sequence number.  Other uses are secondary.  (Furthermore it was known at the time that the PAWS requirements reduce the usefulness for RTT measurement, and that this was implicit from the requirements). 
> 
> My mental model of PAWS is to compute longseq = 4294967296*timestamp+seg.seq and enforce the standard in window checks on both seq and longseq.  This requires the hard constraint that longseq be absolutely monotonic, which in turn causes constraints on when you are permitted to (or must) update the echoed timestamp.
> 
> I admit that I have never worked through the details of PAWS myself, so your algorithm might still be ok.  However failing to meet the constraints imposed by PAWS will cause odd TCP failures...
> 
> I believe that one of the important fixes in 1323bis was about some corner case in exactly this area.
> 
> Also, as far as I know, nobody has worked though possible interactions (or opportunities) between PAWS/timestamps and SACK (or FACK).  Or perhaps you are the first!  :-)
> 
> Thanks,
> --MM--
>

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Tue, 20 Dec 2011 12:59:37 +0000

Thanks Matt and Lloyd for continuing the discussion!

I believe my proposal still addresses both PAWS and RTTM (or more specifically, conservative RTO calculation).  The monotonic increase of the (unmasked part) of the timestamps will be maintained. The main change is, that if a sender may choose to flag some bits masked, the effective "extended" sequence number will have fewer bits (32 - mask) + 32 bits instead of 64 bits... 

The sender must never send a timestamp value that is smaller (excluding the masked portion) than any previously sent timestamp. Therefore, the PAWS algorithm would continue to work as it works now...

The only exception of course being all timestamp bits masked, but that really makes the timestamp field a (unprotected) 2-byte side channel to TCP without yet-another-option :) (Not negotiating timestamps would have the same effect on PAWS / RTO calculation. And there are still a lot of sessions running without timestamps.)

For the conservative RTO calculation  - I really would like to separate RTO calculation from RTT measurement in this context, as these two are really not the same - the proposal "gates" the RTO calculation updates with the (non-)existence of a SACK block, provided SACK was negotiated. If SACK is not negotiated, the receiver would not change the semantic of which timestamps to reflect over RFC1323.

This allows to still maintain a conservative RTO estimate, but also to extract additional data from the network which is currently masked by the specific way how timestamps has to be reflected.

However, reflected timestamps (the TSecr field) is not relevant for PAWS, only TSval is, correct?

The suggestion made by Joe, about which timestamp to put into unsolicited segments (ie. bidirectional data segments ) even advanced this idea, so that the RTTM update could be gated to whenever the seq.ack is different from the previous received segment, or for any received segment...

But again, with the exception of delayed ACK (one ACK every other data segment, or even fewer), the proposal can be used as direct feed into the current algorithms.

I believe the mentioned difference with delayed ACKs would only become relevant, at small window sizes (<4 frames in flight), or when TCP processing on the receiver side has very high variability (in the same order of magnitude, or higher, than the delay in the network itself. I'm not entirely clear myself as to how to reconcile that particular aspect with RTO calculation. For RTO, the sender should - at least when the send window is very small - take the delayed ACK timeout into consideration, in order to be packet conserving. 

On the other hand, the worst case scenario appears to be that RTO does not take the delayed ACK timeout of the receiver into consideration, and re-transmits the last frame of a session sooner than strictly necessary. This would only happen if that last frame itself doesn't trigger an ACK... Now, in some environments, such a behavior may be acceptable (slightly higher duplicate frames, but lower latency when the last frame of a stream is lost).

Then again, as pointed out by Per Hurtig recently, most stacks are already more conservative than required, by restarting the RTO timer with every received ACK rather than with the sending of the particular data frame...

Some guidance from the group as to how to approach these different aspects and reconcile them in the proposal would be very welcome!

Season's greetings,

Richard Scheffenegger

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]]
> Sent: Dienstag, 20. Dezember 2011 05:10
> To: [email-masked]
> Cc: [email-masked]; Scheffenegger, Richard;
> [email-masked]; [email-masked]
> Subject: Re: [tcpm] Timestamp semantic change
> 
> > The sole purpose of 1323 timestamps was the Protection Against Wrapped
> Sequence (PAWS) algorithm, which essentially treats the timestamps as an
> extension to the MSB of the sequence number.  Other uses are secondary.
> (Furthermore it was known at the time that the PAWS requirements reduce
> the usefulness for RTT measurement, and that this was implicit from the
> requirements).
> >
> > My mental model of PAWS is to compute longseq =
> 4294967296*timestamp+seg.seq and enforce the standard in window checks
> on both seq and longseq.  This requires the hard constraint that longseq be
> > Also, as far as I know, nobody has worked though possible interactions (or
> opportunities) between PAWS/timestamps and SACK (or FACK).  Or perhaps
> you are the first!  :-)
> >
> > Thanks,
> > --MM--
> >
> 
>