Random Early Detection Gateways for Congestion Avoidance

 S. Floyd, V. Jacobson, "Random Early Detection Gateways for Congestion Avoidance," IEEE/ACM Transactions on Networking, (August 1993).

This paper talks about the Random Early Detection (RED) gateways for congestion avoidance. The underlying idea is that the gateway drops or marks each arriving packet with a probability that is a function of the average queue size and is proportional to the connection's bandwidth share . The main advantages of RED gateways are:

• No bias against bursty traffic
• Avoids global synchronization
• Gradual deployment  is possible in the current Internet

 The paper started off by discussing some early work on congestion avoidance gateways namely Early Drop Gateways (which being a drop-tail gateway resulted in global synchronization and had biased against bursty traffic) and Early Random Drop gateways (whcih were not successful in controlling misbehaving users). Many of the early congestion avoidance schemes focused on instantaneous queue lengths and not on average queue lengths which obviously created a bias against bursty traffic or traffic with high bandwidth-delay product.

The design of the RED algorithm was pretty neat in the way that it dealt with average queue length which was calculated as (1-w)*avg + w*q. Here q was the instantaneous queue size and w was the queue weight which in a way helped in smoothing out the average by making it dependent on the previous calcualted average and the current queue length. The advantage of this was that the momentary changes in queue lengths due to traffic bursts didn't change the average queue length by a huge amount (thereby not resulting in dropping/marking packets).  The authors backed up their algorithm with adequate simulation which confirmed their results.
 
Overall, this paper was pretty clean in its presentation and put forth its point in a clear manner. However, I felt that it had quite a lot of parameters to  manipulate such as  w (queue weight),  the max/min thresholds, the maximum probability and not enough guidelines were given for determining their values. I personally was quite curious to see how various values of w (queue weight) affect the average queue length (and hence the throughput). Moreover, all the simulations assumed equal packet sizes.  As shown, in case of variable packet sizes, the probability of dropping would have been p = p*(packet size)/(max packet size). It would have been interesting to see the overhead of this operation as unlike other operations which involved bit shifting and addition, this operation would have considerably affected the computation time on the gateway. Moreover, it would be really interesting to discuss as to how successful was RED eventually and how does it stand in the current scenario (when bursty and high bandwidth-delay product traffic has increased a lot in the Internet).