In "Random Early Detection Gateways for Congestion Avoidance", Sally Floyd
and Van Jacobson describe a mechanism to keep gateway queue sizes down (and
thus delay as well) while maintaining good throughput.
The RED algorithm is designed to work well with TCP, as it works by
semi-randomly choosing packets to drop at a gateway, thus signaling
the sending TCP that "congestion" exists, causing it to perform
congestion control procedures.
The algorithm described here is distinguished from a few other alternative
algorithms, including DECbit, Early Random Drop, and Drop Tail. It is
clearly important in any of these schemes to avoid introducing synchronization
by causing a number of connections to enter congestion control, then
building back up, essentially resulting in a traffic oscillation. The
random element of RED is designed to avoid this synchronization behavior.
An interesting characteristic of the RED algorithm versus the others is
the RED's lack of bias towards bursty traffic. This is done by keeping
a particular connection's congestion notifications (packet drops) roughly
proportional to that connection's share of the bandwidth.
The data collected and analyzed via simulation of network behavior seems to
support the authors' conclusion that RED is a fairer congestion notification
alternative than the others presented, and that it supports a higher ultimate
throughput as well.
As Van Jacobson devised many of the TCP congestion control algorithms that
the RED mechanism would exploit, the algorithm certainly would merit
further implementation and study.