TC-HFSC(7)

💖 TC-HFSC(7) 💖

Okay bestie, this is the manual page for tc-hfsc(7), and it's giving Linux 🐧✨

🎀 NAME 🎀

tc-hfcs - Hierarchical Fair Service Curve 🌸

📜 HISTORY & INTRODUCTION 📜

So HFSC (Hierarchical Fair Service Curve) is a network packet scheduling algorithm that was first presented at SIGCOMM'97. It was developed as part of ALTQ (ALTernative Queuing) on NetBSD, then it quickly found its way to other BSD systems, and a few years ago it became part of the linux kernel 🐧. Still, it's not the most popular scheduling algorithm, especially compared to HTB, and it's not well documented for the enduser 😭. This intro is here to explain how HFSC works without using too much math (although some math is inevitable, sorry not sorry 🙈).

Okay so, in short, HFSC aims to:

1. guarantee precise bandwidth and delay allocation for all leaf classes (realtime criterion) 💅
2. allocate excess bandwidth fairly as specified by class hierarchy (linkshare & upperlimit criterion) 👑
3. minimize any discrepancy between the service curve and the actual amount of service provided during linksharing 🫶

The main "selling" point of HFSC is feature (1), and it's achieved by using nonlinear service curves (more on what those actually are later ✨). This is particularly useful in VoIP or games, where you don't just want consistent bandwidth, you also want to limit the initial delay of a data stream 🎮. Note that it only matters for leaf classes (where the actual queues are), so class hierarchy is ignored in the realtime case 🙈.

Feature (2) is, like, obvious. Any algorithm featuring class hierarchy (such as HTB) strives to achieve that 💅. HFSC does it well, although you might end up in unusual situations if you define service curves carelessly. See section CORNER CASES for examples 💀.

Feature (3) is mentioned because of the nature of the problem 🧚. There may be situations where it's either not possible to guarantee service of all curves at the same time, and/or it's impossible to do so fairly. Both will be explained later. Note that this is mainly related to interior (aka aggregate) classes, since the leafs are already handled by (1). Still, it's perfectly possible to create a leaf class without realtime service, and in that case the caveats will naturally extend to leaf classes as well 🌈.

🔤 ABBREVIATIONS 🔤

For the rest of the document, we'll be using these shortcuts:

• RT - realtime
• LS - linkshare
• UL - upperlimit
• SC - service curve

🦋 BASICS OF HFSC 🦋

To understand how HFSC works, we first need to introduce a service curve 🍓. Overall, it's a nondecreasing function of some time unit, returning the amount of service (an allowed or allocated amount of bandwidth) at some specific point in time. The purpose of it should be subconsciously obvious: if a class was allowed to transfer not less than the amount specified by its service curve, then the service curve is not violated ✨.

Still, we need a more elaborate criterion than just the above (although in the most generic case it can be reduced to it). The criterion has to take two things into account:

• idling periods 😴
• the ability to "look back". So if during the current active period the service curve is violated, maybe it isn't, if we count excess bandwidth received during earlier active period(s) 🔙

Let's define the criterion like this:

(1) For each t1, there must exist t0 in set B, so S(t1-t0) <= w(t0,t1)

Here w denotes the amount of service received during some time period between t0 and t1. B is a set of all times where a session becomes active after an idling period (further denoted as "becoming backlogged"). For a clearer picture, imagine two situations:

• a) our session was active during two periods, with a small time gap between them 🤏
• b) as in (a), but with a larger gap 🌌

Consider (a). If the service received during both periods meets (1), then all is well. But what if it doesn't do so during the 2nd period? If the amount of service received during the 1st period is larger than the service curve, then it might compensate for smaller service during the 2nd period and the gap, if the gap is small enough 🫠.

If the gap is larger (b), then it's less likely to happen (unless the excess bandwidth allocated during the 1st part was really large). Still, the larger the gap, the less interesting what happened in the past is (e.g. 10 minutes ago). What matters is the current traffic that just started 💜.

