Editing Random early detection

{{Short description|Algorithm}}
[[Image:Random Early Detection algorithm en.svg|right|519px]]
'''Random early detection''' ('''RED'''), also known as '''random early discard''' or '''random early drop''', is a [[Active Queue Management|queuing discipline]] for a [[network scheduler]] suited for [[network congestion avoidance|congestion avoidance]].<ref>{{cite journal | last = Floyd | first = Sally |author2=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 |date=August 1993 | accessdate = 2008-03-16 | pages = 397–413 | doi = 10.1109/90.251892| citeseerx = 10.1.1.147.3833 | s2cid = 221977646 }}</ref>

In the conventional [[tail drop]] algorithm, a [[router (computing)|router]] or other [[Computer networking device|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 [[Network congestion|congested]]. Tail drop distributes buffer space unfairly among traffic flows. Tail drop can also lead to [[TCP global synchronization]] as all [[Transmission Control Protocol|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]].<ref>{{Cite news|url=https://www.nytimes.com/2019/09/04/science/sally-floyd-dead.html|title=Sally Floyd, Who Helped Things Run Smoothly Online, Dies at 69|first=Katie|last=Hafner|newspaper=The New York Times |date=September 4, 2019}}</ref>

== Operation ==
RED monitors the average queue size and drops (or marks when used in conjunction with [[Explicit Congestion Notification|ECN]]) packets based on statistical [[Probability|probabilities]]. If the buffer is almost empty, then 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 more fair than tail drop, in the sense that it does not possess a bias against bursty traffic that uses only a small portion of the bandwidth. The more a host transmits, the more likely it is that its packets are dropped as the probability of a host's packet being dropped is proportional to the amount of data it has in a queue. Early detection helps avoid TCP global synchronization.

== Problems with classic RED ==
According to Van Jacobson, "there are not one, but two bugs in classic RED."<ref name="jgred">{{cite web
 | url=http://gettys.wordpress.com/2010/12/17/red-in-a-different-light/
 | title=RED in a Different Light
 | first = Jim | last=Gettys | date= 2010-12-17  |work=jg's Ramblings | accessdate =2010-12-27
}}</ref> Improvements to the algorithm were developed, and a draft paper<ref>{{cite journal
  | last1 = Jacobson | first1 = Van | last2 = Nichols | first2 = Kathy | last3 = Poduri | first3 = Kedar
  | title = RED in a Different Light | date = 1999-09-30
  | citeseerx = 10.1.1.22.9406 }}</ref> was prepared, but the paper was never published, and the improvements were not widely disseminated or implemented. There has been some work in trying to finish off the research and fix the bugs.<ref name="jgred" />

Pure RED does not accommodate [[quality of service]] (QoS) differentiation. [[Weighted random early detection|Weighted RED]] (WRED) and RED with In and Out (RIO)<ref>{{cite news
 | title= An Approach to Service Allocation in the Internet
 | url = http://tools.ietf.org/html/draft-clark-diff-svc-alloc-00
 | first1 = David D. | last1 = Clark | first2 = John | last2 = Wroclawski
 | newspaper = Ietf Datatracker
 |date=July 1997  | page = 12 | accessdate = 2011-05-27 | publisher = IETF
}}</ref> provide early detection with QoS considerations.

== Other variants ==

===WRED===
{{Main article|Weighted random early detection}}

In weighted RED you can have different probabilities for different priorities ([[Type of Service|IP precedence]], [[Differentiated Services Code Point|DSCP]])  and/or queues.<ref>{{cite book | first=H. Jonathan |last=Chao | doi=10.1002/0471224391.fmatter_indsub|title= Quality of service control in high speed networks |pages=i-xvi |publisher = John Wiley & Sons Inc.| location = New York|year = 2002 | isbn= 978-0-471-00397-7 |chapter=Frontmatter and Index }}</ref>

===ARED===
The adaptive RED or active RED (ARED) algorithm<ref>{{cite journal | first = Sally | last = Floyd |author2=Gummadi, Ramakrishna |author3=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}}</ref> 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<ref>{{cite book | last = Srikant | first = Rayadurgam | url = https://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 }}</ref> for an in-depth account on these techniques and their analysis.

===RRED===
{{Main article|Robust random early detection}}

Robust random early detection (RRED) algorithm was proposed to improve the TCP throughput against Denial-of-Service (DoS) attacks, particularly [http://sites.google.com/site/cwzhangres/home/files/RREDRobustREDAlgorithmtoCounterLow-rateDenial-of-ServiceAttacks.pdf?attredirects=0 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.<ref name=RRED>{{cite journal|last=Zhang|first=Changwang|author2=Yin, Jianping |author3=Cai, Zhiping |author4= Chen, Weifeng |title=RRED: robust RED algorithm to counter low-rate denial-of-service attacks|journal=IEEE Communications Letters|date=1 May 2010|volume=14|issue=5|pages=489–491|doi=10.1109/LCOMM.2010.05.091407|s2cid=1121461 }}</ref> RRED algorithm can significantly improve the performance of TCP under Low-rate Denial-of-Service attacks.<ref name="RRED"/>

==See also==
* [[Blue (queue management algorithm)]]
* [[Active queue management]]

==References==
{{Reflist}}

==External links==
* [http://www.icir.org/floyd/red.html RED (Random Early Detection) Queue Management]. Author: Sally Floyd
* [http://code.google.com/p/guduz/ Guduz] – A Simple Random Early Detection (RED) Simulator
* [http://www.ee.ust.hk/~heixj/publication/thesis/node37.html Variants of RED] {{Webarchive|url=https://web.archive.org/web/20170720041436/http://www.ee.ust.hk/~heixj/publication/thesis/node37.html |date=2017-07-20 }}. Author: Hei Xiao Jun
* [http://sites.google.com/site/cwzhangres/home/posts/recentpublicationsinrandomearlydetectionredschemes Recent Publications in Random Early Detection (RED) schemes] {{Webarchive|url=https://web.archive.org/web/20160917055738/http://sites.google.com/site/cwzhangres/home/posts/recentpublicationsinrandomearlydetectionredschemes |date=2016-09-17 }}

{{DEFAULTSORT:Random Early Detection}}
[[Category:Network performance]]
[[Category:Network scheduling algorithms]]