Classful and Classless Qdiscs

Every queueing discipline (qdisc) attached to a Linux network device falls into one of two families, and the distinction governs everything you can do with it. A classless qdisc is a single, opaque queue with one built-in policy — packets go in, the qdisc decides the order and rate they come out, and there is nothing inside to configure beyond that policy’s own parameters (pfifo_fast, fq_codel, fq, tbf, sfq, codel). A classful qdisc is a container: it owns a tree of classes, each class can hold its own child qdisc, and filters (The tc Tool and Filters) steer packets into specific leaf classes, letting you partition and prioritize bandwidth per traffic type (htb, hfsc, prio, drr). The canonical classful qdisc is HTB (Hierarchical Token Bucket), whose rate/ceil borrowing model lets a class guarantee a floor of bandwidth while opportunistically borrowing idle bandwidth from siblings up to a ceiling. This note teaches the two families, the class-tree mechanics, HTB’s borrowing algorithm, and the token-bucket math that underlies both TBF and HTB, all pinned to Linux 6.12 LTS (released 2024-11-17) with code verified against the v6.12 source tree.

This note assumes you have read Queueing Disciplines qdisc for the generic qdisc object (the Qdisc_ops .enqueue/.dequeue contract, the per-device root qdisc, handles like 1:, and how the transmit path pulls packets out) and Traffic Control Overview for the place traffic control occupies on the egress path. Here we focus on the taxonomy and the scheduling/shaping algorithms themselves.

Mental Model — One Queue Versus a Tree of Queues

The right way to picture the difference is flat versus hierarchical. A classless qdisc is a black box with one inlet and one outlet; whatever ordering or rate-limiting logic it implements is fixed and applies uniformly to every packet that enters. You cannot reach inside it, you cannot attach a child to part of it, and a filter attached to it can at most select among any internal bands it exposes (as prio and pfifo_fast do) but cannot create new structure.

A classful qdisc, by contrast, is the root of a tree. The qdisc itself is the root node (handle 1:); under it sit classes (1:10, 1:20, …), each of which is an internal scheduling slot that can either hold further child classes (an interior class) or hold a leaf qdisc — by default a simple FIFO, but you can replace it with any qdisc, classless or classful. Packets are classified into leaf classes by filters; the scheduling algorithm of the parent qdisc then decides, at dequeue time, which leaf’s packet leaves next and (for shaping qdiscs) whether it is allowed to leave yet.

flowchart TB
  subgraph CLASSLESS["Classless qdisc — one policy, no structure"]
    IN1["packets in"] --> Q["fq_codel / tbf / sfq<br/>single internal policy"]
    Q --> OUT1["packets out (ordered/shaped)"]
  end

  subgraph CLASSFUL["Classful qdisc — a tree of classes"]
    ROOT["root qdisc 1:<br/>(htb)"]
    ROOT --> C10["class 1:10<br/>rate 30mbit ceil 100mbit"]
    ROOT --> C20["class 1:20<br/>rate 70mbit ceil 100mbit"]
    C10 --> L10["leaf qdisc<br/>fq_codel"]
    C20 --> L21["class 1:21 (interior)"]
    C20 --> L22["class 1:22 (interior)"]
    L21 --> LQ1["leaf qdisc<br/>fq_codel"]
    L22 --> LQ2["leaf qdisc<br/>fq_codel"]
    FILT["filters classify<br/>packets into leaves"] -.->|"see The tc Tool and Filters"| C10
    FILT -.-> LQ1
    FILT -.-> LQ2
  end

Left: a classless qdisc is a single queue with a fixed policy — there is nothing inside to address. Right: a classful qdisc (HTB shown) is a tree whose interior nodes are classes and whose leaves hold child qdiscs; filters steer packets into the leaves. The insight to take: classful qdiscs let you express bandwidth as a hierarchy (“the database tier gets at least 30 Mbit but may borrow up to 100 when the link is idle”), which a flat classless qdisc fundamentally cannot — the price is configuration complexity and the need for filters.

Classless Qdiscs — One Policy, No Knobs Beyond It

A classless qdisc registers a Qdisc_ops with .enqueue, .dequeue, and .peek callbacks and no class-management operations. Its behaviour is its algorithm. The kernel ships several:

