Paper review : Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks (CJ89)

Reviewer : Hai Fang (hfang@acm.org)
• Goal

To provide a good control scheme (a.k.a. increase/decrease algorithm) for congestion avoidance.

• Contribution

The authors formulated the congestion problem as system control problems, and mathematically analyzed the performance of possible increase/decrease schemes with respect to the different criteria, from which derived the additive increase/multiplicative decrease algorithm.

• Main ideas

• The key component of any congestion avoidance scheme is the algorithm (or control function) used by the users to increase/decrease their load.
• The key criteria for selecting control are: efficiency, fairness, distributedness, and convergence.
• Under these considerations, a simple additive increase and multiplicative decrease algorithm is the optimal policy.

• Evaluation

• Significance rating: 3
This paper provides a good algorithm for the resource management problem, which is a general problem in the computer networks. (4)
The abstract model that this paper concentrated is still simpler than the practical distributed networks. (-1)

• Convincing rating
The author give a wonderful analysis from the mathematical aspect. Each criteria was characterized as a constraint in the n-dimensional vector space, which denotes the n-user resource allocation status. The author also argued why the non-linear control functions are not feasible for the practice.
On the other side, the author made some assuptions on the abstract model, such as the users only share one bottleneck resource, and they can receive the same binary feedback synchronously.

• Limitation
The main problem related to the increase/decrease algorithm is whether or not the pracitcal networks can provide a synhronized feedback to all users without delay.
Another problem is the tradeoff between the simpleness and the expressiveness of the mathematical model. The binary feedback simplify the math analysis and implementation, whereas it may also lose some useful infomation and control facilities on the other side.

• Conclusion

Mathematical analysis can help us to find the algorithm(s) which fits the problem most under a well-defined abstract model.

9/26/01