]>
Commit | Line | Data |
---|---|---|
2587c01a FW |
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 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 sightly 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. |