Random Early Detection Gateways for Congestion Avoidance; Floyd & Jacobson

This paper describes the Random Early Detection (RED) scheme to detect congestion in gateways. To attain low latency and high throughput, RED attempts to keep the average queue length short while still permitting larger instantaneous queue sizes. It also strives to prevent global synchronization in which multiple connections decrease their window size and resume slow start at one time.

It uses an underlying FIFO and keeps track of the average queue size with a weighted average. It also has minimum and maximum thresholds such that when the average queue size is less than the minimum, packets are free to pass through without interference. When the average queue size is greater than the maximum threshold, every incoming packet is marked (and presumably dropped). In between the minimum and maximum threshold lengths, packets are marked probabilistically based on their associated connection's share of bandwidth. RED can handle bias and burstiness because its average queue length can be weighted higher to give recent traffic more importance or weighted lower to allow bursts of traffic.

RED uses a uniform probability distribution to decide which packets to be marked in the situations when the average queue size is between the min and max. The marking of packets pays no heed to which connections are being marked, though presumably the number of dropped packets per connection should reflect the connection's sent packets; this idea fails to control misbehaving users in the case of RED simply marking and not dropping the packets, as the congestion control is then left up to the ends.

Additionally, RED's reducing traffic by dropping packets relies on the use of TCP, or at least some protocol in which the source realizes a packet was dropped. Furthermore, the size of the packet isn't taken into account, which could potentially lead to a situation in which lots of small packets are dropped but there's still a large number of bytes to be pushed across a link. In general, RED laid out a good, flexible framework that respects different types of traffic and attempts to prevent global synchs and dropping of all packets at a gateway, but it has a number of issues that need to be resolved.