Subject: [tcpm] RFC 1323: Timestamps option

From: David Borman <[email-masked]>
Date: Fri, 26 Jan 2007 12:33:29 -0600

One of the topics that has been discussed in the past for the  
revision of RFC 1323 is to relax the requirement on when to send the  
Timestamps option.  I'd like to come to some resolution on this issue.

Current:
The Timestamps option is negotiated during the initial SYN exchange.   
If both sides support it, then every packet in the connection has to  
have the Timestamps option.

Option #1
---------
The proposed change is to relax the requirement that Timestamps have  
to be negotiated in the initial SYN, and instead allow them to be  
enabled later on in the connection.  At the time 1323 was originally  
written, there was a big concern for legacy TCP stacks that didn't  
handle unknown options in the middle of the connection, but were able  
to properly ignore unknown options during the SYN exchange.  But that  
was a long time ago, and unknown options in the middle of a TCP  
connection *shouldn't* be as big of an issue anymore.

The rules for enabling Timestamps mid-stream would be:
1) If you receive a Timestamps option mid-stream, you can enable  
Timestamps.  From then on, every packet sent will need to contain a  
Timestamps option.
2) If you want to enable Timestamps mid-stream, you can only do so on  
a data packet.  You record the sequence number of that data packet,  
and include the Timestamps option on every packet from then on, until  
you receive an ACK for that sequence number.  If at any time you  
receive a packet with the Timestamps option, then they are enabled  
for the rest of the connection.  If you do not receive a packet with  
a Timestamps option by the time you get the ACK for that initial  
sequence number, then the other side has not enabled Timestamps and  
you must stop sending Timestamps for the duration of the connection.

The restriction on only being able to initiate Timestamps on a data  
packet is that they are the only packets that are delivered reliably,  
so determining whether or not the other side supports them is  
deterministic by getting the ACK for that data.

Option #2
---------
This is similar to Option #1, but not quite the same.  In this case,  
the Timestamps would be negotiated in the initial SYN as before, but  
then no additional packets would have Timestamps options.  At any  
point during the connection, either side can enable the use of  
Timestamps just by starting to send them.  Since we already know that  
both sides support them, once you start sending them you never stop.   
And if you every receive one, you are then required to also send them  
for the duration of the connection.

The question then is, how do you negotiate Timestamps without turning  
them on?  My suggestion would be to send a Timestamps option with the  
special format TSval=0,TSecr=0.  If you receive this in a SYN, then  
the request is to negotiate knowledge of the Timestamps option.  The  
returning SYN,ACK would also need to contain TSval=0,TSecr=0 to  
complete the negotiation.  If you are connecting to a site that  
doesn't support this feature but does support Timestamps, it would  
respond with TSval=xxx,TSecr=0.  At that point, Timestamps are now  
enabled.  The downside of this is that now the originator has started  
their Timestamps values at 0, and must continue from there with their  
timestamps; they can't just suddenly jump to some arbitrary value  
because that could break PAWs.

Option #3
---------
Do nothing, and leave Timestamps alone as they are currently  
defined.  You negotiate them in the SYN, and then include them in  
every packet from then on.

One of the issues with Timestamps is that the TSecr value is defined  
to be valid anytime the ACK bit is set.  This works well with the  
initial SYN negotiation, but when you enable Timestamps midstream,  
the initiator has to send a Timestamps option with an invalid TSecr  
value, but the ACK bit will be set.  That's the case for both of the  
previous options.

So why should we change things?  My recollection was that the primary  
motivation was to conserve option space, to avoid having to put in  
the extra 12 bytes of TCP options on every packet until we get to the  
point where the sequence space might wrap, and then turn them on so  
that we can get PAWS to protect the rest of the connection.  But I'm  
not sure I buy that argument.  One of the things that you lose by  
deferring enabling Timestamps is that you don't get the RTT  
measurements that Timestamps provide.  Without Timestamps, using the  
typical BSD algorithm of timing one segment and waiting for an ACK,  
and adding in the Karn algorithm that you have to invalidate any  
measurements if you had to retransmit in that window, means that at  
best, you'll get one measurement per RTT.  At worst, you can get in a  
state where you never get a valid RTT measurement.  When you use the  
Timestamps option, the worst case is that you'll only get one  
measurement per RTT, and the best case is that you'll get multiple  
valid samples,

