Time passes...

I highly suggest anyone reading this document to instead read my Practical Guide to Linux Traffic Control. It is current, detailed, and more accurate.

Tell your friends.

...ancient document continues...

My application of something as powerful as traffic shaping is actually quite boring. You can do many interesting and complicated things, but I simply limit a few select classes of traffic to a lesser enough portion of my bandwidth that I retain low latency, good response times, and functional interactivity in my ssh sessions with remote hosts on the Internet.

That said, there are many things this document is not:

• a discussion of firewall configuration or setup using Linux v2.4 netfilter (iptables)
• a tutorial on how to patch and compile your own Linux kernel
• an exploration of the technical side of traffic shaping, TCP/IP traffic, or routing
• not necessarily entirely accurate -- but if I've made a mistake, please let me know
• evidence that I in any way claim responsibility for what you do with this information; if it breaks your computer, blows up your house, or eats your neighbor's dog, I am not responsible

With that in mind, let's get started. First, if you haven't, please read about HTB itself. Then, for those following along at home, you'll need to download the following list of software packages for this project:

• Linux 2.4.18 kernel source (HTB patches cleanly against it)
• HTB qdisc (Hierarchal Token Bucket)
• iproute2 tc binary that works with HTB
• HTB init wrapper script (v0.8.3)

As of 05/05/02, HTB v3 is available, but I have not used it. This document only covers how to get the HTB patched against 2.4.18 and linked above working. If you want to try out HTB v3, you're on your own. I suspect HTB init v0.8.3 will still work with HTB v3.

Once you've acquired these components, the order of operations will be to unpack, patch, and reconfigure your new 2.4.18 kernel. Next, we'll walk through a sample HTB init configuration. Finally, we'll reconfigure your iptables firewall to mark packets you want shaped by HTB.

Patching The Kernel

Assuming you're starting with a clean 2.4.18 source tree, the appropriate sequence of commands and output ought to be similar to:

nebula:/usr/src# tar -jxvf linux-2.4.18.tar.bz2
linux/arch/mips64/mips-boards/
linux/arch/mips64/mips-boards/atlas/
linux/arch/mips64/mips-boards/atlas/Makefile
linux/arch/mips64/mips-boards/atlas/atlas_int.c
linux/arch/mips64/mips-boards/atlas/atlas_rtc.c
linux/arch/mips64/mips-boards/atlas/atlas_setup.c
linux/arch/mips64/mips-boards/generic/
linux/arch/mips64/mips-boards/generic/Makefile
linux/arch/mips64/mips-boards/generic/cmdline.c
linux/arch/mips64/mips-boards/generic/display.c
linux/arch/mips64/mips-boards/generic/gdb_hook.c
...
linux/Documentation/power/
linux/Documentation/power/pci.txt
linux/Documentation/README.nsp_cs.eng
linux/REPORTING-BUGS
nebula:/usr/src#

Then, assuming you downloaded htb2_2.4.17.diff to /usr/src, do

nebula:/usr/src# cp htb2_2.4.17.diff linux

(You're welcomed to symlink the file, move it, or whatever as you see fit.)

Now we're going to patch the kernel we just untar'd.

nebula:/usr/src# cd linux
nebula:/usr/src/linux# patch -p1 < htb2_2.4.17.diff
patching file net/sched/Config.in
patching file net/sched/Makefile
patching file net/sched/sch_htb.c
patching file include/linux/pkt_sched.h
patching file net/sched/sch_api.c
nebula:/usr/src/linux# cd ..
nebula:/usr/src#

Selecting Kernel Options

For things to work, you'll need to select some additional kernel options to enable the HTB token bucket you just patched you kernel to support. If you've never setup traffic shaping before, you'll need to enable traffic shaping, too. Moreover, you'll need to enable netfilter support for iptables if you haven't set that up yet, either. (Configuring netfilter, besides setting up a mark rule for packets, is beyond the scope of this document. It's possible to get along fine without marking packets via netfilter, more on this later.)

Here are the relevant options for my 2.4.18 kernel supporting netfilter, traffic shaping, and HTB:

