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

Frank Kelly F.P.Kelly at statslab.cam.ac.uk
Sun Jun 10 09:23:14 PDT 2001


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:
> 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
L. Massoulie
G. Vinnicombe

(The early paper by F. Kelly, A. Maulloo and D. Tan 
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 
and the simplified model of Jacobson's congestion avoidance 
algorithm (leading to eqtn (26)) in

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

More information about the end2end-interest mailing list