From HFSC's perspective, the more interesting question is this: when should we start transferring packets so that a service curve of a class is not violated? Or, rephrasing it: how much X() amount of service should a session receive by time t so the service curve is not violated? The function X(), defined below, is the basic building block of HFSC. It's used in: eligible, deadline, virtual-time and fit-time curves. Of course, X() is based on equation (1) and is defined recursively 🧠:

• At the 1st backlogged period beginning, function X is initialized to the generic service curve assigned to a class 🌱.
• At any subsequent backlogged period, X() is:

min(X() from previous period ; w(t0)+S(t-t0) for t>=t0)

... where t0 denotes the beginning of the current backlogged period.

HFSC uses either linear or two-piece linear service curves. In case of linear or two-piece linear convex functions (first slope < second slope), the min() in X's definition reduces to the 2nd argument. But in case of two-piece concave functions, the 1st argument might quickly become lesser for some t>=t0 🙃. Note that for some backlogged period, X() is defined only from that period's beginning. We also define X^(-1)(w) as the smallest t>=t0 for which X(t) = w. We have to define it this way, as X() is usually not an injection 🤓.

The above generic X() can be one of the following:

• E(): In the realtime criterion, selects packets eligible for sending. If none are eligible, HFSC will use the linkshare criterion. Eligible time et is calculated with reference to packets' heads (et = E^(-1)(w)). It's based on the RT service curve, but in case of a convex curve, it uses its 2nd slope only 🚀.
• D(): In the realtime criterion, selects the most suitable packet from the ones chosen by E(). Deadline time dt corresponds to packets' tails (dt = D^(-1)(w+l), where l is the packet's length). Based on the RT service curve 🎯.
• V(): In the linkshare criterion, arbitrates which packet to send next. Note that V() is a function of a virtual time (see LINKSHARE CRITERION section for details ✨). Virtual time vt corresponds to packets' heads (vt = V^(-1)(w)). Based on the LS service curve 🌷.
• F(): An extension to the linkshare criterion, used to limit the speed at which the linkshare criterion is allowed to dequeue. Fit-time ft corresponds to packets' heads as well (ft = F^(-1)(w)). Based on the UL service curve 🛑.

Be sure to make a clean distinction between a session's RT, LS and UL service curves and the above "utility" functions. Bestie, don't mix them up 🙅‍♀️💕.

⏰ REALTIME CRITERION ⏰

RT criterion ignores class hierarchy and guarantees precise bandwidth and delay allocation 💎. We say that a packet is eligible for sending when the current real time is later than the eligible time of the packet. From all eligible packets, the one most suited for sending is the one with the shortest deadline time. This sounds simple, but consider the following example 👀:

Interface 10Mbit, two classes, both with two-piece linear service curves:

• 1st class - 2Mbit for 100ms, then 7Mbit (convex - 1st slope < 2nd slope) 📈
• 2nd class - 7Mbit for 100ms, then 2Mbit (concave - 1st slope > 2nd slope) 📉

Assume for a moment that we only use D() for both finding eligible packets and choosing the most fitting one. Thus eligible time would be computed as D^(-1)(w) and deadline time would be computed as D^(-1)(w+l). If the 2nd class starts sending packets 1 second after the 1st class, it's of course impossible to guarantee 14Mbit, as the interface capability is only 10Mbit. 😱 The only workaround in this scenario is to allow the 1st class to send packets earlier than would normally be allowed. That's where a separate E() comes to help 🦸‍♀️. Putting all the math aside (see HFSC paper for details), E() for an RT concave service curve is just like D(), but for an RT convex service curve, it's constructed using only the RT service curve's 2nd slope (in our example, 7Mbit) 💅.

