Subject: Idle Restart Algorithms

From: Patrick McManus <[email-masked]>
Date: Wed, 24 Feb 1999 12:36:33 -0500 (EST)

So, I've been thinking about TCP idle restarts based on the reading of
both tcpimpl-prob-05 (paxson, et al..) and tcpimpl-restart-00 (hughes,
touch, heidemann exp 09/98).. and something doesn't feel right.

I offer up this narrative in case I've not grasped something correctly
and someone wants to do the kind favor of setting me straight before I
go much further. This rambles a bit, but it does capture my thinking on the
topic. 

From a heuristic pov, the purpose of congestion control is to
dynamically rate limit the pace of a stream to match the current
capacity characteristics of the underlying medium. Because both
contention for that medium is changing and the medium itself may
change (due to routing adjustments) this must be constantly
re-evaluated. TCP's basic approach is to race forward to about 1/2 of
what it thinks the limit might be, and then inch upwards until it gets
rebuked. This creates some kind of rolling estimate of an acceptable
send rate based on a feedback loop from the network. 

After a period of inactivity this estimate becomes less useful due to
lack of recent pertinent feedback. Traditional implementations react
to this by re-entering slow start which in effect re-discovers the
current available bandwidth. Alternatively, [Hughes,Touch,Heidemann]
suggest Congestion Window Monitoring which fundamentally imposes a
'use it or lose it' policy on growing CWNDs that are in excess of 4
plus the amount of outstanding data which would ensure that after an
idle period the cwnd is maxed out at 4.

The basic issue at hand is that the past performance of the network is
being used to predict the future. It is recognized that the longer the
interval between past input and the current decision time is, the less
reliable that data is for making the decision. However, traditional
reaction to this issue uses a simple 2 step function (valid/not valid)
to make that determination. The only input to this decision is RTO, which
in my opinion exerts a counter-productive force on the decision. For
two links with the same average RTT the link with the greater variance
is going to fall into the 'valid data' step more than the one with a
lesser variance. In essence, this increases the likelihood of using
past data to predict the future on a link that has proven _more_
volatile (and thus less likely to obey past patterns of
behavior). That doesn't seem like a good thing.

On a gut level, I'm not much of a fan of CWM either.. While leaky
bucket scenarios are attractive to me, CWM essentially enforces a
gushing bucket where sending capacity is throttled quickly back if the
sending rate doesn't equal the ack-reception rate. It strikes me as
over-aggressive... using 4 as a fall back instead of 1 is likely meant
to mitigate this, but I dislike the constants as they cannot apply
well to all mediums current or future.. (the increased use of
satellite services for downstream in use for things like DirectPC and
rural African service exhibit huge bandwidth delay properties that are
un-necessarily crippled by this)

I think there needs to be a little more discussion on the types of
timeouts that are realistic. Discussion generally just cites HTTP/1.1
and leaves it at that. I see several different scenarios within just
HTTP and also suspect NNTP exhibits relevant behavior. Some possible sources:

  * Short timeouts.. probably as a result of document retrieval,
    parsing time, and subsequent requests for embedded objects.. Just
    how long this takes depends on a lot of things of course, not the
    least of which are document composition and client
    implementation.. but it's probably on the order of 10RTT
  * longer timeouts.. the result of human interpretation of past
    results and the subsequent request to follow one of the presented
    related references.. on the order of a few whole seconds.
  * Folks reading news with NNTP (as opposed to NNTP used for
    transport) are going to exhibit patterns similar to the HTTP
    longer timeout mentioned above.. more and more private news servers
    are being introduced into the fabric of the web for use as a
    discussion medium, but for security/demand reasons are not propagated in
    any kind of general purpose fashion, so interactive news reading
    is becoming more of a WAN phenomenon.
  * HTTP cache interaction.. particularly pre-emptive retrieval
    scenarios that propagate information between caches.

I think the essence of the problem is the overloading of burst
management and flow rate control onto a single mechanism. A large,
previously established, cwnd may have been achieved through an earlier
long sustained flow and slowly ramped up. Even if the properties of
that link have not changed there is no guarantee that the link can
support a full cwnd burst presented all at once without dropping
packets. However it's quite possible that it can, as well and in the
case of large bandwidth*delay links that is really something that
should be taken advantage of.

