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

[Jon Crowcroft]

um, the equations in that paper model a resource cost which in some
senses is equivalent to delay- the joint
optimisation problem is to maximise user share of a resource subject
to maximising utilsiatio nof the network, with the proprotional
max-min fairness element being that no increase in your share of the
resource (path/route) is at the "expense" of another user who shares
the bottleneck on the resource ....sort of

the original solution to stability, btw is generally done by casting
the problem as a control theoretic one, and firing up a z-transform of
the transfer function as a function of time, then showing that the solutions
stays in the unit circul in the complex plane and are thus
stable....van's conservation of packets argument is part of he
constraints on the rtt estimator and noise in the systenm to make sure
that this stays true....several papers in the 90s on tcp-lfriendly sstems use
this approach to show their systems are stable and then seperately
show they are fair to tcp with arguments along the lines of kelly's
(though less sophisticated)

yes, the low work is quite different as far as i can tell ....and not
the same as the ffamily of generalised increase/decrease function
papers we've seen recently...

In message <Pine.SUN.3.91.1010608174345.20840o-100000 at the-way>, Dina Katabi typ
ed:

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

 cheers

   jon