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.
7.1. HTB, Hierarchical Token Bucket
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
|
7.1.1. Software requirements
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.
7.1.2. Shaping
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.
7.1.3. Borrowing
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.
7.1.4. HTB class parameters
- default
An optional parameter with every HTB qdisc object,
the default default is 0, which cause any unclassified
traffic to be dequeued at hardware speed, completely bypassing
any of the classes attached to the root qdisc.
- rate
Used 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.
- ceil
Used 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".
- burst
This is the size of the rate bucket (see
Tokens and buckets). HTB will dequeue
burst bytes before awaiting the arrival of more
tokens.
- cburst
This is the size of the ceil bucket (see
Tokens and buckets). HTB will dequeue
cburst bytes before awaiting the arrival of more
ctokens.
- quantum
This is a key parameter used by HTB to control borrowing.
Normally, the correct quantum is 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 over rate (but below
ceil) and to transmit packets from these same
classes.
- r2q
Also, usually calculated for the user, r2q is a hint to
HTB to help determine the optimal quantum
for a particular class.
- mtu
- prio
7.1.5. Rules
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.
Because HTB does not shape in any class except the leaf
class, the sum of the rates of leaf classes should not
exceed the ceil of a parent class. Ideally, the sum of
the rates of the children classes would match the
rate of 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).
The quantum is only only used when a class is over
rate but below ceil.
The quantum should be set at MTU or higher. HTB
will dequeue a single packet at least per service opportunity even
if quantum is too small. In such a case, it will not be
able to calculate accurately the real bandwidth consumed
.
Parent classes lend tokens to children in increments of
quantum, so for maximum granularity and most
instantaneously evenly distributed bandwidth, quantum
should 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".
7.3. PRIO, priority scheduler
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.
7.4. CBQ, Class Based Queuing
CBQ is the classic implementation (also called venerable) of a traffic
control system. This section will be completed at a later date.
|
|