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

Dina Katabi dina at ai.mit.edu
Fri Jun 8 14:56:13 PDT 2001

```No, I am not referring to the effect of noise or error.

Kelly's proof of convergence that I have seen doesn't take into
consideration the feedback delay in the system. The differential
equations and the Lyapunov function used to prove the convergence do not
have any delay model.

Recently there were attempts to address the delays in the feedback loops
but all of the proves that I know about are for local stability. You can
take a look at:

"End-to-End Congestion Control for the Internet: Delays and Stability" by
Johari and Tan (Kelly's students)

"Stability of Distributed Congestion Control" by Massoulie.

-Dina

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

>
> Correct me if I'm wrong. What I understood from Kelly's results
> is as far as the product of the incremental factor (the step size)
> and the round trip time delay satisfies certain conditions,
> the system is going to converge to some point. Of course it
> relys on accurate marking of the incoming packets at the
> intermediate routers. Maybe what you meant is what if the
> marking had some errors (noises). Otherwise, I think Kelly's
> results did considered time-lags.
>
> On Fri, 8 Jun 2001, Dina Katabi wrote:
>
> >
> >
> >
> > 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
> > >
> > >
> >
>
> 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
>
>

```