Subject: Re: [TERNLI] Notes from tonight's ad hoc

From: Aaron Falk <[email-masked]>
Date: Tue, 1 Aug 2006 21:37:32 -0700

On Jul 28, 2006, at 5:56 AM, Mark Allman wrote:

>   + Giving a generic signal that *something* has changed and it likely
>     matters and so the transport should re-init itself (e.g.,  
> forget the
>     SRTT, RTTVAR, cwnd, ssthresh, MTU value, etc.).

Perhaps the signal should be that congestion state or RTT estimate is  
no longer valid.  I.e., make the signal have transport semantics.

--aaron

---

From: Joe Touch <[email-masked]>
Date: Wed, 02 Aug 2006 07:19:17 -0700

Aaron Falk wrote:
>>     matters and so the transport should re-init itself (e.g., forget the
> Perhaps the signal should be that congestion state or RTT estimate is no
> longer valid.  I.e., make the signal have transport semantics.

That is what I was afraid of - that means that the link knows what the
network is doing, e.g., whether it is using the link for CBR or bursty
traffic, etc.

Joe

---

From: Gorry Fairhurst <[email-masked]>
Date: Wed, 02 Aug 2006 16:07:47 +0100

> network is doing, e.g., whether it is using the link for CBR or bursty

It isn't clear to me yet that the idea of transport semantics is useful...

If say, the link has a substantial change in RTT: this obviously effects 
the RTO in TCP (how much depends upon how much the total path RTT 
changes), the signal could impact what a sender stores to calculate the 
SRTT -  perhaps it also means that you may have to change other things 
(such as cwnd), but links don't really know the implications on the 
transport ...

Gorry

---

From: Aaron Falk <[email-masked]>
Date: Wed, 2 Aug 2006 08:12:54 -0700

> network is doing, e.g., whether it is using the link for CBR or bursty

Joe-

I agree with you so I must not be making myself clear.  What I mean  
is to select those characteristics of the path which are possibly/ 
generally of interest to transport.  It seems to me as though some of  
those characteristics will be more clearly visible to the network  
(e.g., path), some to the link (or subnetwork, really) (e.g., loss  
rate).

I'm not asserting I have an answer here.  Just probing the problem.

--aaron

---

From: Bob Briscoe <[email-masked]>
Date: Wed, 02 Aug 2006 21:29:14 +0100

Aaron,

>I'm not asserting I have an answer here.  Just probing the problem.

I prefer to talk specifics (but excuse me if I've missed some shared 
context - I missed the ad hoc BoF, but I've tried to pick it up from the 
archive)...

We certainly know what info the *congestion control* part of the transport 
needs: congestion and delay. So for that we merely need to signal the 
information the transport needs in packets. And if either of these values 
changes, it's obvious it's changed. Surely the transport doesn't then need 
a "something's changed" message. Surely the problem is that the netwk layer 
doesn't signal congestion information with enough precision for the modern 
transport's needs.

My personal preference is to keep the DoS-resistant model where lower layer 
info is piggy-backed on packets to the receiver, then the receiver deals 
with feedback.

So we would need the following changes to protocols:
* a multi-bit netwk layer congestion field within the forwarded packet.
* the addition of multi-bit congestion feedback in transport protocols.

A drastic change in load at any router would immediately be visible as a 
change in this higher-precision congestion field (if it's a re-route but 
the new path has the same congestion, the transport doesn't need to know 
anything has changed). A multi-bit congestion field would also quickly 
bootstrap a connection's knowledge of path congestion in the feedback from 
the very first packet.

I'm not just choosing congestion as the signal because we already have it. 
There is a good argument for why it is right (and other metrics are wrong).

Congestion is a probability p in [0,1] which represents the proportion of 
the load unlikely to be able to be served. IMHO, signalling p with more 
precision is *better* than signalling explicit rate information (like 
QS/XCP). p gives as much information as signalling explicit rate infomation 
without the router having to decide who gets what.

For instance, the variable p is the internal variable in the RED algorithm 
that drives the random dice throw to decide whether to {drop | mark ECN} or 
not. I'm saying routers should write this number into the multi-bit 
congestion field of each packet (accumulating it from multiple routers is 
described later).

 From p, the source can work out the excess rate it is sending like this: 
if the local congestion on an interface is p, incoming load is Y and 
outgoing capacity is X, then p ~ (Y-X)/Y. So if every flow getting signal p 
reduced its rate by p%, they would all fit through the available capacity. 
But of course, sources actually do some form of AIMD to allow for new flows 
etc, but the alg is essentially designed to converge on a rate that is p% 
lower than the one being used. Essentially, a signal of p can be reverse 
engineered to get a rate signal.

But the important difference is that p is normalised, so it is 
proportionate to the bit rate sent in each flow but the router doesn't have 
to understand flows. Basically, the router doesn't have to dish out 
bandwidth allocations, which saves it understanding who it is dishing out 
stuff to.

If instead the router dishes out rate to flows (like XCP/QS), sources can 
cheat by splitting one flow into multiple flows. The idea that fairness 
means that all flows should get equal rate is completely daft and should 
never have taken hold - it's just soooo vulnerable to cheating by splitting 
flow IDs.

The other strength of using p, is that it can be combined properly when 
there are multiple bottlenecks. The accumulation algorithm to update the 
header field h as it passes through a router with local congestion p should 
use combinatorial probability
         h  <-    1 - (1-h)(1-p)
So, for instance, if there are two bottlenecks, with p of 5% and 1%, the 
header would end up carrying h = 5.95% (= 100% - 95%*99%).

This way, the traffic matrix packs into the network most efficiently. It 
stems from the meaning of congestion as a probability. Finding the minimum 
bottleneck (like XCP & QS) isn't necessarily the best approach.

Basically, I'm saying
a) Instead of signalling "something's changed", I believe it is more 
practical to continuously signal the "something".
b) What congestion control needs most is greater precision for the 
congestion signal
c) There are strong but subtle reasons for using probability as a universal 
congestion signal that lead to overall simplicity when the whole picture is 
taken into account (which we lose if we adopt QS or XCP).

