Blue (queue management algorithm)

Blue (queue management algorithm)

Blue [W. Feng, D. Kandlur, D. Saha, K. Shin. "Blue: A New Class of Active Queue Management Algorithms." U. Michigan CSE-TR-387-99, April 1999.] is an Active Queue Management algorithm. Like RED, it operates by randomly dropping or ECN-marking packets in a router's queue before it overflows. Unlike RED, however, it requires little or no tuning on the part of the network administrator.

Operation of Blue

A Blue queue maintains a drop/mark probability "p", and drops/marks packets with probability "p" as they enter the queue. Whenever the queue overflows, "p" is increased by a small constant "pd", and whenever the queue is empty, "p" is decreased by a constant "pid".

Assuming the mix of traffic on the interface doesn't change, "p" will slowly converge to a value that keeps the queue within its bounds with full link utilisation.

tochastic Fair Blue

The main flaw of Blue, which it shares with most single-queue queing disciplines, is that it doesn't distinguish between flows, and treats all flows as a single aggregate. Therefore, a single aggressive flow can push out of the queue packets belonging to other, better behaved flows.

Stochastic Fair Blue (SFB) [Wu-Chang Feng, Dilip D. Kandlur, Debanjan Saha, Kang G. Shin. Stochastic Fair Blue: an algorithm for enforcing fairness. In "Proc. INFOCOM'2001". 2001.] is a stochastically fair variant of blue which hashes flows and maintains a different mark/drop probability for each hash value. Assuming no hash collisions, SFB is able to provide a fair share of buffer space for every flow. In the presence of hash collisions, SFB is only stochastically fair.

Unlike other stochastically fair queuing disciplines, such as SFQ, SFB can be implemented using a Bloom filter rather than a hash table, which dramatically reduces its storage requirements when the number of flows is large.

When a flow's drop/mark probability reaches 1, the flow has been shown to not react to congestion indications from the network. Such an inelastic flow is put in a penalty box, and rate-limited.

References

External links

* [http://www.thefengs.com/wuchang/blue/ Wu-chang Feng's page about Blue and SFB] .
* [http://www.pps.jussieu.fr/~jch/software/sfb/ An implementation of SFB for the Linux kernel] .


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Active Queue Management — (AQM) (Активное Управление Очередью)  технология в сетевых маршрутизаторах, заключающаяся в отбрасывании или установлении флага ECN пакетов до того, как очередь маршрутизатора заполнится. Содержание 1 Управление очередью 1.1 Преимущества AQM …   Википедия

  • OPTICS algorithm — OPTICS ( Ordering Points To Identify the Clustering Structure ) is an algorithm for finding density based clusters in spatial data. It was presented by Mihael Ankerst, Markus M. Breunig, Hans Peter Kriegel and Jörg Sander[1]. Its basic idea is… …   Wikipedia

  • Red (disambiguation) — Red is a color.Red or RED may also refer to:General*Red Army the name of the Soviet Army until 1947 *RED Digital Cinema, a manufacturer of digital film cameras *Red (nightclub), in Washington, D.C. *Random early detection, a queue management… …   Wikipedia

  • SFB — may refer to: *San Francisco Bay * The IATA airport code for Orlando Sanford International Airport * Star Fleet Battles, a tactical strategy board game set in the Star Fleet Universe * A Sunken Feature or Sunken Floored Building, also known as a… …   Wikipedia

  • Scheduling (computing) — This article is about processes assignment in operating systems. For other uses, see Scheduling (disambiguation). Scheduling is a key concept in computer multitasking, multiprocessing operating system and real time operating system designs.… …   Wikipedia

  • Paging — This article is about computer virtual memory. For the wireless communication devices, see Pager . Bank switching is also called paging. Page flipping is also called paging. For calling people in a public place see Public address. In computer… …   Wikipedia

  • OS/2 — A typical OS/2 Warp 4 desktop Company / developer IBM Microsoft …   Wikipedia

  • Microsoft Windows — Windows redirects here. For the part of a building, see Window. For other uses, see Windows (disambiguation). Microsoft Windows …   Wikipedia

  • Denial-of-service attack — DoS redirects here. For other uses, see DOS (disambiguation). DDoS Stacheldraht Attack diagram. A denial of service attack (DoS attack) or distributed denial of service attack (DDoS attack) is an attempt to make a computer resource unavailable to …   Wikipedia

  • Ada (programming language) — For other uses of Ada or ADA, see Ada (disambiguation). Ada Paradigm(s) Multi paradigm Appeared in 1980 Designed by MIL STD 1815/Ada 83: Jean Ichbiah Ada 95: Tucker Taft Ada 2005: Tucker Taft Stable release …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”