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

This paper analyzes increase/decrease algorithms for congestion avoidance. Early in the paper, a key distinction is made between congestion control, which tries to prevent the network from entering a congested state, and congestion avoidance, which tries to keep the network around the "knee", or "sweet spot", before throughput saturates and response time increases with increasing load. Increase/decrease algorithms are ones where users increase/decrease their load in response to feedback from the network resource. In the paper, the authors focus on binary feedback (overloaded/underloaded), and look at linear control for the most part.

Through the use of efficiency, fairness and distributedness criterions (and lack of global knowledge), the authors show algebraically that the increase stage must have an additive component greater than 0, and multiplicative component of at least 1, and the decrease stage must have an additive component of 0, and multiplicative component at least 0 and less than 1. The actual parameters can be chosen based on convergence criterion, and essentially lead to an additive increase and multiplicative decrease. It is also nice to see that there is an algebraic trade-off between responsiveness and smoothness - something that is to be expected.

What I liked a lot about this paper was the use of the vector diagrams to demonstrate the criterions, and to give intuition about how different linear increase/decrease algorithms would behave with respect to those criterion. The paper was very well-written and easy to read, and very quickly describes the problem at hand, narrows the scope, and deliver the punchlines effectively. There were no surprises along the way.

I think this paper provides a convincing argument as to why the additive-increase/multiplicativ-decrease is the best choice for congestion avoidance. The scheme is simple to implement, is distributed among hosts, requires low-rate feedback that is easily generated by network resources, and yet is provably shown to satisfy efficiency and fairness criterion (albeit ones chosen by the authors) while achieving optimal (?) convergence, at least among linear increase/decrease control algorithms.

Issues that were not discussed is how to identify the knee point, which would be necessary in generating the binary feedback. This could be a straightforward thing to do, but it is not clear to me. The efficiency criterion is closely related to this knee point, and if this knee point is not chosen correctly, than being overloaded would be extremely disastrous.

Because the scheme is so devastingly simple, it could have the effect of closing off research on congestion avoidance schemes, since even if another scheme could be shown to perform better, it would probably not be simpler to implement in practice. On the other hand, an possible weakness seems to be the assumption of compliance and cooperativeness. What would happen if a host cheats and continues to increase load even as it knows (from feedback) that others would decrease their load? Would there be another congestion avoidance scheme that could punish non-compliant hosts?