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

Reviewer: Jie Zhou

Problem

Congestion avoidance is a kind of mechanism which prevents the network from becoming congested. The key component of any congestion avoidance scheme is the algorithm used by users to increase or decrease their load. An important issue is what algorithm should we choose.

Contribution

The paper explores the user increase/decrease policy under the constraint that the feedback from the system is limited to a single bit. It formulates a set of conditions that any increase/decrease policy should satisfy to ensure convergence to efficient and fair state in a distributed manner.

Main Ideas

  • For linear control without truncation, the decrease policy should be multiplicative, and the increase policy should always have an additive component and optionally it may have a multiplicative component with the coefficient no less than one.
  • For the linear controls with truncation, the increase and decrease policies can each have tbth additive and multiplicative components, satisfying the constrants in two equations.
  • Nonlinear control policies are not suitable for practice, because they are too sensitive to system parameters.

    Critique

    The paper provides the theorectical basis for the additive increase with multiplicative decrease policy which is chosen for the congestion avoidance scheme recommended for Digital Networking Architecture and OSI Transport Class 4 Networks. I rate its significance at 4 (significant contribution)

    The author provides complete mathematical proof for the proposed constraint conditions. Logically, the paper is very convincing. But it is based on the assumption that all users are runing in a sychronous mode. This is not realistic for current Internet. So, had not I known the practical result of the proposed algorithm that is used in current TCP, I would doubt its credibility.

    Lessons:

  • One general principle in choosing an algorithm in a general architecture is to be independent of hardware and software scales or parameters as much as possible.

    Open Questions

    The author leaves four further questions:
  • How does delayed feedback affect theo control?
  • What is the marginal utility of increased bits of feedback?
  • Is it worthwhile to guess the current number of user n?
  • What is the impact of asynchronous operation?