My viewpoint
------------
Right now, I'm inclined to leave the Timestamps option alone; you  
negotiate it during the SYN exchange, and then include it on every  
packet.  I'm willing to be convinced otherwise, but now I've placed a  
stake in the ground, and the mailing list will have to decide if  
there is sufficient reason to change the behavior.

			-David Borman

_______________________________________________
tcpm mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/tcpm

---

From: Sally Floyd <[email-masked]>
Date: Fri, 26 Jan 2007 11:09:59 -0800

David -

I don't have any feedback about *when* to negotiate timestamps, but I 
do have some feedback
about how the RTO should be estimated when timestamps are used.  Just 
as something
to include in a revision of RFC 1323...

Regards,
- Sally
http://www.icir.org/floyd/

Here is some old email of mine on this:

> To: [email-masked]
> cc: "Ethan Blanton" <[email-masked]>,
>     "Aaron Falk" <[email-masked]>, "Ted Faber" <[email-masked]>,
>     [email-masked], "Scott Bradner" <[email-masked]>
> Bcc:
> From: Sally Floyd <[email-masked]>
> Subject: Re: Mark Allman: would this fly?
> Date: Tue, 09 Aug 2005 13:45:18 -0700
> Sender: [email-masked]
>
> Mark -
>
> >> It is worth noting that if timestamps are being used, with the
> >> currently-specified time constant for estimating the average RTT and
> >> variance, then the first thing that needs to be done is to change 
> the
> >> time constant so that the average RTT and the variance aren't being
> >> estimated over a small fraction of a window of data (as is possible
> >> when timestamps are used with current parameters).  (Unless this has
> >> already been fixed in recent standards, and I just missed it...)
> >
> >I don't think this has been fixed.  And, I don't see this potential 
> i-d
> >as the place to fix it.  I wanted this to be an alternative response 
> to
> >spurious timeouts, not some general RTO change.  Does that make sense?
>
> It makes sense.  Except that if in fact the average and variance are
> being estimated over a small fraction of a window size, because
> the TCP connection is using timestamps and has a moderate-to-large
> congestion window, then the estimated variance might be very small
> (because it is measured over RTTs calculated essentially from the
> most recent N packets, for N < cwnd, and the burstiness for rtts for
> the most recent fraction of a cwnd might be quite small).
>
> So in that situation, increasing the multiple of the variance might
> have almost no effect on the RTO, because the variance might be
> unrealistically small when calculated only over this small time
> scale.  And changing the weight for estimating the rtt average and
> variance to make sure that the average RTT and variance are estimated
> from RTTs calculated over a period of several rtts, might make your
> technique much more powerful, by making the calculated variance
> much more interesting and useful.  Worth noting, at any rate.  IMHO.
>
> - Sally

---

From: Mark Allman <[email-masked]>
Date: Fri, 26 Jan 2007 14:42:17 -0500

[obviously, without co-chair hat]

Hi Dave-

I am not going to vote yet.  I want to try to understand what you write
a little more ...

> One of the things that you lose by deferring enabling Timestamps is
> that you don't get the RTT measurements that Timestamps provide.
> Without Timestamps, using the typical BSD algorithm of timing one
> segment and waiting for an ACK, and adding in the Karn algorithm that
> you have to invalidate any measurements if you had to retransmit in
> that window, means that at best, you'll get one measurement per RTT.
> At worst, you can get in a state where you never get a valid RTT
> measurement.  When you use the Timestamps option, the worst case is
> that you'll only get one measurement per RTT, and the best case is
> that you'll get multiple valid samples,

