| 1 |
.TH TC 8 "24 January 2012" "iproute2" "Linux" |
| 2 |
.SH NAME |
| 3 |
sfq \- Stochastic Fairness Queueing |
| 4 |
.SH SYNOPSIS |
| 5 |
.B tc qdisc ... |
| 6 |
.B [ divisor |
| 7 |
hashtablesize |
| 8 |
.B ] [ limit |
| 9 |
packets |
| 10 |
.B ] [ perturb |
| 11 |
seconds |
| 12 |
.B ] [ quantum |
| 13 |
bytes |
| 14 |
.B ] [ flows |
| 15 |
number |
| 16 |
.B ] [ depth |
| 17 |
number |
| 18 |
.B ] [ headdrop |
| 19 |
.B ] [ redflowlimit |
| 20 |
bytes |
| 21 |
.B ] [ min |
| 22 |
bytes |
| 23 |
.B ] [ max |
| 24 |
bytes |
| 25 |
.B ] [ avpkt |
| 26 |
bytes |
| 27 |
.B ] [ burst |
| 28 |
packets |
| 29 |
.B ] [ probability |
| 30 |
P |
| 31 |
.B ] [ ecn |
| 32 |
.B ] [ harddrop ] |
| 33 |
.SH DESCRIPTION |
| 34 |
|
| 35 |
Stochastic Fairness Queueing is a classless queueing discipline available for |
| 36 |
traffic control with the |
| 37 |
.BR tc (8) |
| 38 |
command. |
| 39 |
|
| 40 |
SFQ does not shape traffic but only schedules the transmission of packets, based on 'flows'. |
| 41 |
The goal is to ensure fairness so that each flow is able to send data in turn, thus preventing |
| 42 |
any single flow from drowning out the rest. |
| 43 |
|
| 44 |
This may in fact have some effect in mitigating a Denial of Service attempt. |
| 45 |
|
| 46 |
SFQ is work-conserving and therefore always delivers a packet if it has one available. |
| 47 |
.SH ALGORITHM |
| 48 |
On enqueueing, each packet is assigned to a hash bucket, based on the packets hash value. |
| 49 |
This hash value is either obtained from an external flow classifier (use |
| 50 |
.B |
| 51 |
tc filter |
| 52 |
to set them), or a default internal classifier if no external classifier has been configured. |
| 53 |
|
| 54 |
When the internal classifier is used, sfq uses |
| 55 |
.TP |
| 56 |
(i) |
| 57 |
Source address |
| 58 |
.TP |
| 59 |
(ii) |
| 60 |
Destination address |
| 61 |
.TP |
| 62 |
(iii) |
| 63 |
Source and Destination port |
| 64 |
.P |
| 65 |
If these are available. SFQ knows about ipv4 and ipv6 and also UDP, TCP and ESP. |
| 66 |
Packets with other protocols are hashed based on the 32bits representation of their |
| 67 |
destination and source. A flow corresponds mostly to a TCP/IP connection. |
| 68 |
|
| 69 |
Each of these buckets should represent a unique flow. Because multiple flows may |
| 70 |
get hashed to the same bucket, sfqs internal hashing algorithm may be perturbed at configurable |
| 71 |
intervals so that the unfairness lasts only for a short while. Perturbation may |
| 72 |
however cause some inadvertent packet reordering to occur. After linux-3.3, there is |
| 73 |
no packet reordering problem, but possible packet drops if rehashing hits one limit |
| 74 |
(number of flows or packets per flow) |
| 75 |
|
| 76 |
When dequeuing, each hashbucket with data is queried in a round robin fashion. |
| 77 |
|
| 78 |
Before linux-3.3, the compile time maximum length of the SFQ is 128 packets, which can be spread over |
| 79 |
at most 128 buckets of 1024 available. In case of overflow, tail-drop is performed |
| 80 |
on the fullest bucket, thus maintaining fairness. |
| 81 |
|
| 82 |
After linux-3.3, maximum length of SFQ is 65535 packets, and divisor limit is 65536. |
| 83 |
In case of overflow, tail-drop is performed on the fullest bucket, unless headdrop was requested. |
| 84 |
|
| 85 |
.SH PARAMETERS |
| 86 |
.TP |
| 87 |
divisor |
| 88 |
Can be used to set a different hash table size, available from kernel 2.6.39 onwards. |
| 89 |
The specified divisor must be a power of two and cannot be larger than 65536. |
| 90 |
Default value: 1024. |
| 91 |
.TP |
| 92 |
limit |
| 93 |
Upper limit of the SFQ. Can be used to reduce the default length of 127 packets. |
| 94 |
After linux-3.3, it can be raised. |
| 95 |
.TP |
| 96 |
depth |
| 97 |
Limit of packets per flow (after linux-3.3). Default to 127 and can be lowered. |
| 98 |
.TP |
| 99 |
perturb |
| 100 |
Interval in seconds for queue algorithm perturbation. Defaults to 0, which means that |
| 101 |
no perturbation occurs. Do not set too low for each perturbation may cause some packet |
| 102 |
reordering or losses. Advised value: 60 |
| 103 |
This value has no effect when external flow classification is used. |
| 104 |
Its better to increase divisor value to lower risk of hash collisions. |
| 105 |
.TP |
| 106 |
quantum |
| 107 |
Amount of bytes a flow is allowed to dequeue during a round of the round robin process. |
| 108 |
Defaults to the MTU of the interface which is also the advised value and the minimum value. |
| 109 |
.TP |
| 110 |
flows |
| 111 |
After linux-3.3, it is possible to change the default limit of flows. |
| 112 |
Default value is 127 |
| 113 |
.TP |
| 114 |
headdrop |
| 115 |
Default SFQ behavior is to perform tail-drop of packets from a flow. |
| 116 |
You can ask a headdrop instead, as this is known to provide a better feedback for TCP flows. |
| 117 |
.TP |
| 118 |
redflowlimit |
| 119 |
Configure the optional RED module on top of each SFQ flow. |
| 120 |
Random Early Detection principle is to perform packet marks or drops in a probabilistic way. |
| 121 |
(man tc-red for details about RED) |
| 122 |
.nf |
| 123 |
redflowlimit configures the hard limit on the real (not average) queue size per SFQ flow in bytes. |
| 124 |
.fi |
| 125 |
.TP |
| 126 |
min |
| 127 |
Average queue size at which marking becomes a possibility. Defaults to |
| 128 |
.B max |
| 129 |
/3 |
| 130 |
.TP |
| 131 |
max |
| 132 |
At this average queue size, the marking probability is maximal. Defaults to |
| 133 |
.B redflowlimit |
| 134 |
/4 |
| 135 |
.TP |
| 136 |
probability |
| 137 |
Maximum probability for marking, specified as a floating point number from 0.0 to 1.0. Default value is 0.02 |
| 138 |
.TP |
| 139 |
avpkt |
| 140 |
Specified in bytes. Used with burst to determine the time constant for average queue size calculations. Default value is 1000 |
| 141 |
.TP |
| 142 |
burst |
| 143 |
Used for determining how fast the average queue size is influenced by the real queue size. |
| 144 |
.nf |
| 145 |
Default value is : |
| 146 |
.B (2 * min + max) / (3 * avpkt) |
| 147 |
.fi |
| 148 |
.TP |
| 149 |
ecn |
| 150 |
RED can either 'mark' or 'drop'. Explicit Congestion |
| 151 |
Notification allows RED to notify remote hosts that their rate exceeds the |
| 152 |
amount of bandwidth available. Non-ECN capable hosts can only be notified by |
| 153 |
dropping a packet. If this parameter is specified, packets which indicate |
| 154 |
that their hosts honor ECN will only be marked and not dropped, unless the |
| 155 |
queue size hits |
| 156 |
.B depth |
| 157 |
packets. |
| 158 |
.TP |
| 159 |
harddrop |
| 160 |
If average flow queue size is above |
| 161 |
.B max |
| 162 |
bytes, this parameter forces a drop instead of ecn marking. |
| 163 |
.SH EXAMPLE & USAGE |
| 164 |
|
| 165 |
To attach to device ppp0: |
| 166 |
.P |
| 167 |
# tc qdisc add dev ppp0 root sfq |
| 168 |
.P |
| 169 |
Please note that SFQ, like all non-shaping (work-conserving) qdiscs, is only useful |
| 170 |
if it owns the queue. |
| 171 |
This is the case when the link speed equals the actually available bandwidth. This holds |
| 172 |
for regular phone modems, ISDN connections and direct non-switched ethernet links. |
| 173 |
.P |
| 174 |
Most often, cable modems and DSL devices do not fall into this category. The same holds |
| 175 |
for when connected to a switch and trying to send data to a congested segment also |
| 176 |
connected to the switch. |
| 177 |
.P |
| 178 |
In this case, the effective queue does not reside within Linux and is therefore not |
| 179 |
available for scheduling. |
| 180 |
.P |
| 181 |
Embed SFQ in a classful qdisc to make sure it owns the queue. |
| 182 |
|
| 183 |
It is possible to use external classifiers with sfq, for example to hash traffic based only |
| 184 |
on source/destination ip addresses: |
| 185 |
.P |
| 186 |
# tc filter add ... flow hash keys src,dst perturb 30 divisor 1024 |
| 187 |
.P |
| 188 |
Note that the given divisor should match the one used by sfq. If you have |
| 189 |
changed the sfq default of 1024, use the same value for the flow hash filter, too. |
| 190 |
|
| 191 |
.P |
| 192 |
Example of sfq with optional RED mode : |
| 193 |
.P |
| 194 |
# tc qdisc add dev eth0 parent 1:1 handle 10: sfq limit 3000 flows 512 divisor 16384 |
| 195 |
redflowlimit 100000 min 8000 max 60000 probability 0.20 ecn headdrop |
| 196 |
|
| 197 |
.SH SOURCE |
| 198 |
.TP |
| 199 |
o |
| 200 |
Paul E. McKenney "Stochastic Fairness Queuing", |
| 201 |
IEEE INFOCOMM'90 Proceedings, San Francisco, 1990. |
| 202 |
|
| 203 |
.TP |
| 204 |
o |
| 205 |
Paul E. McKenney "Stochastic Fairness Queuing", |
| 206 |
"Interworking: Research and Experience", v.2, 1991, p.113-131. |
| 207 |
|
| 208 |
.TP |
| 209 |
o |
| 210 |
See also: |
| 211 |
M. Shreedhar and George Varghese "Efficient Fair |
| 212 |
Queuing using Deficit Round Robin", Proc. SIGCOMM 95. |
| 213 |
|
| 214 |
.SH SEE ALSO |
| 215 |
.BR tc (8), |
| 216 |
.BR tc-red (8) |
| 217 |
|
| 218 |
.SH AUTHORS |
| 219 |
Alexey N. Kuznetsov, <[email protected]>, |
| 220 |
Eric Dumazet <[email protected]>. |
| 221 |
.P |
| 222 |
This manpage maintained by bert hubert <[email protected]> |