#
# Code maturity level options
#
CONFIG_EXPERIMENTAL=y
#
# Loadable module support
#
CONFIG_MODULES=y
CONFIG_MODVERSIONS=y
CONFIG_KMOD=y

#
# General setup
#
CONFIG_NET=y

#
# Networking options
#
CONFIG_PACKET=y
CONFIG_PACKET_MMAP=y
CONFIG_NETLINK_DEV=y
CONFIG_NETFILTER=y
# CONFIG_NETFILTER_DEBUG is not set
CONFIG_FILTER=y
CONFIG_UNIX=y
CONFIG_INET=y
# CONFIG_IP_MULTICAST is not set
CONFIG_IP_ADVANCED_ROUTER=y
CONFIG_IP_MULTIPLE_TABLES=y
CONFIG_IP_ROUTE_FWMARK=y
CONFIG_IP_ROUTE_NAT=y
CONFIG_IP_ROUTE_MULTIPATH=y
CONFIG_IP_ROUTE_TOS=y
CONFIG_IP_ROUTE_VERBOSE=y
CONFIG_IP_ROUTE_LARGE_TABLES=y
# CONFIG_IP_PNP is not set
# CONFIG_NET_IPIP is not set
# CONFIG_NET_IPGRE is not set
# CONFIG_ARPD is not set
# CONFIG_INET_ECN is not set
CONFIG_SYN_COOKIES=y

#
#   IP: Netfilter Configuration
#
CONFIG_IP_NF_CONNTRACK=m
CONFIG_IP_NF_FTP=m
CONFIG_IP_NF_IRC=m
CONFIG_IP_NF_QUEUE=m
CONFIG_IP_NF_IPTABLES=m
CONFIG_IP_NF_MATCH_LIMIT=m
CONFIG_IP_NF_MATCH_MAC=m
CONFIG_IP_NF_MATCH_MARK=m
CONFIG_IP_NF_MATCH_MULTIPORT=m
CONFIG_IP_NF_MATCH_TOS=m
CONFIG_IP_NF_MATCH_LENGTH=m
CONFIG_IP_NF_MATCH_TTL=m
CONFIG_IP_NF_MATCH_TCPMSS=m
CONFIG_IP_NF_MATCH_STATE=m
CONFIG_IP_NF_MATCH_UNCLEAN=m
CONFIG_IP_NF_MATCH_OWNER=m
CONFIG_IP_NF_FILTER=m
CONFIG_IP_NF_TARGET_REJECT=m
CONFIG_IP_NF_TARGET_MIRROR=m
CONFIG_IP_NF_NAT=m
CONFIG_IP_NF_NAT_NEEDED=y
CONFIG_IP_NF_TARGET_MASQUERADE=m
CONFIG_IP_NF_TARGET_REDIRECT=m
CONFIG_IP_NF_NAT_SNMP_BASIC=m
CONFIG_IP_NF_NAT_IRC=m
CONFIG_IP_NF_NAT_FTP=m
CONFIG_IP_NF_MANGLE=m
CONFIG_IP_NF_TARGET_TOS=m
CONFIG_IP_NF_TARGET_MARK=m
CONFIG_IP_NF_TARGET_LOG=m
CONFIG_IP_NF_TARGET_TCPMSS=m
# CONFIG_IP_NF_COMPAT_IPCHAINS is not set
# CONFIG_IP_NF_COMPAT_IPFWADM is not set
# CONFIG_IPV6 is not set
# CONFIG_KHTTPD is not set
# CONFIG_ATM is not set
# CONFIG_VLAN_8021Q is not set

#
# QoS and/or fair queueing
#
CONFIG_NET_SCHED=y
CONFIG_NET_SCH_CBQ=m
CONFIG_NET_SCH_HTB=m
CONFIG_NET_SCH_CSZ=m
CONFIG_NET_SCH_PRIO=m
CONFIG_NET_SCH_RED=m
CONFIG_NET_SCH_SFQ=m
CONFIG_NET_SCH_TEQL=m
CONFIG_NET_SCH_TBF=m
CONFIG_NET_SCH_GRED=m
CONFIG_NET_SCH_DSMARK=m
CONFIG_NET_SCH_INGRESS=m
CONFIG_NET_QOS=y
CONFIG_NET_ESTIMATOR=y
CONFIG_NET_CLS=y
CONFIG_NET_CLS_TCINDEX=m
CONFIG_NET_CLS_ROUTE4=m
CONFIG_NET_CLS_ROUTE=y
CONFIG_NET_CLS_FW=m
CONFIG_NET_CLS_U32=m
CONFIG_NET_CLS_RSVP=m
CONFIG_NET_CLS_RSVP6=m
CONFIG_NET_CLS_POLICE=y

