Analysis of Increase and Decrease Algorithms for Congestion Avoidance

The authors of this paper analyze algorithms for congestion avoidance using very limited feedback from the global resource--- a single bit sent from the router that indicates whether the network is overloaded or underloaded. Each sender reacts independently (and in a trustworthy manner) with some policy that reflects the goals for the network (such as efficiency, fairness, etc.). In analyzing the potential algorithms, the authors look at policies are reflecting linear space (they do talk a little bit about nonlinear versions, but rightly point out that they may be too complicated); that is, you can add or multiply or do a combination of the two.

The corresponding diagrams on a plane are extremely informative, and intuitively explain some of the conclusions of the paper. For example, the authors advocate additive increases and multiplicative decreases, showing that they converge to optimality in terms of efficiency and fairness. This is because the multiplicative decreases take the network closer to fairness, while the additiveness makes the network more efficient.

Although this paper does not deal with TCP per se (the next one does), the congestion avoidance here is important to study because it was later used to improve TCP's performance, which suffered several meltdowns as the early internet reached higher percentages of capacity.

The paper is essential even just for the graphical explanations of the various congestion avoidance schemes. These help explain the algorithm's relative effectiveness, and, when the algorithm less than ideal, where/why it breaks down. However, the paper does not go into the specifics of what the parameters should be--- this would require some kind of simulation. Still, a specific example that shows behavior for some sets of patterns would be useful. In addition, how are the parameters related to the network parameters (things like bandwidth, latency, number of nodes, etc.)? Even broad relationships between network and optimum congestion avoidance policy would be interesting. Lastly, of course, this requires some sort of global state at the router level in order to send feedback to the endpoints.

Given all of that, I think the essential point of the paper is important to remember: to converge to optimum efficiency and fairness, one should use additive increase and multiplicative decrease.