Blue (queue management algorithm): Difference between revisions

Content deleted Content added

Inline

Latest revision as of 21:36, 3 August 2023

Blue is a scheduling discipline for the network scheduler developed by graduate student Wu-chang Feng for Professor Kang G. Shin at the University of Michigan and others at the Thomas J. Watson Research Center of IBM in 1999.^[1]

Functioning

Like random early detection (RED), Blue operates by randomly dropping or marking packet with explicit congestion notification mark before the transmit buffer of the network interface controller overflows. Unlike RED, however, it requires little or no tuning to be performed by the network administrator. 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 p_i, and whenever the queue is empty, p is decreased by a constant p_d < p_i.

If the mix of traffic on the interface does not change, p will slowly converge to a value that keeps the queue within its bounds with full link utilization.

Stochastic fair Blue

The main flaw of Blue, which it shares with most single-queue queuing disciplines, is that it does not distinguish between traffic flows, but treats all flows as a single aggregate. Therefore, a single aggressive flow can push packets out of the queue belonging to other, better behaved, flows.

Stochastic fair Blue (SFB) 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.^[2]

Unlike other stochastically fair queuing disciplines, such as SFQ (Stochastic Fairness Queuing), 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.

Resilient stochastic fair Blue

Many scheduling algorithms, including the fairness-aimed ones, are notably vulnerable to spoofing distributed denial-of-service (DDoS) attacks. A resilient stochastic fair Blue (RSFB) algorithm was proposed in 2009 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.^[3]

Implementations

An implementation of Blue is part of ALTQ, the network scheduler for BSD Unix.^[4]

An implementation of SFB for Linux was included in the Linux kernel in version 2.6.39.^[5]^[6]^[7]

References

^ Wu-chang Feng; Dilip D. Kandlur; Debanjan Saha; Kang G. Shin (April 1999). "BLUE: A New Class of Active Queue Management Algorithms" (PDF). Computer Science Technical Report (CSE–TR–387–99). University of Michigan. Retrieved June 8, 2013.
^ Wu-Chang Feng; Dilip D. Kandlur; Debanjan Saha; Kang G. Shin (April 2001). "Stochastic fair blue: A queue management algorithm for enforcing fairness". Proceedings IEEE INFOCOM 2001. Conference on Computer Communications. Twentieth Annual Joint Conference of the IEEE Computer and Communications Society (Cat. No.01CH37213) (PDF). Vol. 3. pp. 1520–1529. CiteSeerX 10.1.1.11.4235. doi:10.1109/INFCOM.2001.916648. ISBN 978-0-7803-7016-6. S2CID 5902623. Retrieved June 8, 2013.
^ Changwang Zhang; Jianping Yin & Zhiping Cai (2009). RSFB: a Resilient Stochastic Fair Blue algorithm against spoofing DDoS attacks (PDF). pp. 1566–1567. ISBN 978-1-4244-4521-9. Retrieved June 8, 2013. {{cite book}}: |journal= ignored (help) Abstract
^ Wu-chang Feng. "Blue". Web page. Retrieved June 8, 2013.
^ Kernel Newbies - Linux 2.6.39 - Networking
^ "SFB Linux kernel network scheduler module". kernel.org. Retrieved 2013-09-07.
^ Juliusz Chroboczek. "Stochastic Fair Blue for the Linux kernel". Retrieved June 8, 2013.

[mich-1] Wu-chang Feng; Dilip D. Kandlur; Debanjan Saha; Kang G. Shin (April 1999). "BLUE: A New Class of Active Queue Management Algorithms" (PDF). Computer Science Technical Report (CSE–TR–387–99). University of Michigan. Retrieved June 8, 2013.

[2] Wu-Chang Feng; Dilip D. Kandlur; Debanjan Saha; Kang G. Shin (April 2001). "Stochastic fair blue: A queue management algorithm for enforcing fairness". Proceedings IEEE INFOCOM 2001. Conference on Computer Communications. Twentieth Annual Joint Conference of the IEEE Computer and Communications Society (Cat. No.01CH37213) (PDF). Vol. 3. pp. 1520–1529. CiteSeerX 10.1.1.11.4235. doi:10.1109/INFCOM.2001.916648. ISBN 978-0-7803-7016-6. S2CID 5902623. Retrieved June 8, 2013.

[RSFB-3] Changwang Zhang; Jianping Yin & Zhiping Cai (2009). RSFB: a Resilient Stochastic Fair Blue algorithm against spoofing DDoS attacks (PDF). pp. 1566–1567. ISBN 978-1-4244-4521-9. Retrieved June 8, 2013. {{cite book}}: |journal= ignored (help) Abstract

[4] Wu-chang Feng. "Blue". Web page. Retrieved June 8, 2013.

[5] Kernel Newbies - Linux 2.6.39 - Networking

[6] "SFB Linux kernel network scheduler module". kernel.org. Retrieved 2013-09-07.

[7] Juliusz Chroboczek. "Stochastic Fair Blue for the Linux kernel". Retrieved June 8, 2013.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

