NAME¶
sfb - Stochastic Fair Blue
SYNOPSIS¶
tc qdisc ... blue rehash milliseconds
db milliseconds
limit packets
max packets
target packets
increment
float
decrement float
penalty_rate packets per second
penalty_burst packets
DESCRIPTION¶
Stochastic Fair Blue is a classless qdisc to manage congestion based on packet
loss and link utilization history while trying to prevent non-responsive flows
(i.e. flows that do not react to congestion marking or dropped packets) from
impacting performance of responsive flows. Unlike RED, where the marking
probability has to be configured, BLUE tries to determine the ideal marking
probability automatically.
ALGORITHM¶
The
BLUE algorithm maintains a probability which is used to mark or drop
packets that are to be queued. If the queue overflows, the mark/drop
probability is increased. If the queue becomes empty, the probability is
decreased. The
Stochastic Fair Blue (SFB) algorithm is designed to
protect TCP flows against non-responsive flows.
This SFB implementation maintains 8 levels of 16 bins each for accounting. Each
flow is mapped into a bin of each level using a per-level hash value.
Every bin maintains a marking probability, which gets increased or decreased
based on bin occupancy. If the number of packets exceeds the size of that bin,
the marking probability is increased. If the number drops to zero, it is
decreased.
The marking probability is based on the minimum value of all bins a flow is
mapped into, thus, when a flow does not respond to marking or gradual packet
drops, the marking probability quickly reaches one.
In this case, the flow is rate-limited to
penalty_rate packets per
second.
LIMITATIONS¶
Due to SFBs nature, it is possible for responsive flows to share all of its bins
with a non-responsive flow, causing the responsive flow to be misidentified as
being non-responsive.
The probability of a responsive flow to be misidentified is dependent on the
number of non-responsive flows, M. It is (1 - (1 - (1 / 16.0)) ** M) **8, so
for example with 10 non-responsive flows approximately 0.2% of responsive
flows will be misidentified.
To mitigate this, SFB performs performs periodic re-hashing to avoid
misclassification for prolonged periods of time.
The default hashing method will use source and destination ip addresses and port
numbers if possible, and also supports tunneling protocols. Alternatively, an
external classifier can be configured, too.
PARAMETERS¶
- rehash
- Time interval in milliseconds when queue perturbation occurs to avoid
erroneously detecting unrelated, responsive flows as being part of a
non-responsive flow for prolonged periods of time. Defaults to 10
minutes.
- db
- Double buffering warmup wait time, in milliseconds. To avoid destroying
the probability history when rehashing is performed, this implementation
maintains a second set of levels/bins as described in section 4.4 of the
SFB reference. While one set is used to manage the queue, a second set is
warmed up: Whenever a flow is then determined to be non-responsive, the
marking probabilities in the second set are updated. When the rehashing
happens, these bins will be used to manage the queue and all
non-responsive flows can be rate-limited immediately. This value
determines how much time has to pass before the 2nd set will start to be
warmed up. Defaults to one minute, should be lower than
rehash.
- limit
- Hard limit on the real (not average) total queue size in packets. Further
packets are dropped. Defaults to the transmit queue length of the device
the qdisc is attached to.
- max
- Maximum length of a buckets queue, in packets, before packets start being
dropped. Should be sightly larger than target , but should not be
set to values exceeding 1.5 times that of target . Defaults to
25.
- target
- The desired average bin length. If the bin queue length reaches this
value, the marking probability is increased by increment. The
default value depends on the max setting, with max set to 25
target will default to 20.
- increment
- A value used to increase the marking probability when the queue appears to
be over-used. Must be between 0 and 1.0. Defaults to 0.00050.
- decrement
- Value used to decrease the marking probability when the queue is found to
be empty. Must be between 0 and 1.0. Defaults to 0.00005.
- penalty_rate
- The maximum number of packets belonging to flows identified as being
non-responsive that can be enqueued per second. Once this number has been
reached, further packets of such non-responsive flows are dropped. Set
this to a reasonable fraction of your uplink throughput; the default value
of 10 packets is probably too small.
- penalty_burst
- The number of packets a flow is permitted to exceed the penalty rate
before packets start being dropped. Defaults to 20 packets.
STATISTICS¶
This qdisc exposes additional statistics via 'tc -s qdisc' output. These are:
- earlydrop
- The number of packets dropped before a per-flow queue was full.
- ratedrop
- The number of packets dropped because of rate-limiting. If this value is
high, there are many non-reactive flows being sent through sfb. In such
cases, it might be better to embed sfb within a classful qdisc to better
control such flows using a different, shaping qdisc.
- bucketdrop
- The number of packets dropped because a per-flow queue was full. High
bucketdrop may point to a high number of aggressive, short-lived
flows.
- queuedrop
- The number of packets dropped due to reaching limit. This should normally
be 0.
- marked
- The number of packets marked with ECN.
- maxqlen
- The length of the current longest per-flow (virtual) queue.
- maxprob
- The maximum per-flow drop probability. 1 means that some flows have been
detected as non-reactive.
NOTES¶
SFB automatically enables use of Explicit Congestion Notification (ECN). Also,
this SFB implementation does not queue packets itself. Rather, packets are
enqueued to the inner qdisc (defaults to pfifo). Because sfb maintains virtual
queue states, the inner qdisc must not drop a packet previously queued.
Furthermore, if a buckets queue has a very high marking rate, this
implementation will start dropping packets instead of marking them, as such a
situation points to either bad congestion, or an unresponsive flow.
EXAMPLE & USAGE¶
To attach to interface $DEV, using default options:
# tc qdisc add dev $DEV handle 1: root sfb
Only use destination ip addresses for assigning packets to bins, perturbing hash
results every 10 minutes:
# tc filter add dev $DEV parent 1: handle 1 flow hash keys dst perturb 600
SEE ALSO¶
tc(8),
tc-red(8),
tc-sfq(8)
SOURCES¶
- o
- 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.
AUTHORS¶
This SFB implementation was contributed by Juliusz Chroboczek and Eric
Dumazet.