The effect of such E() is that packets will be sent earlier, and at the same time D() will be updated, so the current deadline time calculated from it will be later. Thus, when the 2nd class starts sending packets later, both the 1st and the 2nd class will be eligible, but the 2nd session's deadline time will be smaller, so its packets will be sent first 🏃‍♀️💨. When the 1st class becomes idle at some later point, the 2nd class will be able to "buffer" up again for the later active period of the 1st class 🧺.

A short remark: in a situation where the total amount of bandwidth available on the interface is larger than the allocated total realtime parts (imagine a 10 Mbit interface, but 1Mbit/2Mbit and 2Mbit/1Mbit classes), the sole speed of the interface could suffice to guarantee the times 🌈.

An important part of the RT criterion is that, apart from updating its D() and E(), the V() used by the LS criterion is also updated 🧩. Generally the RT criterion is secondary to the LS one, and it's used only if there's a risk of violating precise realtime requirements. Still, the "participation" in bandwidth distributed by the LS criterion is there, so V() has to be updated along the way. The LS criterion can then properly compensate for a non-ideal fair sharing situation caused by RT scheduling 🫶. If you use a UL service curve, its F() will be updated as well (the UL service curve is an extension to the LS one, see UPPERLIMIT CRITERION section 🔝).

Anyway, careless specification of LS and RT service curves can lead to potentially undesired situations (see CORNER CASES for examples 🙈). This wasn't the case in the HFSC paper, where LS and RT service curves couldn't be specified separately 📄✨.

💖 LINKSHARING CRITERION 💖

okay so the LS criterion is basically the bandwidth fairy 🧚 its whole job is to hand out bandwidth according to your class hierarchy. Unlike RT, it doesn't compare real time against virtual time at all. It just looks at the virtual times of all the active subclasses and picks the one with the smallest vt to get scheduled. ✨

Here's the big takeaway: absolute values don't matter, only the ratios between them 🎀 So two children with plain linear 1Mbit service curves get exactly the same treatment from LS as two children with 5Mbit curves. Same vibe, different numbers. The other thing that's lowkey iconic is that in a perfectly fluid system with linear curves, every virtual time across the whole class hierarchy ends up equal 🦋

Why is VC defined in terms of virtual time, though? And what even is it? 🤔

Picture this: class A has two children, A1 and A2, both with 10Mbit SCs. If A2 is idle, A1 gets all of A's bandwidth, and its V() updates along the way. Now A2 becomes active. A1's virtual time is already way ahead of A2's, and since LS only cares about picking the smallest vt, A1 would just sit there idle for ages 😭 The fix is to adjust the virtual time of the class that's becoming active, basically getting it "up to date". HFSC takes the mean of the smallest and the biggest virtual time of the currently active children that are fit for sending. Since it's no longer real time (unless every class goes active at the same time and never goes idle, which is the trivial case), it gets called virtual time ✨

Ngl this approach has a price though 💀 The problem is basically the same one from the last section, and it comes from the non-linearity of service curves:

1. Either it's impossible to guarantee service curves and keep fairness during certain time periods.

Remember the RT example, slightly tweaked with 3Mbit slopes instead of 2Mbit ones:

• 1st class: 3Mbit for 100ms, then 7Mbit (convex, since 1st slope < 2nd slope) 💅
• 2nd class: 7Mbit for 100ms, then 3Mbit (concave, since 1st slope > 2nd slope) 💅

They add up perfectly to 10Mbit, the interface's capacity 🙌 But if you wanted to use only LS for guarantees and fairness, it just won't work. In the LS context, only V() gets used to decide which class to schedule. If the 2nd class becomes active while the 1st one is in its second slope, fairness is preserved (the ratio is 1:1, so 7Mbit:7Mbit), but LS can't guarantee the absolute values themselves. It would have to go beyond what the interface can handle, and that's not happening 🙅‍♀️

2. And/or it's impossible to guarantee the service curves of all classes at the same time, fairly or not.