@@ Line 1: / Line 1: @@
+'''Blue'''  is a [[scheduling discipline]] for the [[network scheduler]] developed by graduate student Wu-chang Feng for Professor [[Kang G. Shin]] at the [[University of Michigan]] and others at the [[Thomas J. Watson Research Center]] of [[IBM]] in 1999.<ref name="mich">{{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 |date=April 1999 |url=http://www.eecs.umich.edu/techreports/cse/99/CSE-TR-387-99.pdf |publisher= University of Michigan |journal= Computer Science Technical Report |issue=CSE–TR–387–99 |accessdate= June 8, 2013 }}</ref>
-{{cleanup|reason=heading, inline external link, ref based article needed|date=June 2011}}
-{{primarysources|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.
+==Functioning==
-==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.-->
+Like [[random early detection]] (RED), Blue operates by randomly dropping or marking packet with [[explicit congestion notification]] mark before the transmit buffer of the [[network interface controller]] overflows. Unlike RED, however, it requires little or no tuning to be performed by the network administrator. 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 ''p<sub>i</sub>'', and whenever the queue is empty, ''p'' is decreased by a constant ''p<sub>d</sub>&nbsp;< p<sub>i</sub>''.
+If the mix of traffic on the interface does not change, ''p'' will slowly converge to a value that keeps the queue within its bounds with full link utilization.
-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<sub>d</sub>'', and whenever the queue is empty, ''p'' is decreased by a constant ''p<sub>i</sub><p<sub>d</sub>''.
+===Stochastic fair Blue===
-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.
+The main flaw of Blue, which it shares with most single-queue [[queuing discipline]]s, is that it does not distinguish between [[Traffic flow (computer networking)|traffic flows]], but treats all flows as a single aggregate.  Therefore, a single aggressive flow can push packets out of the queue belonging to other, better behaved, flows.
+Stochastic fair Blue (SFB)  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.<ref>{{Cite book|author1=Wu-Chang Feng |author2=Dilip D. Kandlur |author3=Debanjan Saha |author4=Kang G. Shin |title=Proceedings IEEE INFOCOM 2001. Conference on Computer Communications. Twentieth Annual Joint Conference of the IEEE Computer and Communications Society (Cat. No.01CH37213) |chapter=Stochastic fair blue: A queue management algorithm for enforcing fairness |url=http://www.thefengs.com/wuchang/blue/41_2.PDF |date=April 2001 |pages=1520–1529 |doi=10.1109/INFCOM.2001.916648 |accessdate= June 8, 2013 |volume=3|isbn=978-0-7803-7016-6 |citeseerx=10.1.1.11.4235 |s2cid=5902623 }}</ref>
-==Stochastic Fair <span style="font-variant: small-caps;">B'''lue'''</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'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.
+Unlike other stochastically fair queuing disciplines, such as SFQ ([[Stochastic Fairness Queuing]]), 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.
+===Resilient stochastic fair Blue===
-==Resilient Stochastic Fair Blue ([http://sites.google.com/site/cwzhangres/home/files/RSFBaResilientStochasticFairBluealgorithmagainstspoofingDDoSattacks.pdf?attredirects=0 RSFB])==
+Many scheduling algorithms, including the fairness-aimed ones, are notably vulnerable to spoofing [[distributed denial-of-service]] (DDoS) attacks. A resilient stochastic fair Blue (RSFB) algorithm was proposed in 2009 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>{{Cite book |author1=Changwang Zhang |author2=Jianping Yin |author3=Zhiping Cai  |name-list-style=amp |url=  http://sites.google.com/site/cwzhangres/home/files/RSFBaResilientStochasticFairBluealgorithmagainstspoofingDDoSattacks.pdf |title=  RSFB: a Resilient Stochastic Fair Blue algorithm against spoofing DDoS attacks |journal= International Symposium on Communication and Information Technology (ISCIT) |year= 2009 |pages= 1566–1567 |isbn= 978-1-4244-4521-9 |accessdate= June 8, 2013 }} [http://portal.acm.org/citation.cfm?id=1789954.1790341 Abstract]</ref>
-The existing Active Queue Management (AQM) algorithms, including the fairness-aimed ones, are notably vulnerable to spoofing Distributed Denial-of-Service (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==
+An implementation of Blue is part of [[ALTQ]], the [[network scheduler]] for BSD Unix.<ref>{{Cite web |title= Blue |work= Web page |author= Wu-chang Feng |url= http://www.thefengs.com/wuchang/blue/ |accessdate= June 8, 2013 }}</ref>
+An implementation of SFB for [[Linux]] was included in the [[Linux kernel]] in version 2.6.39.<ref>[http://kernelnewbies.org/Linux_2_6_39#head-87ffd4407af29460251c521e0228fe0ac9219d4b Kernel Newbies - Linux 2.6.39 - Networking]</ref><ref>{{cite web |url=https://git.kernel.org/cgit/linux/kernel/git/stable/linux-stable.git/tree/net/sched/sch_sfb.c |title=SFB Linux kernel network scheduler module |publisher=[[kernel.org]] |accessdate=2013-09-07}}</ref><ref>{{Cite web |title= Stochastic Fair Blue for the Linux kernel |author= Juliusz Chroboczek |url= http://www.pps.univ-paris-diderot.fr/~jch/software/sfb/ |accessdate= June 8, 2013  }}</ref>
-An implementation of Blue is part of [[ALTQ]], the alternative AQM framework for BSD Unix{{Citation needed|date=April 2011}}.
-An implementation of SFB for Linux<ref>Juliusz Chroboczek. [http://www.pps.jussieu.fr/~jch/software/sfb/ An implementation of SFB for the Linux kernel]</ref> has been included in Linux since version 2.6.39{{Citation needed|date=April 2011}}.
 ==References==
+{{Reflist}}
-<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].
 [[Category:Packets (information technology)]]