| .TH SFB 8 "August 2011" "iproute2" "Linux" | |
| .SH NAME | |
| sfb \- Stochastic Fair Blue | |
| .SH SYNOPSIS | |
| .B tc qdisc ... blue | |
| .B rehash | |
| milliseconds | |
| .B db | |
| milliseconds | |
| .B limit | |
| packets | |
| .B max | |
| packets | |
| .B target | |
| packets | |
| .B increment | |
| float | |
| .B decrement | |
| float | |
| .B penalty_rate | |
| packets per second | |
| .B penalty_burst | |
| packets | |
| .SH 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. | |
| .SH ALGORITHM | |
| The | |
| .B 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 | |
| .B 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 | |
| .B penalty_rate | |
| packets per second. | |
| .SH 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. | |
| .SH PARAMETERS | |
| .TP | |
| 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. | |
| .TP | |
| 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 | |
| .B | |
| rehash. | |
| .TP | |
| 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. | |
| .TP | |
| max | |
| Maximum length of a buckets queue, in packets, before packets start being | |
| dropped. Should be sightly larger than | |
| .B target | |
| , but should not be set to values exceeding 1.5 times that of | |
| .B target . | |
| Defaults to 25. | |
| .TP | |
| target | |
| The desired average bin length. If the bin queue length reaches this value, | |
| the marking probability is increased by | |
| .B increment. | |
| The default value depends on the | |
| .B max | |
| setting, with max set to 25 | |
| .B target | |
| will default to 20. | |
| .TP | |
| 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. | |
| .TP | |
| 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. | |
| .TP | |
| 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. | |
| .TP | |
| penalty_burst | |
| The number of packets a flow is permitted to exceed the penalty rate before packets | |
| start being dropped. | |
| Defaults to 20 packets. | |
| .SH STATISTICS | |
| This qdisc exposes additional statistics via 'tc -s qdisc' output. | |
| These are: | |
| .TP | |
| earlydrop | |
| The number of packets dropped before a per-flow queue was full. | |
| .TP | |
| 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. | |
| .TP | |
| 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. | |
| .TP | |
| queuedrop | |
| The number of packets dropped due to reaching limit. This should normally be 0. | |
| .TP | |
| marked | |
| The number of packets marked with ECN. | |
| .TP | |
| maxqlen | |
| The length of the current longest per-flow (virtual) queue. | |
| .TP | |
| maxprob | |
| The maximum per-flow drop probability. 1 means that some | |
| flows have been detected as non-reactive. | |
| .SH 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. | |
| .SH EXAMPLE & USAGE | |
| To attach to interface $DEV, using default options: | |
| .P | |
| # 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: | |
| .P | |
| # tc filter add dev $DEV parent 1: handle 1 flow hash keys dst perturb 600 | |
| .SH SEE ALSO | |
| .BR tc (8), | |
| .BR tc-red (8), | |
| .BR tc-sfq (8) | |
| .SH SOURCES | |
| .TP | |
| 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. | |
| .SH AUTHORS | |
| This SFB implementation was contributed by Juliusz Chroboczek and Eric Dumazet. |