• pfifo/bfifo — a plain first-in-first-out queue bounded by packet count (pfifo) or bytes (bfifo). It does nothing but buffer; it is the default leaf qdisc that classful classes wrap.
• pfifo_fast — historically the compiled-in default. It is a three-band priority FIFO: bands are selected by the packet’s Type-of-Service / skb->priority via a fixed prio2band map, and a higher-priority band is always drained before a lower one. In v6.12 the per-device default is set by default_qdisc_ops = &pfifo_fast_ops in net/sched/sch_generic.c.
• fq_codel (Fair Queuing with Controlled Delay) and codel — active-queue-management qdiscs that fight bufferbloat by dropping/marking packets that sit too long in the queue (a sojourn-time target), with fq_codel adding per-flow fair queuing on top. These are covered in Queueing Disciplines qdisc and cross-link to Byte Queue Limits and Buffer Bloat.
• fq (Fair Queue / pacing) — per-flow scheduling with packet pacing, the qdisc designed to pair with the BBR congestion-control algorithm (see TCP Congestion Control).
• sfq (Stochastic Fairness Queueing) — hashes flows into a fixed number of FIFO sub-queues and round-robins among them, giving approximate per-flow fairness cheaply.
• tbf (Token Bucket Filter) — a pure rate-limiter; covered in depth below because its token-bucket core is the same mechanism HTB uses internally.

Uncertain

Verify: the effective default qdisc on a running system. The kernel’s compiled-in default is pfifo_fast (confirmed: default_qdisc_ops = &pfifo_fast_ops in v6.12 sch_generic.c), but the net.core.default_qdisc sysctl overrides it at device-creation time (set_default_qdisc in net/core/sysctl_net_core.c), and systemd sets it to fq_codel on most modern distributions. So “the default qdisc is fq_codel” is true as deployed on a typical distro but false as compiled in the kernel — the precise systemd default and per-distro behaviour is a userspace decision, not a kernel fact, and should be checked with sysctl net.core.default_qdisc on the target system. Reason: distro/systemd policy varies and is not in the kernel source. uncertain

TBF — The Token Bucket, Walked Symbol by Symbol

TBF is the simplest shaping qdisc and the clearest place to learn the token-bucket model that HTB reuses. The formal definition in the source comment (net/sched/sch_tbf.c) is: a data flow obeys TBF with rate R and bucket depth B if, for any interval from time t_i to t_f, the number of transmitted bits does not exceed B + R·(t_f − t_i). In the packetized version, for a sequence of packets of sizes s_i served at times t_i, for any i ≤ k:

s_i + … + s_k  ≤  B + R · (t_k − t_i)

Reading the symbols: s_i … s_k is the total bytes sent in the window, B is the bucket depth (the maximum burst — bytes you may send instantaneously when the bucket is full), R is the sustained rate, and R·(t_k − t_i) is the bytes “earned” by the passage of time. The bucket holds N(t) tokens, initialized to B/R and growing as N(t + δ) = min{B/R, N(t) + δ} — i.e. it refills at the rate of one unit of “send-time” per unit of real time, capped at the depth. A head-of-queue packet of length S may be transmitted only when S/R ≤ N(t), and on transmission the bucket drops by S/R. Two consequences fall out of the math and are stated in the source comment: the maximum burst rate is R_crit = B · HZ (because the watchdog timer resolution is 1/HZ, so within one tick you can drain the whole bucket), and to get a high peak rate TBF supports a second, smaller bucket with peak rate P and depth M (equal to the link MTU) that limits short-timescale bursts — the “double TBF” where P > R and B > M.

The actual v6.12 dequeue logic implements this directly. In tbf_dequeue (sch_tbf.c), tokens are tracked in nanoseconds of send-time, not abstract units:

now  = ktime_get_ns();
toks = min_t(s64, now - q->t_c, q->buffer);   /* time since last send, capped at bucket depth */
/* (peak bucket: ptoks computed the same way, capped at q->mtu) */
toks += q->tokens;                              /* add tokens accumulated before */
if (toks > q->buffer) toks = q->buffer;         /* clamp to depth B */
toks -= (s64) psched_l2t_ns(&q->rate, len);     /* subtract cost of this packet (len → time at rate R) */
 
if ((toks | ptoks) >= 0) {                       /* enough tokens in BOTH buckets? */
    skb = qdisc_dequeue_peeked(q->qdisc);        /* release the packet */
    q->t_c = now; q->tokens = toks; q->ptokens = ptoks;
    return skb;
}
qdisc_watchdog_schedule_ns(&q->watchdog, now + max_t(long, -toks, -ptoks));  /* else sleep until enough */

