7. Classful Queuing Disciplines (qdiscs)
The flexibility and control of Linux traffic control can be unleashed through the agency of the classful qdiscs. Remember that the classful queuing disciplines can have filters attached to them, allowing packets to be directed to particular classes and subqueues.
There are several common terms to describe classes directly attached to
the root qdisc and terminal classes. Classess attached to the
root qdisc are known as root classes, and more generically inner
classes. Any terminal class in a particular queuing discipline is known
as a leaf class by analogy to the tree structure of the classes. Besides
the use of figurative language depicting the structure as a tree, the
language of family relationships is also quite common.
HTB uses the concepts of tokens and buckets
along with the class-based system and filters to allow for
complex and granular control over traffic. With a complex
borrowing model, HTB can perform a variety of sophisticated
traffic control techniques. One of the easiest ways to use HTB
immediately is that of shaping.
By understanding tokens and buckets or by grasping the function of TBF, HTB should be merely a logical step. This queuing discipline allows the user to define the characteristics of the tokens and bucket used and allows the user to nest these buckets in an arbitrary fashion. When coupled with a classifying scheme, traffic can be controlled in a very granular fashion.
Below is example output of the syntax for HTB on the command line with the tc tool. Although the syntax for tcng is a language of its own, the rules for HTB are the same.
Example 10. tc usage for HTB
Usage: ... qdisc add ... htb [default N] [r2q N]
default minor id of class to which unclassified packets are sent {0}
r2q DRR quantums are computed as rate in Bps/r2q {10}
debug string of 16 numbers each 0-3 {0}
... class add ... htb rate R1 burst B1 [prio P] [slot S] [pslot PS]
[ceil R2] [cburst B2] [mtu MTU] [quantum Q]
rate rate allocated to this class (class can still borrow)
burst max bytes burst which can be accumulated during idle period {computed}
ceil definite upper class rate (no borrows) {rate}
cburst burst but for ceil {computed}
mtu max packet size we create rate map for {1600}
prio priority of leaf; lower are served first {0}
quantum how much bytes to serve from leaf at once {use r2q}
TC HTB version 3.3
|
Unlike almost all of the other software discussed, HTB is a newer queuing discipline and your distribution may not have all of the tools and capability you need to use HTB. The kernel must support HTB; kernel version 2.4.20 and later support it in the stock distribution, although earlier kernel versions require patching. To enable userland support for HTB, see HTB for an iproute2 patch to tc.
One of the most common applications of HTB involves shaping transmitted traffic to a specific rate.
All shaping occurs in leaf classes. No shaping occurs in inner or root classes as they only exist to suggest how the borrowing model should distribute available tokens.
A fundamental part of the HTB qdisc is the borrowing mechanism.
Children classes borrow tokens from their parents once they have
exceeded rate. A child class will continue to
attempt to borrow until it reaches ceil, at which
point it will begin to queue packets for transmission until more
tokens/ctokens are available. As there are only two primary types of
classes which can be created with HTB the following table and
diagram identify the various possible states and the behaviour of the
borrowing mechanisms.
Table 2. HTB class states and potential actions taken
| type of class | class state | HTB internal state | action taken |
|---|---|---|---|
| leaf | < rate | HTB_CAN_SEND | Leaf class will dequeue queued bytes up to available tokens (no more than burst packets) |
| leaf | > rate, < ceil | HTB_MAY_BORROW |
Leaf class will attempt to borrow tokens/ctokens from
parent class. If tokens are available, they will be lent in
quantum increments and the leaf class will dequeue up
to cburst bytes
|
| leaf | > ceil | HTB_CANT_SEND | No packets will be dequeued. This will cause packet delay and will increase latency to meet the desired rate. |
| inner, root | < rate | HTB_CAN_SEND | Inner class will lend tokens to children. |
| inner, root | > rate, < ceil | HTB_MAY_BORROW |
Inner class will attempt to borrow tokens/ctokens from
parent class, lending them to competing children in
quantum increments per request.
|
| inner, root | > ceil | HTB_CANT_SEND | Inner class will not attempt to borrow from its parent and will not lend tokens/ctokens to children classes. |
This diagram identifies the flow of borrowed tokens and the manner in which tokens are charged to parent classes. In order for the borrowing model to work, each class must have an accurate count of the number of tokens used by itself and all of its children. For this reason, any token used in a child or leaf class is charged to each parent class until the root class is reached.
Any child class which wishes to borrow a token will request a token
from its parent class, which if it is also over its rate will
request to borrow from its parent class until either a token is
located or the root class is reached. So the borrowing of tokens
flows toward the leaf classes and the charging of the usage of tokens
flows toward the root class.
Note in this diagram that there are several HTB root classes. Each of these root classes can simulate a virtual circuit.
defaultAn optional parameter with every HTB
qdiscobject, the defaultdefaultis 0, which cause any unclassified traffic to be dequeued at hardware speed, completely bypassing any of the classes attached to therootqdisc.rateUsed to set the minimum desired speed to which to limit transmitted traffic. This can be considered the equivalent of a committed information rate (CIR), or the guaranteed bandwidth for a given leaf class.
ceilUsed to set the maximum desired speed to which to limit the transmitted traffic. The borrowing model should illustrate how this parameter is used. This can be considered the equivalent of “burstable bandwidth”.
burstThis is the size of the
ratebucket (see Tokens and buckets). HTB will dequeueburstbytes before awaiting the arrival of more tokens.cburstThis is the size of the
ceilbucket (see Tokens and buckets). HTB will dequeuecburstbytes before awaiting the arrival of more ctokens.quantumThis is a key parameter used by HTB to control borrowing. Normally, the correct
quantumis calculated by HTB, not specified by the user. Tweaking this parameter can have tremendous effects on borrowing and shaping under contention, because it is used both to split traffic between children classes overrate(but belowceil) and to transmit packets from these same classes.r2qAlso, usually calculated for the user,
r2qis a hint to HTB to help determine the optimalquantumfor a particular class.mtuprio
Below are some general guidelines to using HTB culled from http://docum.org/ and the LARTC mailing list. These rules are simply a recommendation for beginners to maximize the benefit of HTB until gaining a better understanding of the practical application of HTB.
Shaping with HTB occurs only in leaf classes. See also Section 7.1.2, “Shaping”.
Because HTB does not shape in any class except the leaf class, the sum of the
rates of leaf classes should not exceed theceilof a parent class. Ideally, the sum of therates of the children classes would match therateof the parent class, allowing the parent class to distribute leftover bandwidth (ceil-rate) among the children classes.This key concept in employing HTB bears repeating. Only leaf classes actually shape packets; packets are only delayed in these leaf classes. The inner classes (all the way up to the root class) exist to define how borrowing/lending occurs (see also Section 7.1.3, “Borrowing”).
The
quantumis only only used when a class is overratebut belowceil.The
quantumshould be set at MTU or higher. HTB will dequeue a single packet at least per service opportunity even ifquantumis too small. In such a case, it will not be able to calculate accurately the real bandwidth consumed [9].Parent classes lend tokens to children in increments of
quantum, so for maximum granularity and most instantaneously evenly distributed bandwidth,quantumshould be as low as possible while still no less than MTU.A distinction between tokens and ctokens is only meaningful in a leaf class, because non-leaf classes only lend tokens to child classes.
HTB borrowing could more accurately be described as “using”.
The HFSC classful qdisc balances delay-sensitive traffic against throughput sensitive traffic. In a congested or backlogged state, the HFSC queuing discipline interleaves the delay-sensitive traffic when required according service curve definitions. Read about the Linux implementation in German, HFSC Scheduling mit Linux or read a translation into English, HFSC Scheduling with Linux. The original research article, A Hierarchical Fair Service Curve Algorithm For Link-Sharing, Real-Time and Priority Services, also remains available.
This section will be completed at a later date.
The PRIO classful qdisc works on a very simple precept. When it is ready to dequeue a packet, the first class is checked for a packet. If there's a packet, it gets dequeued. If there's no packet, then the next class is checked, until the queuing mechanism has no more classes to check.
This section will be completed at a later date.
CBQ is the classic implementation (also called venerable) of a traffic control system. This section will be completed at a later date.
[9]
HTB will report bandwidth usage in this scenario
incorrectly. It will calculate the bandwidth used by
quantum instead of the real dequeued packet size.
This can skew results quickly.