Subject: Re: Doubt regarding the MANAGING THE RTO TIMER

From: Mark Allman <[email-masked]>
Date: Mon, 10 Dec 2001 22:39:15 -0500

> However, I think that if traces would be collected at some
> wireless gateway, the result might have been different. The
> environment I was looking at included slow overbuffered links with
> occasional delay spikes.

We also found delay spikes.

> On slow links the queueing delay can double between two adjacent
> RTT samples if they are collected once per window. This type of
> situation was the motivation for VJ to increase the RTTvar
> coefficient from 2 to 4. Still, experimenting in NS with TCP
> without timestamps I was getting spurios timeouts after even a
> slight delay spike or during fast recovery. A technical report
> with results and traces to back-up this will be available
> shortly. Hopefully, we will have an interesting discussion.

I'd like to see your tech report.  We did some very simple
experiments of links with varying propagation delay (satellite
stuff).  One of the scenarios we tested was a scenario where the RTT
doubled instantly (it was a handoff -- and we modeled it as perfect
(no drops, no reordering)).  When using an RTO that is RFC 2988
compliant we noted no spurious retransmits.  When using a finer
grained timer with no minimum RTO we did notice some bogus
retransmits.

(Of course, in our scenario no amount of RTT measurements would have
predicted this increase in RTT because it happened instantly.  The
point is that the RTT doubled without a spurious retransmit.)

The experiment is outlined in the following short paper:

    Mark Allman, Jim Griner, Alan Richard. TCP Behavior in Networks
    with Dynamic Propagation Delay. Proceedings of Globecom 2000,
    November 2000. 
    http://roland.grc.nasa.gov/~mallman/papers/var-delay.ps

allman

---
Mark Allman -- NASA GRC/BBN -- http://roland.grc.nasa.gov/~mallman/

---

From: Reiner Ludwig <[email-masked]>
Date: Tue, 11 Dec 2001 13:26:13 +0100

I'm cross-posting since this is being discussed on [email-masked] 
and [email-masked] ...

By now, we have raised (at least) 3 different issues:
1. timing every packet(e.g., by using Timestamps) or not
2. timer granularity
3. RTO minimum

Concerning 1:
I have found that timing every packet (usually) makes no big difference on 
delay-dominated paths *but* it makes a big difference on bandwith-dominated 
paths.
Since, I know the trace collection Mark & Vern used for their SIGCOMM99 
paper quite well (I used it for my own analysis), I also know that those 
traces mostly (>> 95%) stem from delay-dominated paths. I believe that 
that's the reason why Mark & Vern found no big impact when using the 
Timestamps option. However, I definitely cannot agree to the conclusion 
that the Timestamps option has no effect on RTO accuracy in the general 
case. Timing every packet does make the RTO more accurate on 
bandwidth-dominated links, and thus helps avoid spurious timeouts across 
such paths. The problem is that the constant gains 1/4 and 1/8 are not 
appropriate when timing every packet if many packets are in flight (i.e., 
cwnd is large). In that case, the TCP sender forgets the RTT history too 
fast. A solution is to make the gains adaptive. This has been addressed in 
this paper:
Reiner Ludwig, Keith Sklower, The Eifel Retransmission Timer. Appears in ACM
Computer Communications Review, Vol. 30, No. 3, July 2000.
http://iceberg.cs.berkeley.edu/publications.html

Others have shown that timing every packet helps avoid spurious timeouts 
across bandwidth-dominated paths:
http://www.ietf.org/internet-drafts/draft-khafizov-pilc-cdma2000-00.txt

BTW, when timing every packet, the motivation that Van Jacobson gave for 
increasing the RTTVAR weight factor from 2 to 4 does not hold any longer. 
My current analysis shows that a weight factor of 2 is mostly sufficent 
when timing every packet. But that work hasn't concluded yet.

Concerning 2:
In my research, I confirm Mark & Vern's finding that in today's Internet a 
timer granularity of 100 ms gives the best trade-off between timer accuracy 
vs. host processing load due to timer handling. However, the RTO does get 
more precise when going down to 10 ms timer ticks, but it's mostly not 
worth the effort. This might change in the future when typical Internet 
RTTs come below 100ms. Then, a 10 ms timer granularity is probably more 
appropriate.

Concerning 3:
I find it bogus that RFC2988 hardwires the minimum RTO to 1 second. I 
haven't found any motivation for that. If the retransmission timer is 
implemented as a hardbeat timer, an RTO minimum of 2 x the granularity (as 
in BSD) is sufficient. I have data to confirm this, and hope to write that 
up some time next year.

///Reiner

---

From: Phil Karn <[email-masked]>
Date: Tue, 11 Dec 2001 11:13:46 -0800

>In my research, I confirm Mark & Vern's finding that in today's
>Internet a timer granularity of 100 ms gives the best trade-off
>between timer accuracy vs. host processing load due to timer
>handling. However, the RTO does get more precise when going down to
>10 ms timer ticks, but it's mostly not worth the effort. This might
>change in the future when typical Internet RTTs come below
>100ms. Then, a 10 ms timer granularity is probably more appropriate.

