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

[Guo, Liang]

I think both Frank Kelly and Steven Low had some recent results on
this issue (not explicitly on AIMD but a generalized rate/window based
control scheme with the help from (implicit) pricing scheme). I'm not sure
if rate-based schemes can reach the "fairness" line (it depends on how
accurate the round-trip time estimation is done at the end and how
"fairness" is defined), but they will certainly stabilize around the
efficiency line.


On Fri, 8 Jun 2001, Michael Welzl wrote:

> Hi all,
> 
> 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:
> 
> Stability (actually not stability, but convergence to equilibrium which
> oscillates around the optimal point) of AIMD is explained in "Analysis
> of the Increase and Decrease Algorithms for Congestion Avoidance in
> Computer Networks", Dah-Ming Chiu & Raj Jain,
> http://www.cis.ohio-state.edu/~jain/papers.html
> 
> This paper is used as a reference in "Congestion Avoidance and Control"
> and explains the case of synchronous operation (similar RTT's) ONLY. This
> is mentioned explicitely in the "Practical Considerations" / "Further
> Questions" section. They also note that "this topic is currently under
> further study", but I have not found an explanation in any related papers
> by Raj Jain - I read the complete "Congestion Avoidance in Computer
> Networks With A Connectionless Network Layer" suite, "Congestion Control
> in Computer Networks: Issues and Trends", "A timeout based congestion
> control scheme for window flow-controlled-networks". The latter explains
> CUTE, which is mentioned in footnote 2, page 2 of the "Cong. Av. and
> Control"
> paper. It also does not seem to explain why AIMD is still stable in the
> context of heterogeneous RTT's.
> 
> The "Congestion Avoidance and Control" paper mentions AIMD stability based
> on the "Analysis of the Increase and Decrease ..." paper reasoning.
> Additionally, it is mentioned that the flow on a TCP connection should obey
> a "conservation of packets" principle (in equilibrium, do not send a new
> packet into the network unless an old one has left). This works with window
> based flow control, but not with rate based flow control. All other
> reasoning
> about stability in the "congestion avoidance .." paper seems to deal with
> the idea of exponential backoff.
> 
> 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
> 
> 

Guo, Liang 

guol at cs.bu.edu                     Dept. of Comp. Sci., Boston Univ.,
(617)353-5222 (O)                  111 Cummington St., MCS-217,
(617)375-9206 (H)                  Boston, MA 02215