Random early detection
≈ 3 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
Random early detection (RED), also known as random early discard or random early drop, is a queuing discipline for a network scheduler suited for congestion avoidance. In the conventional tail drop algorithm, a router or other network component buffers as many packets as it can, and simply drops the ones it cannot buffer. If buffers are constantly full, the network is congested. Tail drop distributes buffer space unfairly among traffic flows. Tail drop can also lead to TCP global synchronization as all TCP connections "hold back" simultaneously, and then step forward simultaneously. Networks become under-utilized and flooded—alternately, in waves. RED addresses these issues by pre-emptively dropping packets before the buffer becomes completely full. It uses predictive models to decide which packets to drop. It was invented in the early 1990s by Sally Floyd and Van Jacobson.
Random early detection (RED), also known as random early discard or random early drop, is a queuing discipline for a network scheduler suited for congestion avoidance. In the conventional tail drop algorithm, a router or other network component buffers as many packets as it can, and simply drops the ones it cannot buffer. If buffers are constantly full, the network is congested. Tail drop distributes buffer space unfairly among traffic flows. Tail drop can also lead to TCP global synchronization as all TCP connections "hold back" simultaneously, and then step forward simultaneously. Networks become under-utilized and flooded—alternately, in waves. RED addresses these issues by pre-emptively dropping packets before the buffer becomes completely full. It uses predictive models to decide which packets to drop. It was invented in the early 1990s by Sally Floyd and Van Jacobson.
WRED
In weighted RED you can have different probabilities for different priorities (IP precedence, DSCP) and/or queues.
ARED
The adaptive RED or active RED (ARED) algorithm infers whether to make RED more or less aggressive based on the observation of the average queue length. If the average queue length oscillates around min threshold then early detection is too aggressive. On the other hand, if the average queue length oscillates around max threshold then early detection is being too conservative. The algorithm changes the probability according to how aggressively it senses it has been discarding traffic. See Srikant for an in-depth account on these techniques and their analysis.
RRED
Robust random early detection (RRED) algorithm was proposed to improve the TCP throughput against Denial-of-Service (DoS) attacks, particularly Low-rate Denial-of-Service (LDoS) attacks. Experiments have confirmed that the existing RED-like algorithms are notably vulnerable under Low-rate Denial-of-Service (LDoS) attacks due to the oscillating TCP queue size caused by the attacks. RRED algorithm can significantly improve the performance of TCP under Low-rate Denial-of-Service attacks.
See also
Blue (queue management algorithm) Active queue management
References
External links
RED (Random Early Detection) Queue Management. Author: Sally Floyd Guduz – A Simple Random Early Detection (RED) Simulator Variants of RED . Author: Hei Xiao Jun Recent Publications in Random Early Detection (RED) schemes
Text derived from https://en.wikipedia.org/w/index.php?oldid=1192615738 under CC BY-SA 4.0; modifications have been made.