So for the sake of clarity, I want to remove the concept of burst
control from the discussion of restart algorithms. Perhaps a 'burst
window' or other such technique can be orthogonally implemented to
address the issue (something that would learn in a similar fashion
what the maximum allowable network burst would be).

Moving back to idle algorithms I would like to experiment with
something adaptive.. maybe a cwnd reduction of 20% (min 1 segment) for
every A-4D elapsed in the idle period (apply in a compounding
fashion).. This reverses the impact of the variance mentioned above
while providing more fine grained input into the 'trust' process.

While I intend to go ahead in looking at this, I'm soliciting any
helpful insights or 'been there done that' comments folks may have.

Thanks,
-Pat

Patrick R. McManus - AppliedTheory Communications  -	Software Engineering
http://pat.appliedtheory.com/~mcmanus			Lead Developer
[email-masked]	'Prince of Pollywood'	Standards, today!

---

From: Joe Touch <[email-masked]>
Date: Wed, 24 Feb 1999 10:35:19 -0800 (PST)

> From [email-masked] Wed Feb 24 10:00:51 1999
> From: Patrick McManus <[email-masked]>
> Subject: Idle Restart Algorithms
> To: [email-masked]
> Date: Wed, 24 Feb 1999 12:36:33 -0500 (EST)
> 
...

This is certainly a difficult issue, exemplified by the delay in
our getting out the update to the restart ID...

The primary issue, to me, is as follows:

	- the current scheme (time since receive) is defeated
		by request/response protocols, unintentionally
		generating excessive bursts

	- timeout based schemes are 'too' binary in nature (as you noted)
		there is no timeout for 'just under an RTO'
		there is a full window adjustment for anything larger
		(i.e., they are step functions - all on, or all off,
		not smooth)

CWM was one attempt at a continuous, graceful degradation of
performance, intended at avoiding line-rate bursts. We have a
different one, designed with Sally Floyd, which addresses another
source of bursts - packet loss. This mechanism is a more direct
leaky-bucket, which itself is a nice tool for controlling 
and limiting bursts to acceptable values.

Granted, as we have noted, there are many parameters that need
to be tuned - 

	- does the bucket size vary?

		e.g., a time-based decay of the bucket size

> capacity characteristics of the underlying medium.

Agreed - which is why true rate-pacing is preferable, but somewhat more
cumbersome. John Heidemann developed a version of this (RBP), which
kicks in only when the RTO goes off, and goes away when ACK clocking
resumes. Again, this has a step-mode which I would prefer to smooth 
somehow.

> idle period the cwnd is maxed out at 4.

It seems reasonable that, after a very long period of time, the window
should essentially revert to the same as a new connection would be
able to inject. I.e., after long idles, a connection knows no more
about the network than a new connection.

> in my opinion exerts a counter-productive force on the decision.

> to mitigate this,

4 is intended to allow the window to open at full rate,
given non-sequential ACK losses. The sending capacity is thottled
back only if less than 1/4 the expected ACKs are returned within 
a RTT. 

> but I dislike the constants as they cannot apply

Huge BW*delay is not directly an issue. The number of outstanding
packets is, and when it is high, the system is necessarily more
volatile. The question is whether to be aggressive or conservative;
satellite systems often work better with aggressive behavior. That
is something that could be discovered on a per-path basis (e.g., 
pathchar) and applied per-connection (e.g., some new TCP option {?}
or by control-block sharing {e.g., RFC2140}). 

>   * Short timeouts..
>   * longer timeouts...
>   * Folks reading news with NNTP 
>   * HTTP cache interaction..

This would be designing step-functions based on current behavior;
when behavior changes (as it did with the advent of HTTP), this
are just as likely to be inappropriate.

> management and flow rate control onto a single mechanism.

Agreed (as in the ID). True rate pacing decouples the two.

> what the maximum allowable network burst would be).

A burst window is what a leaky bucket implements. The question
appears to be "is it variable, and on what basis".

----

As noted above, we are continuing to refine the ID.  It is not intended
to solve the problem completely immediately, but rather to 

	- define the problem
	- describe some issues in a solution
	- propose a few candidate solutions
	- recommend a quick fix for current implementations,
		based on minimal code modifications and
		generally conservative behavior