#
# Network device support
#
CONFIG_NETDEVICES=y

#
# Ethernet (10 or 100Mbit)
#
CONFIG_NET_ETHERNET=y
CONFIG_NET_VENDOR_3COM=y
CONFIG_EL3=m

# CONFIG_PLIP is not set
CONFIG_PPP=m
# CONFIG_PPP_MULTILINK is not set
# CONFIG_PPP_FILTER is not set
CONFIG_PPP_ASYNC=m
CONFIG_PPP_SYNC_TTY=m
CONFIG_PPP_DEFLATE=m
CONFIG_PPP_BSDCOMP=m
# CONFIG_PPPOE is not set
# CONFIG_SLIP is not set

The above configuration snippet includes support for QoS and Netfilter. HTB is located in the QoS section. You'll note I also included PPP and a NIC in the above config, but it's likely you have that setup already. I left them for completeness. You can probably compile everything into the kernel, but I'll assume you compiled everything as a module from here forth.

Compile Your Kernel and Post Compile Check

Now, you can add whatever other patches you'd like, if necessary, and compile the kernel using your choice method. Personally, I use Debian's make-kpkg command, in the kernel-package package. Once you've compiled your kernel, install it and reboot your machine.

Check that you have the following modules in your /lib/modules/2.4.{17,18,ect} directory:

rebecca:/lib/modules/2.4.18/kernel/net# ls sched/ ipv4/netfilter/
ipv4/netfilter/:
ip_conntrack.o
ipt_LOG.o
ipt_length.o
ipt_tos.o
ip_conntrack_ftp.o
ipt_MARK.o
ipt_limit.o
ipt_ttl.o
ip_conntrack_irc.o
ipt_MASQUERADE.o
ipt_mac.o
ipt_unclean.o
ip_nat_ftp.o
ipt_MIRROR.o
ipt_mark.o
iptable_filter.o
ip_nat_irc.o
ipt_REDIRECT.o
ipt_multiport.o
iptable_mangle.o
ip_nat_snmp_basic.o
ipt_REJECT.o
ipt_owner.o
iptable_nat.o
ip_queue.o
ipt_TCPMSS.o
ipt_state.o
ip_tables.o
ipt_TOS.o
ipt_tcpmss.o

sched/:
cls_fw.o
cls_rsvp6.o
sch_cbq.o
sch_gred.o
sch_prio.o
sch_tbf.o
cls_route.o
cls_tcindex.o
sch_csz.o
sch_htb.o
sch_red.o
sch_teql.o
cls_rsvp.o
cls_u32.o
sch_dsmark.o
sch_ingress.o
sch_sfq.o
rebecca:/lib/modules/2.4.18/kernel/net#

Later on, when things are configured and running, lsmod should give output similar to what you see below:

rebecca:/lib/modules/2.4.18/kernel/net# lsmod
Module                  Size  Used by    Tainted: P
cls_route               4000   0  (unused)
cls_u32                 4676   0  (unused)
cls_fw                  2240   1
sch_sfq                 3328   2
sch_htb                12032   1
ipt_MARK                 736   3  (autoclean)
ipt_TOS                 1024  17  (autoclean)
ipt_MASQUERADE          1216   1  (autoclean)
ipt_state                608   3  (autoclean)
ipt_REJECT              2784   8  (autoclean)
ipt_LOG                 3200  11  (autoclean)
ipt_limit                960   4  (autoclean)
iptable_mangle          1728   0  (autoclean) (unused)
iptable_filter          1728   0  (autoclean) (unused)
ip_conntrack_irc        2464   0  (unused)
ip_nat_irc              2304   0  (unused)
ip_conntrack_ftp        3200   0  (unused)
ip_nat_ftp              2944   0  (unused)
iptable_nat            13140   2  [...]
ip_tables              10432  12  [...]
ip_conntrack           12908   4  [...]

