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

Chiu, D. and Jain, R. Analysis of the increase and decrease algorithms for congestion avoidance in computer networks. Comput. Netw. ISDN Syst. 1989

Congestion control mechanisms can be broadly divided into 2 categories, congestion avoidance and congestion recovery. Both of them are aimed at solving the underlying network resource management problem at their heart however with different approaches. The former is a 'preventive' approach where appropriate steps are taken so that the network doesn't reach the congested state in the first palce while the latter is more of a 'responsive' approach which sets into action when the network is already congested. This paper discusses the nuances of the former congestion avoidance approach by taking into account various performance metrics such as efficiency, fairness, convergence time and size of oscillations.

At the heart of the congestion avoidance approach is the 'binary feedback scheme' which kind of acts as a network monitor and sends a binary feedback back to the host (1 if overloaded and 0 if underloaded). Now, when a host comes to know the status of the network through this feedback, it must either increase (in case bit = 0) or decrease (in case bit = 1) its throughput accordingly. Considering a linear change is the new rate (which the author argues is quite simple and sufficient to handle), the new throughput can be given as:

X(t+1) = a + bX(t)

where, a and b can be 'theorectically' positive or negative depending on the increase/decrease. However, when the author took the properties of efficiency, fairness and distributedness into account, the variables a and b pretty much reduced to the condition of b = 1 for increase and  a = 0 for decrease. In other words, it was found that additive increase (X(t+1) = a + X(t)) where a > 0 and multiplicative decrease (X(t+1) = bX(t)) where 0 < b < 1 worked best. At the end, the author also introduced nonlinear controls in a fleeting manner and said that they unnecessarly complicate the task of finding the right scaling factors.

Overall, this paper was a good read because of the simplicity and straightforwardness of its explanations. I loved the way it explained the convergence to efficiency and fairness feasibility conditions through vector graphs! The paper mentions that it considers both under-utilization of network channel and over utilization to be equally wrong and something that the congestion algorithm should tackle accordingly. In spite of the convincing maths and graphs, I somehow find the additive (slow?) increase and multiplicative (faster?) decrease intuitively opposing to the equally wrong consideration. Secondly,  as the author highlights, non-linear controls offer us far more flexibility in reaching equilibrium, however there are obviously performance and complexity trade-offs. It would be really interesting to discuss these trade-offs in class. Furthermore, it would also be great to discuss the behavior of congestion avoidance algorithms in a dynamic environment such as P2P sharing etc. where the hosts join and leave often.