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