Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Network
Reviewer: Jie Zhou
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.
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.
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.
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.
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
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?