[Iccrg] Meeting agenda (really! :-) )

[Lachlan Andrew]

Greetings Bob,

On 11/10/06, Bob Briscoe <rbriscoe at jungle.bt.co.uk> wrote:
>
> 1/ I have a paper that
> deconstructs the dominant understanding of
> fairness used in congestion control

That sounds fascinating, and I look forward to hearing about it.

> 2/ We may also have work presentable by Feb on what per datagram congestion
> 'signalling' bandwidth is necessary for hi speed congestion control as flow
> rates increase. What do I mean by signalling bandwidth? As an example,
> packet discard or ECN gives 1 bit per packet of signalling bandwidth. FAST
> claims to use congestion loss to give multibit feedback per packet, but we
> aim to quantify what 'multibit' means in this case, and why you get less
> signalling bandwidth per packet from measuring congestion delay as link
> speeds increase. The aim is to quantify at what point congestion
> delay-based approaches would get less than 1 bit per packet signalling
> bandwidth

That also sounds very interesting.  Do you have link to a draft of
that?  Information theory suggests that you get something like  log(1+
delay / jitter)  [adjusted for jitter not being i.i.d. Gaussian...].
Is that the principle you use?

One thing to note is that the 1 bit you get from dropping or ECN has
to be used carefully or it also degrates at high bandwidths.  In
particular, if you use normal AIMD, then the information you get per
congestion epoch is the number of packets in that epoch.  That is, you
get  O(log(N)/N)  bits of ECN information per packet if the TCP epoch
length is  N.  (Even if you are not using AIMD yourself, if someone
else uses the same ECN marks and does use AIMD, then you are limited
to marking one every  N  packets.)

Using packet drops instead of ECN gives about  p log(1/p)  bits per
packet if the link utilisation is to be at least  1-p on links
upstream of the bottleneck,  which is again very much less than 1
unless the utilisation is allowed to drop to 50%.

It would be very interesting to quantify when delay-based signalling
gives less than loss-based signalling, rather than when it gives less
than 1 bit per packet.

You might be interested in some non-AIMD ECN schemes.  In principle,
schemes like that of Thommes and Coates
<http://www.tsp.ece.mcgill.ca/Networks/projects/pdf/thommes_ACMTN06.pdf>
can actually give O(1) bit per packet.

That scheme is very sensitive to a particular quantisation parameter,
but we have a related scheme
<http://netlab.caltech.edu/~lachlan/abstract/ADPM_CL.pdf>,
<http://netlab.caltech.edu/~lachlan/abstract/ADPM_Allerton06.pdf>
which scales nicely to give information faster when the congestion
level changes faster.

It still only gives  O(log(k)/k)  bits per packet, but that "k" is
adapted to the time-scale of changes in congestion level, rather than
some epoch length.  If the congestion level changes slowly, you don't
need much information per packet, but if it changes quickly, this
scheme gives up to 1 bit per packet.  More importantly, the marking
uses the ECN bits   without   interfering with the way TCP uses those
bits.

Cheers,
Lachlan

-- 
Lachlan Andrew  Dept of Computer Science, Caltech
1200 E California Blvd, Mail Code 256-80, Pasadena CA 91125, USA
Phone: +1 (626) 395-8820    Fax: +1 (626) 568-3603