Stochastic Fair Blue (SFB) is an active queue management algorithm for packet routers that attempts to simultaneously:
SFB doesn't require much tuning, and uses a very small amount of memory for book-keeping.
The main issue with SFB is that the notion of fairness it pursues is not necessarily the one you want: SFB enforces resource fairness between flows, meaning that all flows get roughly the same amount of buffer space. It is not clear how well this translates into fairness in throughput between flows, notably with varying RTT and different implementations of congestion control.
In other words, SFB will neither guarantee the same rate in bytes per second or packets per second between flows, but it will come pretty close. It will reliably detect flows that don't react to congestion indications, and treat them really badly.
SFB is described in excruciating detail in
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. Available online.
SFB classifies all traffic into aggregates. Depending how it is configured, SFB can treat each flow (TCP connection) as an aggregate, or all traffic destined to a given IP address as an aggregate, etc. SFB will try to ensure that each aggregate gets its fair share of buffer space.
For each aggregate, SFB maintains two pieces of data, the drop probability pm and the number qlen of queued packets that belong to the aggregate. While SFB maintains all packets in a single queue, you may want to think of SFB as maintaining a set of per-flow virtual queues, and qlen being the length of a given virtual queue.
SFB is parameterised by two values: max, which is the absolute maximum length of a virtual queue, and target, which is the desired maximum length of a virtual queue.
Normally, a flow's qlen stays below max, and packets are ECN-marked or dropped randomly with probability pm. The mark/drop probability pm is dynamically adjusted to keep qlen between 0 and target.
Sometimes, due to a burst, qlen will grow beyond max. In that case, packets will be dropped (and pm adjusted).
When an aggregate's mark/drop probability reaches 1.0, the aggregate has been detected as non-responsive, meaning that it doesn't respond to congestion indications. From now on, it will be rate-limited.
SFB doesn't actually maintain pm and qlen for every flow; it uses a data structure called a Bloom filter, which uses similar principles to a hash table, but uses orders of magnitude less memory (at a fixed collision probability).
When deciding whether to hard drop a packet, this implementation considers the minimum of all matching bucket sizes rather than the maximum, as suggested in the paper. Either the paper is wrong, or I don't understand how Bloom filters work.
If an aggregate has a very high marking rate, then either it is unresponsive, or we are badly congested. In either case, it is a good idea to start dropping packets rather than just marking them. If pm is below 1/2, we mark/drop with probability pm; if pm is larger than 1/2, then we drop with probability pm * (2 * pm - 1/2), and mark/drop with probability pm * (3/2 - 2 * pm).
sch_sfb is an implementation of SFB for the Linux kernel.
sch_sfb is implemented as a pure buffer management qdisc: it will drop and mark packets, but it will never delay them or reorder them. However, sch_sfb delegates queuing to its child discipline, which might perform reordering for us. For example, you may want to use sch_prio or even sch_sfq as a child of sch_sfb.
Read sch_sfb's README.
SFB works better when hosts use ECN marking, especially on slow interfaces. You should enable ECN on as many of your hosts as possible.
On Linux, this can be done by typing
# sysctl net.ipv4.tcp_ecn=1
On most Linux distributions, this change can be made permanent by
adding the following line to /etc/sysctl.conf:
net.ipv4.tcp_ecn=1
A slightly modified version of this code has been committed by Éric Dumazet (under his own name) into the Linux tree, and is part of Linux since 2.6.39. My original version of sch_sfb is now of historical interest only.