Dynamics of Random Early Detection

Dong Lin and Robert Morris

Published in the ACM SIGCOMM 1997 Conference Proceedings.


In this paper, we demonstrate the effectiveness of Random Early Detection (RED) on three different traffic types: greedy, bursty and adaptive. We point out that RED contributes to unfair bandwidth sharing when a mixture of the three traffic types exist at the shared gateway. This unfairness is caused by the fact that RED proportionally drops packets from the competing connections according to their bandwidth usages. We propose Fair Random Early Drop (FRED), a modified version of RED. FRED detects incipient congestion by monitoring the average queue length and decides whether to drop a packet when the running average exceeds a threshold. While connections in RED experience the same packet loss rate, FRED makes different dropping decisions over connections with different bandwidth usages by use of per-active- connection accounting. We show that FRED provides better protections for bursty connections. In addition, FRED is able to isolate ill-behaved greedy traffic more effectively. These improvements are demonstrated by simulations of TCP and UDP traffic. FRED does not make any assumptions on the queueing architecture. The cost of FRED's per-active-connection accounting is only proportional to the total buffer size and is independent of the number of connections.

PostScript, PDF.