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).
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
ifconfig. By default, its value is 1000. Here is an example of how to change it to 200 it via
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
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,
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,
On reading the comments,
one can easily infer that this function returns one of the following:
NULL, if the packet should be dropped
-1, if the packet should be queued into direct_queue
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:
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.
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.
Some sources one might consult:
Linux Network Traffic Control — Implementation Overview (PDF)
Journey to the Center of the Linux Kernel: Traffic Control, Shaping and QoS
Demystification of TC - Criteo R&D Blog
Queueing in the Linux Network Stack - Linux Journal