Blue (queue management algorithm): Difference between revisions

Revision as of 14:00, 3 April 2011

Revision as of 10:30, 19 May 2011

Line 1:

'''<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-99CSE–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.

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

Line 11:

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'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 <span style="font-variant: small-caps;">Blue</span> (SFB)<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 [[Bloom filter]] rather than a hash table, which dramatically reduces its storage requirements when the number of flows is large.