Blue (queue management algorithm)
Encyclopedia
Blue 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.
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 pid .
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 (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.
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.
, the alternative AQM framework for BSD Unix.
An implementation of SFB for Linux has been included in Linux since version 2.6.39.
Active Queue Management
In Internet routers, active queue management is a technique that consists in dropping or ECN-marking packets before a router's queue is full.-Queue management:...
algorithm. Like RED
Random early detection
Random early detection , also known as random early discard or random early drop is an active queue management algorithm. It is also a congestion avoidance algorithm....
, it operates by randomly dropping or ECN
Explicit Congestion Notification
Explicit Congestion Notification is an extension to the Internet Protocol and to the Transmission Control Protocol and is defined in RFC 3168 . ECN allows end-to-end notification of network congestion without dropping packets. ECN is an optional feature that is only used when both endpoints...
-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
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 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 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.
Unlike other stochastically fair queuing disciplines, such as SFQ, SFB can be implemented using a Bloom filter
Bloom filter
A Bloom filter, conceived by Burton Howard Bloom in 1970, is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positives are possible, but false negatives are not; i.e. a query returns either "inside set " or "definitely not in set"...
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
Penalty box
The penalty box is the area in ice hockey, rugby league, rugby union and some other sports where a player sits to serve the time of a given penalty, for an offense not severe enough to merit outright expulsion from the contest...
", and rate-limited.
Resilient Stochastic Fair Blue (RSFB)
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.Implementations
An implementation of Blue is part of ALTQALTQ
ALTQ is an ALTernate Queueing framework for BSD. ALTQ provides queueing disciplines and other QoS related components required to realize resource-sharing and Quality of Service. It is most commonly implemented on BSD-based routers...
, the alternative AQM framework for BSD Unix.
An implementation of SFB for Linux has been included in Linux since version 2.6.39.