This one is similar but a bit more sneaky 👀 Let's look at two subtrees, arbitrated by their common parent (the root here):

R (root) - 10Mbit

A  - 7Mbit, then 3Mbit
A1 - 5Mbit, then 2Mbit
A2 - 2Mbit, then 1Mbit

B  - 3Mbit, then 7Mbit

R arbitrates between the left subtree (A) and the right one (B). Assume A2 and B are constantly backlogged, and at some later point A1 becomes backlogged too (once all the other classes are in their 2nd linear part).

So what happens? B, the choice R makes, always gets 7Mbit, because R only cares about the ratio between its direct children 🙄 That leaves the A subtree with 3Mbit, but its children would want 5Mbit + 1Mbit at the moment A1 became backlogged. That's obviously impossible, since they can only share 3Mbit because of the interface limit 😤

In the left subtree we get the same situation as before: a fair split between A1 and A2, but the guarantees are violated. In the whole tree there's no fairness either (B got 7Mbit, while A1 and A2 have to squeeze into 3Mbit), and no guarantees for all classes (only B got what it wanted). Even if we broke fairness inside the A subtree and set A2's service curve to 0, A1 still wouldn't get the bandwidth it needs 😭

---

🦋 UPPERLIMIT CRITERION 🦋

the UL criterion is an extension to LS that only lets packets get sent when the current real time is later than the fit-time (ft) 🎀 So the modified LS criterion becomes: pick the smallest virtual time from all active children, such that fit-time < current real time also holds. The fit-time comes from F(), which is based on the UL service curve. You'll notice its role is kinda similar to E() in the RT criterion 🥰 And for obvious reasons, you can't specify a UL service curve without an LS one. No UL without LS, bestie 🙅‍♀️

The main purpose of the UL service curve is to keep HFSC within the bandwidth available on the upstream router 🏠 Think of an ADSL home modem/router, plus a Linux server acting as NAT/firewall/etc. with a 100Mbit+ connection to that modem/router. Usually you make a single class directly under root, set a linear UL service curve to the available bandwidth, and then build your whole class structure downwards from there 💅 You're also free to add a UL service curve (linear or not) to any class that has an LS criterion.

Here's the important part: whenever a class doesn't qualify for linksharing because of its fit-time, the next time it does qualify, it updates its virtual time to the smallest virtual time of all active children that are fit for linksharing ✨ This keeps one of the main goals of the LS criterion alive, which is equality of all virtual times across the whole hierarchy (in a perfectly fluid system with only linear curves, all virtual times would be equal).

