<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML ><HEAD ><TITLE >Classful Queuing Disciplines (qdiscs)</TITLE ><META NAME="GENERATOR" CONTENT="Modular DocBook HTML Stylesheet Version 1.7"><LINK REL="HOME" TITLE="Traffic Control HOWTO" HREF="index.html"><LINK REL="PREVIOUS" TITLE="Classless Queuing Disciplines (qdiscs)" HREF="classless-qdiscs.html"><LINK REL="NEXT" TITLE="Rules, Guidelines and Approaches" HREF="rules.html"></HEAD ><BODY CLASS="section" BGCOLOR="#FFFFFF" TEXT="#000000" LINK="#0000FF" VLINK="#840084" ALINK="#0000FF" ><DIV CLASS="NAVHEADER" ><TABLE SUMMARY="Header navigation table" WIDTH="100%" BORDER="0" CELLPADDING="0" CELLSPACING="0" ><TR ><TH COLSPAN="3" ALIGN="center" >Traffic Control HOWTO: </TH ></TR ><TR ><TD WIDTH="10%" ALIGN="left" VALIGN="bottom" ><A HREF="classless-qdiscs.html" ACCESSKEY="P" >Prev</A ></TD ><TD WIDTH="80%" ALIGN="center" VALIGN="bottom" ></TD ><TD WIDTH="10%" ALIGN="right" VALIGN="bottom" ><A HREF="rules.html" ACCESSKEY="N" >Next</A ></TD ></TR ></TABLE ><HR ALIGN="LEFT" WIDTH="100%"></DIV ><DIV CLASS="section" ><H1 CLASS="section" ><A NAME="classful-qdiscs" ></A >7. Classful Queuing Disciplines (<A HREF="components.html#c-qdisc" ><TT CLASS="constant" >qdisc</TT ></A >s)</H1 ><P > 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. </P ><P > There are several common terms to describe classes directly attached to the <TT CLASS="constant" >root</TT > qdisc and terminal classes. Classess attached to the <TT CLASS="constant" >root</TT > 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. </P ><DIV CLASS="section" ><H2 CLASS="section" ><A NAME="qc-htb" ></A >7.1. HTB, Hierarchical Token Bucket</H2 ><P > HTB uses the concepts of tokens and buckets along with the class-based system and <A HREF="components.html#c-filter" ><TT CLASS="constant" >filter</TT ></A >s to allow for complex and granular control over traffic. With a complex <A HREF="classful-qdiscs.html#qc-htb-borrowing" >borrowing model</A >, HTB can perform a variety of sophisticated traffic control techniques. One of the easiest ways to use HTB immediately is that of <A HREF="classful-qdiscs.html#qc-htb-borrowing" >shaping</A >. </P ><P > By understanding <A HREF="overview.html#o-tokens" >tokens</A > and <A HREF="overview.html#o-buckets" >buckets</A > or by grasping the function of <A HREF="classless-qdiscs.html#qs-tbf" >TBF</A >, 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 <A HREF="elements.html#e-classifying" >classifying</A > scheme, traffic can be controlled in a very granular fashion. </P ><P > </P ><P > Below is example output of the syntax for HTB on the command line with the <A HREF="software.html#s-iproute2-tc" ><B CLASS="command" >tc</B ></A > tool. Although the syntax for <A HREF="software.html#s-tcng" ><B CLASS="command" >tcng</B ></A > is a language of its own, the rules for HTB are the same. </P ><DIV CLASS="example" ><A NAME="ex-qc-htb-usage" ></A ><P ><B >Example 10. <B CLASS="command" >tc</B > usage for HTB</B ></P ><TABLE BORDER="0" BGCOLOR="#E0E0E0" WIDTH="100%" ><TR ><TD ><FONT COLOR="#000000" ><PRE CLASS="programlisting" > 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 </PRE ></FONT ></TD ></TR ></TABLE ></DIV ><P > </P ><DIV CLASS="section" ><H3 CLASS="section" ><A NAME="qc-htb-software" ></A >7.1.1. Software requirements</H3 ><P > 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 <A HREF="http://luxik.cdi.cz/~devik/qos/htb/" TARGET="_top" >HTB</A > for an <B CLASS="command" >iproute2</B > patch to <B CLASS="command" >tc</B >. </P ></DIV ><DIV CLASS="section" ><H3 CLASS="section" ><A NAME="qc-htb-shaping" ></A >7.1.2. Shaping</H3 ><P > One of the most common applications of HTB involves shaping transmitted traffic to a specific rate. </P ><P > All shaping occurs in leaf classes. No shaping occurs in inner or root classes as they only exist to suggest how the <A HREF="classful-qdiscs.html#qc-htb-borrowing" >borrowing model</A > should distribute available tokens. </P ><P > </P ><P > </P ></DIV ><DIV CLASS="section" ><H3 CLASS="section" ><A NAME="qc-htb-borrowing" ></A >7.1.3. Borrowing</H3 ><P > A fundamental part of the HTB qdisc is the borrowing mechanism. Children classes borrow tokens from their parents once they have exceeded <A HREF="classful-qdiscs.html#vl-qc-htb-params-rate" ><TT CLASS="parameter" ><I >rate</I ></TT ></A >. A child class will continue to attempt to borrow until it reaches <A HREF="classful-qdiscs.html#vl-qc-htb-params-ceil" ><TT CLASS="parameter" ><I >ceil</I ></TT ></A >, 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. </P ><P > </P ><DIV CLASS="table" ><A NAME="tb-qc-htb-borrowing" ></A ><P ><B >Table 2. HTB class states and potential actions taken</B ></P ><TABLE BORDER="1" CLASS="CALSTABLE" ><THEAD ><TR ><TH ALIGN="LEFT" VALIGN="MIDDLE" >type of class</TH ><TH ALIGN="LEFT" VALIGN="MIDDLE" >class state</TH ><TH ALIGN="LEFT" VALIGN="MIDDLE" >HTB internal state</TH ><TH ALIGN="LEFT" VALIGN="MIDDLE" >action taken</TH ></TR ></THEAD ><TBODY ><TR ><TD ALIGN="LEFT" VALIGN="MIDDLE" >leaf</TD ><TD ALIGN="LEFT" VALIGN="MIDDLE" >< <TT CLASS="parameter" ><I >rate</I ></TT ></TD ><TD ALIGN="LEFT" VALIGN="MIDDLE" ><TT CLASS="parameter" ><I >HTB_CAN_SEND</I ></TT ></TD ><TD ALIGN="LEFT" VALIGN="MIDDLE" > Leaf class will dequeue queued bytes up to available tokens (no more than burst packets) </TD ></TR ><TR ><TD ALIGN="LEFT" VALIGN="MIDDLE" >leaf</TD ><TD ALIGN="LEFT" VALIGN="MIDDLE" >> <TT CLASS="parameter" ><I >rate</I ></TT >, < <TT CLASS="parameter" ><I >ceil</I ></TT ></TD ><TD ALIGN="LEFT" VALIGN="MIDDLE" ><TT CLASS="parameter" ><I >HTB_MAY_BORROW</I ></TT ></TD ><TD ALIGN="LEFT" VALIGN="MIDDLE" > Leaf class will attempt to borrow tokens/ctokens from parent class. If tokens are available, they will be lent in <TT CLASS="parameter" ><I >quantum</I ></TT > increments and the leaf class will dequeue up to <TT CLASS="parameter" ><I >cburst</I ></TT > bytes </TD ></TR ><TR ><TD ALIGN="LEFT" VALIGN="MIDDLE" >leaf</TD ><TD ALIGN="LEFT" VALIGN="MIDDLE" >> <TT CLASS="parameter" ><I >ceil</I ></TT ></TD ><TD ALIGN="LEFT" VALIGN="MIDDLE" ><TT CLASS="parameter" ><I >HTB_CANT_SEND</I ></TT ></TD ><TD ALIGN="LEFT" VALIGN="MIDDLE" > No packets will be dequeued. This will cause packet delay and will increase latency to meet the desired rate. </TD ></TR ><TR ><TD ALIGN="LEFT" VALIGN="MIDDLE" >inner, root</TD ><TD ALIGN="LEFT" VALIGN="MIDDLE" >< <TT CLASS="parameter" ><I >rate</I ></TT ></TD ><TD ALIGN="LEFT" VALIGN="MIDDLE" ><TT CLASS="parameter" ><I >HTB_CAN_SEND</I ></TT ></TD ><TD ALIGN="LEFT" VALIGN="MIDDLE" > Inner class will lend tokens to children. </TD ></TR ><TR ><TD ALIGN="LEFT" VALIGN="MIDDLE" >inner, root</TD ><TD ALIGN="LEFT" VALIGN="MIDDLE" >> <TT CLASS="parameter" ><I >rate</I ></TT >, < <TT CLASS="parameter" ><I >ceil</I ></TT ></TD ><TD ALIGN="LEFT" VALIGN="MIDDLE" ><TT CLASS="parameter" ><I >HTB_MAY_BORROW</I ></TT ></TD ><TD ALIGN="LEFT" VALIGN="MIDDLE" > Inner class will attempt to borrow tokens/ctokens from parent class, lending them to competing children in <TT CLASS="parameter" ><I >quantum</I ></TT > increments per request. </TD ></TR ><TR ><TD ALIGN="LEFT" VALIGN="MIDDLE" >inner, root</TD ><TD ALIGN="LEFT" VALIGN="MIDDLE" >> <TT CLASS="parameter" ><I >ceil</I ></TT ></TD ><TD ALIGN="LEFT" VALIGN="MIDDLE" ><TT CLASS="parameter" ><I >HTB_CANT_SEND</I ></TT ></TD ><TD ALIGN="LEFT" VALIGN="MIDDLE" > Inner class will not attempt to borrow from its parent and will not lend tokens/ctokens to children classes. </TD ></TR ></TBODY ></TABLE ></DIV ><P > 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. </P ><P > Any child class which wishes to borrow a token will request a token from its parent class, which if it is also over its <TT CLASS="parameter" ><I >rate</I ></TT > 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. </P ><DIV CLASS="mediaobject" ><P ><IMG SRC="images/htb-borrow.png"></P ></DIV ><P > Note in this diagram that there are several HTB root classes. Each of these root classes can simulate a virtual circuit. </P ></DIV ><DIV CLASS="section" ><H3 CLASS="section" ><A NAME="qc-htb-params" ></A >7.1.4. HTB class parameters</H3 ><P > </P ><P ></P ><DIV CLASS="variablelist" ><DL ><DT ><A NAME="vl-qc-htb-params-default" ></A ><TT CLASS="parameter" ><I >default</I ></TT ></DT ><DD ><P > An optional parameter with every HTB <A HREF="components.html#c-qdisc" ><TT CLASS="constant" >qdisc</TT ></A > object, the default <TT CLASS="parameter" ><I >default</I ></TT > is 0, which cause any unclassified traffic to be dequeued at hardware speed, completely bypassing any of the classes attached to the <TT CLASS="constant" >root</TT > qdisc. </P ></DD ><DT ><A NAME="vl-qc-htb-params-rate" ></A ><TT CLASS="parameter" ><I >rate</I ></TT ></DT ><DD ><P > Used to set the minimum desired speed to which to limit transmitted traffic. This can be considered the equivalent of a committed information rate (<SPAN CLASS="acronym" >CIR</SPAN >), or the guaranteed bandwidth for a given leaf class. </P ></DD ><DT ><A NAME="vl-qc-htb-params-ceil" ></A ><TT CLASS="parameter" ><I >ceil</I ></TT ></DT ><DD ><P > 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 <SPAN CLASS="QUOTE" >"burstable bandwidth"</SPAN >. </P ></DD ><DT ><A NAME="vl-qc-htb-params-burst" ></A ><TT CLASS="parameter" ><I >burst</I ></TT ></DT ><DD ><P > This is the size of the <A HREF="classful-qdiscs.html#vl-qc-htb-params-rate" ><TT CLASS="parameter" ><I >rate</I ></TT ></A > bucket (see <A HREF="overview.html#o-buckets" >Tokens and buckets</A >). HTB will dequeue <TT CLASS="parameter" ><I >burst</I ></TT > bytes before awaiting the arrival of more tokens. </P ></DD ><DT ><A NAME="vl-qc-htb-params-cburst" ></A ><TT CLASS="parameter" ><I >cburst</I ></TT ></DT ><DD ><P > This is the size of the <A HREF="classful-qdiscs.html#vl-qc-htb-params-ceil" ><TT CLASS="parameter" ><I >ceil</I ></TT ></A > bucket (see <A HREF="overview.html#o-buckets" >Tokens and buckets</A >). HTB will dequeue <TT CLASS="parameter" ><I >cburst</I ></TT > bytes before awaiting the arrival of more ctokens. </P ></DD ><DT ><A NAME="vl-qc-htb-params-quantum" ></A ><TT CLASS="parameter" ><I >quantum</I ></TT ></DT ><DD ><P > This is a key parameter used by HTB to control borrowing. Normally, the correct <TT CLASS="parameter" ><I >quantum</I ></TT > 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 <A HREF="classful-qdiscs.html#vl-qc-htb-params-rate" ><TT CLASS="parameter" ><I >rate</I ></TT ></A > (but below <A HREF="classful-qdiscs.html#vl-qc-htb-params-ceil" ><TT CLASS="parameter" ><I >ceil</I ></TT ></A >) and to transmit packets from these same classes. </P ></DD ><DT ><A NAME="vl-qc-htb-params-r2q" ></A ><TT CLASS="parameter" ><I >r2q</I ></TT ></DT ><DD ><P > Also, usually calculated for the user, <TT CLASS="parameter" ><I >r2q</I ></TT > is a hint to HTB to help determine the optimal <A HREF="classful-qdiscs.html#vl-qc-htb-params-quantum" ><TT CLASS="parameter" ><I >quantum</I ></TT ></A > for a particular class. </P ></DD ><DT ><A NAME="vl-qc-htb-params-mtu" ></A ><TT CLASS="parameter" ><I >mtu</I ></TT ></DT ><DD ><P > </P ></DD ><DT ><A NAME="vl-qc-htb-params-prio" ></A ><TT CLASS="parameter" ><I >prio</I ></TT ></DT ><DD ><P > </P ></DD ></DL ></DIV ><P > </P ></DIV ><DIV CLASS="section" ><H3 CLASS="section" ><A NAME="qc-htb-rules" ></A >7.1.5. Rules</H3 ><P > Below are some general guidelines to using HTB culled from <A HREF="http://docum.org/" TARGET="_top" >http://docum.org/</A > and the <A HREF="http://mailman.ds9a.nl/mailman/listinfo/lartc/" TARGET="_top" >LARTC mailing list</A >. 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. </P ><P > </P ><P ></P ><UL ><LI ><P > Shaping with HTB occurs only in leaf classes. See also <A HREF="classful-qdiscs.html#qc-htb-shaping" >Section 7.1.2</A >. </P ></LI ><LI ><P > Because HTB does not shape in any class except the leaf class, the sum of the <TT CLASS="parameter" ><I >rate</I ></TT >s of leaf classes should not exceed the <TT CLASS="parameter" ><I >ceil</I ></TT > of a parent class. Ideally, the sum of the <TT CLASS="parameter" ><I >rate</I ></TT >s of the children classes would match the <TT CLASS="parameter" ><I >rate</I ></TT > of the parent class, allowing the parent class to distribute leftover bandwidth (<TT CLASS="parameter" ><I >ceil</I ></TT > - <TT CLASS="parameter" ><I >rate</I ></TT >) among the children classes. </P ><P > 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 <A HREF="classful-qdiscs.html#qc-htb-borrowing" >Section 7.1.3</A >). </P ></LI ><LI ><P > The <TT CLASS="parameter" ><I >quantum</I ></TT > is only only used when a class is over <TT CLASS="parameter" ><I >rate</I ></TT > but below <TT CLASS="parameter" ><I >ceil</I ></TT >. </P ></LI ><LI ><P > The <TT CLASS="parameter" ><I >quantum</I ></TT > should be set at MTU or higher. HTB will dequeue a single packet at least per service opportunity even if <TT CLASS="parameter" ><I >quantum</I ></TT > is too small. In such a case, it will not be able to calculate accurately the real bandwidth consumed <A NAME="AEN1146" HREF="#FTN.AEN1146" ><SPAN CLASS="footnote" >[1]</SPAN ></A >. </P ></LI ><LI ><P > Parent classes lend tokens to children in increments of <TT CLASS="parameter" ><I >quantum</I ></TT >, so for maximum granularity and most instantaneously evenly distributed bandwidth, <TT CLASS="parameter" ><I >quantum</I ></TT > should be as low as possible while still no less than MTU. </P ></LI ><LI ><P > A distinction between tokens and ctokens is only meaningful in a leaf class, because non-leaf classes only lend tokens to child classes. </P ></LI ><LI ><P > HTB borrowing could more accurately be described as <SPAN CLASS="QUOTE" >"using"</SPAN >. </P ></LI ></UL ><P > </P ></DIV ></DIV ><DIV CLASS="section" ><H2 CLASS="section" ><A NAME="qc-hfsc" ></A >7.2. HFSC, Hierarchical Fair Service Curve</H2 ><P > The HFSC classful qdisc balances delay-sensitive traffic against throughput sensitive traffic. In a congested or backlogged state, the HFSC queuing discipline interleaves the delay-sensitive traffic when required according service curve definitions. Read about the Linux implementation in German, <A HREF="http://klaus.geekserver.net/hfsc/hfsc.html" TARGET="_top" >HFSC Scheduling mit Linux</A > or read a translation into English, <A HREF="http://linux-ip.net/tc/hfsc.en/" TARGET="_top" >HFSC Scheduling with Linux</A >. The original research article, <A HREF="http://acm.org/sigcomm/sigcomm97/program.html#ab011" TARGET="_top" >A Hierarchical Fair Service Curve Algorithm For Link-Sharing, Real-Time and Priority Services</A >, also remains available. </P ><P > This section will be completed at a later date. </P ></DIV ><DIV CLASS="section" ><H2 CLASS="section" ><A NAME="qc-prio" ></A >7.3. PRIO, priority scheduler</H2 ><P > 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. </P ><P > This section will be completed at a later date. </P ></DIV ><DIV CLASS="section" ><H2 CLASS="section" ><A NAME="qc-cbq" ></A >7.4. CBQ, Class Based Queuing</H2 ><P > CBQ is the classic implementation (also called venerable) of a traffic control system. This section will be completed at a later date. </P ><P > </P ></DIV ></DIV ><H3 CLASS="FOOTNOTES" >Notes</H3 ><TABLE BORDER="0" CLASS="FOOTNOTES" WIDTH="100%" ><TR ><TD ALIGN="LEFT" VALIGN="TOP" WIDTH="5%" ><A NAME="FTN.AEN1146" HREF="classful-qdiscs.html#AEN1146" ><SPAN CLASS="footnote" >[1]</SPAN ></A ></TD ><TD ALIGN="LEFT" VALIGN="TOP" WIDTH="95%" ><P > HTB will report bandwidth usage in this scenario incorrectly. It will calculate the bandwidth used by <TT CLASS="parameter" ><I >quantum</I ></TT > instead of the real dequeued packet size. This can skew results quickly. </P ></TD ></TR ></TABLE ><DIV CLASS="NAVFOOTER" ><HR ALIGN="LEFT" WIDTH="100%"><TABLE SUMMARY="Footer navigation table" WIDTH="100%" BORDER="0" CELLPADDING="0" CELLSPACING="0" ><TR ><TD WIDTH="33%" ALIGN="left" VALIGN="top" ><A HREF="classless-qdiscs.html" ACCESSKEY="P" >Prev</A ></TD ><TD WIDTH="34%" ALIGN="center" VALIGN="top" ><A HREF="index.html" ACCESSKEY="H" >Home</A ></TD ><TD WIDTH="33%" ALIGN="right" VALIGN="top" ><A HREF="rules.html" ACCESSKEY="N" >Next</A ></TD ></TR ><TR ><TD WIDTH="33%" ALIGN="left" VALIGN="top" >Classless Queuing Disciplines (<A HREF="components.html#c-qdisc" ><TT CLASS="constant" >qdisc</TT ></A >s)</TD ><TD WIDTH="34%" ALIGN="center" VALIGN="top" > </TD ><TD WIDTH="33%" ALIGN="right" VALIGN="top" >Rules, Guidelines and Approaches</TD ></TR ></TABLE ></DIV ></BODY ></HTML >