So, 

  + I agree that getting into a state whereby you never get an RTT
    measurement is Not Good.

    (Although, one could think of ways to avoid this and we might also
    decide this is pathological.)

  + Why is the "best case" that you'll get multiple samples per RTT?  It
    seems to me that the underlying assumption is that "more is better",
    but I am not sure it is.  We have done some analysis that suggests
    more samples are not better.  I don't want to say our analysis is
    the last word here, but I'd be interested in hearing arguments for
    taking more samples [using the current RTO estimator] per RTT being
    a clear win.

    I think this is an important point in choosing a path.  I.e., if
    multiple RTT measurements matter then that might suggest a different
    approach than if multiple RTTs buy you little/nothing.

    Ref:

        Mark Allman, Vern Paxson.  On Estimating End-to-End Network Path
        Properties.  Proceedings of the ACM SIGCOMM Technical Symposium,
        Cambridge, MA, September 1999.
        http://www.icir.org/mallman/papers/estimation.ps

allman

-- 
Mark Allman -- ICIR/ICSI -- http://www.icir.org/mallman/

---

From: David Borman <[email-masked]>
Date: Fri, 26 Jan 2007 13:43:47 -0600

Hi Sally,

Yes, thanks.  That is one of the other open issue with 1323.  Over  
the next week or so I'm planning on sending out individual emails for  
each of the other issues, so that they can be discussed individually,  
rather than trying to discuss them all in one big email thread.  But  
since you brought it up, let's begin this thread now. :-)

For the RFC, at a minimum we need to add a description of the  
problem, and say that implementors should take into account the more  
frequent timestamp values.  I don't think we should trying to tell  
them exactly how to address the issue, but it'd be nice to have a  
reasonably example that could be easily implemented and achieve the  
desired effect.

So, my idea is to use a two-tier approach.  As without Timestamps,  
you record the sequence number to begin measuring the RTT.  Until you  
get the ACK for that sequence number, you take all the measurements  
from the Timestamps options and average them together.  Once the ACK  
for the sequence number returns, you take the averaged value and use  
that in the traditional RTO calculations, and reset the sequence  
number and averaged value.  There are probably better algorithms, but  
this one is simple and should be fairly easy to implement, and would  
produce better results than the situation today where all the  
Timestamps are fed into the RTO calculation without adjusting for the  
increased frequency of the measurements.

		-David Borman

On Jan 26, 2007, at 1:09 PM, Sally Floyd wrote:

> David -
>
> I don't have any feedback about *when* to negotiate timestamps, but  
> I do have some feedback
> about how the RTO should be estimated when timestamps are used.   
> Just as something
>> >> variance, then the first thing that needs to be done is to  
>> change the
>> >I don't think this has been fixed.  And, I don't see this  
>> potential i-d
>> >as the place to fix it.  I wanted this to be an alternative  
>> response to

---

From: Matt Mathis <[email-masked]>
Date: Fri, 26 Jan 2007 14:49:17 -0500 (EST)

> have the Timestamps option.

... snip ...

> My viewpoint

The real problem is a zero configuration issue:  for the 100 million or so US
home users on DSL (or worse, compressing modems), timestamps offer little
gain and often substantial penalty.  For the 10 Million(?) US university
users, timestamps are necessary for good performance.  Who do you think the
manufacturers cater to? The simple answer is the home user, but many current
systems use some sort of heuristic (e.g. is the interface faster than 100
Mb/s?).

The current situation forces us to try to educate 9.99 million non-network
savvy users how to inspect and tweak their kernels.

I want ZERO config from at least 9.6 kbs to 9 Gbps.  Some form of late
timestamp negotiation is required before this can become the default.

(BTW Japan and Europe, with true high speed to the home might change the
equation quite a bit.  This path leads to some ugly market positions.)

Thanks,
--MM--

P.S.  The default WSCALE for MS Vista and mainline Linux is now 8 and 7
respectively for large memory systems, so the harder part of the zero config
problem has already been solved.  These correspond to 16 and 8 MByte TCP
buffers. Roll out is going to take a while, but that will give people a chance
to notice how the traffic might affect the network.  QoS anyone?

Thanks,
--MM--
-------------------------------------------
Matt Mathis      http://www.psc.edu/~mathis
Work:412.268.3319    Home/Cell:412.654.7529
-------------------------------------------
Evil is defined by mortals who think they know
"The Truth" and use force to apply it to others.

---

From: Fernando Gont <[email-masked]>
Date: Fri, 26 Jan 2007 16:56:14 -0300

