Readings for Lecture Sep 9, 2008

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

The co-existence of new technologies like Local Network Area (LANs) and fiber optic LANs and old technologies with low bandwidth like the twisted pair resulted in the discrepancy in the arrival and service rates in the intermediate nodes in the network causing increasing queue and congestions.

To allow networks to operate in the optimal region of low delay and high throughput, congestion avoidance is needed to prevent networks from being congested. As the load increases, the throughput increases. After the load reaches the network capacity, the throughput will stop increasing. If the load continues to increase further, the queues start to build up and this potentially results in packet being dropped. One of the congestion avoidance schemes is “binary feedback scheme” with increase/decrease algorithms can be used to address the problem.

The criteria for selecting control are efficiency, fairness, distributedness, and convergence. The efficiency of resource usage is the closeness of the total load on the resource to its knee, Xknee = Σxi(t). Users should be given the same amount of resource if they belong to the same equivalent class. They should be treated fairly by using some fairness index such as: F(x) = (Σx¬i)2/n( Σxi2). The control scheme should be distributed instead of being centralized. The system should be relatively stable, this means that the control scheme should converge, not really to a steady state but it should reach an “equilibrium”.

For the linear control: xi(t + 1) = aI + bIxi(t) if y(t) = 0 => Increase; xi(t + 1) = aD + bDxi(t) if y(t) = 0 => Decrease. With different assignments to aI, bI, aD, bD, we have different control functions. With different criteria for selecting control, we obtain constraints for aI, bI, aD, bD and thus, we establish the feasible control region. The time to converge is disproportionate with respect to the oscillation size for the efficiency criterion. For optimal convergence, the policy should be additive increase and multiplicative decrease.

The problem in the paper is very abstracted. To apply the results to practice, many other issues need to take into consideration such as the resource allocations must be integral and thus, simple rounding off to the nearest integer may cause violation of convergence criteria. Additionally, the scales and parameters in the papers are not easily gathered automatically and often require human help to configure and so the algorithm is more vulnerable to human error.
The paper has not discuss the affect of delayed feedback to the control and seemingly, it assumes that the communication time is zero. Further extension from “binary” feedback to multi-valued feedback would help in describing the exact state of the receivers. The paper also assumes that the number of users stays the same during time and all users start from initial state and follow the same phases of computation and feedback.

Congestion Avoidance and Control

Starting from a sudden factor-of-thousand drop in bandwidth, the authors try to investigate why things had gotten so bad. The principle of “conversation of packet” is that, when a connection in equilibrium, a new packet is not put into the network until old packet leaves. The physics of flow predicts that systems with this property should be robust in the face of congestion.

However, from observation of the Internet, this was not particularly robust. The reasons for this failure would be: connection does not reach equilibrium, or a sender injects a new packet before an old on has exited, or the equilibrium can’t be reached because of resource limits along the path.

To help connection reach equilibrium, a slow start scheme is used. Each connection will have a congestion window, cwnd. Whenever starting or restarting after a loss, set cwnd to one packet. Each acknowledgment for new data, increase cwnd by one packet. When sending, send the minimum of the receiver’s advertised window and cwnd.

The second problem is originated from neglecting the variation of the round trip time R since R would increase quickly with load. Thus, the retransmit timeout interval, RTO, has to be estimate accurately from updated R.

Congestion avoidance scheme is used to adapt the connection to a path. The strategy employs additive increase / multiplicative decrease policy: on any timeout, set cwnd to half the current window size; on each acknowledge, increase cwnd by 1/cwnd; when sending, send the minimum of the receiver’s advertised window and cwnd. This strategy can be easily mistaken with slow start scheme, however actually, congestion avoidance scheme will set the start threshold for the slow start, otherwise, the cwnd will increase unbounded.

The paper deals with algorithm for endpoints, which is not really relevant if the two endpoints are farther away from each other. The algorithm should be extended for gateway congestion avoidance. This could be difficult since each gateway often has many different flows.