Jump to content

Random early detection

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Kvng (talk | contribs) at 04:31, 26 May 2013 (Reverted 1 edit by 67.6.34.158 (talk): No improvement. (TW)). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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.[1]

In the conventional tail drop algorithm, a router or other network component discard one or more incoming pockets before the output buffer is fully complete,in order to improve performance of the network which is referred to as Tail drop that 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.

Operation

RED 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 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."[2] Improvements to the algorithm were developed, and a draft paper[3] 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.[2]

Pure RED does not accommodate quality of service (QoS) differentiation. Weighted RED (WRED) and RED with In and Out (RIO)[4] 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 (IP precedence, DSCP) and/or queues.[5]

ARED

The adaptive RED or active RED (ARED) algorithm[6] 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[7] 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 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.[8] RRED algorithm can significantly improve the performance of TCP under Low-rate Denial-of-Service attacks.[8]

See also

References

  1. ^ Floyd, Sally (1993). "Random Early Detection (RED) gateways for Congestion Avoidance". IEEE/ACM Transactions on Networking. 1 (4): 397–413. doi:10.1109/90.251892. Retrieved 2008-03-16. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help); Unknown parameter |month= ignored (help)
  2. ^ a b Gettys, Jim (2010-12-17). "RED in a Different Light". jg's Ramblings. Retrieved 2010-12-27.
  3. ^ Jacobson, Van; Nichols, Kathy; Poduri, Kedar (1999-09-30). "RED in a Different Light".
  4. ^ Clark, David D.; Wroclawski, John (1997). "An Approach to Service Allocation in the Internet". IETF. p. 12. Retrieved 2011-05-27. {{cite web}}: Unknown parameter |month= ignored (help)
  5. ^ Chao, H. Jonathan (2002). Quality of service control in high speed networks. 605 Third Avenue, New York, NY: John Wiley & Sons Inc. doi:10.1002/0471224391.fmatter_indsub. ISBN 0-471-00397-2.{{cite book}}: CS1 maint: location (link)
  6. ^ Floyd, Sally (2001-08-01). "Adaptive RED: An Algorithm for Increasing the Robustness of RED's Active Queue Management". Retrieved 2008-03-16. {{cite journal}}: Cite journal requires |journal= (help); Unknown parameter |coauthors= ignored (|author= suggested) (help)
  7. ^ Srikant, Rayadurgam (2004). The Mathematics of Internet Congestion Control. Boston, MA, USA: Birkhäuser. ISBN 978-0-8176-3227-4.
  8. ^ a b Zhang, Changwang (1 May 2010). "RRED: robust RED algorithm to counter low-rate denial-of-service attacks". IEEE Communications Letters. 14 (5): 489–491. doi:10.1109/LCOMM.2010.05.091407. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
Retrieved from "https://en.wikipedia.org/w/index.php?title=Random_early_detection&oldid=556821446"