Hi David,

I'm inclined for option #3, too.

Some comments inline....

>Option #2
[....]
>because that could break PAWs.

IIRC, there are some implementations that randomize the TCP sequence 
number, but use monotonically increasing timestamp generator.
Those implementations would cause, the BSD hack of allowing the 
establishment of a new connection if the ISN of the new incarnation 
of the conenction is larger than the last seq number seen on the old 
connection to fail fail.
IIRC, Linux also takes into account the Timestamp. Thus, if you 
randomize the ISN, but use a monotonically increasing timestamp 
generator, the hack would still succeed.

However, option #2 above would break this.

[....]
>that we can get PAWS to protect the rest of the connection.

I assume this means that one would turn timestamps on when starting a 
bulk transfer on the connection (?).

If so I'm not sure the space we'd be saving would be worth the 
additional complexity: For most application protocols usually 
employed for bulk transfers, the bulk transfer is preceded by only a 
few packets (to establish the TCP connection and send the application 
request). So option space would be saved in only a few segments.

Am I missing something?

Also, in order to enable timestamps midstream, I guess applications 
should perform a call to setsockopt() or the like? If so, this 
require specification of the corresponding socket option, would 
require applications to be modified, and we would also requier us to 
agree on "what the option should default to", etc.

So, unless some strong reason is raised for going with option #1 or 
option #2, I would stick with option #3.

Thanks,

-- 
Fernando Gont
e-mail: [email-masked] || [email-masked]
PGP Fingerprint: 7809 84F5 322E 45C7 F1C9 3945 96EE A9EF D076 FFF1

---

From: David Borman <[email-masked]>
Date: Fri, 26 Jan 2007 14:05:34 -0600

You've probably already seen my reply to Sally, but I'll clarify a  
few things:

>     approach than if multiple RTTs buy you little/nothing.

Perhaps "best case" was the wrong term.  Being guaranteed at least  
one good RTT measurement per RTT is a good thing.  The current RTO  
estimator is based on getting one sample per RTT, no matter how much  
data flows during that time.  As you know, when you start using all  
the samples from multiple Timestamps options, if you just feed them  
into the current RTO estimator it can seriously skew the results,  
especially if you are getting lots of samples per RTT.  In my reply  
to Sally, I suggested taking the average of all the Timestamps  
received during one RTT, and feeding that into the RTO estimator.  An  
alternative would be to take the largest sample received during the  
RTT interval, and feed that into the estimator.  That'd be even  
easier to implement.  Do you have any thoughts as to which would be  
better?

Another alternative would be to only use the sample from the  
Timestamps option in the ACK for the sequence number that is being  
timed, i.e. back to one sample per RTT.  But that is still a win over  
the old method, because with Timestamps, we know that the measurement  
will always be accurate, even if there was a retransmission during  
the RTT.

But I totally agree, just feeding in the more frequent samples from  
the Timestamps into the RTO estimator is not a good thing.

		-David Borman

---

From: David Malone <[email-masked]>
Date: Fri, 26 Jan 2007 21:09:00 +0000

> Timestamps.  From then on, every packet sent will need to contain a  

Based on some of the behaviour noted in:

	http://www.caida.org/publications/papers/2005/fingerprinting/

It seems some implementations have already effectively chosen Option #1.  

	David.

---

From: Mark Allman <[email-masked]>
Date: Fri, 26 Jan 2007 20:40:54 -0500

> You've probably already seen my reply to Sally, but I'll clarify a

Yes - I just read it (although, I am a bit behind on the thread, so
apologies if some of the stuff below has been said).  But, I think it
is orthogonal to my concern.  Likely, I am not stating things well.

Sally's observation (and, she is not the only one to make it over the
years) is that the current TCP RTO algorithm keeps history in terms of
the *number* of samples taken.  So, if you take two RTT samples per RTT
as opposed to one then you are keeping half as much history in *time
units*.  I think we all agree with this and that it should be addressed
**when a TCP connection is taking more than one RTT sample per RTT**.
Exactly how we address it is a discussion we can have (averaging samples
into one per RTT that is fed to the estimator, taking the max sample per
RTT, adjusting the EWMA gains based on the cwnd, etc.).  This problem
manifests itself *when* we take multiple samples per RTT.  What I am
asking about is *whether* we need multiple samples per RTT.

