Blue (queue management algorithm): Difference between revisions
m rm inapplicable hatnote -- see WP:NAMB |
Undid revision 361399971 by 173.85.56.213 (talk) |
||
| Line 1: | Line 1: | ||
'''Blue'''<ref>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.</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'''<ref>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.</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 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 ''p<sub>d</sub>'', and whenever the queue is empty, ''p'' is decreased by a constant ''p<sub>i</sub><p<sub>d</sub>''. |
|||
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 Fair Blue== |
==Stochastic Fair Blue== |
||
Revision as of 13:30, 12 June 2010
Blue[1] 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 pi<pd.
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 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)[2] 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.