Content deleted Content added
No edit summary |
m →Resilient stochastic fair Blue: task, replaced: journal= International Symposium on Communication and Information Technology (ISCIT) → journal= International Symposium on Communication and Information Technology |
||
| (21 intermediate revisions by 15 users not shown) | |||
Line 1:
'''Blue''' is
==Functioning==
▲'''Blue''' is an [[active queue management]] algorithm for a [[network scheduler]]. 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 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 |year=1999 |month=April |url=http://www.eecs.umich.edu/techreports/cse/99/CSE-TR-387-99.pdf |publisher= University of Michigan |work= Computer Science Technical Report |issue=CSE–TR–387–99 |accessdate= June 8, 2013 }}</ref>
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>
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
▲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>d</sub>'', and whenever the queue is empty, ''p'' is decreased by a constant ''p<sub>i</sub><p<sub>d</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 utilisation.
===Stochastic fair Blue===
The main flaw of Blue, which it shares with most single-queue
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>{{
▲The main flaw of Blue, which it shares with most single-queue queueing disciplines, 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.
Unlike other stochastically fair queuing disciplines, such as SFQ
▲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>{{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=Proceedings of INFOCOM 2001 |year=2001 |month=April |pages=1520–1529 |doi=10.1109/INFCOM.2001.916648 |accessdate= June 8, 2013 |volume=3}}</ref>
▲Unlike other stochastically fair queuing disciplines, such as SFQ,<!-- what is that? --> 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===
▲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 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 journal |author= Changwang Zhang, Jianping Yin, and Zhiping Cai |url= http://sites.google.com/site/cwzhangres/home/files/RSFBaResilientStochasticFairBluealgorithmagainstspoofingDDoSattacks.pdf |title= RSFB: a Resilient Stochastic Fair Blue algorithm against spoofing DDoS attacks |work= 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>
An implementation of Blue is part of [[ALTQ]], the
▲===Implementations===
▲An implementation of Blue is part of [[ALTQ]], the alternative AQM framework 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]]
==References==
{{Reflist}}
[[Category:Packets (information technology)]]
| |||