Line by line: q->t_c is the last “check-point” time; now - q->t_c is how much send-time has accrued since then, capped at q->buffer (the depth, in nanoseconds). psched_l2t_ns(&q->rate, len) converts the packet’s length to the nanoseconds it would take to transmit at rate R — that is the cost subtracted from the bucket. If both the rate bucket (toks) and the optional peak bucket (ptoks) are non-negative, the packet is released and the buckets are debited; otherwise the watchdog timer is armed for exactly max(-toks, -ptoks) nanoseconds — the moment the bucket will have refilled enough — and the qdisc throttles. This is the entire shaping mechanism: time is the only source of tokens, and a packet may leave only when enough time-tokens have accumulated to pay for it.

Classful Qdiscs — The Class Tree

A classful qdisc adds class-management operations to its Qdisc_ops (.graft, .leaf, .find, .change, .delete, .walk, plus a .tcf_block/.tcf_chain to host filters). Each class has a 32-bit handle of the form major:minor, where major matches the qdisc’s handle and minor is the class number — so 1:10 is class 10 under root qdisc 1:. The class tree has these invariants:

• Leaves hold child qdiscs. A class with no child classes is a leaf; by default it holds a FIFO, replaceable with any qdisc. Packets only ever physically queue at leaves.
• Filters classify into leaves. A packet entering the root qdisc is run through the filter chain (The tc Tool and Filters); the filter returns a classid naming the leaf class whose qdisc the packet is enqueued into. If no filter matches, the qdisc’s default class (or band) is used.
• The parent schedules among children. At dequeue, the qdisc walks its tree according to its scheduling algorithm to pick which leaf releases the next packet.

The four in-tree classful qdiscs differ entirely in that scheduling algorithm:

• prio — strict priority. A fixed number of bands (classes :1, :2, …); prio_dequeue (sch_prio.c) loops bands lowest-to-highest and returns the first non-empty one, so a higher-priority band is always fully drained before a lower one is touched. There is no shaping and no fairness — just priority. It is the classful generalization of pfifo_fast.
• drr — Deficit Round Robin. Approximate fair sharing by byte quantum rather than rate.
• hfsc — Hierarchical Fair Service Curve. Decouples bandwidth and delay guarantees using piecewise-linear service curves.
• htb — Hierarchical Token Bucket. Rate guarantees with ceiling-bounded borrowing; the workhorse for bandwidth partitioning.

DRR — Deficit Round Robin, the Quantum Mechanism

DRR is the cleanest fairness scheduler to read. Each class carries a configured quantum (bytes, defaulting to the interface MTU) and a running deficit counter. Active classes (those with queued packets) sit on a round-robin list. drr_dequeue (sch_drr.c) takes the class at the head of the active list, and:

cl = list_first_entry(&q->active, struct drr_class, alist);
skb = cl->qdisc->ops->peek(cl->qdisc);
len = qdisc_pkt_len(skb);
if (len <= cl->deficit) {        /* class has enough deficit credit */
    cl->deficit -= len;          /* spend it, send the packet */
    ... return skb;
}
cl->deficit += cl->quantum;      /* not enough: top up by one quantum */
list_move_tail(&cl->alist, &q->active);  /* and move to back of the round-robin */

The insight: a class accumulates quantum bytes of “credit” each time its turn comes around. When the head packet is no larger than the accumulated deficit, it is sent and the deficit is debited by the packet length; otherwise the class gets one more quantum added and yields its turn to the back of the list. Over many rounds, each class sends in proportion to its quantum — fair sharing weighted by quantum, with the deficit counter elegantly handling the fact that packets are variable-sized and you cannot send a fractional packet. DRR’s weakness is that it gives fairness but no rate ceiling and no latency bound; a class can monopolize the link if others are idle, and a low-quantum class can suffer high latency.

HTB — The Canonical Shaping Qdisc

HTB is “TBF with multiple classes” (the source comment in net/sched/sch_htb.c), implementing David Floyd’s link-sharing model. It is the default choice when you want to guarantee a floor of bandwidth to each traffic class while letting idle bandwidth be borrowed up to a ceiling. Every HTB class carries two token buckets, not one:

• a rate bucket with rate rate and depth buffer (configured as burst), controlling the guaranteed rate; its current fill is tokens.
• a ceil bucket with rate ceil and depth cbuffer (configured as cburst), controlling the maximum rate including borrowed bandwidth; its current fill is ctokens.