Are you referring to the granularity of the RTT measurements, or the
granularity of the timer used to schedule retransmissions? These are
often different on many operating systems. E.g., Linux sets the clock
interrupt to 100 Hz, meaning it can schedule actions to a 10 ms
granularity (modulo CPU scheduling delays). But the x86 hardware lets
you read the CPU clock directly, making it possible to achieve
extremely fine granularity (1ns for a 1GHz system) when timestamping
events like receiving a packet.

Phil

---

From: Alan Cox <[email-masked]>
Date: Tue, 11 Dec 2001 20:01:35 +0000 (GMT)

> events like receiving a packet.

Only if you are comparing per processor. The x86 world makes no guarantee that
your processors are clocking at the same rate or started at the same clock.

---

From: Reiner Ludwig <[email-masked]>
Date: Wed, 12 Dec 2001 00:30:59 +0100

At 20:13 11.12.2001, Phil Karn wrote:
>granularity of the timer used to schedule retransmissions?

The latter.

///Reiner

---

From: Phil Karn <[email-masked]>
Date: Tue, 11 Dec 2001 21:58:47 -0800

Good point, the multi-CPU case hadn't occurred to me.

But don't most multi-CPU motherboards use a common clock for all CPUs,
at least when they're all running at the same clock rate?  And aren't
the CPU reset pins driven from the same source? If so, the CPU clock
counters should be pretty close.

So, in practice, how matched are the RDTSC timestamps on a multi-CPU
machine?

Phil

---

From: Phil Karn <[email-masked]>
Date: Tue, 11 Dec 2001 22:31:36 -0800

>The latter.

Ah. So how accurately can events now be scheduled on the various OSes?
I haven't kept up with this stuff.

The PC architecture has always provided multiple hardware timer
channels that can be programmed to interrupt at some future time,
either in a one-shot or a repeating mode.  The granularity is set by
the clock to the timer chip, which is considerably slower than the CPU
clock. One of these timers is usually programmed at boot time to
interrupt at a 100 Hz rate, and this drives most of the timer events
in UNIX and UNIX-like kernels.

The original PC had four timer channels. One was used to provide a
clock tick to the OS and another was dedicated to memory refresh (this
is probably all different now -- I haven't actively programmed at this
level since 1990 or so). That left at least one spare timer channel
that could schedule an interrupt with a granularity much better than
10 ms.

So you sort your scheduled events into a list and set the hardware
timer for the first event. When it ticks, you pop the top item off the
list, execute it and reload the timer with the appropriate interval
for the next event. I did this in my NOS TCP/IP code for scheduling
TCP transmissions and it worked well.

I don't know if any modern OSes provide a fine-grained scheduling
feature like this, but TCP sure would find it useful, especially
for transmit pacing.

Phil

---

From: Reiner Ludwig <[email-masked]>
Date: Wed, 12 Dec 2001 12:03:14 +0100

>feature like this, but TCP sure would find it useful, especially

At one point Keith Sklower at UC Berkeley and myself were thinking of 
implementing that feature for FreeBSD, but we never got around to do it. 
That would certainly make a difference given that FreeBSD still uses a 
timer tick of 500 ms for TCP's retransmission timer :-(

BTW, since you asked. I believe that latest
- Solaris uses 10 ms ticks,
- LINUX uses 10 ms ticks, and
- MS uses 100 ms ticks.

///Reiner

---

From: Alan Cox <[email-masked]>
Date: Wed, 12 Dec 2001 14:08:28 +0000 (GMT)

> Ah. So how accurately can events now be scheduled on the various OSes?

Linux we are still using 100Hz. There are patches for doing microsecond
level event triggering around.

> in UNIX and UNIX-like kernels.

Basically the 8259 disappeared into the chipset logic, people sawed off
unused bits and it doesnt do much any more. There is also the CMOS RTC
timer interrupt available (several KHz) and newer machines have ACPI OS
timers which run at constant rate at about 2Mhz.

Alan

---

From: Erich Nahum <[email-masked]>
Date: Wed, 12 Dec 2001 13:45:15 -0500 (EST)

> - LINUX uses 10 ms ticks, and

Actually, FreeBSD discarded the 500 ms timer 2 years ago.  From the
changelog:

| Revision 1.31 Mon Aug 30 21:17:06 1999 UTC (2 years, 3 months ago) by jlemon 
| Branch: MAIN 
| Changes since 1.30: +288 -224 lines
| Diff to previous 1.30 (colored)
| 
| Restructure TCP timeout handling:
| 
| - eliminate the fast/slow timeout lists for TCP and instead use a
|   callout entry for each timer.
| - increase the TCP timer granularity to HZ
| - implement "bad retransmit" recovery, as presented in "On Estimating 
|   End-to-End Network Path Properties", by Allman and Paxson.
| 
| Submitted by:   jlemon, wollmann

HZ is usually 100 (10 ms clock), but can be compile-time set to larger
values.  Many people set HZ to 1000 to get a 1 ms clock.

If you look at the timer code you'll see they're using a variant
of Varghese's timing wheels algorithm.  This not only helps timer
granularity but scalability for servers.  Since web servers have
large numbers of connections, many of which are in the TIME-WAIT state,
handling large numbers of timers efficiently makes a big difference
in server throughput.

-Erich

-- 
Erich M. Nahum                  IBM T.J. Watson Research Center
Networking Research             P.O. Box 704
[email-masked]            Yorktown Heights NY 10598