Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks

This paper explores a class of increase/decrease algorithms that can be used for congestion avoidance schemes and concludes that the additive increase, multiplicative decrease algorithm quickly converges to the key performance metrics: efficiency and fairness. The authors classify both congestion avoidance (operating around the "knee" of the network traffic curve) and congestion control (staying to the left of the "knee") mechanisms as dynamic resource management problems. Congestion avoidance mechanisms specifically increase or decrease the packet output rate in response to the network load. For simplicity, the analysis in this paper is based on the binary feedback model, which assumes a synchronous feedback and control loop. Four general increase/decrease algorithms are presented - MIMD (multiplicative increase/multiplicative decrease), MIAD, AIMD and AIAD - and the criteria to be used to evaluate their effectiveness are also established: efficiency, fairness, distributedness and convergence. Next, the additive increase, multiplicative decrease scheme is graphically shown to converge to the optimal point marked by the intersection of the fairness and efficiency lines. On the other hand, the path traced by the additive increase, additive decrease scheme remains parallel to the fairness line and never converges. The case for an AIMD scheme is further supported by sections with somewhat rigorous algebraic and vector analysis.

I really enjoyed this paper because it provided detailed, technical reasoning behind the choice of the AIMD increase/decrease scheme in TCP transport, something that is taken for granted throughout undergraduate networking. Moreover, there was no inherent bias towards the AIMD scheme - the authors set out to explore all four classes of increase/decrease algorithms and demonstrated exactly why they arrived at this scheme. Even though the authors provided a preview of delayed feedback and asynchronous operation at the end of the paper, an actual effort to incorporate it into the initial analysis would have been interesting. Some of the assumptions that were made may be a little too strong. Overall, very interesting paper and definitely a keeper for the syllabus.