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

This paper presents an analytical analysis of congestion avoidance algorithms and proposes an "optimal" algorithm.

The paper assumes that network throughput typically follows the curve shown in the figure on the right. In other words, throughput increases quickly with load until a point when the system is nearly saturated (the knee) after which the increase in throughput is slow and soon afterwards the throughput falls dramatically (the cliff) due to packet loss. Using this model, the authors argue that the optimal algorithm will keep the system at "the knee" to avoid congestion rather than using a back-off algorithm to control congestion after it occurs.

The authors evaluate algorithms on efficiency, fairness, distributedness and convergence. Efficiency refers to how close to the load is to the knee with the assumption that the knee is the optimal operating point. Fairness means that users bottle-necked on the same resource should have an equal share of it. Distributedness means that there is no central control with full system knowledge. Finally, convergence refers to the rate of reaching equilibrium (the knee) and the size of oscillations about the equilibrium point.

Using these criteria the authors determine the key traits of an optimal algorithm. Specifically, one should increase transmission rate additively but decrease it multiplicatively when congestion occurs.

I am not fully convinced that the throughput vs load curve is always of the shape that the authors assume. That being said the mathematical analysis of congestion is very valuable and suggests that currently used policies are probably quite good.