[e2e] "congestion" avoidance...

[David P. Reed]

I think I was trying to "napsterize".

The seed of the idea is that you get all kinds of signals as a result of 
congestion that can be used in a control loop, so why not add a simple 
signal that can be modulated on the basis of source/dest intent, and which 
is shared with other participants in the congestion.  (It's like money in 
the sense that its scarcity means you only want to use it at a rate you can 
afford.)

Besides your packet rate (which directly affects other flows in the 
"flux"), having a bit per packet input that is combined into the other 
flows' flags would seem to be a powerful differential signalling channel.
Let's say that a normal flow has about 50% of its packets with "urgency" 
on, 50% off.
Say when you turn on ECN in a packet with the "urgency" flag set, you turn 
off the next "urgency" flag you see on a packet arriving into the 
queue.  Then the source/dest of the other flow sees that it is interfering 
with an urgent flow because it sees that its own urgency rate has 
dropped.  [This is the sketch of how a cross-flow signalling scheme might 
provide information from one flow to others - the algorithm is not intended 
to work, of course.]

At 11:20 AM 4/17/01 +0100, Jon Crowcroft wrote:


>so the problem i have with the current "ECN pricing" thinking is that
>it ignores users preferences for stability and predictability over
>cheapness (and we have a LOT of evidence gathered from mobile phone
>contracts, web and traditional telewphony as well as airline procing
>and so on i can cite)
>
>the shadow price for a packet (smart market) is one model, but leads
>to potential rapid fluctation in price aroudn flash crowd periods,
>which are all to common in IP networks
>
>the simple alternative  is a shadow price for a virtual circuit - this
>gives a stable price for the throughput over the "lifetime" of a
>session.....
>
>
>if you Mix this, you can get into nasty arbritrage situations....and i
>don't buy into the story that yo ucan offer users a choce via risk
>brokers - for the very reason that the traffic is highly dynamic...
>
>also, risk brokers form markets  themselves.....
>
>what i was thinking ewas to "democratise" (disintermediate) the risk
>broker and let users form their +own+ cartels dynamically...
>
>i.e. we napsterise congestion pricing for packets and flows...
>
>In message <5.0.2.1.2.20010417060401.03063510 at mail.reed.com>, "David P. 
>Reed" t
>yped:
>
>  >>Interesting thoughts.  However, money or something like it needs to enter
>  >>into the thinking.  I.e. some notion of sharing responsibility for costs
>  >>imposed on others.
>  >>
>  >>IE: At a point of congestion, the "indirect channels" among competing 
> flows
>  >>provide a way of signalling (at some bitrate) for a bargaining scheme.
>  >>
>  >>What range of bargaining schemes can be piggybacked on this signalling 
> channel?
>  >>
>  >>For example, what if a single (urgency) bit per packet (like the ECN 
> flag,
>  >>but provided by the source to the congested queue) could be modulated at
>  >>the source, tracked in a state variable at a router queue, and coupled 
> into
>  >>a bit in each outgoing packet that controls rate like ECN.
>  >>
>  >>
>  >>At 10:06 AM 4/17/01 +0100, Jon Crowcroft wrote:
>  >>
>  >>
>  >>
>  >>>there have been some steps recently to look at a range of rate and
>  >>>window based mechanisms for sharing the net amongst a set of sources (or
>  >>>sinks if we include receiver based multicast schemes) - i was looking
>  >>>at these and wondering if it isnt time to revisit some of the
>  >>>congestion control and avoidance thinking
>  >>>
>  >>>some schemes have been proposed that smooth the adjustment so that
>  >>>over an RTT we creep up to the operating rate, and creep down, on a
>  >>>packet by packet (inter-packet delay adjustment) basis
>  >>>(RAP from Handley et al)
>  >>>
>  >>>other schemes have proposed different powers for the increase decrease
>  >>>function (and assert that so long as we decrease x^n, and increase
>  >>>x^(n-1), we ought to be "ok" for some definition of ok)
>  >>>(binomial adjustment etc from
>  >>>
>  >>>the TCP AIMD with fast retransmit scheme has several motivating factors
>  >>>some intended, some lucky happenstance (serendipitous)...
>  >>>
>  >>>1/ sampling network conditions and eliminating noise:
>  >>>
>  >>>currently, this operates over the RTT timescale, but is memoryless
>  >>>after that....estimates for loss effectively im,plicit in the AIMD
>  >>>operation, but the noise filter (number of dupacks) is somewhat
>  >>>rigid...
>  >>>
>  >>>2/ safe/stable operation:
>  >>>given feedback controller, its reasonable to operate this over
>  >>>packet conservation/self clocking makes it more smooth
>  >>>
>  >>>3/ relating end system rate adjustment timescale to buffering 
> provisioning
>  >>>the AIMD scheme has the bandwidth/delay product wrth of network
>  >>>buffering as a necessary side effect - other adjustment schemes might
>  >>>need less (some might need more but that almost certainly means they
>  >>>are trouble:-)
>  >>>
>  >>>4/ social coupling - we have a target operating point which will be
>  >>>some fraction of a bottleneck link
>  >>>if we take a flow f, and a flux (sum of flows into a bottleneck) F,
>  >>>then the idea is that we get a share proportional to the _resource_ we
>  >>>use, which (approximately) includes 1/RTT as a factor (kelly et al, le
>  >>>boudec et al)  the idea is that a set of fs in an F are coupled by the
>  >>>loss or ECN feedback function, and by some reaction period being at
>  >>>least in the same ballpark....
>  >>>
>  >>>in fact, though we don't have to have smooth functions at all, nor do
>  >>>we have to sample only the average loss rate, nor choose the sample
>  >>>rate to be an RTT - the RTT is a way of _loosely _ coupling things,
>  >>>but is perhaps too strong
>  >>>
>  >>>what if someone wanted a _rate_ that persited for all (or a larger
>  >>>part) of a connection? how could we work out some sort of congestion
>  >>>model that accommodated both packet and connection timescales?
>  >>>
>  >>>at least one factor seems missing, and that is some estimate of the
>  >>>number (and rate of change of number) of flows....if we alter the
>  >>>sample period, and sample bot hte hcongestion feedback Mean, AND its
>  >>>variance, we might be able to (assuming the social coupling function
>  >>>was still "social") estimate this
>  >>>
>  >>>obviosuly if people want to they can behave anti-socially (but that is
>  >>>and wil lalways be true unti lwe do pricing or othewr forms of
>  >>>admission control) - letsassume they behave "nicely"....
>  >>>
>  >>>could someone choose to operate a "very slow" congestion control
>  >>>scheme? why not? lets say i run a connection that takes 1/10 of the
>  >>>capacity, but there are 5 other connections, then why should i react
>  >>>to loss unless my longer term loss (or ecn) rate  tells me that
>  >>>there's now 9+ other flows? currently,  if i run any adjustment
>  >>>scheme based just on average, i have a chance of adjusting wrongly...
>  >>>
>  >>>more importantly, maybe
>  >>>secondly, how about re-examining the social coupling function? why
>  >>>shouldn't ten people _agree_ a different congestion partition function
>  >>>(e.g. they have an application that requires n sources)
>  >>>
>  >>>i guess this could be implemented via the Congestion Manager type API,
>  >>>but i am interested in the general family of functions that fit this
>  >>>more general model - for example, it seems to me that you can have
>  >>>radically different increase/decrease if you have
>  >>>a) a different sample period and a more accurate deascripotion of the
>  >>>evolutuon of the loss/load process over time (e.g. some sort of fancy
>  >>>bayesian predictor)
>  >>>b) a different share/social function - e.g. if we have 10 sources
>  >>>agreeing on a different load, then how do they distribute this
>  >>>information and how do  we make sure they aren't penalized by any
>  >>>extra fancy stuff people might later add!
>  >>>
>  >>>j.
>  >>
>
>  cheers
>
>    jon

- David
--------------------------------------------
WWW Page: http://www.reed.com/dpr.html