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

[Michael Welzl]

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