| 1 |
.TH SFB 8 "August 2011" "iproute2" "Linux" |
| 2 |
.SH NAME |
| 3 |
sfb \- Stochastic Fair Blue |
| 4 |
.SH SYNOPSIS |
| 5 |
.B tc qdisc ... blue |
| 6 |
.B rehash |
| 7 |
milliseconds |
| 8 |
.B db |
| 9 |
milliseconds |
| 10 |
.B limit |
| 11 |
packets |
| 12 |
.B max |
| 13 |
packets |
| 14 |
.B target |
| 15 |
packets |
| 16 |
.B increment |
| 17 |
float |
| 18 |
.B decrement |
| 19 |
float |
| 20 |
.B penalty_rate |
| 21 |
packets per second |
| 22 |
.B penalty_burst |
| 23 |
packets |
| 24 |
|
| 25 |
.SH DESCRIPTION |
| 26 |
Stochastic Fair Blue is a classless qdisc to manage congestion based on |
| 27 |
packet loss and link utilization history while trying to prevent |
| 28 |
non-responsive flows (i.e. flows that do not react to congestion marking |
| 29 |
or dropped packets) from impacting performance of responsive flows. |
| 30 |
Unlike RED, where the marking probability has to be configured, BLUE |
| 31 |
tries to determine the ideal marking probability automatically. |
| 32 |
|
| 33 |
.SH ALGORITHM |
| 34 |
|
| 35 |
The |
| 36 |
.B BLUE |
| 37 |
algorithm maintains a probability which is used to mark or drop packets |
| 38 |
that are to be queued. If the queue overflows, the mark/drop probability |
| 39 |
is increased. If the queue becomes empty, the probability is decreased. The |
| 40 |
.B Stochastic Fair Blue |
| 41 |
(SFB) algorithm is designed to protect TCP flows against non-responsive flows. |
| 42 |
|
| 43 |
This SFB implementation maintains 8 levels of 16 bins each for accounting. |
| 44 |
Each flow is mapped into a bin of each level using a per-level hash value. |
| 45 |
|
| 46 |
Every bin maintains a marking probability, which gets increased or decreased |
| 47 |
based on bin occupancy. If the number of packets exceeds the size of that |
| 48 |
bin, the marking probability is increased. If the number drops to zero, it |
| 49 |
is decreased. |
| 50 |
|
| 51 |
The marking probability is based on the minimum value of all bins a flow is |
| 52 |
mapped into, thus, when a flow does not respond to marking or gradual packet |
| 53 |
drops, the marking probability quickly reaches one. |
| 54 |
|
| 55 |
In this case, the flow is rate-limited to |
| 56 |
.B penalty_rate |
| 57 |
packets per second. |
| 58 |
|
| 59 |
.SH LIMITATIONS |
| 60 |
|
| 61 |
Due to SFBs nature, it is possible for responsive flows to share all of its bins |
| 62 |
with a non-responsive flow, causing the responsive flow to be misidentified as |
| 63 |
being non-responsive. |
| 64 |
|
| 65 |
The probability of a responsive flow to be misidentified is dependent on |
| 66 |
the number of non-responsive flows, M. It is (1 - (1 - (1 / 16.0)) ** M) **8, |
| 67 |
so for example with 10 non-responsive flows approximately 0.2% of responsive flows |
| 68 |
will be misidentified. |
| 69 |
|
| 70 |
To mitigate this, SFB performs periodic re-hashing to avoid |
| 71 |
misclassification for prolonged periods of time. |
| 72 |
|
| 73 |
The default hashing method will use source and destination ip addresses and port numbers |
| 74 |
if possible, and also supports tunneling protocols. |
| 75 |
Alternatively, an external classifier can be configured, too. |
| 76 |
|
| 77 |
.SH PARAMETERS |
| 78 |
.TP |
| 79 |
rehash |
| 80 |
Time interval in milliseconds when queue perturbation occurs to avoid erroneously |
| 81 |
detecting unrelated, responsive flows as being part of a non-responsive flow for |
| 82 |
prolonged periods of time. |
| 83 |
Defaults to 10 minutes. |
| 84 |
.TP |
| 85 |
db |
| 86 |
Double buffering warmup wait time, in milliseconds. |
| 87 |
To avoid destroying the probability history when rehashing is performed, this |
| 88 |
implementation maintains a second set of levels/bins as described in section |
| 89 |
4.4 of the SFB reference. |
| 90 |
While one set is used to manage the queue, a second set is warmed up: |
| 91 |
Whenever a flow is then determined to be non-responsive, the marking |
| 92 |
probabilities in the second set are updated. When the rehashing |
| 93 |
happens, these bins will be used to manage the queue and all non-responsive |
| 94 |
flows can be rate-limited immediately. |
| 95 |
This value determines how much time has to pass before the 2nd set |
| 96 |
will start to be warmed up. |
| 97 |
Defaults to one minute, should be lower than |
| 98 |
.B |
| 99 |
rehash. |
| 100 |
.TP |
| 101 |
limit |
| 102 |
Hard limit on the real (not average) total queue size in packets. |
| 103 |
Further packets are dropped. Defaults to the transmit queue length of the |
| 104 |
device the qdisc is attached to. |
| 105 |
.TP |
| 106 |
max |
| 107 |
Maximum length of a buckets queue, in packets, before packets start being |
| 108 |
dropped. Should be slightly larger than |
| 109 |
.B target |
| 110 |
, but should not be set to values exceeding 1.5 times that of |
| 111 |
.B target . |
| 112 |
Defaults to 25. |
| 113 |
.TP |
| 114 |
target |
| 115 |
The desired average bin length. If the bin queue length reaches this value, |
| 116 |
the marking probability is increased by |
| 117 |
.B increment. |
| 118 |
The default value depends on the |
| 119 |
.B max |
| 120 |
setting, with max set to 25 |
| 121 |
.B target |
| 122 |
will default to 20. |
| 123 |
.TP |
| 124 |
increment |
| 125 |
A value used to increase the marking probability when the queue appears |
| 126 |
to be over-used. Must be between 0 and 1.0. Defaults to 0.00050. |
| 127 |
.TP |
| 128 |
decrement |
| 129 |
Value used to decrease the marking probability when the queue is found |
| 130 |
to be empty. Must be between 0 and 1.0. |
| 131 |
Defaults to 0.00005. |
| 132 |
.TP |
| 133 |
penalty_rate |
| 134 |
The maximum number of packets belonging to flows identified as being |
| 135 |
non-responsive that can be enqueued per second. Once this number has been |
| 136 |
reached, further packets of such non-responsive flows are dropped. |
| 137 |
Set this to a reasonable fraction of your uplink throughput; the |
| 138 |
default value of 10 packets is probably too small. |
| 139 |
.TP |
| 140 |
penalty_burst |
| 141 |
The number of packets a flow is permitted to exceed the penalty rate before packets |
| 142 |
start being dropped. |
| 143 |
Defaults to 20 packets. |
| 144 |
|
| 145 |
.SH STATISTICS |
| 146 |
|
| 147 |
This qdisc exposes additional statistics via 'tc -s qdisc' output. |
| 148 |
These are: |
| 149 |
.TP |
| 150 |
earlydrop |
| 151 |
The number of packets dropped before a per-flow queue was full. |
| 152 |
.TP |
| 153 |
ratedrop |
| 154 |
The number of packets dropped because of rate-limiting. |
| 155 |
If this value is high, there are many non-reactive flows being |
| 156 |
sent through sfb. In such cases, it might be better to |
| 157 |
embed sfb within a classful qdisc to better control such |
| 158 |
flows using a different, shaping qdisc. |
| 159 |
.TP |
| 160 |
bucketdrop |
| 161 |
The number of packets dropped because a per-flow queue was full. |
| 162 |
High bucketdrop may point to a high number of aggressive, short-lived |
| 163 |
flows. |
| 164 |
.TP |
| 165 |
queuedrop |
| 166 |
The number of packets dropped due to reaching limit. This should normally be 0. |
| 167 |
.TP |
| 168 |
marked |
| 169 |
The number of packets marked with ECN. |
| 170 |
.TP |
| 171 |
maxqlen |
| 172 |
The length of the current longest per-flow (virtual) queue. |
| 173 |
.TP |
| 174 |
maxprob |
| 175 |
The maximum per-flow drop probability. 1 means that some |
| 176 |
flows have been detected as non-reactive. |
| 177 |
|
| 178 |
.SH NOTES |
| 179 |
|
| 180 |
SFB automatically enables use of Explicit Congestion Notification (ECN). |
| 181 |
Also, this SFB implementation does not queue packets itself. |
| 182 |
Rather, packets are enqueued to the inner qdisc (defaults to pfifo). |
| 183 |
Because sfb maintains virtual queue states, the inner qdisc must not |
| 184 |
drop a packet previously queued. |
| 185 |
Furthermore, if a buckets queue has a very high marking rate, |
| 186 |
this implementation will start dropping packets instead of |
| 187 |
marking them, as such a situation points to either bad congestion, or an |
| 188 |
unresponsive flow. |
| 189 |
|
| 190 |
.SH EXAMPLE & USAGE |
| 191 |
|
| 192 |
To attach to interface $DEV, using default options: |
| 193 |
.P |
| 194 |
# tc qdisc add dev $DEV handle 1: root sfb |
| 195 |
|
| 196 |
Only use destination ip addresses for assigning packets to bins, perturbing |
| 197 |
hash results every 10 minutes: |
| 198 |
.P |
| 199 |
# tc filter add dev $DEV parent 1: handle 1 flow hash keys dst perturb 600 |
| 200 |
|
| 201 |
.SH SEE ALSO |
| 202 |
.BR tc (8), |
| 203 |
.BR tc-red (8), |
| 204 |
.BR tc-sfq (8) |
| 205 |
.SH SOURCES |
| 206 |
.TP |
| 207 |
o |
| 208 |
W. Feng, D. Kandlur, D. Saha, K. Shin, BLUE: A New Class of Active Queue Management Algorithms, |
| 209 |
U. Michigan CSE-TR-387-99, April 1999. |
| 210 |
|
| 211 |
.SH AUTHORS |
| 212 |
|
| 213 |
This SFB implementation was contributed by Juliusz Chroboczek and Eric Dumazet. |