Without that, vt would lag behind the other virtual times, and that causes problems 😬 Consider an interface with 10Mbit capacity and these leaf classes (just in case you're skimming, this example shows behaviour that does not happen):

A - ls 5.0Mbit
B - ls 2.5Mbit
C - ls 2.5Mbit, ul 2.5Mbit

If B is idle while A and C are constantly backlogged, A and C would normally (as far as the LS criterion is concerned) split bandwidth in a 2:1 ratio. But because of the UL service curve on C, C gets at most 2.5Mbit, and A gets the remaining 7.5Mbit 💀 The longer the backlogged period goes on, the further the virtual times of A and C drift apart. If B becomes backlogged at some later point, its virtual time gets set to (A's vt + C's vt)/2, which blocks A from sending any traffic until B's virtual time catches up with A's 🙈

---

🌸 SEPARATE LS / RT SCs 🌸

Another difference from the original HFSC paper: RT and LS SCs can be specified separately 🎀 On top of that, leaf classes are allowed to have only an RT SC or only an LS SC. For interior classes, only LS SCs make sense, so any RT SC gets ignored on them 🙃

---

💀 CORNER CASES 💀

Separate service curves for the LS and RT criteria can lead to some traps that come from the "fighting" between ideal linksharing and enforced realtime guarantees 😤 The original HFSC paper didn't have these situations, because it never talked about specifying separate LS and RT service curves.

Consider an interface with 10Mbit capacity and these leaf classes:

A - ls 5.0Mbit, rt 8Mbit
B - ls 2.5Mbit
C - ls 2.5Mbit

Imagine A and C are constantly backlogged. Since B is idle, A and C would split bandwidth 2:1 according to the LS service curve (so in theory, 6.66 and 3.33). But RT takes priority, so A gets 8Mbit, and LS can only compensate class C for 2 Mbit. That creates a discrepancy between the virtual times of A and C 😭

Now suppose this goes on for a long time with no idle periods, and then B suddenly becomes active. B's virtual time gets updated to (A's vt + C's vt)/2, which lands it right between A's and C's virtual times. The result? B has no RT guarantees, so it gets punished and isn't allowed to transfer until C's virtual time catches up 💔

If the interface had a higher capacity, say 100Mbit, this example would behave perfectly fine 🌈

Let's look closer, because the example above "cleverly" breaks one of the basic goals of the LS criterion, which is equality of all virtual times across the class hierarchy. Leaf classes without RT service curves are basically left to their own fate, governed by messed-up virtual times 😵

It also doesn't really make sense. Class A is always guaranteed up to 8Mbit, which is more than any absolute bandwidth that could come from its LS criterion (except the trivial case where only A is active). If the bandwidth A takes is smaller than the absolute value from the LS criterion, the unused part gets automatically given to the other active classes, since A has idle periods in that case ✨ The only "advantage" is that even with low average bandwidth, bursts get handled at the speed defined by the RT criterion. Still, if you need extra speed (e.g. because of latency), non-linear service curves should be used instead 🫶

In other words: the LS criterion is meaningless in the example above 💅

You can "workaround" it by making sure every leaf class has an RT service curve assigned, which guarantees all of them will get some bandwidth. It doesn't make the setup any more valid though 🙄

Keep in mind: if you use non-linear curves and the irregularities explained above only happen in the first segment, then there's little wrong with "overusing" the RT curve a bit:

A - ls 5.0Mbit, rt 9Mbit/30ms, then 1Mbit
B - ls 2.5Mbit
C - ls 2.5Mbit

Here, the vt of A will "spike" during the initial period, but after that A will never get more than 1Mbit until B and C catch up. Then everything goes back to normal 🌸✨

✨ LINUX AND TIMER RESOLUTION ✨

okay so the scheduler can throttle itself 😭 and set up a so-called watchdog to wake up the dequeue function at some time later. For HFSC that happens when, for example, no packet is eligible for scheduling and a UL service curve is limiting how fast the LS criterion is allowed to dequeue packets. It's called throttling, and how accurate it is depends on how the kernel was compiled 🧚

there're 3 important options in modern kernels when it comes to timer resolution: tickless system, high resolution timer support and timer frequency 💖

if you have tickless system enabled, the timer interrupt triggers as slowly as possible, but each time the scheduler throttles itself (or any other part of the kernel needs better accuracy), the rate gets bumped up as needed / possible. the ceiling is either timer frequency if high resolution timer support isn't available or isn't compiled in, or it's hardware dependent and can go far beyond the highest timer frequency setting available 🚀

if tickless system is NOT enabled, the timer fires at a fixed rate set by timer frequency, regardless of whether high resolution timers are or aren't available 🙈

keep these settings in mind, bestie, because a scenario like: no tickless, no HR timers, frequency set to 100hz gives throttling accuracy of 10ms. It doesn't automatically mean you'd be limited to ~0.8Mbit/s (assuming packets at ~1KB), as long as your queues are prepared to cover for timer inaccuracy. Of course, for e.g. locally generated UDP traffic, an appropriate socket size is needed as well. Quick example to make it click (assume hardcore anti-schedule settings: HZ=100, no HR timers, no tickless):

tc qdisc add dev eth0 root handle 1:0 hfsc default 1
tc class add dev eth0 parent 1:0 classid 1:1 hfsc rt m2 10Mbit

Assuming ~1KB packets and HZ=100, that averages to ~0.8Mbit. Anything beyond it (e.g. the example above with a specified rate over 10x larger) will require appropriate queuing and cause bursts every ~10 ms. As you can imagine, any HFSC's RT guarantees will be seriously invalidated by that 💀. The example above is mainly important if you deal with old hardware, as is particularly popular for home server chores. Even then, you can easily set HZ=1000 and have very accurate scheduling for typical ADSL speeds ✨

anything modern (apic or even hpet msi based timers + tickless system) will provide enough accuracy for superb 1Gbit scheduling. For example, on one of my cheap dual-core AMD boards I have the following settings 🔥:

tc qdisc add dev eth0 parent root handle 1:0 hfsc default 1
tc class add dev eth0 parent 1:0 classid 1:1 hfsc rt m2 300mbit

And a simple:

nc -u dst.host.com 54321 </dev/zero
nc -l -p 54321 >/dev/null

...will yield the following effects over a period of ~10 seconds (taken from /proc/interrupts):

319: 42124229   0  HPET_MSI-edge  hpet2 (before)
319: 42436214   0  HPET_MSI-edge  hpet2 (after 10s.)

That's roughly 31000/s 😳. Now compare it with HZ=1000. The obvious drawback of it is that CPU load can be rather high from servicing that many timer interrupts. The example with 300Mbit RT service curve on 1Gbit link is particularly ugly, as it requires a lot of throttling with minuscule delays 🥲

Also note that it's just an example showing the capabilities of current hardware. The above example (essentially a 300Mbit TBF emulator) is pointless on an internal interface to begin with: you will pretty much always want a regular LS service curve there, and in such a scenario HFSC simply doesn't throttle at all 🙄

300Mbit RT service curve (selected columns from mpstat -P ALL 1):

10:56:43 PM  CPU  %sys     %irq   %soft   %idle
10:56:44 PM  all  20.10    6.53   34.67   37.19
10:56:44 PM    0  35.00    0.00   63.00    0.00
10:56:44 PM    1   4.95   12.87    6.93   73.27

So, in the rare case you need those speeds with only an RT service curve, or with a UL service curve: remember the drawbacks 🫶

✨ CAVEAT: RANDOM ONLINE EXAMPLES ✨

for reasons unknown (though well guessed), many examples you can google love to overuse UL criterion and stuff it in every node possible. This makes no sense and works against what HFSC tries to do (and does pretty damn well) 💅. Use UL where it makes sense: on the uppermost node to match upstream router's uplink capacity. Or in special cases, such as testing (limit certain subtree to some speed), or customers that must never get more than certain speed. In the last case you can usually achieve the same by just using a RT criterion without LS+UL on leaf nodes.

As for the router case, remember it's good to differentiate between "traffic to router" (remote console, web config, etc.) and "outgoing traffic", so for example:

tc qdisc add dev eth0 root handle 1:0 hfsc default 0x8002
tc class add dev eth0 parent 1:0 classid 1:999 hfsc rt m2 50Mbit
tc class add dev eth0 parent 1:0 classid 1:1 hfsc ls m2 2Mbit ul m2 2Mbit

... so "internet" tree under 1:1 and "router itself" as 1:999 🌸

✨ LAYER2 ADAPTATION ✨

Please refer to tc-stab(8) 🦋

✨ SEE ALSO ✨

tc(8), tc-hfsc(8), tc-stab(8) 🧚

Please direct bugreports and patches to: <netdev@vger.kernel.org> 🐛

✨ AUTHOR ✨

Manpage created by Michal Soltys (soltys@ziu.info) 👑

---

that's a wrap, bestie!! 🌈 iproute2, 31 October 2011, TC-HFSC(7) 💜 slay forever 💅✨