Subject: Re: [Tsvwg] Updating timestamps (ts_recent) in Linux

From: David Borman <[email-masked]>
Date: Wed, 13 Aug 2003 09:52:16 -0500 (CDT)

> Date: Wed, 13 Aug 2003 10:26:33 +0200
> From: Reiner Ludwig <[email-masked]>
> Subject: Re: [Tsvwg] Updating timestamps (ts_recent) in Linux
>
> At 17:53 12.08.2003, David Borman wrote:
> >As a final thought, updating TSrecent more often does not mean that you
> >can get RTT measurements more often.  It continues to be the case that the
> >only time you can get a reliable RTT measurement from timestamps is when
> >when new data is acknowledged.  That is because dup ACK packets can be
> >spontainiously generated by the remote side to do a window update.  In
> >that case, taking an RTT measurement can be vastly over inflated.  And
> >since there is no way to reliably identify whether a received dup ACK
> >is due to out-of-order data arriving or due to the remote side deciding
> >to update the window, the best course of action is to only take RTT
> >measurements when new data is acknowledged.
>
> This brings up another issue that is currently not defined in any RFC: what 
> is a DUPACK?
>
> The BSD code (tcp_input.c) is quite clear about it: an ACK is a DUPACK if
>    1. the TCP sender has outstanding data, AND
>    2. the ACK number is the largest seen so far, i.e., it acks snd_una, AND
>    3. the ACK is a pure ACK, i.e., SEG.LEN == 0, AND
>    4. the advertized window info didn't change,
>       i.e., this is *not a window update*.
>
> So, we with this definition of a DUPACK it should be save for the TCP 
> receiver to echo the most recently received ts_val in DUPACKs, and for the 

Yes, the changed rule (2) in section 3.4 does a much better job of updating
TSrecent.  The only time it doesn't update TSrecent when a newer timestamp
is received, is when a packet arrives out-of-order.

If you always update TSrecent when you get a newer timestamp, then you'd
get this scenario with re-ordering packets (modified from 1323):
                                                      TS.Recent
                    <A, TSval=1> ------------------->
                                                          1
          #1)                <---- <ACK(A), TSecr=1>
                                                          1
                    <C, TSval=3> ------------------->
                                                          3
          #2)                <---- <ACK(A), TSecr=3>
                                                          3
                    <B, TSval=2> ------------------->
                                                          3
          #3)                <---- <ACK(C), TSecr=3>
                                                          3
                    <E, TSval=5> ------------------->
                                                          5
          #4)                <---- <ACK(C), TSecr=5>
                                                          5
                    <D, TSval=4> ------------------->
                                                          5
          #5)                <---- <ACK(E), TSecr=5>

As you can see, the ACK#3 and ACK#5 both are echoing a timestamp
that is newer than the timestamp that was received in the packet
that filled the hole.  This leads to an underestimation for the RTT
for both packets, which are the ones that would be used for RTT
measurement.

In addition, if #3 got lost, then #4 would be seen as the new
ACK and it's shorter RTT value would be used.  With the 1323 rules,
#4 would be echoing TSecr=2, not TSecr=5, leading to an overestimation
of the RTT rather than an underestimation.  The argument in 1323 is
that it's always better to overestimate than underestimate the RTT.

> TCP sender to use such DUPACKs to get a reliable RTT measurement.
> 
> Did I miss something?
>
> ///Reiner

In the above example, if you allow the RTT values from the
DUPACKs to be used (#2 & #4),  you'll be using even shorter RTT
values, skewing the RTT even more.  And if the other side is not
using this new echo scheme, then using the DUPACKs for timing
information could lead wildly overestimating the RTT (too much of
an overestimation is also a bad thing...)

			-David Borman

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

---

From: Reiner Ludwig <[email-masked]>
Date: Wed, 13 Aug 2003 19:50:21 +0200

>is received, is when a packet arrives out-of-order.

And, I still think we can do better ...

>for both packets, which are the ones that would be used for RTT

I played with your example for a while, and looked at the following 
scenario: Assume we have a constant (real) RTT of 100 ms, and the TCP 
sender's cwnd allows to send the five packets A - E.
The TCP sender sends A,
10 ms after it sent A, it sends B,
10 ms after it sent B, it sends C,
20 ms after it sent C, it sends D,
10 ms after it sent D, it sends E.

To cause the rordering in your example:
B is held up in the network for 20 ms so that C "overtakes", and
D is held up in the network for 20 ms so that E "overtakes".

As usual the TCP sender (blindly) does 'tcp_now - TSecr' to derive an RTT 
from every ACK (Karn can be safely disabled with timestamps).

The real RTT samples as seen by "somebody traveling in the packet", and as 
they arrive at the TCP sender are:
RTT(A)=100
RTT(C)=100
RTT(B)=120
RTT(E)=100
RTT(D)=120

The RTT samples taken by a TCP sender using the rule I suggested are:
RTT(A)=100
RTT(C)=100
RTT(B)=110(-10)
RTT(E)=100
RTT(D)=110(-10)

The RTT samples taken by a TCP sender using RFC1323 are:
RTT(A)=100
RTT(C)=120(+20)
RTT(B)=120
RTT(E)=140(+40)
RTT(D)=120

So, you are right. The rule I suggested leads to a slight underestimation, 
while RFC1323 - as expected - leads to overestimation.

But, what if we simply forget about TS.Recent and simply let the TCP 
receiver echo TSval received in the segment for which it sends an ACK? 
Then, in your example the TCP sender would see TSecr=1, 3, 2, 5, 4, and in 
the scenario I gave above the RTT samples taken by the TCP sender would be:
RTT(A)=100
RTT(C)=100
RTT(B)=120
RTT(E)=100
RTT(D)=120
=> the true RTTs. No over-/under-estimation.

We would still need to take care of delayed ACKs, though. For that we could 
use TS.Recent. We would store in TS.Recent the TSval from an in-sequence 
data segement for which an ACK is not generated immediately due to delayed 
ACK, and would echo TS.Recent in the delayed ACK.

>values, skewing the RTT even more.

I don't think so. Those RTT values would even be the correct values.

>And if the other side is not

A TCP sender could easily detect whether a TCP receiver is using RFC1323 or 
a newer echo scheme: with RFC1323 the TSecr values in subsequent DUPACKs 
don't change.

Apart from these corner cases, I wonder if we are losing the bigger 
picture. The very common case is that the TCP sender receives a series of 
DUPACKs during loss recovery. The recovery phase at least lasts for one RTT 
during which today with RFC1323 the RTT can't be sampled.

Reordering, on the other hand, has so far only been reported to be a rare 
event in the Internet. Studies that did find large reordering, later found 
that this was due to some hardware glitch that then got fixed.

///Reiner