Bob

____________________________________________________________________________
Bob Briscoe, <[email-masked]>      Networks Research Centre, BT Research
B54/77 Adastral Park,Martlesham Heath,Ipswich,IP5 3RE,UK.    +44 1473 645196

---

From: Lars Eggert <[email-masked]>
Date: Thu, 3 Aug 2006 09:57:36 +0200

Hi,

On Aug 2, 2006, at 22:29, Bob Briscoe wrote:
> We certainly know what info the *congestion control* part of the  
> transport needs: congestion and delay. So for that we merely need  
> to signal the information the transport needs in packets. And if  
> either of these values changes, it's obvious it's changed. Surely  
> the transport doesn't then need a "something's changed" message.

actually, it's not that obvious. Yes, the transport eventually learns  
that things have changed based on its ongoing path probing, but that  
may be several RTTs later, during which it has transmitted at a rate  
based on stale state. Furthermore, its reaction to the change may be  
too conservative (not a big issue) or not conservative enough.

> Surely the problem is that the netwk layer doesn't signal  
> congestion information with enough precision for the modern  
> transport's needs.

It's not only congestion, it's also delay, plus maybe additional  
information. One work item from the ad hoc meeting was to figure out  
which kinds of information transports do or could operate on.

> My personal preference is to keep the DoS-resistant model...

<I need to think about the snipped parts more.>

> Basically, I'm saying
> a) Instead of signalling "something's changed", I believe it is  
> more practical to continuously signal the "something".

That's an interesting observation. By constantly providing the raw  
information, it is up to the transports to decide what difference  
constitutes a "change" vs. having the network layer decide that a  
"change" has occurred. It also allows transports to process the raw  
information into events any way they see fit, instead of assuming one  
specific way at the layer below.

> c) There are strong but subtle reasons for using probability as a  
> universal congestion signal that lead to overall simplicity when  
> the whole picture is taken into account (which we lose if we adopt  
> QS or XCP).

