TC(8)

🎀 sfq: Stochastic Fairness Queueing 🎀

manual for Linux, filed under tc(8) 💅

✨ NAME ✨

sfq is Stochastic Fairness Queueing 💖. It's a classless queueing discipline you can use with the tc(8) command. Iconic, right?

🧚 SYNOPSIS 🧚

tc qdisc ...  [ divisor hashtablesize ] [ limit packets ] [ perturb
seconds ] [ quantum bytes ] [ flows number ] [ depth number ] [ headdrop
] [ redflowlimit bytes ] [ min bytes ] [ max bytes ] [ avpkt bytes ] [
burst packets ] [ probability P ] [ ecn ] [ harddrop ]

🌸 DESCRIPTION 🌸

okay so SFQ doesn't shape your traffic 🙈. It only decides the order packets get sent in, based on flows. The whole goal is fairness: every flow gets its turn to send data, so no single flow can hog the link and drown out everybody else. Main character energy for every connection 👑.

This may actually help a bit against a Denial of Service attempt. Not a full fix, but it's giving protection 🛡️.

SFQ is work-conserving, which means it always sends a packet if it has one ready to go. No waiting around, no cap 🔥.

🦋 ALGORITHM 🦋

When a packet gets enqueued, it's dropped into a hash bucket based on its hash value. That hash value comes from either an external flow classifier (you set those up with tc filter) or a default internal classifier, if you haven't configured an external one.

When SFQ uses the internal classifier, it looks at:

• (i) Source address
• (ii) Destination address
• (iii) Source and Destination port

...as long as those are available. SFQ knows about IPv4 and IPv6, plus UDP, TCP and ESP. Packets with other protocols get hashed based on the 32bits representation of their destination and source. A flow mostly means one TCP/IP connection 🧵.

Each bucket is supposed to hold one unique flow 💜. Multiple flows can land in the same bucket, though, so SFQ's internal hash can be perturbed at set intervals. That way the unfairness only lasts a little while. Perturbation can cause some accidental packet reordering, though 😭. After linux-3.3 there's no reordering problem anymore, but packets can get dropped if rehashing runs into a limit (number of flows or packets per flow).

When dequeuing, every hash bucket that has data gets checked in a round robin fashion 🔁.

Before linux-3.3, the compile time maximum length of SFQ is 128 packets. Those can be spread over at most 128 buckets, out of 1024 available. If it overflows, tail-drop happens on the fullest bucket, which keeps things fair ⚖️.

After linux-3.3, the maximum length of SFQ is 65535 packets, and the divisor limit is 65536. On overflow, tail-drop happens on the fullest bucket, unless headdrop was requested ✨.

💅 PARAMETERS 💅

• divisor — Lets you pick a different hash table size, available from kernel 2.6.39 onwards. The divisor must be a power of two and can't be bigger than 65536. Default: 1024 🎀.
• limit — The upper limit of the SFQ. Use it to shrink the default length of 127 packets. After linux-3.3, you can raise it too 📈.
• depth — Limit of packets per flow (after linux-3.3). It defaults to 127, and you can lower it 🧘.
• perturb — The interval in seconds for queue algorithm perturbation. It defaults to 0, which means no perturbation at all 🙅‍♀️. Don't set it too low, because each perturbation can cause some packet reordering or losses 😬. Advised value: 60. This value has no effect when external flow classification is used. It's better to increase the divisor value to lower the risk of hash collisions 💡.
• quantum — The amount of bytes a flow is allowed to dequeue during one round of the round robin process. It defaults to the MTU of the interface, which is also the advised value and the minimum value 📦.
• flows — After linux-3.3, you can change the default limit of flows. The default value is 127 🌈.
• headdrop — By default SFQ tail-drops packets from a flow. You can ask for a headdrop instead, which is known to give better feedback for TCP flows 🫶.
• redflowlimit — Configures the optional RED module on top of each SFQ flow. RED works by marking or dropping packets in a probabilistic way 🎲. (Check man tc-red for the deets about RED 📖.) redflowlimit sets the hard limit on the real (not average) queue size per SFQ flow, in bytes 🧱.
• min — The average queue size at which marking becomes a possibility. Defaults to max /3 🌤️.
• max — At this average queue size, the marking probability is maximal 🔝. Defaults to redflowlimit /4.
• probability — The maximum probability for marking, given as a floating point number from 0.0 to 1.0. Default value is 0.02 🎯.
• avpkt — Specified in bytes. Used together with burst to determine the time constant for average queue size calculations ⏱️. Default value is 1000.
• burst — Decides how fast the average queue size gets influenced by the real queue size 🏃‍♀️. Default value is (2 * min + max) / (3 * avpkt).
• ecn — RED can either mark or drop 🏷️. Explicit Congestion Notification lets RED tell remote hosts that their rate is more than the bandwidth available. Non-ECN capable hosts can only be told this by dropping a packet 🙃. If you specify this parameter, packets from hosts that honor ECN will only get marked and not dropped, unless the queue size hits depth packets 🤝.
• harddrop — If the average flow queue size is above max bytes, this parameter forces a drop instead of ECN marking 💀.

🍓 EXAMPLE & USAGE 🍓

To attach to device ppp0:

# tc qdisc add dev ppp0 root sfq

Please note that SFQ, like all non-shaping (work-conserving) qdiscs, is only useful if it owns the queue ‼️. That's the case when the link speed equals the bandwidth that's actually available. This holds for regular phone modems, ISDN connections and direct non-switched ethernet links.

Most of the time, cable modems and DSL devices don't fall into this category 😩. Same goes for when you're connected to a switch and trying to send data to a congested segment that's also connected to the switch.

In that case, the effective queue doesn't live inside Linux, so it isn't available for scheduling 🫠.

To make sure it owns the queue, embed SFQ in a classful qdisc 🧩.

You can use external classifiers with SFQ, for example to hash traffic based only on source/destination IP addresses:

# tc filter add ... flow hash keys src,dst perturb 30 divisor 1024

Note that the given divisor should match the one used by SFQ. If you changed the SFQ default of 1024, use the same value for the flow hash filter too ⚠️.

Example of SFQ with optional RED mode:

# tc qdisc add dev eth0 parent 1:1 handle 10: sfq limit 3000 flows 512
divisor 16384
  redflowlimit 100000 min 8000 max 60000 probability 0.20 ecn headdrop

📚 SOURCE 📚

• Paul E. McKenney "Stochastic Fairness Queuing", IEEE INFOCOMM'90 Proceedings, San Francisco, 1990.
• Paul E. McKenney "Stochastic Fairness Queuing", "Interworking: Research and Experience", v.2, 1991, p.113-131.
• See also: M. Shreedhar and George Varghese "Efficient Fair Queuing using Deficit Round Robin", Proc. SIGCOMM 95.

🫧 SEE ALSO 🫧

tc(8), tc-red(8)

👩‍💻 AUTHORS 👩‍💻

Alexey N. Kuznetsov, <kuznet@ms2.inr.ac.ru>, Eric Dumazet <eric.dumazet@gmail.com>.

This manpage is maintained by bert hubert <ahu@ds9a.nl> 🌷.

bestie, that's the whole sfq tea 🌈💖 iproute2 · 24 January 2012 · TC(8) 🦋✨