Blue (queue management algorithm): Difference between revisions

Revision as of 16:42, 3 March 2013

Revision as of 18:56, 8 June 2013

Line 1:

{{cleanup|reason=heading, inline external link, ref based article needed|date=June 2011}}

{{primary sources|date=June 2011}}

'''<span style="font-variant: small-caps;">Blue</span>'''<ref>{{Citation |title=BLUE: A New Class of Active Queue Management Algorithms |author1=Wu-chang Feng |author2=Dilip D. Kandlur |author3=Debanjan Saha |author4=Kang G. Shin |year=1999 |month=April |url=http://www.eecs.umich.edu/techreports/cse/99/CSE-TR-387-99.pdf |journal=U. Michigan Computer Science Technical Report |issue=CSE–TR–387–99 |accessdate=2010-12-22}}</ref> is an [[Active Queue Management]] algorithm. Like [[Random early detection|RED]], it operates by randomly dropping or [[Explicit Congestion Notification|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.

'''Blue''' is an [[active queue management]] algorithm. Like [[random early detection]] (RED), it operates by randomly dropping or marking packet with [[explicit congestion notification]] 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.<ref>{{Cite journal |title=BLUE: A New Class of Active Queue Management Algorithms |author1=Wu-chang Feng |author2=Dilip D. Kandlur |author3=Debanjan Saha |author4=Kang G. Shin |year=1999 |month=April |url=http://www.eecs.umich.edu/techreports/cse/99/CSE-TR-387-99.pdf |journal=U. Michigan Computer Science Technical Report |issue=CSE–TR–387–99 |accessdate= June 8, 2013 }}</ref>

==Operation of <span style="font-variant: small-caps;">Blue</span>== <!--Bolding small cap letters looks MUCH better on Firefox; don't know about other browsers.-->

==Operation==

A <span style="font-variant: small-caps;">Blue</span> 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 ''p_d'', and whenever the queue is empty, ''p'' is decreased by a constant ''p_i<p_d''.

A <span style="font-variant: small-caps;">Blue</span> 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 ''p_d'', and whenever the queue is empty, ''p'' is decreased by a constant ''p_i<p_d''.

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.

==Stochastic Fairfair <span style="font-variant: small-caps;">Blue</span>==

The main flaw of <span style="font-variant: small-caps;">Blue</span>, which it shares with most single-queue queueing disciplines, is that it doesn'tdoes not 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 Fairfair <spanBlue (SFB) is a stochastically fair style="font-variant: small-caps;">of Blue< which hashes flows and maintains a different mark/span>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.<ref>{{Citation |author1=Wu-Chang Feng |author2=Dilip D. Kandlur |author3=Debanjan Saha |author4=Kang G. Shin |title=Stochastic Fair Blue: an algorithm for enforcing fairness |url=http://www.thefengs.com/wuchang/blue/41_2.PDF |journal=Proc. INFOCOM 2001 |year=2001 |month=April |pages=1520–1529 |doi=10.1109/INFCOM.2001.916648 |accessdate=2010-01-02 |volume=3}}</ref> is a stochastically fair variant of <span style="font-variant: small-caps;">Blue</span> 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 [[Bloombloom 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.

==Resilient stochastic fair Blue==

==Resilient Stochastic Fair Blue ([http://sites.google.com/site/cwzhangres/home/files/RSFBaResilientStochasticFairBluealgorithmagainstspoofingDDoSattacks.pdf?attredirects=0 RSFB])==

The existing Active Queuequeue Managementmanagement (AQM) algorithms, including the fairness-aimed ones, are notably vulnerable to spoofing Distributed[[distributed Denialdenial-of-Serviceservice]] (DDoS) attacks. A Resilient Stochastic Fair Blue (RSFB) algorithm was proposed against spoofing DDoS attacks. The basic idea behind RSFB is to record the responsive normal TCP flows and rescue their dropped packets. RSFB algorithm is effective in preserving the TCP throughput in the presence of spoofing DDoS attacks.<ref name=RSFB>Changwang Zhang, Jianping Yin, and Zhiping Cai, [http://sites.google.com/site/cwzhangres/home/files/RSFBaResilientStochasticFairBluealgorithmagainstspoofingDDoSattacks.pdf?attredirects=0 RSFB: a Resilient Stochastic Fair Blue algorithm against spoofing DDoS attacks], in International Symposium on Communication and Information Technology (ISCIT), 2009. [http://portal.acm.org/citation.cfm?id=1789954.1790341 Ref]</ref>

==Implementations==