5. An Overview of Common qdiscs

Linux traffic control affords you access to many different shapers and schedulers. A brief overview of each and its capabilities is needed before you can employ them.

5.1. Classless qdiscs

5.1.1. pfifo / bfifo

The most basic scheduler available, pfifo is your standard first-in first-out queue. pfifo is the scheduler all leaf nodes of classful qdiscs are assigned by default if you choose not to override it with a different scheduler.


Usage: ... [p|b]fifo [ limit NUMBER ]

The only available option is a limit on the queue size. It is assumed to be packets if you are using pfifo and bytes if you are using bfifo.

Additional information on the pfifo qdisc:

5.1.2. sfq

A scheduler designed to be CPU and flow friendly, sfq employs a stochastic algorithm to ensure reasonable fairness amongst flows. Stochastic is a fancy way of saying probabilities are employed instead of exacting precision. In a nutshell, sfq uses a constantly changing hashing algorithm over packets which it files into internal FIFOs which are pulled from round robin style.


Usage: ... sfq [ perturb SECS ] [ quantum BYTES ]

The perturb parameter allows you to specify how often sfq changes its hashing algorithm. The quantum parameter controls how many bytes are released from each internal FIFO in round robin fashion. You cannot set this below your maximum transmission unit (MTU) size.

Additional information on the sfq qdisc:

5.1.3. tbf

An excellent scheduler for throttling traffic, the token bucket filter is just that, a bucket. Each token corresponds to a byte. Each byte is paired up with a token. When a flow is less than the specified rate, these tokens add up, allowing for bursts if it exceeds the specified rate. When an excess of packets build up without matching tokens for each byte, new packets are dropped.

As of Linux 2.6.1, tbf is now a classful qdisc. By default it will behave as it did in prior versions of Linux. The classful variant automatically creates a class with a minor node of 1. The major node number will be what you assigned to the tbf qdisc. You can attach both classless and classful qdiscs to the new tbf in 2.6.1 and later.


Usage: ... tbf limit BYTES burst BYTES[/BYTES] rate KBPS [ mtu BYTES[/BYTES] ]
[ peakrate KBPS ] [ latency TIME ]

The rate parameter allows you to specify the speed limit for this scheduler. You must also specify the burst parameter, which is essentially the size of your token bucket in bytes. The limit parameter is the number of bytes to queue before packets are tail dropped. (In Linux 2.6.1 and later if you attach a qdisc to your tbf class, the limit is ignored in favor of your attached qdisc.) A detailed explanation of using the peakrate and latency parameters is beyond the scope of this document.

Additional information for the tbf qdisc:

5.2. Classful qdiscs

5.2.1. prio

The prio qdisc, a priority scheduler, is an interesting classful scheduler. The prio qdisc automatically creates three classes when used, with the first's minor node number starting at 1 and incrementing from there. Each of these is queried in turn, starting with the first, and all available packets are sent. It continues this until it runs out of classes or available bandwidth has been exhausted. By default, traffic is assigned to each of the three priority classes based on type of service (TOS) bits set in each packet, but you can override this behavior.


Usage: ... prio bands NUMBER priomap P1 P2...

You can specify the number of bands using the bands parameter. The priomap parameter is a bit more complicated. The priomap parameter takes sixteen integers as an argument, with each corresponding to a priority class. While the prio qdisc classes begin at 1, priorities begin at 0. Each position in this map of numbers corresponds to a specific TOS bit. The ordering is hardcoded. In practice you likely will not need to change these assignments.

More detailed information on the prio qdisc:

5.2.2. htb

The htb qdisc, or hierarchical token bucket, is a classful shaping qdisc. It packs a lot of flexibility and has numerous options available. It calculates reasonable default values for anything you do not specify, which is generally fine. A htb qdisc accepts the default parameter, which specifies which class to direct unclassified flows to. All other options pertain to the actual classes.


Usage:
... qdisc add ... htb [default N] [r2q N]
... class add ... htb rate R1 burst B1 [prio P] [slot S] [pslot PS]
                      [ceil R2] [cburst B2] [mtu MTU] [quantum Q]

Generally, a htb parent class is given a rate and a ceil (ceiling) in bits per second. This defines how much bandwidth is available. If not specified, ceil defaults to whatever you specified rate to be. The parent class serves as a container for its children and should have a rate equal to the practical amount of bandwidth available.

If you choose a value as your rate for a class that is less than your ceil, that class can borrow up to your ceil value. For example, if your ceil is 512Kbps and your rate is 128Kbps, a total of 384Kbps could be borrowed. Its important to note that unlike borrowing something in meat space, bandwidth borrowed amongst htb classes is not returned. Because rate is the bandwidth guaranteed to the class, it cannot exceed the number specified for the outer most parent class. If a particular class requests bandwidth greater than its specified rate, it will borrow based on the proportion of its rate to its parent. For example, if a parent class with 100Kbps rate has two children with rates of 80Kbps and 20Kbps respectively, the the former can borrow bandwidth in a proportion of 4:1 with respect to the latter. In other words, classes with a higher rate in comparison to other siblings can borrow more.

The default option specifies which class unclassified traffic should be associated with. Any traffic not classified via one of the methods described later will be assigned to this class. If you do not specify the default option at all, any unclassified traffic with not be subject to traffic control. In otherwords, you probably want to specify a default.

More detailed information is available on the htb qdisc: