decbit

A Binary Feedback Scheme for Congestion Avoidance in Computer

Networks K.K.Ramakrishnan and Raj Jain, Digital Equipment, 1990

Summary. The authors propose a congestion avoidance scheme in networks with connectionless network layers. The scheme uses minimal feedback (so as to not generate superfluous traffic), converges quickly and is fair. Routers calculate a exponentially weighted running average queue size. If the average queue size is greater than one, than a congestion indication bit is set in the packet header. The ``user'' (which could be either the source or the destination depending on the network architecture) examines the congestion indication bit and, if the bit is set, will increase of decrease its window size.

More Detail

Some terminology. Flow control is the policy used to ensure that the link has sufficient buffers at the destination (selfish). Congestion control is a policy used to coordinate the links in the network so that the congestion doesn't occur (social).

The point at which throughput falls off rapidly is called the cliff and the point at which additional throughput results in rapidly increasing response time the knee. Congestion avoidance attempts to operate the network at the knee whereas congestion control detects the fact that the network has reached the cliff and reducesthe load so that the network can recover.

The authors propose a congestion avoidance scheme. The goals are to

Feedback signal. How is the current condition assessed? The authors .considered two algorithms for feedback signals: simple threshold and hysteresis. "The hysteresis algorithm...indicates congestion when the queue size is increasing and crosses a threshold value, for instance,T2. The feedback signal continues to indicate congfestion as the queue size decreases, till it reaches the smaller threshold value." The idea behind hysteresis is to minimize the on-off signals (which we don't send in this scheme so I don't know why this is considered). Simple threshold is the obvious algorithm: report congestion when above some threshold. Under simulation, they found that the power is maximum when the hysteresis is ``non-existent'' and the threshold value is 1.

Feedback filter. How do we filter the current condition to determine congestion? The authors use an EWRA because it

  1. does not communicate transient effects and

  2. is fair (if we used just the current feedback signal, some users would receive congestion indication and others would not).

When the EWRA is >= 1, the congestion bit is set. Queue size includes the .packet currently in service. The period over which the average is calculated is the regeneration cycle (last busy+idle cycle) plus the current period. The average is the (integral) area under the queue size curve over this interval. They considered using just the previous regeneration cycle but determined that this could cause the filtered output to be inaccurate when the current cycle was long.

Decision policy. Once the feedback signal is filtered at the router and forwarded to the user, there are four aspects to the user's decision policy for determining the window size:

  1. Decision frequency. How often will the window size be updated? If the window size were updated for every packet, oscillation would result. Rather, the window size is updated only after a waiting period has gone by. If Wp is the number of packets sent in the previous cycle and Wc is the number of packets sent in the current cycle, we wiat for (Wp+Wc) packets to be acknowledged. This allows the effects of the update to be reflected and avoids oscillations.

  2. Use of received information. Will the user use all of the information received from the router? The Wp packets will be ignored; only the Wc packets' bits will be examined.

  3. Signal filtering. For simplicity, increase the window size if >50% of the bits are set; decrease otherwise.

  4. Increase/Decrease Algorithms for Window Size. Use +/*. +/+ is unfair. There is a tradeoff between the timeliness of convergence and the quantity of oscillations when setting the d factor for the multiplicative decrease: Small values of d achieve converge more quicly but tend to oscillate more once they reach that point. Authors decided to minimize oscillations: d = .875.

Simulations. A number of simulations were run both to determine the above .details and to determine if the scheme worked. 3 scenarios previously outlined as essential for an acceptable scheme were tested:

All tests produced reasonable behavior. .