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

[Dina Katabi]

Kelly proves convergence only for a model that assumes no feedback delay 
(sources learn about network congestion immediately). As such his proof 
does not apply to the different RTTs case.

There was recent work that generalizes Kelly's proof of convergence to 
the case where there are different RTTs in the feedback loop, yet the 
proof is only a local proof of convergence (i.e., if the system reaches the 
equilibrium point it stays at it.)


Concerning Low's approach, (to my understanding) it is not a  
generalized form of AMID.

-Dina




On Fri, 8 Jun 2001, Guo, Liang wrote:

> 
> 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
> 
>