I am trying to understand the queuing mechanism of linux-htb QDisc and QDisc of linux tc in general.

What I could gather: During TX, the packet is queued into the queue inside the linux tc. This queue by default follows a pfifo_fast QDisc with a txqueuelen of 1000. The packet scheduler dequeues the packet from this queue and puts it onto the TX driver queue (ring buffer).
When we use linux-htb, the txqueuelen is inherited only for the default queue. [Link]. My question: Consider the tree (rates are specified in kbits/sec in parenthesis ()):

      1:   root qdisc (class htb)
     / | \ 
    /  |  \
   /   |   \
 1:1  1:2  1:3    parent qdiscs (class htb)
(30)  (10)  (60)
  1. Are there internal queues maintained for each of the parent htb classes (1:1, 1:2 and 1:3)? If yes what is their queue length? If not, how many queues are actually maintained and for what purpose? What is their queue length?

  2. What exactly is meant by Queueing Discipline (QDisc)? Is it the property of the data structure used (queue)? or it is a property of the packet scheduler? Or maybe both combined?

  3. While reading the source code of htb QDisc [Link], I came accross something called a direct queue. What is a direct_queue?

Provide link to relevant sources if possible.


Disclaimer: Those are a lot of questions and I haven't used HTB in like a decade? So I can't answer with confidence. But since you got zero replies so far, maybe this is still of some help.

Are there internal queues maintained for each of the parent htb classes (1:1, 1:2 and 1:3)?

They are leaf classes, and each is represented by a qdisc queue struct, so I assume that counts as internal queues. Not sure about the queue length - sorry.

Code from sch_htb.c:

struct htb_class_leaf {
    int     deficit[TC_HTB_MAXDEPTH];
    struct Qdisc    *q;
} leaf;

the Qdisc structure is defined in include/net/sch_generic.h

What exactly is meant by Queueing Discipline (QDisc)?

This depends on context but basically, it's a kernel API in which packets are enqueued and dequeued; so the QDisc is given some control about the order in which (or time when) packets that come in should go out again (or dropped altogether, even). That is how QDiscs like HTB, SFQ or PRIO then shape traffic in various ways, like prioritize or impose bandwidth limits.

Comment from sch_api.c:

   Generally, queueing discipline ("qdisc") is a black box,
   which is able to enqueue packets and to dequeue them (when
   device is ready to send something) in order and at times
   determined by algorithm hidden in it.

And HTB is just one of several such algorithms.

What is a direct_queue?

Not part of the API but handled internally... so you could consider it part of the HTB algorithm.

If you deliberately classify packets to X:0 or if the default class doesn't exist, HTB decided to put them in a separate queue, and on dequeue it will attempt to send those packets out first.

Comment from sch_htb.c

 * [...] If we end up with classid MAJOR:0 we enqueue the skb into special
 * internal fifo (direct). These packets then go directly thru. If we still
 * have no valid leaf we try to use MAJOR:default leaf. It still unsuccessful
 * then finish and return direct queue.

...and this is where it dequeues direct packets first.

This is usually the result of a misconfiguration (sending packets to nonexistent class), but the HTB devs decided in that case, all traffic should be passed, instead of all traffic should be dropped (too destructive).

|improve this answer|||||

I am going to answer my own question since I have done some source code reading and research work myself. If I had not done some research work myself, the answers by frostschutz and sourcejedi would be of a great help too – they seem to be correct as far as my knowledge goes (although not into as much detail, but they give you a starting point to do the rest of the research yourself).

Some theory: There are two kinds of queuing disciplines: classful and classless.

Classful disciplines are (as the answer by sourcejedi says) flexible. They allow you to attach children classful qdiscs to them and can share bandwidth with other classes, when possible. Leaf classes have a classless qdisc (elementary/fundamental qdisc) attached to them (also called an elementary qdisc). The queues managed by these elementary qdiscs is where the packets get queued and dequeued. The packets are dequeued and enqueued from these classes by an algorithm corresponding to the class. Examples of classful qdiscs are: HTB and CBQ.

Classless qdiscs are the fundamental or the elementary qdiscs, which are rigid in the sense that they cannot have children qdiscs attached to them, nor can they share bandwidth. In naive terms, they are on their own. These qdiscs own a queue from which they queue and dequeue packets according to the algorithm corresponding the qdisc. Examples of classless qdisc: pfifo, bfifo, pfifo_fast (default used by Linux tc), tbf, sfq and a few more.

In the example tree in the question, each of the leaf htb classes 1:1, 1:2 and 1:3 has an elementary qdisc attached to it, which is by default pfifo (not pfifo_fast). The elementary qdisc attached to the leaf can be changed using the tc userspace utility in the following way:

tc qdisc add dev eth0 parent 1:11 handle 30: pfifo limit 5 
tc qdisc add dev eth0 parent 1:12 handle 40: sfq perturb 10

