[LARTC] [OT]: rtt measurement using tcp timestamps from a MITM position

[Patrick McHardy <kaber@trash.net>]

Hi everyone,

i know this is not the right place to discuss this, but i assume some 
people here might have some good ideas which could help me.
Also, i don't really know where else to turn ..

I'm writing a tcp rate control implementation for linux at the moment. 
For people not familiar with rate control, is basically works by 
manipulating the tcp window size to force the sender not to exceed the 
bandwidth you would like a particular connection to have. The nice thing 
about it is it works without throwing packets away, you just "tell" the 
sender how fast you would like it to go.

For the window size calculation the roundtrip time needs to be known.
One approach would be to remember the time a segment passed and to 
calculate the difference when it is acknowledged. In order not to have 
to remeber many sequence numbers/times usually only one rtt per window 
size is calculated. This works fine for low packet rates (small 
windows), for high rates the estimated rtt may be seriously wrong.

RFC1323 comes up with a solution for this, the TCP timestamp option:
The sender puts a 32bit timestamp in the tcp header, the receiver echos 
this field in its acknowledge. The sender just has to calculate the 
difference to get the rtt. This can be done with every packet sent 
without storing additional data.

The problem arises if you want to calculate rtt using timestamps from a 
man-in-the-middle position. The timestamps themselves are meaningless, 
you can't know how the sender chose them. One could remeber all 
timestamps and when they passed and calculate the difference when it is 
echoed back by the receiver, again this would mean storing probably many 
timestamps/receive times.
Another way would be to replace them by your own timestamps, but this 
would prevent the real sender to perform accurate rtt estimation.

A solution could work like this:
RFC1323 specifies the senders timestamp clock should increase by one 
every 1ms - 1s. This means the low 16bit will wrap
every ~11 minutes - ~18hours. We could just remeber the high 16bit and 
replace them with a 16bit timestamp of our own.
On reception of a echoed timestamp, we calculate the difference and put 
the original 16bit back in and pass it on.

The problem with this is that timestamps are not only used by the sender 
to calculate the rtt but also by the receiver for
PAWS (protect against wrapped sequence numbers). From RFC1323: "PAWS 
uses the same TCP Timestamps option as the RTTM mechanism described 
earlier, and assumes that every received TCP segment (including data and 
ACK segments) contains a timestamp SEG.TSval whose values are monotone 
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 timestamp recently received on this connection."

This means we have to make sure the resulting timestamp (16bit our 
timestamp, original low 16bit) still has the property of beeing monotone 
non-decreasing in time, otherwise PAWS will reject retransmitted segments.

The solution i came up with breaks PAWS itself, the protection against 
wrapped sequence numbers will be gone. This is not really a problem 
(remeber i need it for rate control) since rate control is usually not 
done on gigabit backbone routers but on corporate border routers.

It works like this:

Timestamp Option:

       31    16 15      0          31     16 15       0
tsval: [  UH   |   LH   ]   tsecr: [   UH   |    LH   ]

UH means upper half, LH lower half, tsval is the senders timestamp, 
tsecr the echoed value.

For each direction, three variables need to be kept:
ts.UH           Upper half of timestamps currently transmitted by sender
ts.UH.last      ts.UH before LH wraparound
ts.wrap         time wraparound occured

On reception of a timestamp the following is done (in pseudo C code):

/* tsval handling */

if (! ts.UH)
    ts.UH = tsval.UH;       /* remeber upper half */

if (tsval.UH != ts.UH) {    /* low 16 bit wraped */
    ts.wrap = now;
    ts.UH.last = ts.UH;
    ts.UH = tsval.UH;
}

tsval.UH = now;             /* put in out timestamp */

if (now = ts.wrap)
    tsval.UH++;             /* increment UH to reflect LH wraparound */

/* tsecr handling */

rtt = tsecr.UH - now;

if (tsecr.UH < ts.wrap)
    UH = ts.UH.last;        /* if timestamp was generated before
                                LH wrap around, put back last LH */
else
    UH = ts.UH;             /* current LH otherwise */


This seems to keep the timestamp values seen by the receiver non-decreasing.

The remaining problem are "Outdated Timestamps".

 From RFC1323:
"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 usually takes care of this (wraparound after min. 24.8 days), but 
this will not be true anymore. if we choose our timestamp clock to 
increase once every 1 ms the sign bit will wrap after 5.5 minutes. I'm 
not sure what to do about this (this is why i'm writing), does anyone 
here have good ideas? I would also be happy about a completly different 
approach, somehing totaly passive would be nice .. :)

Thanks (for the time you spent reading until down here :)
Patrick


_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/