[e2e] more theory on benefits and handicaps of additive increase

[Sergey Gorinsky]

  Dear colleagues,

  Already six years have passed since I announced on this list about the 
report "Additive Increase Appears Inferior", which stirred some interest 
then. Now, I would like to draw your attention to another report "A Theory 
of Load Adjustments and its Implications for Congestion Control" written 
in collaboration with my students:

     http://www.arl.wustl.edu/~gorinsky/pdf/WUCSE-TR-2006-40.pdf

  The full abstract is at the bottom of this posting but in a nutshell 
the paper extends even further the classical Chiu-Jain analysis of MAIMD 
algorithms (which generalize AIMD via optional inclusion of MI) and 
uncovers some surprises. One particularly counterintuitive result is the 
ability of an MAIMD to provide a faster asymptotic speed of convergence 
to equal individual loads than under a less smooth AIMD (the classical 
metric of smoothness captures the maximal oscillations of the total load 
after it reaches the target). The report also derives other theoretical 
results (e.g., convergence to a unique canonical cycle of oscillations 
and various scalability properties of MAIMD algorithms) and briefly 
discusses practical implications of the theory.

  All your comments are certainly welcome.
  
  Thank you,

    Sergey Gorinsky

    Applied Research Laboratory
    Department of Computer Science and Engineering
    Washington University in St. Louis
________________________________________________________________________
S. Gorinsky, M. Georg, M. Podlesny, and C. Jechlitschek, "A Theory of 
Load Adjustments and its Implications for Congestion Control", Technical 
Report WUCSE-2006-40, Department of Computer Science and Engineering, 
Washington University in St. Louis, August 2006

Abstract:   Multiplicative Increase (MI), Additive Increase (AI), and 
Multiplicative Decrease (MD) are linear adjustments used extensively in 
networking. However, their properties are not fully understood. We 
analyze responsiveness (time for the total load to reach the target 
load), smoothness (maximal size of the total load oscillations after 
reaching the target load), fairing speed (speed of convergence to equal 
individual loads) and scalabilities of MAIMD algorithms, which generalize  
AIMD algorithms via optional inclusion of MI. We prove that an MAIMD can  
provide faster asymptotic fairing than a less smooth AIMD. Furthermore,  
we discover that loads under a specific MAIMD converge from any initial  
state to the same periodic pattern, called a canonical cycle. While  
imperfectly correlated with smoothness, the canonical cycle reliably 
predicts the asymptotic fairing speed. We also show that AIMD algorithms 
offer the best trade-off between smoothness and responsiveness. Then, we 
introduce smoothness-responsiveness diagrams to investigate MAIMD 
scalabilities. Finally, we discuss implications of the theory for the 
practice of congestion control.
________________________________________________________________________