Setting up HTB init

Now, it's time to setup HTB init, which greatly simplifies creating bandwidth management classes with HTB. For this discussion, I am going to assume that you have downloaded the tc command linked above along with HTB init and have placed them both in /usr/local/bin such that running ls against that directory returns (Of course your entries will vary greatly -- I renamed the tc binary so I knew what it was for and linked it back to itself):

rebecca:/usr/local/bin# ls -l
htb.init-v0.8.3
tc -> tc-htb
tc-htb
...

Now, I strongly recommend that you read the instructions in htb-init-v0.8.3 a few times so that you have a good understanding of how it likes things set up. The examples I intend to use below duplicate a fair amount of the material therein, so after reading that you might possibly want to skip this section or skim it.

Now, I edited these two entries and pointed them to the locations shown below:

### Default HTB_PATH & HTB_CACHE settings
HTB_PATH=${HTB_PATH:-/etc/htb}
HTB_CACHE=${HTB_CACHE:-/var/cache/htb.init}

You'll notice the defaults are different. What I use above works nicely, though. If you did go ahead and compile the QoS kernel options into the kernel itself, you'll want to pay special attention to the HTB_PROBE shell variable and make sure you set it to "" (nothing), so as not to break things.

Creating HTB init Configuration Files

Inside your HTB_PATH, /etc/htb, you'll create a set of configuration files with names that conveniently match up exactly with QoS interface and class ID hierarchies. Each file will have one or more options contained within.

rebecca:/usr/local/bin# ls /etc/htb/
eth0  eth0-2.root  eth0-2:10.ed  eth0-2:30.def

The first required file must be named after your interface name. For my setup, it's eth0. It must exist, even if it's empty. The only option you need to get started is the option DEFAULT, which denotes a QoS class ID which all unclassified traffic flows through. You'll probably want to define this to some integer greater than zero to "avoid surprises" as the HTB init documentation states. Here's my interface file:

rebecca:/etc/htb# cat eth0
# default
DEFAULT=30

Next, let's look at eth0-2.root, the next required file. It's useful to note that the period and everything following it in the filename is optional, for descriptive purposes. I appended root as a hint that this is my top level configuration file for my eth0 interface. You can set quite a few options inside this file, but to get started all you need to define is a RATE. Let's have a look:

rebecca:/etc/htb# cat eth0-2.root
RATE=112Kbit

I defined my RATE, which is essentially how fat your upstream pipe is, to 112 kilobits a second, or about 14K a second, the upper end of my residential Cable connection. Your RATE will probably be different, but it must be in kilobits per second.

Next, we'll look at a child of our eth0 with class ID of 2, class 2:10, which describes the RATE, CEILING, and so forth for my only classified traffic. Your desired setup will likely vary from this greatly:

rebecca:/etc/htb# cat eth0-2\:10.ed
RATE=80Kbit
CEIL=80Kbit
BURST=2K
LEAF=sfq
MARK=1

Here, I set the RATE for this class to a number less than what I earlier specified as my maximum possible RATE. That's because I wish to constrain traffic in this particular class, which I nicknamed ed for, not surprisingly, EDonkey. CEIL defaults to RATE, but if you specify it explicitly, the difference between the two is how much traffic this class can borrow from its parent class. In this case, the parent class has class ID 2. (And you'll remember from above is described as eth0-2.root.) In my configuration, I decided to disallow any borrowing of excess upstream bandwidth. If I had not included the CEIL variable, it would've had the same effect, because, again, CEIL defaults to RATE. I left it in for clarity. (If you haven't read the HTB author's page, linked above, which explains in great depth how class borrowing works, I highly recommend that you do, or this whole exercise will be a waste of your time.)

In this configuration file, I specified a BURST. You can include it in any file (excluding the interface file itself) you'd like, but it's calculated for you if you exclude it. At your discretion you can tweak it to some other value, and here I choose to set it to 2K. BURST is specified in bytes or kilobytes per second. It'll be more clear if I quote the relevant section of the htb-init file:

"BURST and CBURST parameters control the amount of data that can be sent from one class at maximum (hardware) speed before trying to service other class."

LEAF allows you to attach a queueing discipline to an HTB class file, such as the one above. You can choose from a few options, but the best is sfq. It ensures approximate fairness in sharing between multiple hosts assigned to the same class. You can set additional options for any of the available LEAFs you choose. You can only choose one.

MARK picks up on an internal packet mark made via Netfilter. Packets that I want included in this class are marked via an iptables rule. The integer will be one you specified to iptables for a particular match. In this instance, I marked relevant packets with the integer one. You can have multiple MARK entries in a class file.

That's about as complicated as it gets, actually. The last class file, 2:30, is for all unaccounted for traffic and thus it's the default class. You might remember we specified the DEFAULT as 30 in our root configuration file for eth0. Well, here it is:

rebecca:/etc/htb# cat eth0-2\:30.def
RATE=112Kbit
CEIL=112Kbit
BURST=2K
LEAF=sfq

You'll note there's nothing new here. The RATE and CEIL values are the same as for class ID 2 (eth0-2.root) and in fact we could have omitted both. The default would've been to use the RATE of the parent, and to set the CEIL value to the RATE. Again, I included both for clarity. I also attached sfq as my LEAF discipline. (The description, .def, is meant to stand for -- surprise -- default.)

Marking Packets With IPTables

Earlier we encountered the MARK option, and I had seemingly set mine to the integer one out of thin air. Well, no. Here's where I pulled that number from. If you didn't compile support for Netfilter, you won't be able to use this method for marking packets. (An alternate will be touched upon later.)

In my firewall script, I specify the following which works with iptables v1.2.6a, to mark the specific packets that interested me in class 2:10. Specifically, traffic coming or going on port 4662:

/sbin/iptables -A PREROUTING -t mangle -p tcp \
        --sport 4662 --j MARK --set-mark 1

/sbin/iptables -A PREROUTING -t mangle -p tcp \
        --dport 4662 --j MARK --set-mark 1

The traffic running through my firewall is all DNAT'd. It's possible you may need to use the INPUT chain instead if your setup is different. (Substitute INPUT for PREROUTING.) Previously I had specified an interface as well, but as of v1.2.6a, -j MARK will not accept an interface.

Marking Packets With HTB Init

Your other option for marking packets is to use the u32 filter directly via rules in your interface class files. So, for instance, instead of MARK=1 in my eth0-2:10.ed class file, I could've used:

RULE=*:4662,

Notice the trailing comma. It denotes a match on traffic leaving any host on port 4662. It helps to understand the intricacies of the u32 filter to fully utilize the RULE option. You can specify RULE multiple times in a class file.

Testing Your Configuration

To verify you selected the correct kernel options and that your kernel compiled okay, you might want to first set up a rather draconian class file with RATE set to something very, very small. Then, match traffic from one of your hosts against that rule, like:

/sbin/iptables -A PREROUTING -t mangle -p tcp \
       --src 192.168.0.3 --j MARK --set-mark 1

So, start to pull down a large file from your test machine. (Run dd if=/dev/zero of=/tmp/empty bs=1024 count=1000000 if you need a 100MB file.) Then, start HTB init like so:

rebecca:/root# /usr/local/bin/htb-init-v0.8.3 start

If started during your FTP or HTTP retrieval of the file, you should see a drastic reduction in throughput. That's HTB at work! Substitute stop for start when you want to turn off your HTB setup.

Finishing Up

If you want to do something more sophisticated than simply shaping traffic on a particular port or host and port, I recommend you read the following documents. Each contains a wealth of useful information that should help you tweak your HTB setup to match your needs. Remember, you can create as many classes for traffic as you need on as many interfaces as you need to shape. Enjoy.

• HTB's Web site
• Linux Advanced Routing & Traffic Control HOWTO
• Linux QoS and TC
• Linux Traffic Shaping Site

Copyright and Revision Information

04-26-02 - Initial Release; Incomplete
05-17-02 - First Complete Draft
10-30-04 - Document Retired