Subject: Re: large RTT variation caused by bandwidth oscillation

From: Kacheong Poon <[email-masked]>
Date: Tue, 8 Jan 2002 19:16:04 -0800 (PST)

Sorry for the late reply in this thread.  I was on vacation the
last month.  I just want to make several comments since Solaris 
was mentioned several times in this thread.

It was mentioned that Solaris always had a problem with spurious
retransmission.  In pre-Solaris 2.6, Karn's algorithm (maybe this
is the reason why Phil Karn stopped using Solaris...) was not
implemented correctly.  One can see that what this can cause when a 
timeout due to congestion happens.  And there were various other 
little things which caused problems with slow link.  I guess this all 
leads to the now "infamous" quote about Solaris having serious 
spurious retransmission problem...  I hope this can be straightened 
out.

Another comment is about RFC 2988 compliant.  We have several
reservations about RFC 2988.  And it may be better not to conform
to it.

For example, in section 2, rule 2.2, one can easily see that if G 
is not a big value (say at least 500ms or 1s), this can cause problem
in a slow link.  For example, consider the case that the first 
segment which is used for RTT sampling has only a few bytes and the 
next segment sent is actually a full MSS size segments.  If G is
in the range of 100ms and the slowest link speed of the route is
9600bps, the second segment will trigger a timeout.  This problem
is masked by rule 2.4, which restricts the minimum RTO to be 1s.
But as mentioned in the RFC, this is quite conservative.  And I
beleive many implementations choose not to comply with it.  As
a matter of fact, I believe having a fixed RTO of 1s for land
links (no wireless) should be able to aovid most spurious 
retransmission in today's Internet (oops, I cannot substantiate 
this claim with facts )-:)  We don't need to do RTT sampling at 
all (-:

There is one comment specifically saying that Solaris does not
comply with Section 5, rule 5.3.  It is correct, Solaris does
not implement the part of restarting timer in rule 5.3.  The timer
is restarted when a fast retransmit happens or during the fast 
recovery phase when missing segments are retransmitted.  

Rule 5.3 simply says that the RTO calculation is not good enough so 
that implementations should add a little fudge factor to it.  For
example, if 2 segments are sent and the receiver does not delay
ack'ing.  The second segment is dropped.  After the ACK for the
first segment arrives, rule 5.3 suggests that the timer should
be restarted.  This means that the actual timeout value for the
second segment is RTO+RTT.  The arrival of first data segment 
correlates weakly, if there is any correlation, to the fate of the
next segment.  This point has been mentioned by a lot of other people.
And the fact that it helps spurious retransmission is that it makes 
the timeout longer and longer.  If we make RTO a fixed 5s, I conjecture
that there will be no spurious retransmission, even for wireless
links (-:  (Please don't take those "smiley points" seriously (-:)

And I believe Farid Khafizov's last email (there are too many emails 
in my various mailboxes, I may have missed some...) mentioned that
even with this timeout fudge factor, RTT oscillation is still a
problem.  His earlier mails suggesting that RFC 2988 compliant
TCP implementations could handle his earlier experiements may just
be "pure luck..."  The current TCP RTO algorithm is not designed to
handle this kind of wireless environment.  And we all know that the 
current assumption of the RTO calculation is that the round trip route
does not change much.  So it seems to me that we may need a better way
to deal with this in the RTO calculation.  A quick hack for Solaris 
admin is to set tcp_rexmit_interval_extra to a value which is appropriate
for the kind of RTT oscillation of the particular network.  This
knob is there to handle cases when the RTO algorithm fails, and I
believe this kind of oscillation in the wireless medium may be one
of them.  In any case, we are open to suggestions to what we should
do to accomodate different network environments.

I have another minor comment about what actually happens after a timeout.
I believe all modern TCP implementations will not have the false fast
retransmit after timeout problem mentioned in this thread.

							K. Poon.
							[email-masked]

---

From: "Andrei Gurtov" <[email-masked]>
Date: Wed, 9 Jan 2002 13:34:22 +0200

In my opinion, connections using SACK and Limited transmit can afford having
a conservative RTO since they suffer non-spurious timeouts infrequently.

RFC2988 is a good starting point to provide a conservative enough timer
suitable for wireless environment. The next step could be to use
non-decreasing version of the timer, i.e. to use only RTT samples that
increase the RTO value. This way the RTO timer becomes the estimate of the
highest RTT value observed on this connection  so far.

Andrei

---

From: Gorry Fairhurst <[email-masked]>
Date: Wed, 09 Jan 2002 14:42:23 +0000

> highest RTT value observed on this connection  so far.

But, what about path changes, from a slow/long path to a short delay path?
--- surely there must be some grounds for reducing the RTO. Even if, the
tendency is to fix the RTO much larger than the RTT measurements, MAX seems
excessive...

Gorry

---

From: Kacheong Poon <[email-masked]>
Date: Wed, 9 Jan 2002 16:13:04 -0800 (PST)

> a conservative RTO since they suffer non-spurious timeouts infrequently.

If I am not mistaken, rule 5.3 of RFC 2988  restarts the timer only if
new data is ack'ed.  Duplicate acks do not ack new data.  So rule 5.3 
does not help in the above cases.  It does not even restart the timer for 
fast retransmit.

> highest RTT value observed on this connection  so far.

The question is if RFC 2988 works because of coincidence or it
has a solid foundation.  I still do not understand the reason
behind restarting the timer when an ack for new data arrives.
It does delay a timeout, but for what reason?

I do not think using the above suggested method is a good idea.
we may as well use a fixed timeout of the max we know of for today's
Internet (-:

							K. Poon.
							[email-masked]

---

From: Andrei Gurtov <[email-masked]>
Date: Thu, 10 Jan 2002 14:17:43 +0200 (EET)

> tendency is to fix the RTO much larger than the RTT measurements, MAX seems

I know it sounds overly conservative, but nothing better comes to mind
while thinking of a suitable rxmt timer for GPRS with fairly stable 1
s RTT with eventual 10 sec delay spikes. A possible option is to reset the
timer to estimate based on actual RTT when a non-spurious timeout is
encountered. Still, this may be a better approach than hard-coding some
(arbitrary) fixed minimum RTO.

Andrei

---

From: Kacheong Poon <[email-masked]>
Date: Thu, 10 Jan 2002 17:09:16 -0800 (PST)

> (arbitrary) fixed minimum RTO.

Some questions about GPRS.  What is the approximate bandwidth
delay product in such network?   What kind of network apps are 
supposed to run on it?  It seems that interactive apps are out 
of questions.  How often will those delay spikes happen?  Thanks.

							K. Poon.
							[email-masked]

---

From: "Andrei Gurtov" <[email-masked]>
Date: Sun, 13 Jan 2002 18:12:22 +0200

> of questions.  How often will those delay spikes happen?  Thanks.

Bandwidth is 10-50 kbps, RTT about 800 ms. People use it for normal Internet
access. Frequency of delay spikes depends on many things. E.g. voice calls
to your mobile terminal suspend the data connection. Driving in Helsinki
seems to generate handovers (delay spikes) roughly every minute.

For more details please check
http://www.cs.helsinki.fi/u/gurtov/papers/icc01.html
http://www.cs.helsinki.fi/u/gurtov/papers/pwc01.html

Andrei

---

From: Reiner Ludwig <[email-masked]>
Date: Mon, 21 Jan 2002 22:33:33 +0100

Hi Kacheong,

I'm slowly working through my e-mail backlog ...

>next segment.  This point has been mentioned by a lot of other people.

I thought the same for quite a while but our recent research showed that 
rule 5.3 in RFC2988 is often an important (although fairly imprecise) 
safeguard.

Imagine the case of a bandwidth dominated link where, e.g., the packet 
transmission delay across the bottleneck link dominates the RTT. This is 
typical for paths across wide-area wireless access. When the queue starts 
to build up at the bottleneck link, the RTT will increase significantly. 
Thus, when the RTT for packet N has increased significantly compared to 
SRTT, chances are that the RTT for packet N+1 will also be increased.  Rule 
5.3 implicitly factors this in. We found that this often saves you from a 
spurious timeout, because the SRTT and RTTVAR are often not sensitive 
enough to account for such RTT spikes (due to the gains 1/4 and 1/8).

[Side note: This example also argues in favor of timing every segment 
across bandwidth dominated paths. This is because an inreasing RTT is 
sooner reflected in an increased RTO. Problem: How does the sender know 
that it is running across a bandwidth dominated path?]

See also section 3.3 in our paper in CCR Vol. 30 No. 3, July 2000. At that 
time, we thought it would be better to change rule 5.3 as follows:

(1) REXMT = RTO - 'age of oldest outstanding segment';

When timing every packet, we also changed the gains (1/4 for SRTT, and 1/8 
for RTTVAR) to the single factor 1/(4 x flightsize). This is to avoid that 
the estimators (SRTT and RTTVAR) lose their memory too quick. With that 
change in place, we made the estimators even less sensitive to RTT spikes. 
The effect was that when an RTT spike occured, 'age of oldest outstanding 
segment' became very large, and REXMT became very low (often too low) to 
due rule (1).

To solve that our current RTO looks like this:

(2) RTO = MAX(SRTT, RTT) + MAX((K x RTTVAR), (2 x G)); with RTTVAR defined 
as given in the mentioned CCR paper.

When timing every packet, we chose K = 2, and find pretty good timer 
performance.

>[...] The current TCP RTO algorithm is not designed to
>to deal with this in the RTO calculation.

I doubt that we will find an RTO that will work fine under all conditions. 
Instead, I agree with Mark Allman that an RTO should be "reset" to be more 
conservative "for a while" after a spurious timeout has been detected. This 
is the link to the Eifel algorithm (which at this point is a pure detection 
scheme) and a corresponding response algorithm (revert CC state & adapt RTO).

>retransmit after timeout problem mentioned in this thread.

I'm not quite sure what you mean. Please explain this.

///Reiner

---

From: Kacheong Poon <[email-masked]>
Date: Tue, 22 Jan 2002 12:45:31 -0800 (PST)

> that it is running across a bandwidth dominated path?]

I can see your reason for timing every segment because of the queue 
building up.  But it still seems to be a hack for restarting the timer.
It just tells us that the timer is not good enough.  What does an ACK 
for segment N tell TCP about the fate of segment N+1?  If the timer
is not good enough, there are other "hacks" to deal with it, I guess.
Restarting the timer hack is not neccessarily the best one.

> scheme) and a corresponding response algorithm (revert CC state & adapt RTO).

This is why I asked the question whether TCP should have more than one
RTO algorithm.  I believe everyone spoken so far agrees that it is
probably not possible to have an RTO algorithm to work good in all
situations.  But there is only one right now specified in a standard
RFC and everyone has to use it.  We know that it does not work well 
in some network environments.  If people know about this, they can 
switch to another one which is good for their situations.  One question
is how many such algorithms is enough?  And should a TCP stack allow a 
user or sys admin to specify a user defined algorithm?  There are
many other issues.  That's why I hope people can give their comments.

> I'm not quite sure what you mean. Please explain this.

It was suggested that the go-back-N behavior of TCP after a spurious
timeout can trigger false fast retransmit due to those dup ACKS.  I 
was saying that it was not true for all modern TCP impls.

						K. Poon.
						[email-masked]

---

From: Reiner Ludwig <[email-masked]>
Date: Fri, 25 Jan 2002 05:51:18 +0100

At 21:45 22.01.2002, Kacheong Poon wrote:
>for segment N tell TCP about the fate of segment N+1?

I agree with you that restarting REXMT with RTO when a new ACK arrives 
introduces this offset, and that that is sort of a hack. I.e., it typically 
makes the REXMT unnecessarily conservative.

I hope you agree, though, that REXMT does need to be restarted when a new 
ACK arrives. But then to be precise this offset which is this mentioned 
'age of oldest outstanding segment' needs to be taken account somehow. Do 
you agree with that?
For example, one could do REXMT = RTO - 'age of oldest outstanding 
segment'; as suggested before. But that should only be done in "normal" 
phases, not during loss recovery.

Still this is not sufficient, because it may be the case that the ACK
for segment N does in fact indicate something about the fate of segment 
N+1: If the RTT for N has suddenly increased compared to SRTT, chances are 
quite high that the RTT for N+1 will also be increased. However, since SRTT 
and RTTVAR are smoothing averages, they might not react appropriately quick 
to compensate for such an RTT spike. Simply doing "REXMT = RTO - 'age of 
oldest outstanding segment';" will then become too aggressive. That's why 
we changed our RTO calc to RTO = MAX(SRTT, LastRTTSample) + 'some variation';

>RTO algorithm.

I still believe that we can find a single one that will be OK in general. 
Not that I believe that an REXMT/RTO can be found that catches each and 
every RTT spike. Such an REXMT/RTO would probably be far too conservative. 
Instead, TCP should be able to deal with spurious timeouts :-)

>was saying that it was not true for all modern TCP impls.

Yes, TCP's that implement the careful version of bugfix from RFC2582 don't 
have that problem.

///Reiner