It seems to me that your notes assume somehow that more than one sample
per RTT is useful.  Why?  Or, 

> Being guaranteed at least one good RTT measurement per RTT is a good
> thing.

Why?

(I don't mean to be flip.  Surely one good RTT sample per RTT is a fine
goal.  The "why?" is in response to the "guaranteed" part of your
statement.) 

Clearly we want an evolution of the RTO to take into account changing
RTTs and the variance in the RTT.  So, we don't want to use a static
number and we do not want to take a single sample and then stop
(although, actually, this latter does not perform too bad).

Let me try to put this a different way... what is the problem with the
non-TS one sample / RTT sampling technique?  You have noted a couple of
things:

  + That we might not be able to get *any* RTT sample.

  + That Karn's algorithm means that during some RTTs we will not get a
    sample.

  + (Are there others?)

The first of these is a clear problem that using the TS option from the
beginning can solve (although, a small tweak to retransmit SYNs with
timestamps even if the original did not have a TS may well fix this).
I do wonder how much I should care about this case.  It seems like it
will be exceedingly rare to get into this situation and further even if
we do I am not sure I care about performance (if that means including a
12-byte blob on every packet sent for this express reason).

The second case above is for sure true.  But, the question is does it
matter at all?  In other words, what is the impact on the RTO of getting
a sample during these RTTs as opposed to not?  

I ask these questions to test the assumptions.  My own thinking goes
like this .... Timestamps are essentially a general disambiguation
mechanism.  There is a clear need for some form of disambiguation when
the sequence space wraps too quickly.  That mechanism does not have to
be timestamps, but they work fine.  However, such a disambiguation
scheme is not needed when the sequence space cannot wrap too quickly.

RFC 1323 also laid out a couple reasons for using a disambiguation
mechanism for RTT timing.  One of those is because the ambiguity leads
to no RTT samples in some situations (i.e., when we retransmit).  The
other item is the [what I would consider] conjecture that more RTT
samples help the RTO.  In the time since RFC 1323 was published I think
there is some evidence that says that the need for disambiguation for
RTT sampling is thin.  Maybe I am biased by my own work.  Our work is
one data point.  What I am really looking for is other work / evidence /
experience that makes the case that we need disambiguation for RTT
sampling in anything but corner cases and then what do we gain from this
disambiguation?

allman

---

From: Mark Allman <[email-masked]>
Date: Fri, 26 Jan 2007 20:47:41 -0500

