| 1 |
.TH "TC\-HFSC" 7 "31 October 2011" iproute2 Linux |
| 2 |
.SH "NAME" |
| 3 |
tc-hfcs \- Hierarchical Fair Service Curve |
| 4 |
. |
| 5 |
.SH "HISTORY & INTRODUCTION" |
| 6 |
. |
| 7 |
HFSC (Hierarchical Fair Service Curve) is a network packet scheduling algorithm that was first presented at |
| 8 |
SIGCOMM'97. Developed as a part of ALTQ (ALTernative Queuing) on NetBSD, found |
| 9 |
its way quickly to other BSD systems, and then a few years ago became part of |
| 10 |
the linux kernel. Still, it's not the most popular scheduling algorithm \- |
| 11 |
especially if compared to HTB \- and it's not well documented for the enduser. This introduction aims to explain how HFSC works without using |
| 12 |
too much math (although some math it will be |
| 13 |
inevitable). |
| 14 |
|
| 15 |
In short HFSC aims to: |
| 16 |
. |
| 17 |
.RS 4 |
| 18 |
.IP \fB1)\fR 4 |
| 19 |
guarantee precise bandwidth and delay allocation for all leaf classes (realtime |
| 20 |
criterion) |
| 21 |
.IP \fB2)\fR |
| 22 |
allocate excess bandwidth fairly as specified by class hierarchy (linkshare & |
| 23 |
upperlimit criterion) |
| 24 |
.IP \fB3)\fR |
| 25 |
minimize any discrepancy between the service curve and the actual amount of |
| 26 |
service provided during linksharing |
| 27 |
.RE |
| 28 |
.PP |
| 29 |
. |
| 30 |
The main "selling" point of HFSC is feature \fB(1)\fR, which is achieved by |
| 31 |
using nonlinear service curves (more about what it actually is later). This is |
| 32 |
particularly useful in VoIP or games, where not only a guarantee of consistent |
| 33 |
bandwidth is important, but also limiting the initial delay of a data stream. Note that |
| 34 |
it matters only for leaf classes (where the actual queues are) \- thus class |
| 35 |
hierarchy is ignored in the realtime case. |
| 36 |
|
| 37 |
Feature \fB(2)\fR is well, obvious \- any algorithm featuring class hierarchy |
| 38 |
(such as HTB) strives to achieve that. HFSC does that well, although |
| 39 |
you might end with unusual situations, if you define service curves carelessly |
| 40 |
\- see section CORNER CASES for examples. |
| 41 |
|
| 42 |
Feature \fB(3)\fR is mentioned due to the nature of the problem. There may be |
| 43 |
situations where it's either not possible to guarantee service of all curves at |
| 44 |
the same time, and/or it's impossible to do so fairly. Both will be explained |
| 45 |
later. Note that this is mainly related to interior (aka aggregate) classes, as |
| 46 |
the leafs are already handled by \fB(1)\fR. Still, it's perfectly possible to |
| 47 |
create a leaf class without realtime service, and in such a case the caveats will |
| 48 |
naturally extend to leaf classes as well. |
| 49 |
|
| 50 |
.SH ABBREVIATIONS |
| 51 |
For the remaining part of the document, we'll use following shortcuts: |
| 52 |
.nf |
| 53 |
.RS 4 |
| 54 |
|
| 55 |
RT \- realtime |
| 56 |
LS \- linkshare |
| 57 |
UL \- upperlimit |
| 58 |
SC \- service curve |
| 59 |
.RE |
| 60 |
.fi |
| 61 |
. |
| 62 |
.SH "BASICS OF HFSC" |
| 63 |
. |
| 64 |
To understand how HFSC works, we must first introduce a service curve. |
| 65 |
Overall, it's a nondecreasing function of some time unit, returning the amount |
| 66 |
of |
| 67 |
service (an allowed or allocated amount of bandwidth) at some specific point in |
| 68 |
time. The purpose of it should be subconsciously obvious: if a class was |
| 69 |
allowed to transfer not less than the amount specified by its service curve, |
| 70 |
then the service curve is not violated. |
| 71 |
|
| 72 |
Still, we need more elaborate criterion than just the above (although in |
| 73 |
the most generic case it can be reduced to it). The criterion has to take two |
| 74 |
things into account: |
| 75 |
. |
| 76 |
.RS 4 |
| 77 |
.IP \(bu 4 |
| 78 |
idling periods |
| 79 |
.IP \(bu |
| 80 |
the ability to "look back", so if during current active period the service curve is violated, maybe it |
| 81 |
isn't if we count excess bandwidth received during earlier active period(s) |
| 82 |
.RE |
| 83 |
.PP |
| 84 |
Let's define the criterion as follows: |
| 85 |
.RS 4 |
| 86 |
.nf |
| 87 |
.IP "\fB(1)\fR" 4 |
| 88 |
For each t1, there must exist t0 in set B, so S(t1\-t0)\~<=\~w(t0,t1) |
| 89 |
.fi |
| 90 |
.RE |
| 91 |
. |
| 92 |
.PP |
| 93 |
Here 'w' denotes the amount of service received during some time period between t0 |
| 94 |
and t1. B is a set of all times, where a session becomes active after idling |
| 95 |
period (further denoted as 'becoming backlogged'). For a clearer picture, |
| 96 |
imagine two situations: |
| 97 |
. |
| 98 |
.RS 4 |
| 99 |
.IP \fBa)\fR 4 |
| 100 |
our session was active during two periods, with a small time gap between them |
| 101 |
.IP \fBb)\fR |
| 102 |
as in (a), but with a larger gap |
| 103 |
.RE |
| 104 |
. |
| 105 |
.PP |
| 106 |
Consider \fB(a)\fR: if the service received during both periods meets |
| 107 |
\fB(1)\fR, then all is well. But what if it doesn't do so during the 2nd |
| 108 |
period? If the amount of service received during the 1st period is larger |
| 109 |
than the service curve, then it might compensate for smaller service during |
| 110 |
the 2nd period \fIand\fR the gap \- if the gap is small enough. |
| 111 |
|
| 112 |
If the gap is larger \fB(b)\fR \- then it's less likely to happen (unless the |
| 113 |
excess bandwidth allocated during the 1st part was really large). Still, the |
| 114 |
larger the gap \- the less interesting is what happened in the past (e.g. 10 |
| 115 |
minutes ago) \- what matters is the current traffic that just started. |
| 116 |
|
| 117 |
From HFSC's perspective, more interesting is answering the following question: |
| 118 |
when should we start transferring packets, so a service curve of a class is not |
| 119 |
violated. Or rephrasing it: How much X() amount of service should a session |
| 120 |
receive by time t, so the service curve is not violated. Function X() defined |
| 121 |
as below is the basic building block of HFSC, used in: eligible, deadline, |
| 122 |
virtual\-time and fit\-time curves. Of course, X() is based on equation |
| 123 |
\fB(1)\fR and is defined recursively: |
| 124 |
|
| 125 |
.RS 4 |
| 126 |
.IP \(bu 4 |
| 127 |
At the 1st backlogged period beginning function X is initialized to generic |
| 128 |
service curve assigned to a class |
| 129 |
.IP \(bu |
| 130 |
At any subsequent backlogged period, X() is: |
| 131 |
.nf |
| 132 |
\fBmin(X() from previous period ; w(t0)+S(t\-t0) for t>=t0),\fR |
| 133 |
.fi |
| 134 |
\&... where t0 denotes the beginning of the current backlogged period. |
| 135 |
.RE |
| 136 |
. |
| 137 |
.PP |
| 138 |
HFSC uses either linear, or two\-piece linear service curves. In case of |
| 139 |
linear or two\-piece linear convex functions (first slope < second slope), |
| 140 |
min() in X's definition reduces to the 2nd argument. But in case of two\-piece |
| 141 |
concave functions, the 1st argument might quickly become lesser for some |
| 142 |
t>=t0. Note, that for some backlogged period, X() is defined only from that |
| 143 |
period's beginning. We also define X^(\-1)(w) as smallest t>=t0, for which |
| 144 |
X(t)\~=\~w. We have to define it this way, as X() is usually not an injection. |
| 145 |
|
| 146 |
The above generic X() can be one of the following: |
| 147 |
. |
| 148 |
.RS 4 |
| 149 |
.IP "E()" 4 |
| 150 |
In realtime criterion, selects packets eligible for sending. If none are |
| 151 |
eligible, HFSC will use linkshare criterion. Eligible time \&'et' is calculated |
| 152 |
with reference to packets' heads ( et\~=\~E^(\-1)(w) ). It's based on RT |
| 153 |
service curve, \fIbut in case of a convex curve, uses its 2nd slope only.\fR |
| 154 |
.IP "D()" |
| 155 |
In realtime criterion, selects the most suitable packet from the ones chosen |
| 156 |
by E(). Deadline time \&'dt' corresponds to packets' tails |
| 157 |
(dt\~=\~D^(\-1)(w+l), where \&'l' is packet's length). Based on RT service |
| 158 |
curve. |
| 159 |
.IP "V()" |
| 160 |
In linkshare criterion, arbitrates which packet to send next. Note that V() is |
| 161 |
function of a virtual time \- see \fBLINKSHARE CRITERION\fR section for |
| 162 |
details. Virtual time \&'vt' corresponds to packets' heads |
| 163 |
(vt\~=\~V^(\-1)(w)). Based on LS service curve. |
| 164 |
.IP "F()" |
| 165 |
An extension to linkshare criterion, used to limit at which speed linkshare |
| 166 |
criterion is allowed to dequeue. Fit\-time 'ft' corresponds to packets' heads |
| 167 |
as well (ft\~=\~F^(\-1)(w)). Based on UL service curve. |
| 168 |
.RE |
| 169 |
|
| 170 |
Be sure to make clean distinction between session's RT, LS and UL service |
| 171 |
curves and the above "utility" functions. |
| 172 |
. |
| 173 |
.SH "REALTIME CRITERION" |
| 174 |
. |
| 175 |
RT criterion \fIignores class hierarchy\fR and guarantees precise bandwidth and |
| 176 |
delay allocation. We say that a packet is eligible for sending, when the |
| 177 |
current real |
| 178 |
time is later than the eligible time of the packet. From all eligible packets, the one most |
| 179 |
suited for sending is the one with the shortest deadline time. This sounds |
| 180 |
simple, but consider the following example: |
| 181 |
|
| 182 |
Interface 10Mbit, two classes, both with two\-piece linear service curves: |
| 183 |
.RS 4 |
| 184 |
.IP \(bu 4 |
| 185 |
1st class \- 2Mbit for 100ms, then 7Mbit (convex \- 1st slope < 2nd slope) |
| 186 |
.IP \(bu |
| 187 |
2nd class \- 7Mbit for 100ms, then 2Mbit (concave \- 1st slope > 2nd slope) |
| 188 |
.RE |
| 189 |
.PP |
| 190 |
Assume for a moment, that we only use D() for both finding eligible packets, |
| 191 |
and choosing the most fitting one, thus eligible time would be computed as |
| 192 |
D^(\-1)(w) and deadline time would be computed as D^(\-1)(w+l). If the 2nd |
| 193 |
class starts sending packets 1 second after the 1st class, it's of course |
| 194 |
impossible to guarantee 14Mbit, as the interface capability is only 10Mbit. |
| 195 |
The only workaround in this scenario is to allow the 1st class to send the |
| 196 |
packets earlier that would normally be allowed. That's where separate E() comes |
| 197 |
to help. Putting all the math aside (see HFSC paper for details), E() for RT |
| 198 |
concave service curve is just like D(), but for the RT convex service curve \- |
| 199 |
it's constructed using \fIonly\fR RT service curve's 2nd slope (in our example |
| 200 |
7Mbit). |
| 201 |
|
| 202 |
The effect of such E() \- packets will be sent earlier, and at the same time |
| 203 |
D() \fIwill\fR be updated \- so the current deadline time calculated from it |
| 204 |
will be later. Thus, when the 2nd class starts sending packets later, both |
| 205 |
the 1st and the 2nd class will be eligible, but the 2nd session's deadline |
| 206 |
time will be smaller and its packets will be sent first. When the 1st class |
| 207 |
becomes idle at some later point, the 2nd class will be able to "buffer" up |
| 208 |
again for later active period of the 1st class. |
| 209 |
|
| 210 |
A short remark \- in a situation, where the total amount of bandwidth |
| 211 |
available on the interface is larger than the allocated total realtime parts |
| 212 |
(imagine a 10 Mbit interface, but 1Mbit/2Mbit and 2Mbit/1Mbit classes), the sole |
| 213 |
speed of the interface could suffice to guarantee the times. |
| 214 |
|
| 215 |
Important part of RT criterion is that apart from updating its D() and E(), |
| 216 |
also V() used by LS criterion is updated. Generally the RT criterion is |
| 217 |
secondary to LS one, and used \fIonly\fR if there's a risk of violating precise |
| 218 |
realtime requirements. Still, the "participation" in bandwidth distributed by |
| 219 |
LS criterion is there, so V() has to be updated along the way. LS criterion can |
| 220 |
than properly compensate for non\-ideal fair sharing situation, caused by RT |
| 221 |
scheduling. If you use UL service curve its F() will be updated as well (UL |
| 222 |
service curve is an extension to LS one \- see \fBUPPERLIMIT CRITERION\fR |
| 223 |
section). |
| 224 |
|
| 225 |
Anyway \- careless specification of LS and RT service curves can lead to |
| 226 |
potentially undesired situations (see CORNER CASES for examples). This wasn't |
| 227 |
the case in HFSC paper where LS and RT service curves couldn't be specified |
| 228 |
separately. |
| 229 |
|
| 230 |
.SH "LINKSHARING CRITERION" |
| 231 |
. |
| 232 |
LS criterion's task is to distribute bandwidth according to specified class |
| 233 |
hierarchy. Contrary to RT criterion, there're no comparisons between current |
| 234 |
real time and virtual time \- the decision is based solely on direct comparison |
| 235 |
of virtual times of all active subclasses \- the one with the smallest vt wins |
| 236 |
and gets scheduled. One immediate conclusion from this fact is that absolute |
| 237 |
values don't matter \- only ratios between them (so for example, two children |
| 238 |
classes with simple linear 1Mbit service curves will get the same treatment |
| 239 |
from LS criterion's perspective, as if they were 5Mbit). The other conclusion |
| 240 |
is, that in perfectly fluid system with linear curves, all virtual times across |
| 241 |
whole class hierarchy would be equal. |
| 242 |
|
| 243 |
Why is VC defined in term of virtual time (and what is it)? |
| 244 |
|
| 245 |
Imagine an example: class A with two children \- A1 and A2, both with let's say |
| 246 |
10Mbit SCs. If A2 is idle, A1 receives all the bandwidth of A (and update its |
| 247 |
V() in the process). When A2 becomes active, A1's virtual time is already |
| 248 |
\fIfar\fR later than A2's one. Considering the type of decision made by LS |
| 249 |
criterion, A1 would become idle for a long time. We can workaround this |
| 250 |
situation by adjusting virtual time of the class becoming active \- we do that |
| 251 |
by getting such time "up to date". HFSC uses a mean of the smallest and the |
| 252 |
biggest virtual time of currently active children fit for sending. As it's not |
| 253 |
real time anymore (excluding trivial case of situation where all classes become |
| 254 |
active at the same time, and never become idle), it's called virtual time. |
| 255 |
|
| 256 |
Such approach has its price though. The problem is analogous to what was |
| 257 |
presented in previous section and is caused by non\-linearity of service |
| 258 |
curves: |
| 259 |
.IP 1) 4 |
| 260 |
either it's impossible to guarantee service curves and satisfy fairness |
| 261 |
during certain time periods: |
| 262 |
|
| 263 |
.RS 4 |
| 264 |
Recall the example from RT section, slightly modified (with 3Mbit slopes |
| 265 |
instead of 2Mbit ones): |
| 266 |
|
| 267 |
.IP \(bu 4 |
| 268 |
1st class \- 3Mbit for 100ms, then 7Mbit (convex \- 1st slope < 2nd slope) |
| 269 |
.IP \(bu |
| 270 |
2nd class \- 7Mbit for 100ms, then 3Mbit (concave \- 1st slope > 2nd slope) |
| 271 |
|
| 272 |
.PP |
| 273 |
They sum up nicely to 10Mbit \- the interface's capacity. But if we wanted to only |
| 274 |
use LS for guarantees and fairness \- it simply won't work. In LS context, |
| 275 |
only V() is used for making decision which class to schedule. If the 2nd class |
| 276 |
becomes active when the 1st one is in its second slope, the fairness will be |
| 277 |
preserved \- ratio will be 1:1 (7Mbit:7Mbit), but LS itself is of course |
| 278 |
unable to guarantee the absolute values themselves \- as it would have to go |
| 279 |
beyond of what the interface is capable of. |
| 280 |
.RE |
| 281 |
|
| 282 |
.IP 2) 4 |
| 283 |
and/or it's impossible to guarantee service curves of all classes at the same |
| 284 |
time [fairly or not]: |
| 285 |
|
| 286 |
.RS 4 |
| 287 |
|
| 288 |
This is similar to the above case, but a bit more subtle. We will consider two |
| 289 |
subtrees, arbitrated by their common (root here) parent: |
| 290 |
|
| 291 |
.nf |
| 292 |
R (root) -\ 10Mbit |
| 293 |
|
| 294 |
A \- 7Mbit, then 3Mbit |
| 295 |
A1 \- 5Mbit, then 2Mbit |
| 296 |
A2 \- 2Mbit, then 1Mbit |
| 297 |
|
| 298 |
B \- 3Mbit, then 7Mbit |
| 299 |
.fi |
| 300 |
|
| 301 |
R arbitrates between left subtree (A) and right (B). Assume that A2 and B are |
| 302 |
constantly backlogged, and at some later point A1 becomes backlogged (when all |
| 303 |
other classes are in their 2nd linear part). |
| 304 |
|
| 305 |
What happens now? B (choice made by R) will \fIalways\fR get 7 Mbit as R is |
| 306 |
only (obviously) concerned with the ratio between its direct children. Thus A |
| 307 |
subtree gets 3Mbit, but its children would want (at the point when A1 became |
| 308 |
backlogged) 5Mbit + 1Mbit. That's of course impossible, as they can only get |
| 309 |
3Mbit due to interface limitation. |
| 310 |
|
| 311 |
In the left subtree \- we have the same situation as previously (fair split |
| 312 |
between A1 and A2, but violated guarantees), but in the whole tree \- there's |
| 313 |
no fairness (B got 7Mbit, but A1 and A2 have to fit together in 3Mbit) and |
| 314 |
there's no guarantees for all classes (only B got what it wanted). Even if we |
| 315 |
violated fairness in the A subtree and set A2's service curve to 0, A1 would |
| 316 |
still not get the required bandwidth. |
| 317 |
.RE |
| 318 |
. |
| 319 |
.SH "UPPERLIMIT CRITERION" |
| 320 |
. |
| 321 |
UL criterion is an extensions to LS one, that permits sending packets only |
| 322 |
if current real time is later than fit\-time ('ft'). So the modified LS |
| 323 |
criterion becomes: choose the smallest virtual time from all active children, |
| 324 |
such that fit\-time < current real time also holds. Fit\-time is calculated |
| 325 |
from F(), which is based on UL service curve. As you can see, its role is |
| 326 |
kinda similar to E() used in RT criterion. Also, for obvious reasons \- you |
| 327 |
can't specify UL service curve without LS one. |
| 328 |
|
| 329 |
The main purpose of the UL service curve is to limit HFSC to bandwidth available on the |
| 330 |
upstream router (think adsl home modem/router, and linux server as |
| 331 |
NAT/firewall/etc. with 100Mbit+ connection to mentioned modem/router). |
| 332 |
Typically, it's used to create a single class directly under root, setting |
| 333 |
a linear UL service curve to available bandwidth \- and then creating your class |
| 334 |
structure from that class downwards. Of course, you're free to add a UL service |
| 335 |
curve (linear or not) to any class with LS criterion. |
| 336 |
|
| 337 |
An important part about the UL service curve is that whenever at some point in time |
| 338 |
a class doesn't qualify for linksharing due to its fit\-time, the next time it |
| 339 |
does qualify it will update its virtual time to the smallest virtual time of |
| 340 |
all active children fit for linksharing. This way, one of the main things the LS |
| 341 |
criterion tries to achieve \- equality of all virtual times across whole |
| 342 |
hierarchy \- is preserved (in perfectly fluid system with only linear curves, |
| 343 |
all virtual times would be equal). |
| 344 |
|
| 345 |
Without that, 'vt' would lag behind other virtual times, and could cause |
| 346 |
problems. Consider an interface with a capacity of 10Mbit, and the following leaf classes |
| 347 |
(just in case you're skipping this text quickly \- this example shows behavior |
| 348 |
that \f(BIdoesn't happen\fR): |
| 349 |
|
| 350 |
.nf |
| 351 |
A \- ls 5.0Mbit |
| 352 |
B \- ls 2.5Mbit |
| 353 |
C \- ls 2.5Mbit, ul 2.5Mbit |
| 354 |
.fi |
| 355 |
|
| 356 |
If B was idle, while A and C were constantly backlogged, A and C would normally |
| 357 |
(as far as LS criterion is concerned) divide bandwidth in 2:1 ratio. But due |
| 358 |
to UL service curve in place, C would get at most 2.5Mbit, and A would get the |
| 359 |
remaining 7.5Mbit. The longer the backlogged period, the more the virtual times of |
| 360 |
A and C would drift apart. If B became backlogged at some later point in time, |
| 361 |
its virtual time would be set to (A's\~vt\~+\~C's\~vt)/2, thus blocking A from |
| 362 |
sending any traffic until B's virtual time catches up with A. |
| 363 |
. |
| 364 |
.SH "SEPARATE LS / RT SCs" |
| 365 |
. |
| 366 |
Another difference from the original HFSC paper is that RT and LS SCs can be |
| 367 |
specified separately. Moreover, leaf classes are allowed to have only either |
| 368 |
RT SC or LS SC. For interior classes, only LS SCs make sense: any RT SC will |
| 369 |
be ignored. |
| 370 |
. |
| 371 |
.SH "CORNER CASES" |
| 372 |
. |
| 373 |
Separate service curves for LS and RT criteria can lead to certain traps |
| 374 |
that come from "fighting" between ideal linksharing and enforced realtime |
| 375 |
guarantees. Those situations didn't exist in original HFSC paper, where |
| 376 |
specifying separate LS / RT service curves was not discussed. |
| 377 |
|
| 378 |
Consider an interface with a 10Mbit capacity, with the following leaf classes: |
| 379 |
|
| 380 |
.nf |
| 381 |
A \- ls 5.0Mbit, rt 8Mbit |
| 382 |
B \- ls 2.5Mbit |
| 383 |
C \- ls 2.5Mbit |
| 384 |
.fi |
| 385 |
|
| 386 |
Imagine A and C are constantly backlogged. As B is idle, A and C would divide |
| 387 |
bandwidth in 2:1 ratio, considering LS service curve (so in theory \- 6.66 and |
| 388 |
3.33). Alas RT criterion takes priority, so A will get 8Mbit and LS will be |
| 389 |
able to compensate class C for only 2 Mbit \- this will cause discrepancy |
| 390 |
between virtual times of A and C. |
| 391 |
|
| 392 |
Assume this situation lasts for a long time with no idle periods, and |
| 393 |
suddenly B becomes active. B's virtual time will be updated to |
| 394 |
(A's\~vt\~+\~C's\~vt)/2, effectively landing in the middle between A's and C's |
| 395 |
virtual time. The effect \- B, having no RT guarantees, will be punished and |
| 396 |
will not be allowed to transfer until C's virtual time catches up. |
| 397 |
|
| 398 |
If the interface had a higher capacity, for example 100Mbit, this example |
| 399 |
would behave perfectly fine though. |
| 400 |
|
| 401 |
Let's look a bit closer at the above example \- it "cleverly" invalidates one |
| 402 |
of the basic things LS criterion tries to achieve \- equality of all virtual |
| 403 |
times across class hierarchy. Leaf classes without RT service curves are |
| 404 |
literally left to their own fate (governed by messed up virtual times). |
| 405 |
|
| 406 |
Also, it doesn't make much sense. Class A will always be guaranteed up to |
| 407 |
8Mbit, and this is more than any absolute bandwidth that could happen from its |
| 408 |
LS criterion (excluding trivial case of only A being active). If the bandwidth |
| 409 |
taken by A is smaller than absolute value from LS criterion, the unused part |
| 410 |
will be automatically assigned to other active classes (as A has idling periods |
| 411 |
in such case). The only "advantage" is, that even in case of low bandwidth on |
| 412 |
average, bursts would be handled at the speed defined by RT criterion. Still, |
| 413 |
if extra speed is needed (e.g. due to latency), non linear service curves |
| 414 |
should be used in such case. |
| 415 |
|
| 416 |
In the other words: the LS criterion is meaningless in the above example. |
| 417 |
|
| 418 |
You can quickly "workaround" it by making sure each leaf class has RT service |
| 419 |
curve assigned (thus guaranteeing all of them will get some bandwidth), but it |
| 420 |
doesn't make it any more valid. |
| 421 |
|
| 422 |
Keep in mind - if you use nonlinear curves and irregularities explained above |
| 423 |
happen \fIonly\fR in the first segment, then there's little wrong with |
| 424 |
"overusing" RT curve a bit: |
| 425 |
|
| 426 |
.nf |
| 427 |
A \- ls 5.0Mbit, rt 9Mbit/30ms, then 1Mbit |
| 428 |
B \- ls 2.5Mbit |
| 429 |
C \- ls 2.5Mbit |
| 430 |
.fi |
| 431 |
|
| 432 |
Here, the vt of A will "spike" in the initial period, but then A will never get more |
| 433 |
than 1Mbit until B & C catch up. Then everything will be back to normal. |
| 434 |
. |
| 435 |
.SH "LINUX AND TIMER RESOLUTION" |
| 436 |
. |
| 437 |
In certain situations, the scheduler can throttle itself and setup so |
| 438 |
called watchdog to wakeup dequeue function at some time later. In case of HFSC |
| 439 |
it happens when for example no packet is eligible for scheduling, and UL |
| 440 |
service curve is used to limit the speed at which LS criterion is allowed to |
| 441 |
dequeue packets. It's called throttling, and accuracy of it is dependent on |
| 442 |
how the kernel is compiled. |
| 443 |
|
| 444 |
There're 3 important options in modern kernels, as far as timers' resolution |
| 445 |
goes: \&'tickless system', \&'high resolution timer support' and \&'timer |
| 446 |
frequency'. |
| 447 |
|
| 448 |
If you have \&'tickless system' enabled, then the timer interrupt will trigger |
| 449 |
as slowly as possible, but each time a scheduler throttles itself (or any |
| 450 |
other part of the kernel needs better accuracy), the rate will be increased as |
| 451 |
needed / possible. The ceiling is either \&'timer frequency' if \&'high |
| 452 |
resolution timer support' is not available or not compiled in, or it's |
| 453 |
hardware dependent and can go \fIfar\fR beyond the highest \&'timer frequency' |
| 454 |
setting available. |
| 455 |
|
| 456 |
If \&'tickless system' is not enabled, the timer will trigger at a fixed rate |
| 457 |
specified by \&'timer frequency' \- regardless if high resolution timers are |
| 458 |
or aren't available. |
| 459 |
|
| 460 |
This is important to keep those settings in mind, as in scenario like: no |
| 461 |
tickless, no HR timers, frequency set to 100hz \- throttling accuracy would be |
| 462 |
at 10ms. It doesn't automatically mean you would be limited to ~0.8Mbit/s |
| 463 |
(assuming packets at ~1KB) \- as long as your queues are prepared to cover for |
| 464 |
timer inaccuracy. Of course, in case of e.g. locally generated UDP traffic \- |
| 465 |
appropriate socket size is needed as well. Short example to make it more |
| 466 |
understandable (assume hardcore anti\-schedule settings \- HZ=100, no HR |
| 467 |
timers, no tickless): |
| 468 |
|
| 469 |
.nf |
| 470 |
tc qdisc add dev eth0 root handle 1:0 hfsc default 1 |
| 471 |
tc class add dev eth0 parent 1:0 classid 1:1 hfsc rt m2 10Mbit |
| 472 |
.fi |
| 473 |
|
| 474 |
Assuming packet of ~1KB size and HZ=100, that averages to ~0.8Mbit \- anything |
| 475 |
beyond it (e.g. the above example with specified rate over 10x larger) will |
| 476 |
require appropriate queuing and cause bursts every ~10 ms. As you can |
| 477 |
imagine, any HFSC's RT guarantees will be seriously invalidated by that. |
| 478 |
Aforementioned example is mainly important if you deal with old hardware \- as |
| 479 |
is particularly popular for home server chores. Even then, you can easily |
| 480 |
set HZ=1000 and have very accurate scheduling for typical adsl speeds. |
| 481 |
|
| 482 |
Anything modern (apic or even hpet msi based timers + \&'tickless system') |
| 483 |
will provide enough accuracy for superb 1Gbit scheduling. For example, on one |
| 484 |
of my cheap dual-core AMD boards I have the following settings: |
| 485 |
|
| 486 |
.nf |
| 487 |
tc qdisc add dev eth0 parent root handle 1:0 hfsc default 1 |
| 488 |
tc class add dev eth0 parent 1:0 classid 1:1 hfsc rt m2 300mbit |
| 489 |
.fi |
| 490 |
|
| 491 |
And a simple: |
| 492 |
|
| 493 |
.nf |
| 494 |
nc \-u dst.host.com 54321 </dev/zero |
| 495 |
nc \-l \-p 54321 >/dev/null |
| 496 |
.fi |
| 497 |
|
| 498 |
\&...will yield the following effects over a period of ~10 seconds (taken from |
| 499 |
/proc/interrupts): |
| 500 |
|
| 501 |
.nf |
| 502 |
319: 42124229 0 HPET_MSI\-edge hpet2 (before) |
| 503 |
319: 42436214 0 HPET_MSI\-edge hpet2 (after 10s.) |
| 504 |
.fi |
| 505 |
|
| 506 |
That's roughly 31000/s. Now compare it with HZ=1000 setting. The obvious |
| 507 |
drawback of it is that cpu load can be rather high with servicing that |
| 508 |
many timer interrupts. The example with 300Mbit RT service curve on 1Gbit link is |
| 509 |
particularly ugly, as it requires a lot of throttling with minuscule delays. |
| 510 |
|
| 511 |
Also note that it's just an example showing the capabilities of current hardware. |
| 512 |
The above example (essentially a 300Mbit TBF emulator) is pointless on an internal |
| 513 |
interface to begin with: you will pretty much always want a regular LS service |
| 514 |
curve there, and in such a scenario HFSC simply doesn't throttle at all. |
| 515 |
|
| 516 |
300Mbit RT service curve (selected columns from mpstat \-P ALL 1): |
| 517 |
|
| 518 |
.nf |
| 519 |
10:56:43 PM CPU %sys %irq %soft %idle |
| 520 |
10:56:44 PM all 20.10 6.53 34.67 37.19 |
| 521 |
10:56:44 PM 0 35.00 0.00 63.00 0.00 |
| 522 |
10:56:44 PM 1 4.95 12.87 6.93 73.27 |
| 523 |
.fi |
| 524 |
|
| 525 |
So, in the rare case you need those speeds with only a RT service curve, or with a UL |
| 526 |
service curve: remember the drawbacks. |
| 527 |
. |
| 528 |
.SH "CAVEAT: RANDOM ONLINE EXAMPLES" |
| 529 |
. |
| 530 |
For reasons unknown (though well guessed), many examples you can google love to |
| 531 |
overuse UL criterion and stuff it in every node possible. This makes no sense |
| 532 |
and works against what HFSC tries to do (and does pretty damn well). Use UL |
| 533 |
where it makes sense: on the uppermost node to match upstream router's uplink |
| 534 |
capacity. Or in special cases, such as testing (limit certain subtree to some |
| 535 |
speed), or customers that must never get more than certain speed. In the last |
| 536 |
case you can usually achieve the same by just using a RT criterion without LS+UL |
| 537 |
on leaf nodes. |
| 538 |
|
| 539 |
As for the router case - remember it's good to differentiate between "traffic to |
| 540 |
router" (remote console, web config, etc.) and "outgoing traffic", so for |
| 541 |
example: |
| 542 |
|
| 543 |
.nf |
| 544 |
tc qdisc add dev eth0 root handle 1:0 hfsc default 0x8002 |
| 545 |
tc class add dev eth0 parent 1:0 classid 1:999 hfsc rt m2 50Mbit |
| 546 |
tc class add dev eth0 parent 1:0 classid 1:1 hfsc ls m2 2Mbit ul m2 2Mbit |
| 547 |
.fi |
| 548 |
|
| 549 |
\&... so "internet" tree under 1:1 and "router itself" as 1:999 |
| 550 |
. |
| 551 |
.SH "LAYER2 ADAPTATION" |
| 552 |
. |
| 553 |
Please refer to \fBtc\-stab\fR(8) |
| 554 |
. |
| 555 |
.SH "SEE ALSO" |
| 556 |
. |
| 557 |
\fBtc\fR(8), \fBtc\-hfsc\fR(8), \fBtc\-stab\fR(8) |
| 558 |
|
| 559 |
Please direct bugreports and patches to: <[email protected]> |
| 560 |
. |
| 561 |
.SH "AUTHOR" |
| 562 |
. |
| 563 |
Manpage created by Michal Soltys ([email protected]) |