More details about this can be found in the HTB Linux queuing discipline manual.  Therefore the tree actually looks like this:

       1: root qdisc (class htb)
     / | \ 
    /  |  \
   /   |   \
 1:1  1:2  1:3    parent qdiscs (class htb)
(30)  (10)  (60)
 ||    ||    || -----> pfifo qdiscs (queue length: txqueuelen (default, can be changed by tc utitlity))

Notice the parameter txqueuelen is an interface-specific parameter. That means the parameter is a property of the interface and can be changed using iproute2 or ifconfig. By default, its value is 1000. Here is an example of how to change it to 200 it via iproute2:

ip link set eth0 txqueuelen 200

When a leaf node is created (in context of HTB qdisc), pfifo qdisc is attached to the leaf class by default.  This pfifo is initialized with a queue limit of txqueuelen of the interface.  This can be found in the function htb_change_class() in sch_htb.c, line 1395:

/* create leaf qdisc early because it uses kmalloc(GFP_KERNEL)
 * so that can't be used inside of sch_tree_lock
 * -- thanks to Karlis Peisenieks
new_q = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,
                          classid, NULL);

For the default queue length of a pfifo queue, refer to sch_fifo.c, line 61:

u32 limit = qdisc_dev(sch)->tx_queue_len;

The kernel interacts directly with the root qdisc (maybe classful or classless) when it wants to queue or dequeue a packet. If the root qdisc is classful and has children, then it first classifies the packet (decides which child to send the packet to). Kernel source where it is done: sch_htb.c, line 209:

static struct htb_class *htb_classify(struct sk_buff *skb, struct Qdisc *sch,
                                      int *qerr)

On reading the comments, one can easily infer that this function returns one of the following:

  1. NULL, if the packet should be dropped

  2. -1, if the packet should be queued into direct_queue

  3. a leaf node (which contains an elementary qdisc, where the packets actually end up)   This function traverses through all the interior nodes (Classes) of the tree until it returns a leaf node, where the packet should be queued.

While dequeuing, each of the classes follow the algo associated with their qdisc to decide which of the children to dequeue from, and children do the same thing, until a packet is dequeued from an elementary qdisc attached to a leaf class. This also ensures that the rate of a child class is no more than its parent. (Since the parent will decide whether the packet will pass through or not). I have not gone through the source of dequeuing in htb, so I can't provide a source for that.

Direct queue: It is a special internal fifo queue maintained by the HTB qdisc from which the packets are dequeued at hardware speed. Its queue length is txqueuelen. A packet ends up in a direct queue if HTB is unable to classify it into one of the children qdiscs, and the default is not specified.

So the answers to my own questions:

  1. Yes, since they are leaf nodes, by default they are pfifo queues with queue length txqueuelen of the interface which is 1000 by default and can be changed.

  2. A queuing discipline is like the algo together with the queue combined in a single package! If you ask me, queuing discipline is property of both the type of queue and the packet scheduler (here packet scheduler means the algo which enqueues and dequeues the packet). For example, a queue might be of type pfifo or bfifo. The algo used for enqueuing and dequeuing is same, but the queue lengths are measured in bytes for the byte fifo (bfifo). Packets are dropped in a bfifo, when the byte limit is reached. The default byte limit is calculated as mtu*txqueuelen. When a packet is enqueued, for example, the packet length is added to the current queue length. Similarly, when the packet is dequeued, the packet length is subtracted from the queue length.

  3. Answered above.

Some sources one might consult:

  1. Linux Network Traffic Control — Implementation Overview (PDF)

  2. Journey to the Center of the Linux Kernel: Traffic Control, Shaping and QoS

  3. Demystification of TC - Criteo R&D Blog

  4. Queueing in the Linux Network Stack - Linux Journal

|improve this answer|||||

Some quick searches based on vague memories:

HTB is flexible. By default I think you get a FIFO for each leaf class, maybe it uses the default configuration for FIFO. However you can also e.g. use PFIFO or FQ_CODEL for a leaf class. See e.g. "optionally attach queuing disciplines to the leaf classes" here: http://luxik.cdi.cz/~devik/qos/htb/manual/userg.htm

I think you will see them if you run tc qdisc show.

"This 'direct' queue is only used if one of your filter explicitly targets the '0' classid of htb qdisc" https://lists.bufferbloat.net/pipermail/cerowrt-devel/2013-June/006507.html . The direct queue is not shaped. Apparently the length of the direct queue can now be controlled, although I do not know how (or whether) tc supports this. https://patchwork.ozlabs.org/patch/225546/

I would not say there is a separate "packet scheduler". A packet scheduler is a QDisc (although, man tc-tbf describes itself as "never schedules traffic"; what it means is that it never re-orders it).

|improve this answer|||||

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.