[e2e] (Why) does rate-based AIMD lead to a stable network?

[Frank Kelly]

Michael

I just noticed your question: 

> Having spent some time with some of the older papers on congestion
> avoidance, I found a missing link in the reasoning for network stability
> of AIMD, especially for rate-based end2end congestion control schemes.
> Maybe the link is not missing, but I didn't see it - in this case, a
> literature pointer would be very helpful:
<snip>
> Which leaves me asking: "Given heterogeneous RTT's, is there ANY proof that
> a scheme which does not adhere to the 'conservation of packets' principle
> (e.g. any rate based scheme) and uses AIMD will have the network converge
> to an equilibrium around the optimal point in terms of fairness and
> efficiency?"
>
> Cheers,
> Michael Welzl


Proofs of local stability for rate based AIMD schemes have been given by
R. Johari and D. Tan
http://www.statslab.cam.ac.uk/cgi-bin/resreps.pl?term=2000-2&field=number
L. Massoulie
http://research.microsoft.com/scripts/pubs/view.asp?TR_ID=MSR-TR-2000-111
G. Vinnicombe
http://www-control.eng.cam.ac.uk/Homepage/Papers.html#2000pap

(The early paper by F. Kelly, A. Maulloo and D. Tan 
http://www.statslab.cam.ac.uk/~frank/rate.html
considered heterogeneous feedback delays but got only an 
unsatisfactory "overall" condition - the recent advances listed 
above get a set of much nicer "connection-related" conditions.)

The "conservation of packets" principle, weakened to allow
additive increase, is not enough to ensure local stability: see
S. Floyd and V. Jacobson 
http://www.aciri.org/floyd/abstracts.html#FJ92
and the simplified model of Jacobson's congestion avoidance 
algorithm (leading to eqtn (26)) in
http://www.statslab.cam.ac.uk/~frank/mmi.html

Regards
Frank Kelly
-- 
------------------------------------------
web:    www.statslab.cam.ac.uk/~frank/ 
email:  f.p.kelly at statslab.cam.ac.uk  
------------------------------------------