> additional complexity: For most application protocols usually employed
> for bulk transfers, the bulk transfer is preceded by only a few
> packets (to establish the TCP connection and send the application
> should perform a call to setsockopt() or the like? If so, this require
> specification of the corresponding socket option, would require
> applications to be modified, and we would also requier us to agree on
> "what the option should default to", etc.

My view is that the application would not have to be involved.  The app
is not involved in whether to use timestamps or not right now.  (Setting
the socket buffer quite large could be seen as a proxy of this, I
suppose.)  In any case, I don't think you need to worry about knowing a
file is big or not.  In order to need TS for PAWS you have to send 4GB
of data (i.e., wrap).  It should be easy enough to turn TS on after 3GB
or something.  (It really isn't the amount of data being sent, it is the
data rate that PAWS is protecting against and so you could come up with
a better test than simply testing the number of bytes sent---my point is
that without actually wrapping we don't have to worry about TS for
PAWS.)

allman

---

From: Richard Wendland <[email-masked]>
Date: Sat, 27 Jan 2007 12:21:47 +0000 (GMT)

A difficulty with the suggested enabling mechanism for Option #2 is
that a major TCP stack already (mis)behaves in a similar way for current
TCP connections.

> Option #2
...
> complete the negotiation.

The Windows TCP stack currently replies SYN,ACK TSval=0,TSecr=0 to a
regular SYN TSval=xxx,TSecr=0.

So if you send SYN TSval=0,TSecr=0, and get back SYN,ACK TSval=0,TSecr=0
you may be talking to a TCP stack that understands the new enabling
semantics, or a Windows TCP stack that does not.

You could argue this does not really matter, as the Windows TCP stack
will go on using Timestamps (I presume), immediately enabling it on the
fly under the new semantics, so in the end all is fairly well (except
Windows TCP may be sent a few segments with no Timestamps that it does
not expect, until on the fly enabling is completed).  However I don't
think this confusing situation is desirable.

I think Windows TCP behaves in this way because it does not create a
full TCP state block until after SYN,ACK processing, so has nowhere
to record the initial TSvals.  If we are updating RFC1323, I wonder if
this Windows behaviour should be explicitly allowed, since in practice
we have to allow for it now, and it has some merit.

Trying to find legitimacy for the Windows TCP behaviour, it could
be said that 3.2 of RFC1323 wasn't entirely clear in this regard.
It says "When TSecr is not valid, its value must be zero." - I can
conceive of this being understood (out of context) as meaning: if you
do not have a valid TSecr available for some reason, then send a zero;
an interpretation that would permit the Windows TCP behaviour, and make
the suggested enabling mechanism ambiguous.

	Richard
-- 
Richard Wendland				[email-masked]

---

From: Kacheong Poon <[email-masked]>
Date: Mon, 29 Jan 2007 13:08:24 +0800

David Borman wrote:

> Option #3
> ---------
> Do nothing, and leave Timestamps alone as they are currently defined. 
> You negotiate them in the SYN, and then include them in every packet
> from then on.

As an implementor, I'd vote for Option #3.  If the current behavior
is not broken, don't fix it.  Modifying it after so many years of
deployment may cause many troubles.  IMHO, the benefit of modifying
the handling, which is saving 12 bytes, is minor when compared to
the effort of diagnosing why a connection is not working.  If we
want to fix the overhead and other issues, such as auto-tuning, I'd
rather to have a new option or other methods than modifying the
current handling.

I'd like to have several clarifications on timestamps handling.

1. I think it is not stated explicitly that once timestamps option
   is enabled, it should always be used for a connection.  I have
   encountered TCP stack which stops sending timestamps option in
   the middle of a connection.  Could this be made explicitly in
   the update?  I also suggest putting a note on how to handle such
   behavior.  For example, once one side stops sending the option,
   the peer will treat it as if the option is never negotiated and
   also stops using it.

2. As described in CERT VU#637934, there are some inconsistencies
   in RFC 1323 and the not "published" RFC 1323bis.  This creates
   some "variants" of algorithms.  Since this update will obsolete
   both documents, please check the CERT report on the issues and
   clarify it on the update.

3. It is stated that RST should not have a timestamps option.  I
   think this is really not needed.  And it only causes extra check
   in the code not to do that.  For example, an app does an abortive
   close, the code needs to remove the timetstamps option from the
   connection to send the RST.  I don't think it causes any harm if
   the RST has the option.

-- 

						K. Poon.
						[email-masked]

---

From: Gavin McCullagh <[email-masked]>
Date: Mon, 29 Jan 2007 15:55:06 +0000

Hi,

> the Timestamps into the RTO estimator is not a good thing.                                                                    

Indeed. Naturally, it is possible to adjust the RTO estimation to be able
to deal with receiving estimates more often, or even irregularly. Quite a
few OSes (eg Darwin, I think?) use a RTO timer (and time stamps) that ticks
every half a second, and so effectively rounds up to the nearest 500ms.  I
guess this shows that it doesn't matter too much what you do, as long as
you give a reasonable overestimate.

It is conceivable that people might want to use timestamps for things other
than RTO estimation. Some of the high-speed TCP variants want more RTT
samples (we're playing with one that expects an RTT sample per ACK at the
moment).  I don't think any of the suggested new behaviours would cause
problems with these uses, but it may be worth keeping in mind while
updating RFC 1323.

As an example of a more exotic use of the time stamp option, the most
recent version of FreeBSD's syncookies stashes information in the
timestamp:

        http://lists.freebsd.org/pipermail/freebsd-net/2006-September/011651.html

Gavin