Random Early Detection Gateways

This describes a queue discipline that gives better congestion signals to TCP flows than Drop Tail and slight refinements on Drop Tail like Early Random Drop. The authors observe that a problem with Drop Tail and Early Random Drop is that they both only act when the queue is near-full, thereby discriminating against bursty flows and causing global synchronization. To avoid this, this scheme (RED) tracks a long-term average queue size and ‘marks’ (drop for TCP) packets according to this size such that marks are distributed approximately evenly over time. The authors evaluate their scheme with multiple TCP flows with different round-trip times going over a bottleneck link, and show that it avoids global synchronization and achieves fairness among bursty flows (in their example, TCP flows over a high-bandwidth delay product relative to their window size).

The oddest omission from this paper to me was packet sizes: The algorithm and the simulations work in terms of whole packets apparently without considering the size of packets. This is particularly odd given that one might expect bursty interactive flows to have variable packet sizes.

This paper does remarkably simplify its problem by assuming that all flows are running a congestion control algorithm, as this scheme does not converge to fairness in the phase of loss-agnostic flows (which the authors did not test). The authors propose sampling dropped packet, showing that a window of dropped packets is likely to have close to the expected number (based on actual) of dropped packets from each flow; however, the authors don't evaluate this scheme beyond this theoretical observation.