Random early detection


Random early detection

Random early detection (RED), also known as random early discard or random early drop is an active queue management algorithm. It is also a congestion avoidance algorithm. [cite journal | last = Floyd | first = Sally | coauthors = Jacobson, Van | title = Random Early Detection (RED) gateways for Congestion Avoidance | url = http://www.icir.org/floyd/papers/red/red.html | journal = IEEE/ACM Transactions on Networking | volume = 1 | issue = 4 | year = 1993 | month = August | accessdate = 2008-03-16 | pages = 397–413 | doi = 10.1109/90.251892]

In the traditional 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 by turns. RED addresses these issues.

It monitors the average queue size and drops (or marks when used in conjunction with ECN) packets based on statistical probabilities. If the buffer is almost empty, all incoming packets are accepted. As the queue grows, the probability for dropping an incoming packet grows too. When the buffer is full, the probability has reached 1 and all incoming packets are dropped.

RED is considered more fair than tail drop. The more a host transmits, the more likely it is that its packets are dropped. Early detection helps avoid global synchronization.

RED makes Quality of Service (QoS) differentiation impossible. Weighted RED (WRED) and RED In/Out (RIO) provide early detection with some QoS considerations.

Other Variants

In Weighted RED you can have different probabilities for different priorities (IP precedence, DSCP) and/or queues.

The Adaptive / Active RED (ARED) algorithm [cite paper | first = Sally | last = Floyd | coauthors = Gummadi, Ramakrishna; Shenker, Scott | title = Adaptive RED: An Algorithm for Increasing the Robustness of RED's Active Queue Management | url = http://citeseer.ist.psu.edu/floyd01adaptive.html | date = 2001-08-01 | accessdate = 2008-03-16] 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 aggressive it senses it has been discarding traffic.

See Srikant [cite book | last = Srikant | first = Rayadurgam | url = http://www.springer.com/birkhauser/mathematics/book/978-0-8176-3227-4 | title = The Mathematics of Internet Congestion Control | publisher = Birkhäuser | location = Boston, MA, USA | year = 2004 | isbn = 978-0-8176-3227-4 ] for an in-depth account on these techniques and their analysis.

Notes and references

External links

* [http://www.icir.org/floyd/red.html The RED web page]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Random early detection — (RED), auch bekannt als Random early discard oder Random early drop ist ein Verfahren zum aktiven Warteschlangenmanagement in der Netzwerktechnologie und damit auch ein …   Deutsch Wikipedia

  • Random Early Detection — Die Artikel Überlastkontrolle, Network congestion avoidance und Random early detection überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zu vereinigen. Beteilige dich dazu an der Diskussion über diese… …   Deutsch Wikipedia

  • Random early detection — Для термина «RED» см. другие значения. Random early detection (RED) (Произвольное Раннее Обнаружение)  один из алгоритмов AQM для управления переполнением очередей маршрутизаторов …   Википедия

  • Weighted random early detection — (WRED) is a queue management algorithm with congestion avoidance capabilities. It is an extension to Random early detection (RED) where different queues may have different buffer occupation thresholds before random dropping starts, as well as… …   Wikipedia

  • Weighted random early detection — (WRED) /Взвешенное Произвольное Раннее Обнаружение/  один из алгоритмов AQM для управления переполнением очередей маршрутизаторов, с возможностями предотвращения перегрузок. Общие положения Оно является расширением Random early detection… …   Википедия

  • Random early discard — Die Artikel Überlastkontrolle, Network congestion avoidance und Random early detection überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zu vereinigen. Beteilige dich dazu an der Diskussion über diese… …   Deutsch Wikipedia

  • Random early drop — Die Artikel Überlastkontrolle, Network congestion avoidance und Random early detection überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zu vereinigen. Beteilige dich dazu an der Diskussion über diese… …   Deutsch Wikipedia

  • Random number generator attack — The security of cryptographic systems depends on some secret data that is known to authorized persons but unknown and unpredictable to others. To achieve this unpredictability, some randomization is typically employed. Modern cryptographic… …   Wikipedia

  • Dynamic random-access memory — DRAM redirects here. For other uses, see Dram (disambiguation). Computer memory types Volatile RAM DRAM (e.g., DDR SDRAM) SRAM In development T RAM Z RAM TTRAM Historical Delay line memory Selectron tube Williams tube …   Wikipedia

  • Cycle detection — This article is about iterated functions. For another use, see Cycle detection (graph theory). In computer science, cycle detection is the algorithmic problem of finding a cycle in a sequence of iterated function values. For any function ƒ that… …   Wikipedia


We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.