Per the tc-htb(8) man page: rate is “maximum rate this class and all its children are guaranteed,” ceil is “maximum rate at which a class can send, if its parent has bandwidth to spare,” and ceil defaults to rate — meaning no borrowing unless you explicitly set a higher ceiling.

The Three Class Modes and the Levels

Each class is in exactly one of three modes (enum htb_cmode in sch_htb.c):

• HTB_CAN_SEND — the class is under its own guaranteed rate (rate bucket has tokens); it may send from its own allotment.
• HTB_MAY_BORROW — the class is over its rate but under its ceil; it has no tokens of its own but its ceil bucket still has tokens, so it may borrow rate from an ancestor.
• HTB_CANT_SEND — the class is at its ceil (ceil bucket empty); it cannot send at all and is parked on a wait tree until its bucket refills.

htb_class_mode computes the mode from the two buckets (sch_htb.c):

if ((toks = (cl->ctokens + *diff)) < htb_lowater(cl)) { *diff = -toks; return HTB_CANT_SEND; }
if ((toks = (cl->tokens  + *diff)) >= htb_hiwater(cl))                  return HTB_CAN_SEND;
*diff = -toks;                                                          return HTB_MAY_BORROW;

*diff is the elapsed time since the class last sent (so ctokens + diff is the current ceil-bucket fill). If even the ceil bucket is below its low-water mark, the class CANT_SEND and *diff is set to how long until it can. If the rate bucket is above its high-water mark, it CAN_SEND. Otherwise it MAY_BORROW. (htb_lowater/htb_hiwater are zero unless the htb_hysteresis module parameter is on, which adds a small dead-band to cut mode-transition churn at ~1/6 the CPU cost.)

Classes are organized by level: leaves are always level 0, root classes are level TC_HTB_MAXDEPTH-1, and each interior node is one level below its parent. Borrowing flows up the levels: a leaf that MAY_BORROW borrows from its parent’s rate allotment, and the parent may itself borrow from its parent, recursively, as long as each ancestor is CAN_SEND or MAY_BORROW.

Charging Up the Ancestors

The heart of HTB is htb_charge_class (sch_htb.c), called after a leaf dequeues a packet. It walks from the leaf up toward the root, debiting buckets:

while (cl) {
    diff = min_t(s64, q->now - cl->t_c, cl->mbuffer);
    if (cl->level >= level) {                 /* at or above the borrow level: charge the RATE bucket */
        if (cl->level == level) cl->xstats.lends++;
        htb_accnt_tokens(cl, bytes, diff);    /* debit rate tokens, refill by elapsed time */
    } else {                                  /* below the borrow level: this class borrowed */
        cl->xstats.borrows++;
        cl->tokens += diff;                   /* only advance its clock, don't charge its rate */
    }
    htb_accnt_ctokens(cl, bytes, diff);       /* ALWAYS charge the CEIL bucket */
    cl->t_c = q->now;
    /* recompute mode; if it changed, move the class on/off the wait tree */
    old_mode = cl->cmode;
    htb_change_class_mode(q, cl, &diff);
    if (old_mode != cl->cmode) { /* re-park on wait tree at the right level */ }
    cl = cl->parent;
}

The crucial asymmetry: the ceil bucket is always charged (every class on the path pays its ceil tokens for the bytes that flowed through it), but the rate bucket is charged only at or above the level the packet was actually served from. A class that lent bandwidth (level ≥ the serve level) has its rate tokens debited — it “spent” its guarantee. A class that borrowed (below the serve level) does not pay rate tokens, only ceil tokens. This is exactly what makes the guarantee hold: borrowing a sibling’s idle bandwidth never consumes your own rate allotment, but it always counts against your ceiling. If a charge pushes any class into a new mode, it is moved on or off the per-level wait tree (an rbtree keyed by the time it will next be eligible), so the dequeue loop knows when to revisit it.

What You Get and What You Pay

The combined effect: under a class’s rate, it sends freely (CAN_SEND). Between rate and ceil, it sends only if an ancestor has spare rate to lend (MAY_BORROW). At ceil, it is throttled (CANT_SEND). Idle bandwidth is recycled to whoever can use it, bounded by ceilings, while guarantees are never violated. The cost is configuration care: the quantum (bytes served per round, defaulting to rate / r2q where r2q defaults to 10) governs round-robin granularity, and a too-small burst/cburst can prevent a class from ever reaching its configured rate at high link speeds — a classic HTB tuning trap discussed below.

Failure Modes and Common Misunderstandings

