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

[Sergey Gorinsky]

  Hi, Michael.

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

  Recently, Harrick Vin and I addressed this issue in some detail in a paper
entitled "Additive Increase Appears Inferior" (which can be found at
http://www.cs.utexas.edu/users/gorinsky/pubs.html). We examined the AIMD
algorithm in a model where the updates are asynchronous (as would be the
case when the RTTs are not the same). We discovered that AIMD does not
converge to the optimal point in terms of fairness in such a case.
Moreover, the resulting stable range of oscillations was different for
different initial states ("multiple attractors").

  We believe that the deterministic model described in Chiu-Jain's paper
and our extension to it are quite simple. However, I strongly doubt that
making the model more realistic can make AIMD converge to the maxmin-fair
allocation when the updates are asynchronous. One evidence of this is the
well-documented unfairness seen with TCP when the RTTs are different.
However, we do believe that an efficient operating point can be achieved,
and a variety of increase/decrease algorithms will achieve it.

  Sergey