Random Early Detection Gateways for Congestion Avoidance

Summary

This paper describes a method of notifying senders of upcoming congestion before it occurs. The method has the key benefits of being compatible with TCP and not requiring all gateways to use the same congestion control mechanism. This makes it a pragmatic choice, requiring fewer changes than "Congestion Control for High Bandwidth-Delay Product Networks."

The RED algorithm uses the average queue size to detect upcoming congestion. If the queue size is greater than a minimum threshold, packets form each connection may be marked with a congestion bit with some probability. This probability is proportional to he connection's share of the bandwidth at the gateway, thus the RED algorithm addresses both congestion and fairness.

Traditionally, TCP congestion control waits until the queue is full and then drops all packets. This has two negative consequences: dropped packets must be resent and all connections with dropped packets must slowly ramp up again. The RED algorithm addresses these issues by preemptively marking some connections as congested.

Overall, RED helps prevent congestion and keep delay low while being easy to implement on top of TCP.

Thoughts

RED still uses a binary signal for congestion in the same way as traditional TCP congestion control. It is less precise than the algorithm presented in "Congestion Control for High Bandwidth-Delay Product Networks" which allows routers to explicitly control the sender's congestion window. However, RED seems much easier to implement since it can work with TCP and current routers. It would be interesting to see how these two algorithms compare in efficiency and fairness.