We would be very interested in hearing about other solutions, and
would be happy to collect these into a web page... send me your links,
and I'll post a URL shortly....

Thanks!

Joe

---

From: Venkat Padmanabhan <[email-masked]>
Date: Wed, 24 Feb 1999 11:21:41 -0800

I think you've outlined the issues very well. Here are a few comments.

> reliable that data is for making the decision. However, traditional

I am not convinced that there is a strong correlation between the
length of the idle period and the reliability of old congestion
information. Consider a bottleneck link that is shared by multiple
connections. If one of them becomes idle, the others would soon
(within several RTTs) ramp up and consume the bandwidth that the
idle connection freed up. If the idle connection were to restart
after this time and immediately start sending at its old rate, it
may cause overload and packet loss. (This is even assuming that 
packets are sent out smoothly.) So the appropriateness of having
an idle connection restart without slow start dissipates within 
(at most) several RTTs, a duration which is likely to be a much 
shorter than the typical user "think time" in a Web browsing session.

> what the maximum allowable network burst would be).

I couldn't agree with you more! Avoiding bursts, be it via timers,
"burst windows", etc., is the easy part. The hard part is figuring
out what the congestion window and other variables should be set
to after an idle period.

> while providing more fine grained input into the 'trust' process.

This may be worth investigating, but as I have outlined above, I
don't intuitively understand why a gradual decay of the congestion
window (over the timescale of interest -- 10s of seconds) would be
appropriate. Given the current congestion window size, should we be
more confident in estimating the appropriate window size after a
1-minute idle period compared to a 2-minute idle period?

> helpful insights or 'been there done that' comments folks may have.

The approach I took in my work on "TCP Fast Start" was to have an 
explicit protocol mechanism to "hedge" any bets (guesses) we may 
make about the appropriate window size after an idle period. With 
such a mechanism in place, it may be okay to err on the side of being 
too aggressive (i.e., using a larger window size than appropriate). 
The mechanism I used was priority dropping -- i.e., packets sent 
when the sender is unsure of the appropriateness of congestion window
size are assigned a low drop priority. This would shield (to an extent)
other traffic in the event of the guess being incorrect. While
priority dropping is a simple mechanism and similar in spirit to
some of the diffserv mechanisms being considered, the Internet is
not quite ready for it yet. More information on this work is available
from:
http://www.cs.berkeley.edu/~padmanab/papers/gi98.ps
http://www.cs.berkeley.edu/~padmanab/phd-thesis.html (Chapter 8)

One final note: I believe the deployment of RED in routers would
improve the chances of success for a fast start like scheme, because
the router buffers would better be able to absorb the surge in
load due to connections that are restarting.

-Venkat

Venkat Padmanabhan
Microsoft Research
[email-masked]
http://www.research.microsoft.com/~padmanab

---

From: Joe Touch <[email-masked]>
Date: Wed, 24 Feb 1999 13:20:56 -0800 (PST)

> From [email-masked] Wed Feb 24 11:45:45 1999
> From: Venkat Padmanabhan <[email-masked]>
> To: "[email-masked]'" <[email-masked]>
> Cc: "[email-masked]'" <[email-masked]>
> Subject: RE: Idle Restart Algorithms
> Date: Wed, 24 Feb 1999 11:21:41 -0800
> 
...
> http://www.cs.berkeley.edu/~padmanab/phd-thesis.html (Chapter 8)

There was a version of something similar developed at UPenn,
as a follow-on to my own dissertation (Mirage), in which 
the send window was constant, and split into two sub-windows,
the boundary of which varied with the feedback. It would have
differened from Venkat's only in that the scheme was always
running, and that the overall window was constant (a function
of the upperbound RTT*BW, but stable compared to the boundary).

The only reference I have to this is:

	Univ. Penn. CS Tech Report
	MS-CIS-94-55 (DISTRIBUTED SYSTEMS LAB 80) 
	Congestion control by bandwidth-delay tradeoff in 
	very high-speed networks: the case of window-based control 
	Hyogon Kim, David J. Farber

Joe