=head1 A Binary Feedback Scheme for Congestion Avoidance in Computer Networks K.K.Ramakrishnan and Raj Jain, Digital Equipment, 1990 B The authors propose a I 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 I queue size. If the average queue size is greater than one, than a I 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. =head1 More Detail B I is the policy used to ensure that the link has sufficient buffers at the destination B<(selfish)>. I is a policy used to coordinate the links in the network so that the congestion doesn't occur B<(social)>. The point at which throughput falls off rapidly is called the I and the point at which additional throughput results in rapidly increasing response time the I. I attempts to operate the network at the knee whereas I 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 =over 4 =item * Operate efficiently. Efficiency is a function of the I. Power is throughput/responseTime. =item * Operate fairly. =back B. 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. B How do we filter the current condition to determine congestion? The authors use an EWRA because it =over 4 =item 1) does not communicate transient effects and =item 2) is fair (if we used just the current feedback signal, some users would receive congestion indication and others would not). =back 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 I (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. B 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: =over 4 =item 1) B 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. =item 2) B 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. =item 3) B For simplicity, increase the window size if >50% of the bits are set; decrease otherwise. =item 4) B Use +/*. +/+ is unfair. There is a tradeoff between the timeliness of convergence and the quantity of oscillations when setting the I factor for the multiplicative decrease: Small values of I achieve converge more quicly but tend to oscillate more once they reach that point. Authors decided to minimize oscillations: I = .875. =back B 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: =over 4 =item * new user introduced =item * bottleneck introduced =item * packet sizes randomly distributed =back All tests produced reasonable behavior.