Random Early Detection (RED)
RED is the first and most widely used Active Queue Management (AQM)
mechanism. The basic idea is this: a route controlled by RED samples its occupation (queue size) over time, and computes a characteristic (often a decaying average such as an Exponentially Weighted Moving Average (EWMA), although several researchers propose that using the instantaneous queue length works better). This sampled queue length is then used to compute the loss probability for an incoming packet, according to a pre-defined profile
. The decision whether to drop an incoming packet is performed using a random number and the drop probability. In this way, a point of (light) congestion in the network can run with a short queue, which is beneficial for applications because it keeps one-way delay
and round-trip time
low. When the congested link is shared by only a few TCP
streams, RED also prevents synchronization effects that cause degradation of throughput.
Although RED is widely implemented in networking equipment, it is usually "off by default", and not often activated by operators. One reason is that it has various parameters (queue thresholds, EWMA parameters etc.) that need to be configured, and finding good values for these parameters is considered as something of a black art. Also, a huge number of research papers have been published that point out shortcomings of RED in particular scenarios, which discourages network operators from using it. Unfortunately, none of the many alternatives to RED that have been proposed in these publications, such as EXPRED, REM, or BLUE,
has gained any more traction.
activity has rekindled interest in queue-management strategies, and Kathleen Nichols and Van Jacobson, who have a long history of doing research on practical AQM algorithms, have published CoDel
in 2012, which claims to improve upon RED in several key points using a fresh approach.
- 2005-01-07 - 2012-07-12