“My HTB class never reaches its configured rate.” At high link speeds the burst/cburst (the bucket depths buffer/cbuffer) must be large enough that one timer tick’s worth of tokens can pay for a full packet. The man page rule of thumb: burst should be at least rate / HZ bytes. Too small a burst and the class is throttled below its nominal rate because the bucket cannot hold enough tokens to cover the inter-tick gap. The kernel’s tc historically warned about this; if a class underperforms, check the burst sizing first.

“Borrowing isn’t happening.” Because ceil defaults to rate, a class with no explicit ceil cannot borrow at all — its ceil bucket and rate bucket are identical, so it is never in MAY_BORROW. You must set ceil > rate (typically to the link rate) for idle-bandwidth borrowing to occur.

“prio is starving my low-priority traffic.” prio is strict priority with no fairness or rate limit — a saturated high band will starve every lower band indefinitely. If you need a floor for lower-priority traffic, you want HTB (with a guaranteed rate per class), not prio.

Confusing the qdisc handle with a class handle. 1: is the qdisc (minor 0); 1:1, 1:10 are classes. Filters classify to a classid (a class handle), the default parameter names a minor number, and packets only queue at leaves. Attaching a filter to a non-classful qdisc, or pointing a classid at a non-existent class, silently misroutes traffic.

Global qdisc lock contention. Classful qdiscs (and most classless ones) run under a single per-qdisc spinlock (qdisc->seqlock/root lock); on a busy multi-queue NIC this lock can become the bottleneck. The mq/mqprio “multiqueue” qdiscs and per-CPU lockless qdiscs (TCQ_F_NOLOCK, e.g. pfifo_fast) exist precisely to avoid this — covered in Queueing Disciplines qdisc.

Alternatives and When to Choose Them

• Need only rate-limiting, no hierarchy? Use tbf (classless) — one bucket, simple, no filters needed. HTB with a single class is overkill.
• Need bandwidth partitioning with borrowing? Use htb — the standard answer, well-understood, the LARTC reference qdisc.
• Need decoupled bandwidth and latency guarantees? Use hfsc — its real-time service curve can bound a flow’s delay independently of its bandwidth share, which HTB’s coupled rate/ceil cannot. HFSC is more complex and less commonly used.
• Need strict priority with no shaping? Use prio — bands, nothing else.
• Need fair sharing by weight, no rate cap? Use drr (or sfq/fq_codel for the classless, per-flow version).
• Need to fight bufferbloat / latency on a shared link? Use fq_codel or cake (classless AQM) — for most modern desktop/router links these beat hand-tuned HTB, because the problem is queue latency, not bandwidth partitioning. See Byte Queue Limits and Buffer Bloat.

Production Notes

HTB is the qdisc most production traffic-shaping setups reach for — ISP bandwidth tiers, per-tenant rate limits, and home-router QoS scripts overwhelmingly use HTB leaves with fq_codel underneath each class (HTB to partition, fq_codel to de-bloat within each partition). A frequent real-world pattern is htb at the root for per-class rate/ceil, a child fq_codel on each leaf to keep per-class latency low, and tc filter rules (often flower, see The tc Tool and Filters) to classify. Container and Kubernetes bandwidth limiting historically used HTB via CNI plugins’ bandwidth meta-plugin, which programs a tbf/htb qdisc on the pod’s veth interface.

A recurring operational gotcha: HTB accuracy degrades at multi-gigabit speeds because the shaping is timer-driven (1/HZ resolution) and software-only; for line-rate shaping people move to hardware offload or fq-based pacing. Another: because the whole tree runs under one lock, very high packet rates through a deep HTB tree can saturate a CPU on the qdisc lock alone — one reason modern high-throughput designs prefer per-flow classless qdiscs or push shaping into the NIC.

See Also

• Parent / sibling: Queueing Disciplines qdisc — the generic qdisc object and the Qdisc_ops enqueue/dequeue contract these qdiscs implement
• Sibling: Traffic Control Overview — where qdiscs sit on the egress path
• Sibling: The tc Tool and Filters — the tc class/tc filter commands and the classifier subsystem that steers packets into HTB/PRIO/DRR leaf classes
• Related: Byte Queue Limits and Buffer Bloat — the bufferbloat problem fq_codel/codel address; TCP Congestion Control — fq pacing pairs with BBR
• Across: The Network Transmit Path — the egress path qdiscs schedule onto; veth Pairs — where pod bandwidth shaping is applied
• MOC: Linux Networking Stack MOC (§8 Traffic Control)