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

Reviewer: Kenneth Chin

The main idea of the paper is to prove that a simple additive increase and multiplicative decrease algorithm satisfies the sufficient conditions for convergence to an efficient and fair state regardless of the starting state of the network.

Dah-Ming Chiu and Raj Jain used a selective-and-restriction-approach in the sense that they selected a subset of feasible controls from a set of linear controls. Then from that subset, they selected a subset that satisfies the distributedness criterion. After that, they further narrow down to a subset that satisfies the efficiency and fairness convergence. Furthermore, they tried to find a set of controls that optimize the responsiveness and smoothness criteria.

The followings are the contributions from this paper:
  1. a control avoidance algorithm should have 4 basic proprieties:
    1. efficiency
    2. fairness
    3. distributedness
    4. convergence
  2. in order to satisfy the requirements of distributed convergence to efficiency and fairness without truncation, the linear decrease policy should be multiplicative, and the linear increase policy should always have an additive component, and optionally it may have a multiplicative component with the coefficient no less than one.
  3. for the linear controls with truncation, the increase and decrease policies can each have both additive and multiplicative components, satisfying the constraints in Equations (16) and (15) in the paper.
  4. for both feasibility and optimal convergence to fairness, the increase policy should be additive and the decrease policy should be multiplicative.

After reading the paper, I think it is a moderate paper. Although it attempts to prove the additive increase / multiplicative decrease control is the best of a distributed network, the network that is in experiment is largely different from the real network. For example, it assumes that all users sharing the same bottleneck will receive the same feedback, and that the feedback and control loop for all users is synchronous. However, in a real network, the feedback can be delayed or even lost, the number of users are varying all the time, etc. All these practical issues are opposing to the theoretical model used in the paper.

This paper has a grade of 3 because it does not take care of the real network, but it does a good job in giving a solid theoretical idea on how a congestion avoidance algorithm should be.

The most important thing I take out from this paper is the vector representation of a two-user case. It clearly shows how additive/mulitplicative increase/decrease affects the load of the two users accordingly.