Lars
-- 
Lars Eggert                                     NEC Network Laboratories

---

From: Bob Briscoe <[email-masked]>
Date: Thu, 03 Aug 2006 11:29:01 +0100

Lars,

>which kinds of information transports do or could operate on.

Yes, I said the TSV needs congestion and delay, but I only focused on the 
NET signalling congestion upwards, because...:

i) If you meant specifically RTT delay (= propagation + congestion delay), 
the TSV can measure that as often as it needs to without explicit signalling.

ii) However, if you meant specifically congestion delay I disagree - this 
is less useful as a congestion metric (implying I don't believe FAST TCP or 
Vegas are the long term direction - fine as tactical hacks).

Arguments against congestion delay as a metric:
a) Explicit congestion signalling is a richer way for the NET to signal how 
much the TSV should change its rate because, if the NET signals (or the TSV 
measures) congestion delay, in order to signal an equivalent amount of info 
to the TSV for it to know how to change its rate, the NET would also have 
to say what the output line rate of each interface was (meaning numerous 
metrics across a path - yuk). Just signalling congestion does that all in 
one metric, even when accumulated across a path.
b) Measuring congestion delay is fine as a tactical hack to get more 
precise info from the network than 1-bit drop or 1-bit ECN, but it won't be 
useful long term as link speeds increase. Then congestion delay becomes so 
small relative to propagation delay that it becomes a very imprecise metric 
to do congestion control on (IOW, the equiv no. of bits of info per packet 
is currently >1, but will become <1 as the net scales).

(We're in the early stages of writing up and proving the above argument as 
a full paper.)

BTW, I do agree with FAST & Vegas (and Siris's weighted window-based cc) on 
another count: Unlike Reno, delay should only determine the second order 
behaviour, not the first order. Ie the equilibrium rate shouldn't depend on 
RTT, but how fast it gets there should.

>specific way at the layer below.

If the NET says "something's changed",
* 1RTT later the TSV probes.
* The TSV has to probe for everything, because it doesn't know what 
"something" is (unless the NET allows the question "what's changed?" which 
is silly - it would have been better for the NET to say what changed in the 
first place otherwise this would take yet another RTT).
* 1 more RTT later the TSV finds out the info.

That's 2RTTs already.

If we can get down to exactly what the "something's" are, we can know how 
many bits would be needed to continuously repeat them, rather than 
implement the more complicated probe interfaces necessary above.

Additionally, when talking about changes in load/congestion, the NET 
doesn't know what threshold all the different TSVs would like it to use to 
decide when a change has been big enough to say "something's changed". 
Congestion changes all the time. Some changes are bigger than others. So 
the approach of continuously reporting the current level avoids the NET 
second guessing what changes TSVs are interested in.

Bob

---

From: Joe Touch <[email-masked]>
Date: Thu, 03 Aug 2006 10:42:11 -0700

> On Aug 2, 2006, at 22:29, Bob Briscoe wrote:
...
> specific way at the layer below.

So you have congestion. It affects, e.g., only TCP port 80. The network
layer doesn't know that, so it continually tells every transport layer
that congestion has occurred. It's blathering that something needs to be
done, when in fact only one protocol really sees any change.

And congestion can change without affecting latency, and vice-versa. How
do you know what to send the transport? How do you know what it cares about?

The network can't measure *transport* latency, which is what the
transport layer really cares about. Something specific like "the network
layer has lower RTTs right now" assumes that this matters to the
transport layer; it really doesn't, e.g., if the transport on the other
end has larger latency at the same time (due to transport processing load).

I don't much care what the network layer tells the transport; it's the
transport's obligation to verify whether it sees the same thing, or in
fact what it sees anyway.

IMO, 'please re-check the network now' is the primary signal of
interest. Everything else "goes to intent" and makes the network layer
(in this case) recapitulate what it *thinks* the transport layer wants,
 and that isn't particularly informative.

(FWIW, the same is true for link/net interactions)

Joe