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

This paper evaluates various options for linear control functions for preventing congestion in a computer network and demonstrates that an additive increase, multiplicative decrease (AIMD) algorithm is optimal. The paper is very interesting to read because it illustrates the concepts using very intuitive graphs - first a graph of the effects of load on throughput and latency in a network, and second a set of graphs showing how the allocations of two hosts change with respect to fairness and efficiency under various control functions. These graphs show intuitively how AIMD converges to both efficiency and fairness and how its step size decreases, leading hopefully to stability. However, in addition to the graphs, the authors mathematically derive the conditions required for correctness, and then for optimal convergence and stability. A key part of this is done using Jain's fairness metric [6], which is a simple score from 0 to 1 with nice properties, such as being scale-independent and being equal to k/n if k out of n hosts receive service. Finally, the paper talks about nonlinear control functions as well, but explains that they may be overly sensitive to system parameters because they will require multiple scaling factors to be set together in order to move along the correct directions for convergence.

This paper is a great example of how mathematics can support the design of network algorithms, by giving an extra source of confidence to heuristics that seem to work well in practice and telling us right away when some heuristics should be avoided. Of course, this paper is almost entirely mathematical, and a good system paper should include at least a simulation too, if not an evalulation of a real implementation. (The standard seems to have gone up towards real implementations over time.) Because this paper was written after AIMD schemes had been proposed, it seems to aim only to justify the existing schemes, provide a language for discussing congestion avoidance, and warn against some flawed control functions.

One flaw of this paper is that it only considers fairness and efficiency over a single link, and does not discuss what happens in a more complex network. In a full network, different links may be bottlenecks for different flows, and fairness is harder to define. A larger network also has more delay in receiving congestion feedback (not that delay isn't high anyway if we use dropped packets as the signal like TCP does), so it motivates looking into the stability of the scheme over longer periods of time as well.