Linux 2.4 Advanced Routing HOWTO

Netherlabs BV (bert hubert <bert.hubert@netherlabs.nl>) Gregory Maxwell <greg@linuxpower.cx> Remco van Mook <remco@virtu.nl> Martijn van Oosterhout <kleptog@cupid.suninternet.com> Paul B Schroeder <paulsch@us.ibm.com> howto@ds9a.nl v0.3.0 $Date$

A very hands-on approach to iproute2, traffic shaping and a bit of netfilter

Contents

1 Dedication 4

2 Introduction 4 2.1 Disclaimer & License . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Prior knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3 What Linux can do for you . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.4 Housekeeping notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.5 Access, CVS & submitting updates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.6 Mailing list . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.7 Layout of this document . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3 Introduction to iproute2 7 3.1 Why iproute2? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.2 iproute2 tour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.3 Prerequisites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.4 Exploring your current configuration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

3.4.1 ip shows us our links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.4.2 ip shows us our IP addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.4.3 ip shows us our routes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3.5 ARP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

4 Rules - routing policy database 11 4.1 Simple source routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 5 GRE and other tunnels 13

5.1 A few general remarks about tunnels: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 5.2 IP in IP tunneling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 5.3 GRE tunneling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

5.3.1 IPv4 Tunneling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 5.3.2 IPv6 Tunneling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

5.4 Userland tunnels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

6 IPv6 tunneling with Cisco and/or 6bone 16 6.1 IPv6 Tunneling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

7 IPsec: secure IP over the internet 19

8 Multicast routing 19

9 Using Class Based Queueing for bandwidth management 19 9.1 What is queueing? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 9.2 First attempt at bandwidth division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 9.3 What to do with excess bandwidth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 9.4 Class subdivisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 9.5 Loadsharing over multiple interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

9.5.1 Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

10 More queueing disciplines 25 10.1 pfifo fast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 10.2 Stochastic Fairness Queueing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 10.3 Token Bucket Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 10.4 Random Early Detect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 10.5 Ingress policer qdisc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 10.6 DSMARK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

10.6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 10.6.2 What is Dsmark related to? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 10.6.3 Differentiated Services guidelines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 10.6.4 Working with Dsmark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 10.6.5 How SCH DSMARK works. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 10.6.6 TC INDEX Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 11 Other information 31

11.1 WRR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

12 Netfilter & iproute - marking packets 32

13 More classifiers 33 13.1 The ”fw” classifier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 13.2 The ”u32” classifier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

13.2.1 U32 selector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 13.2.2 General selectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 13.2.3 Specific selectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

13.3 The ”route” classifier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 13.4 The ”rsvp” classifier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 13.5 The ”tcindex” classifier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

14 Kernel network parameters 38 14.1 Reverse Path Filtering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 14.2 Obscure settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

14.2.1 Generic ipv4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 14.2.2 Per device settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 14.2.3 Neighbor pollicy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 14.2.4 Routing settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

15 Backbone applications of traffic control 45 15.1 Router queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

16 Cookbook 46 16.1 Running multiple sites with different SLAs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 16.2 Protecting your host from SYN floods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 16.3 Ratelimit ICMP to prevent dDoS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 16.4 Prioritizing interactive traffic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 16.5 Transparent web-caching using netfilter, iproute2, ipchains and squid . . . . . . . . . . . . . . 50

16.5.1 Traffic flow diagram after implementation . . . . . . . . . . . . . . . . . . . . . . . . . 53

17 Advanced Linux Routing 53 17.1 How does packet queueing really work? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 17.2 Advanced uses of the packet queueing system . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

17.3 Other packet shaping systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

18 Dynamic routing - OSPF and BGP 54

19 Other possibilities 55

20 Further reading 56

21 Acknowledgements 57

1 Dedication

This document is dedicated to lots of people, and is my attempt to do something back. To list but a few:

• Rusty Russell

• Alexey N. Kuznetsov

• The good folks from Google

• The staff of Casema Internet

2 Introduction

Welcome, gentle reader.

This document hopes to enlighten you on how to do more with Linux 2.2/2.4 routing. Unbeknownst to most users, you already run tools which allow you to do spectacular things. Commands like ’route’ and ’ifconfig’ are actually very thin wrappers for the very powerful iproute2 infrastructure

I hope that this HOWTO will become as readable as the ones by Rusty Russell of (amongst other things) netfilter fame.

You can always reach us by writing the HOWTO team <mailto:HOWTO@ds9a.nl>. However, please consider posting to the mailing list (see the relevant section) if you have questions which are not directly related to this HOWTO.

Before losing your way in this HOWTO, if all you want to do is simple traffic shaping, skip everything and head to the ’Other possibilties’ chapter, and read about CBQ.init.

2.1 Disclaimer & License

This document is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

In short, if your STM-64 backbone breaks down and distributes pornography to your most esteemed customers - it’s never our fault. Sorry.

Copyright (c) 2001 by bert hubert, Gregory Maxwell, Martijn van Oosterhout, Remco van Mook, Paul B. Schroeder and others.

Please freely copy and distribute (sell or give away) this document in any format. It’s requested that corrections and/or comments be fowarded to the document maintainer. You may create a derivative work and distribute it provided that you:

1. Send your derivative work (in the most suitable format such as sgml) to the LDP (Linux Documentation Project) or the like for posting on the Internet. If not the LDP, then let the LDP know where it is available.

2. License the derivative work with this same license or use GPL. Include a copyright notice and at least a pointer to the license used.

3. Give due credit to previous authors and major contributors.

If you’re considering making a derived work other than a translation, it’s requested that you discuss your plans with the current maintainer.

It is also requested that if you publish this HOWTO in hardcopy that you send the authors some samples for ’review purposes’ :-)

2.2 Prior knowledge

As the title implies, this is the ’Advanced’ HOWTO. While by no means rocket science, some prior knowledge is assumed. This document is meant as a sequel to the Linux 2.4 Networking HOWTO <http://www.ds9a. nl/2.4Networking/> by the same authors. You should probably read that first.

Here are some orther references which might help learn you more:

Rusty Russell’s networking-concepts-HOWTO <http://netfilter.kernelnotes.org/unreliable-guides/networking-concepts-HOWTO.html>

Very nice introduction, explaining what a network is, and how it is connected to other networks

Linux Networking-HOWTO (Previously the Net-3 HOWTO)

Great stuff, although very verbose. It learns you a lot of stuff that’s already configured if you are able to connect to the internet. Should be located in /usr/doc/HOWTO/NET3-4-HOWTO.txt but can be also

     be found online <http://www.linuxports.com/howto/networking>

2.3 What Linux can do for you

A small list of things that are possible:

• Throttle bandwidth for certain computers

• Throttle bandwidth TO certain computers

• Help you to fairly share your bandwidth

• Protect your network from DoS attacks • Protect the internet from your customers

• Multiplex several servers as one, for load balancing or enhanced availability

• Restrict access to your computers

• Limit access of your users to other hosts

• Do routing based on user id (yes!), MAC address, source IP address, port, type of service, time of day or content

Currently not many people are using these advanced features. This has several reasons. While the provided documentation is verbose, it is not very hands on. Traffic control is almost undocumented.

2.4 Housekeeping notes

There are several things which should be noted about this document. While I wrote most of it, I really don’t want it to stay that way. I am a strong believer in Open Source, so I encourage you to send feedback, updates, patches etcetera. Do not hesitate to inform me of typos or plain old errors. If my English sounds somewhat wooden, please realise that I’m not a native speaker. Feel free to send suggestions.

If you feel to you are better qualified to maintain a section, or think that you can author and maintain new sections, you are welcome to do so. The SGML of this HOWTO is available via CVS, I very much envision more people working on it.

In aid of this, you will find lots of FIXME notices. Patches are always welcome! Wherever you find a FIXME, you should know that you are treading unknown territory. This is not to say that there are no errors elsewhere, but be extra careful. If you have validated something, please let us know so we can remove the FIXME notice.

About this HOWTO, I will take some liberties along the road. For example, I postulate a 10Mbit internet connection, while I know full well that those are not very common.

2.5 Access, CVS & submitting updates

The canonical location for the HOWTO is here <http://www.ds9a.nl/2.4Routing>.

We now have anonymous CVS access available for the world at large. This is good in several ways. You can easily upgrade to newer versions of this HOWTO and submitting patches is no work at all.

Furthermore, it allows the authors to work on the source independently, which is good too.

     $ export CVSROOT=:pserver:anon@outpost.ds9a.nl:/var/cvsroot
     $ cvs login
     CVS password: [enter 'cvs' (without 's)]
     $ cvs co 2.4routing
     cvs server: Updating 2.4routing
     U 2.4routing/2.4routing.sgml

If you spot an error, or want to add something, just fix it locally, and run cvs diff -u, and send the result off to us.

A Makefile is supplied which should help you create postscript, dvi, pdf, html and plain text. You may need to install sgml-tools, ghostscript and tetex to get all formats.

2.6 Mailing list

The authors receive an increasing amount of mail about this HOWTO. Because of the clear interest of the community, it has been decided to start a mailinglist where people can talk to each other about Advanced Routing and Traffic Control. You can subscribe to the list here <http://mailman.ds9a.nl/mailman/

listinfo/lartc>.

It should be pointed out that the authors are very hesitant of answering questions asked not on the list. We would like the archive of the list to become some kind of knowledge base. If you have a question, please search the archive, and then post to the mailinglist.

2.7 Layout of this document

We will be doing interesting stuff almost immediately, which also means that there will initially be parts that are explained incompletely or are not perfect. Please gloss over these parts and assume that all will become clear.

Routing and filtering are two distinct things. Filtering is documented very well by Rusty’s HOWTOs, available here:

   • Rusty’s  Remarkably  Unreliable  Guides  <http://netfilter.kernelnotes.org/
     unreliable-guides/>

We will be focusing mostly on what is possible by combining netfilter and iproute2.

3 Introduction to iproute2

3.1 Why iproute2?

Most Linux distributions, and most UNIX’s, currently use the venerable ’arp’, ’ifconfig’ and ’route’ commands. While these tools work, they show some unexpected behaviour under Linux 2.2 and up. For example, GRE tunnels are an integral part of routing these days, but require completely different tools.

With iproute2, tunnels are an integral part of the tool set.

The 2.2 and above Linux kernels include a completely redesigned network subsystem. This new networking code brings Linux performance and a feature set with little competition in the general OS arena. In fact, the new routing, filtering, and classifying code is more featureful then that provided by many dedicated routers and firewalls and traffic shaping products.

As new networking concepts have been invented, people have found ways to plaster them on top of the existing framework in existing OSes. This constant layering of cruft has lead to networking code that is filled with strange behaviour, much like most human languages. In the past, Linux emulated SunOS’s handling of many of these things, which was not ideal.

This new framework makes it possible to clearly express features previously beyond Linux’s reach.

3.2 iproute2 tour

Linux has a sophisticated system for bandwidth provisioning called Traffic Control. This system supports various method for classifying, prioritizing, sharing, and limiting both inbound and outbound traffic.

We’ll start off with a tiny tour of iproute2 possibilities.

3.3 Prerequisites

You should make sure that you have the userland tools installed. This package is called ’iproute’ on both RedHat and Debian, and may otherwise be found at

ftp://ftp.inr.ac.ru/ip-routing/iproute2-2.2.4-now-ss??????.tar.gz".
You can also try here <ftp://ftp.inr.ac.ru/ip-routing/iproute2-current.tar.gz> for the latest ver-

sion.

Some parts of iproute require you to have certain kernel options enabled. It should also be noted that all releases of RedHat up to and including 6.2 come without most of the traffic control features in the default kernel.

FIXME: can anybody confirm that 7.0 does have the necessary stuff compiled in?

Also make sure that you have netlink support, should you chose to roll your own kernel. Iproute2 needs it.

3.4 Exploring your current configuration

This may come as a surprise, but iproute2 is already configured! The current commands ifconfig and route are already using the advanced syscalls, but mostly with very default (ie. boring) settings.

The ip tool is central, and we’ll ask it do display our interfaces for us.

3.4.1 ip shows us our links

     [ahu@home ahu]$ ip link list
     1: lo: <LOOPBACK,UP> mtu 3924 qdisc noqueue
         link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00
     2: dummy: <BROADCAST,NOARP> mtu 1500 qdisc noop
         link/ether 00:00:00:00:00:00 brd ff:ff:ff:ff:ff:ff
     3: eth0: <BROADCAST,MULTICAST,PROMISC,UP> mtu 1400 qdisc pfifo_fast qlen 100
         link/ether 48:54:e8:2a:47:16 brd ff:ff:ff:ff:ff:ff
     4: eth1: <BROADCAST,MULTICAST,PROMISC,UP> mtu 1500 qdisc pfifo_fast qlen 100
         link/ether 00:e0:4c:39:24:78 brd ff:ff:ff:ff:ff:ff
     3764: ppp0: <POINTOPOINT,MULTICAST,NOARP,UP> mtu 1492 qdisc pfifo_fast qlen 10
         link/ppp

Your mileage may vary, but this is what it shows on my NAT router at home. I’ll only explain part of the output as not everything is directly relevant.

We first see the loopback interface. While your computer may function somewhat without one, I’d advise against it. The MTU size (Maximum Transfer Unit) is 3924 octets, and it is not supposed to queue. Which makes sense because the loopback interface is a figment of your kernel’s imagination.

I’ll skip the dummy interface for now, and it may not be present on your computer. Then there are my two physical network interfaces, one at the side of my cable modem, the other serves my home ethernet segment. Furthermore, we see a ppp0 interface.

Note the absence of IP addresses. iproute disconnects the concept of ’links’ and ’IP addresses’. With IP aliasing, the concept of ’the’ IP address had become quite irrelevant anyhow.

It does show us the MAC addresses though, the hardware identifier of our ethernet interfaces.

3.4.2 ip shows us our IP addresses

     [ahu@home ahu]$ ip address show
     1: lo: <LOOPBACK,UP> mtu 3924 qdisc noqueue
         link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00
         inet 127.0.0.1/8 brd 127.255.255.255 scope host lo
     2: dummy: <BROADCAST,NOARP> mtu 1500 qdisc noop
         link/ether 00:00:00:00:00:00 brd ff:ff:ff:ff:ff:ff
     3: eth0: <BROADCAST,MULTICAST,PROMISC,UP> mtu 1400 qdisc pfifo_fast qlen 100
         link/ether 48:54:e8:2a:47:16 brd ff:ff:ff:ff:ff:ff
         inet 10.0.0.1/8 brd 10.255.255.255 scope global eth0
     4: eth1: <BROADCAST,MULTICAST,PROMISC,UP> mtu 1500 qdisc pfifo_fast qlen 100
         link/ether 00:e0:4c:39:24:78 brd ff:ff:ff:ff:ff:ff
     3764: ppp0: <POINTOPOINT,MULTICAST,NOARP,UP> mtu 1492 qdisc pfifo_fast qlen 10
         link/ppp
         inet 212.64.94.251 peer 212.64.94.1/32 scope global ppp0

This contains more information. It shows all our addresses, and to which cards they belong. ’inet’ stands for Internet (IPv4). There are lots of other address families, but these don’t concern us right now.

Let’s examine eth0 somewhat closer. It says that it is related to the inet address ’10.0.0.1/8’. What does this mean? The /8 stands for the number of bits that are in the Network Address. There are 32 bits, so we have 24 bits left that are part of our network. The first 8 bits of 10.0.0.1 correspond to 10.0.0.0, our Network Address, and our netmask is 255.0.0.0.

The other bits are connected to this interface, so 10.250.3.13 is directly available on eth0, as is 10.0.0.1 for example.

With ppp0, the same concept goes, though the numbers are different. Its address is 212.64.94.251, without a subnet mask. This means that we have a point-to-point connection and that every address, with the exception of 212.64.94.251, is remote. There is more information however, it tells us that on the other side of the link is yet again only one address, 212.64.94.1. The /32 tells us that there are no ’network bits’.

It is absolutely vital that you grasp these concepts. Refer to the documentation mentioned at the beginning of this HOWTO if you have trouble.

You may also note ’qdisc’, which stands for Queueing Discipline. This will become vital later on.

3.4.3 ip shows us our routes

Well, we now know how to find 10.x.y.z addresses, and we are able to reach 212.64.94.1. This is not enough however, so we need instructions on how to reach the world. The internet is available via our ppp connection, and it appears that 212.64.94.1 is willing to spread our packets around the world, and deliver results back to us.

     [ahu@home ahu]$ ip route show
     212.64.94.1 dev ppp0  proto kernel  scope link  src 212.64.94.251
     10.0.0.0/8 dev eth0  proto kernel  scope link  src 10.0.0.1
     127.0.0.0/8 dev lo  scope link
     default via 212.64.94.1 dev ppp0

This is pretty much self explanatory. The first 4 lines of output explicitly state what was already implied by ip address show, the last line tells us that the rest of the world can be found via 212.64.94.1, our default gateway. We can see that it is a gateway because of the word via, which tells us that we need to send packets to 212.64.94.1, and that it will take care of things.

For reference, this is what the old ’route’ utility shows us:

     [ahu@home ahu]$ route -n
     Kernel IP routing table
     Destination     Gateway         Genmask         Flags Metric Ref    Use
     Iface
     212.64.94.1     0.0.0.0         255.255.255.255 UH    0      0        0 ppp0
     10.0.0.0        0.0.0.0         255.0.0.0       U     0      0        0 eth0
     127.0.0.0       0.0.0.0         255.0.0.0       U     0      0        0 lo
     0.0.0.0         212.64.94.1     0.0.0.0         UG    0      0        0 ppp0

3.5 ARP

ARP is the Address Resolution Protocol as described in RFC 826 <http://www.faqs.org/rfcs/rfc826. html>. ARP is used by a networked machine to resolve the hardware location/address of another machine on the same local network. Machines on the Internet are generally known by their names which resolve to IP addresses. This is how a machine on the foo.com network is able to communicate with another machine which is on the bar.net network. An IP address, though, cannot tell you the physical location of a machine. This is where ARP comes into the picture.

Let’s take a very simple example. Suppose I have a network composed of several machines. Two of the machines which are currently on my network are foo with an IP address of 10.0.0.1 and bar with an IP address of 10.0.0.2. Now foo wants to ping bar to see that he is alive, but alas, foo has no idea where bar is. So when foo decides to ping bar he will need to send out an ARP request. This ARP request is akin to foo shouting out on the network ”Bar (10.0.0.2)! Where are you?” As a result of this every machine on the network will hear foo shouting, but only bar (10.0.0.2) will respond. Bar will then send an ARP reply directly back to foo which is akin bar saying, ”Foo (10.0.0.1) I am here at 00:60:94:E9:08:12.” After this simple transaction used to locate his friend on the network foo is able to communicate with bar until he (his arp cache) forgets where bar is.

Now let’s see how this works. You can view your machines current arp/neighbor cache/table like so:

     [root@espa041 /home/src/iputils]# ip neigh show
     9.3.76.42 dev eth0 lladdr 00:60:08:3f:e9:f9 nud reachable
     9.3.76.1 dev eth0 lladdr 00:06:29:21:73:c8 nud reachable

As you can see my machine espa041 (9.3.76.41) knows where to find espa042 (9.3.76.42) and espagate (9.3.76.1). Now let’s add another machine to the arp cache.

     [root@espa041 /home/paulsch/.gnome-desktop]# ping -c 1 espa043
     PING espa043.austin.ibm.com (9.3.76.43) from 9.3.76.41 : 56(84) bytes of data.
     64 bytes from 9.3.76.43: icmp_seq=0 ttl=255 time=0.9 ms
     --- espa043.austin.ibm.com ping statistics ---
     1 packets transmitted, 1 packets received, 0% packet loss
     round-trip min/avg/max = 0.9/0.9/0.9 ms
     [root@espa041 /home/src/iputils]# ip neigh show
     9.3.76.43 dev eth0 lladdr 00:06:29:21:80:20 nud reachable
     9.3.76.42 dev eth0 lladdr 00:60:08:3f:e9:f9 nud reachable
     9.3.76.1 dev eth0 lladdr 00:06:29:21:73:c8 nud reachable

As a result of espa041 trying to contact espa043, espa043’s hardware address/location has now been added to the arp/nieghbor cache. So until the entry for espa043 times out (as a result of no communication between the two) espa041 knows where to find espa043 and has no need to send an ARP request.

Now let’s delete espa043 from our arp cache:

     [root@espa041 /home/src/iputils]# ip neigh delete 9.3.76.43 dev eth0
     [root@espa041 /home/src/iputils]# ip neigh show
     9.3.76.43 dev eth0  nud failed
     9.3.76.42 dev eth0 lladdr 00:60:08:3f:e9:f9 nud reachable
     9.3.76.1 dev eth0 lladdr 00:06:29:21:73:c8 nud stale

Now espa041 has again forgotten where to find espa043 and will need to send another ARP request the next time he needs to communicate with espa043. You can also see from the above output that espagate (9.3.76.1) has been changed to the ”stale” state. This means that the location shown is still valid, but it will have to be confirmed at the first transaction to that machine.

4 Rules - routing policy database

If you have a large router, you may well cater for the needs of different people, who should be served differently. The routing policy database allows you to do this by having multiple sets of routing tables.

If you want to use this feature, make sure that your kernel is compiled with the ”IP: advanced router” and ”IP: policy routing” features.

When the kernel needs to make a routing decision, it finds out which table needs to be consulted. By default, there are three tables. The old ’route’ tool modifies the main and local tables, as does the ip tool (by default).

The default rules:

     [ahu@home ahu]$ ip rule list
     0:      from all lookup local
     32766:  from all lookup main
     32767:  from all lookup default

This lists the priority of all rules. We see that all rules apply to all packets (’from all’). We’ve seen the ’main’ table before, it’s output by ip route ls, but the ’local’ and ’default’ table are new.

If we want to do fancy things, we generate rules which point to different tables which allow us to override system wide routing rules.

For the exact semantics on what the kernel does when there are more matching rules, see Alexey’s ip-cref documentation.

4.1 Simple source routing

Let’s take a real example once again, I have 2 (actually 3, about time I returned them) cable modems, connected to a Linux NAT (’masquerading’) router. People living here pay me to use the internet. Suppose one of my house mates only visits hotmail and wants to pay less. This is fine with me, but you’ll end up using the low-end cable modem.

The ’fast’ cable modem is known as 212.64.94.251 and is a PPP link to 212.64.94.1. The ’slow’ cable modem is known by various ip addresses, 212.64.78.148 in this example and is a link to 195.96.98.253.

The local table:

     [ahu@home ahu]$ ip route list table local
     broadcast 127.255.255.255 dev lo  proto kernel  scope link  src 127.0.0.1
     local 10.0.0.1 dev eth0  proto kernel  scope host  src 10.0.0.1
     broadcast 10.0.0.0 dev eth0  proto kernel  scope link  src 10.0.0.1
     local 212.64.94.251 dev ppp0  proto kernel  scope host  src 212.64.94.251
     broadcast 10.255.255.255 dev eth0  proto kernel  scope link  src 10.0.0.1
     broadcast 127.0.0.0 dev lo  proto kernel  scope link  src 127.0.0.1
     local 212.64.78.148 dev ppp2  proto kernel  scope host  src 212.64.78.148
     local 127.0.0.1 dev lo  proto kernel  scope host  src 127.0.0.1
     local 127.0.0.0/8 dev lo  proto kernel  scope host  src 127.0.0.1

Lots of obvious things, but things that need to specified somewhere. Well, here they are. The default table is empty.

Let’s view the ’main’ table:

     [ahu@home ahu]$ ip route list table main
     195.96.98.253 dev ppp2  proto kernel  scope link  src 212.64.78.148
     212.64.94.1 dev ppp0  proto kernel  scope link  src 212.64.94.251
     10.0.0.0/8 dev eth0  proto kernel  scope link  src 10.0.0.1
     127.0.0.0/8 dev lo  scope link
     default via 212.64.94.1 dev ppp0

We now generate a new rule which we call ’John’, for our hypothetical house mate. Although we can work with pure numbers, it’s far easier if we add our tables to /etc/iproute2/rt\_tables.

     # echo 200 John >> /etc/iproute2/rt_tables
     # ip rule add from 10.0.0.10 table John
     # ip rule ls
     0:      from all lookup local
     32765:  from 10.0.0.10 lookup John

     32766:  from all lookup main
     32767:  from all lookup default

Now all that is left is to generate Johns table, and flush the route cache:

     # ip route add default via 195.96.98.253 dev ppp2 table John
     # ip route flush cache

And we are done. It is left as an exercise for the reader to implement this in ip-up.

5 GRE and other tunnels

There are 3 kinds of tunnels in Linux. There’s IP in IP tunneling, GRE tunneling and tunnels that live outside the kernel (like, for example PPTP).

5.1 A few general remarks about tunnels:

Tunnels can be used to do some very unusual and very cool stuff. They can also make things go horribly wrong when you don’t configure them right. Don’t point your default route to a tunnel device unless you know exactly what you are doing :-). Furthermore, tunneling increases overhead, because it needs an extra set of IP headers. Typically this is 20 bytes per packet, so if the normal packet size (MTU) on a network is 1500 bytes, a packet that is sent through a tunnel can only be 1480 bytes big. This is not necessarily a problem, but be sure to read up on IP packet fragmentation/reassembly when you plan to connect large networks with tunnels. Oh, and of course, the fastest way to dig a tunnel is to dig at both sides.

5.2 IP in IP tunneling

This kind of tunneling has been available in Linux for a long time. It requires 2 kernel modules, ipip.o and new tunnel.o.

Let’s say you have 3 networks: Internal networks A and B, and intermediate network C (or let’s say, Internet). So we have network A:

     network 10.0.1.0
     netmask 255.255.255.0
     router  10.0.1.1

The router has address 172.16.17.18 on network C.

and network B:

     network 10.0.2.0
     netmask 255.255.255.0
     router  10.0.2.1

The router has address 172.19.20.21 on network C.

As far as network C is concerned, we assume that it will pass any packet sent from A to B and vice versa. You might even use the Internet for this.

Here’s what you do:

First, make sure the modules are installed:

     insmod ipip.o
     insmod new_tunnel.o

Then, on the router of network A, you do the following:

     ifconfig tunl0 10.0.1.1 pointopoint 172.19.20.21
     route add -net 10.0.2.0 netmask 255.255.255.0 dev tunl0

And on the router of network B:

     ifconfig tunl0 10.0.2.1 pointopoint 172.16.17.18
     route add -net 10.0.1.0 netmask 255.255.255.0 dev tunl0

And if you’re finished with your tunnel:

     ifconfig tunl0 down

Presto, you’re done. You can’t forward broadcast or IPv6 traffic through an IP-in-IP tunnel, though. You just connect 2 IPv4 networks that normally wouldn’t be able to talk to each other, that’s all. As far as compatibility goes, this code has been around a long time, so it’s compatible all the way back to 1.3 kernels. Linux IP-in-IP tunneling doesn’t work with other Operating Systems or routers, as far as I know. It’s simple, it works. Use it if you have to, otherwise use GRE.

5.3 GRE tunneling

GRE is a tunneling protocol that was originally developed by Cisco, and it can do a few more things than IP-in-IP tunneling. For example, you can also transport multicast traffic and IPv6 through a GRE tunnel.

In Linux, you’ll need the ip gre.o module.

5.3.1 IPv4 Tunneling

Let’s do IPv4 tunneling first:

Let’s say you have 3 networks: Internal networks A and B, and intermediate network C (or let’s say, Internet).

So we have network A:

     network 10.0.1.0
     netmask 255.255.255.0
     router  10.0.1.1

The router has address 172.16.17.18 on network C. Let’s call this network neta (ok, hardly original)

and network B:

     network 10.0.2.0
     netmask 255.255.255.0
     router  10.0.2.1

The router has address 172.19.20.21 on network C. Let’s call this network netb (still not original)

As far as network C is concerned, we assume that it will pass any packet sent from A to B and vice versa. How and why, we do not care.

On the router of network A, you do the following:

     ip tunnel add netb mode gre remote 172.19.20.21 local 172.16.17.18 ttl 255
     ip link set netb up
     ip addr add 10.0.1.1 dev netb
     ip route add 10.0.2.0/24 dev netb

Let’s discuss this for a bit. In line 1, we added a tunnel device, and called it netb (which is kind of obvious because that’s where we want it to go). Furthermore we told it to use the GRE protocol (mode gre), that the remote address is 172.19.20.21 (the router at the other end), that our tunneling packets should originate from 172.16.17.18 (which allows your router to have several IP addresses on network C and let you decide which one to use for tunneling) and that the TTL field of the packet should be set to 255 (ttl 255).

The second line enables the device.

In the third line we gave the newly born interface netb the address 10.0.1.1. This is OK for smaller networks, but when you’re starting up a mining expedition (LOTS of tunnels), you might want to consider using another IP range for tunneling interfaces (in this example, you could use 10.0.3.0).

In the fourth line we set the route for network B. Note the different notation for the netmask. If you’re not familiar with this notation, here’s how it works: you write out the netmask in binary form, and you count all the ones. If you don’t know how to do that, just remember that 255.0.0.0 is /8, 255.255.0.0 is /16 and 255.255.255.0 is /24. Oh, and 255.255.254.0 is /23, in case you were wondering.

But enough about this, let’s go on with the router of network B.

     ip tunnel add neta mode gre remote 172.16.17.18 local 172.19.20.21 ttl 255
     ip link set neta up
     ip addr add 10.0.2.1 dev neta
     ip route add 10.0.1.0/24 dev neta

And when you want to remove the tunnelon router A:

     ip link set netb down
     ip tunnel del netb

Of course, you can replace netb with neta for router B.

5.3.2 IPv6 Tunneling

A short bit about IPv6 addresses:

IPv6 addresses are, compared to IPv4 addresses, monstrously big. An example:

3ffe:2502:200:40:281:48fe:dcfe:d9bc

So, to make writing them down easier, there are a few rules:

• Don’t use leading zeroes. Same as in IPv4.

• Use colons to separate every 16 bits or two bytes.

• When you have lots of consecutive zeroes, you can write this down as ::. You can only do this once in an address and only for quantities of 16 bits, though.

Using these rules, the address 3ffe:0000:0000:0000:0000:0020:34A1:F32C can be written down as 3ffe::20:34A1:F32C, which is a lot shorter.

On with the tunnels.

Let’s assume that you have the following IPv6 network, and you want to connect it to 6bone, or a friend.

     Network 3ffe:406:5:1:5:a:2:1/96

Your IPv4 address is 172.16.17.18, and the 6bone router has IPv4 address 172.22.23.24.

     ip tunnel add sixbone mode sit remote 172.22.23.24 local 172.16.17.18 ttl 255
     ip link set sixbone up
     ip addr add 3ffe:406:5:1:5:a:2:1/96 dev sixbone
     ip route add 3ffe::/15 dev sixbone

Let’s discuss this. In the first line, we created a tunnel device called sixbone. We gave it mode sit (which is IPv6 in IPv4 tunneling) and told it where to go to (remote) and where to come from (local). TTL is set to maximum, 255. Next, we made the device active (up). After that, we added our own network address, and set a route for 3ffe::/15 (which is currently all of 6bone) through the tunnel.

GRE tunnels are currently the preferred type of tunneling. It’s a standard that’s also widely adopted outside the Linux community and therefore a Good Thing.

5.4 Userland tunnels

There are literally dozens of implementations of tunneling outside the kernel. Best known are of course PPP and PPTP, but there are lots more (some proprietary, some secure, some that don’t even use IP) and that is really beyond the scope of this HOWTO.

6 IPv6 tunneling with Cisco and/or 6bone

By Marco Davids <marco@sara.nl>

NOTE to maintainer:

As far as I am concerned, this IPv6-IPv4 tunneling is not per definition GRE tunneling. You could tunnel IPv6 over IPv4 by means of GRE tunnel devices (GRE tunnels ANY to IPv4), but the device used here (”sit”) only tunnels IPv6 over IPv4 and is therefore something different.

6.1 IPv6 Tunneling

This is another application of the tunneling capabilites of Linux. It is populair among the IPv6 early adopters, or pioneers if you like. The ’hands-on’ example described below is certainly not the only way to do IPv6 tunneling. However, it is the method that is often used to tunnel between Linux and a Cisco IPv6 capable router and experience learned that this is just the thing many people are after. Ten to one this applies to you too ;-)

A short bit about IPv6 addresses:

IPv6 addresses are, compared to IPv4 addresses, really big: 128 bits against 32 bits. And this provides us just the thing we need: many, many IP-addresses: 340,282,266,920,938,463,463,374,607,431,768,211,465 to be precise. Apart from this, IPv6 (or IPng, for IP Next Generation) is supposed to provide for smaller routing tables on the Internet’s backbone routers, simpler configuration of equipment, better security at the IP-level and better support for QoS.

An example: 2002:836b:9820:0000:0000:0000:836b:9886

Writing down IPv6 addresses can be quite a burden. Therefore, to make life easier there are some rules:

• Don’t use leading zeroes. Same as in IPv4.

• Use colons to separate every 16 bits or two bytes.

• When you have lots of consecutive zeroes, you can write this down as ::. You can only do this once in an address and only for quantities of 16 bits, though.

The address 2002:836b:9820:0000:0000:0000:836b:9886 can be written down as 2002:836b:9820::836b:9886, which is somewhat friendlier.

IPv6, is intended to be the succesor of the current IPv4. Because it it relatively new technology, there is no worldwide native IPv6 network yet. To be able to move forward swiftly, the 6bone was introduced.

Native IPv6 networks are connected to each other by encapsulating the IPv6 protocol in IPv4 packets and send them over the existing IPv4 infrastructure from one IPv6 site to another.

That is precisely where the tunnels steps in.

To be able to use IPv6, we should have a kernel that supports it. There are many good documents on how to achieve this. But it all comes down to a few steps:

• Get yourself a recent Linux-distribution, with suitable glibc.

• Then get yourself an up-to-date kernel source.

If you are all set, than you can go ahead and compile an IPv6-capable kernel:

• Go to /usr/src/linux and type:

• make menuconfig

• Choose ”Networking Options”

• Select ”The IPv6 protocol”, ”IPv6: enable EUI-64 token format”, ”IPv6: disable provider based addresses”

HINT: Don’t go for the ’module’ option. Often this won’t work well.

In other words, compile IPv6 as ’built-in’ in your kernel. You can than save your config like usual and go ahead with compiling the kernel.

HINT: Before doing so, consider editting the Makefile: EXTRAVERSION = -x ; –> ; EXTRAVERSION = -x-IPv6

There is a lot of good documentation about compiling and installing a kernel, however this document is about something else. If you run into problems at this stage, go and look for documentation about compiling a Linux kernel according to your own specifications.

The file /usr/src/linux/README might be a good start. After you acomplished all this, and rebooted with your brand new kernel, you might want to issue an ’/sbin/ifconfig -a’ and notice the brand new ’sit0-device’. SIT stands for Simple Internet Transition. You may give yourself a compliment; you are now one major step closer to IP, the Next Generation ;-)

No on to the next step. You want to connect your host, or maybe even your entire LAN to another IPv6 capable network. This might be the ”6bone” that is setup especially or this particular purpose.

Let’s assume that you have the following IPv6 network: 3ffe:604:6:8::/64 and you want to connect it to 6bone, or a friend. Please note that the /64 subnet notation works just like with regular IP adresses.

Your IPv4 address is 145.100.24.181 and the 6bone router has IPv4 address 145.100.1.5

     # ip tunnel add sixbone mode sit remote 145.100.1.5 [local 145.100.24.181 ttl 225]
     # ip link set sixbone up
     # ip addr add 3FFE:604:6:7::2/126 dev sixbone
     # ip route add 3ffe::0/16 dev sixbone

Let’s discuss this. In the first line, we created a tunnel device called sixbone. We gave it mode sit (which is IPv6 in IPv4 tunneling) and told it where to go to (remote) and where to come from (local). TTL is set to maximum, 255.

Next, we made the device active (up). After that, we added our own network address, and set a route for 3ffe::/15 (which is currently all of 6bone) through the tunnel. If the particular machine you run this on is your IPv6 gateway, then consider adding the following lines:

     # echo 1 >/proc/sys/net/ipv6/conf/all/forwarding
     # /usr/local/sbin/radvd

The latter, radvd is -like zebra- a router advertisement daemon, to support IPv6’s autoconfiguration features. Search for it with your favourite search-engine if you like. You can check things like this:

     # /sbin/ip -f inet6 addr

If you happen to have radvd running on your IPv6 gateway and boot your IPv6 capable Linux on a machine on your local LAN, you would be able to enjoy the benefits of IPv6 autoconfiguration:

     # /sbin/ip -f inet6 addr
     1: lo: <LOOPBACK,UP> mtu 3924 qdisc noqueue inet6 ::1/128 scope host
     3: eth0: <BROADCAST,MULTICAST,UP> mtu 1500 qdisc pfifo_fast qlen 100

     inet6 3ffe:604:6:8:5054:4cff:fe01:e3d6/64 scope global dynamic
     valid_lft forever preferred_lft 604646sec inet6 fe80::5054:4cff:fe01:e3d6/10
     scope link

You could go ahead and configure your bind for IPv6 addresses. The A type has an equivalent for IPv6: AAAA. The in-addr.arpa’s equivalent is: ip6.int. There’s a lot of information available on this topic.

There is an increasing number of IPv6-aware applications available, including secure shell, telnet, inetd, Mozilla the browser, Apache the websever and a lot of others. But this is all outside the scope of this Routing document ;-)

On the Cisco-site the configuration would be something like this:

     !
     interface Tunnel1
     description IPv6 tunnel
     no ip address
     no ip directed-broadcast
     ipv6 enable
     ipv6 address 3FFE:604:6:7::1/126
     tunnel source Serial0
     tunnel destination 145.100.24.181
     tunnel mode ipv6ip
     !
     ipv6 route 3FFE:604:6:8::/64 Tunnel1

But if you don’t have a Cisco at your disposal, try one of the many IPv6 tunnel brokers available on the Internet. They are willing to configure their Cisco with an extra tunnel for you. Mostly by means of a friendly web-interface. Search for ”ipv6 tunnel broker” on your favourite searchengine.

7 IPsec: secure IP over the internet

FIXME: editor vacancy In the meantime, see: The FreeS/WAN project <http://www.freeswan.org/>.

8 Multicast routing

FIXME: Editor Vacancy!

9 Using Class Based Queueing for bandwidth management

Now, when I discovered this, it really blew me away. Linux 2.2 comes with everything to manage bandwidth in ways comparable to high-end dedicated bandwidth management systems.

Linux even goes far beyond what Frame and ATM provide.

The two basic units of Traffic Control are filters and queues. Filters place traffic into queues, and queues gather traffic and decide what to send first, send later, or drop. There are several flavours of filters and queues.

The most common filters are fwmark and u32, the first lets you use the Linux netfilter code to select traffic, and the second allows you to select traffic based on ANY header. The most notable queue is Class Based Queue. CBQ is a super-queue, in that it contains other queues (even other CBQs).

It may not be immediately clear what queueing has to do with bandwidth management, but it really does work.

For our frame of reference, I have modelled this section on an ISP where I learned the ropes, so to speak, Casema Internet in The Netherlands. Casema, which is actually a cable company, has internet needs both for their customers and for their own office. Most corporate computers there have access to the internet. In reality, they have lots of money to spend and do not use Linux for bandwidth management.

We will explore how our ISP could have used Linux to manage their bandwidth.

9.1 What is queueing?

With queueing we determine the order in which data is sent. It it important to realise that we can only shape data that we transmit. How does this changing the order determine the speed of transmission? Imagine a cash register which is able to process 3 customers per minute.

People wishing to pay go stand in line at the ’tail end’ of the queue. This is ’FIFO queueing’ (First In, First Out). Let’s suppose however that we let certain people always join in the middle of the queue, instead of at the end. These people spend a lot less time in the queue and are therefore able to shop faster.

With the way the internet works, we have no direct control of what people send us. It’s a bit like your (physical!) mailbox at home. There is no way you can influence the world to modify the amount of mail they send you, short of contacting everybody.

However, the internet is mostly based on TCP/IP which has a few features that help us. TCP/IP has no way of knowing the capacity of the network between two hosts, so it just starts sending data faster and faster (’slow start’) and when packets start getting lost, because there is no room to send them, it will slow down.

This is the equivalent of not reading half of your mail, and hoping that people will stop sending it to you. With the difference that it works for the Internet :-)

FIXME: explain congestion windows

     [The Internet] ---<E3, T3, whatever>--- [Linux router] --- [Office+ISP]
                                           eth1          eth0

Now, our Linux router has two interfaces which I shall dub eth0 and eth1. eth1 is connected to our router which moves packets from to and from our fibre link.

eth0 is connected to a subnet which contains both the corporate firewall and our network head ends, through which we can connect to our customers.

Because we can only limit what we send, we need two separate but possibly very similar sets of rules. By modifying queueing on eth0, we determine how fast data gets sent to our customers, and therefore how much downstream bandwidth is available for them. Their ’download speed’ in short.

On eth1, we determine how fast we send data to The Internet, how fast our users, both corporate and commercial can upload data.

9.2 First attempt at bandwidth division

CBQ enables us to generate several classes, and even classes within classes. The larger devisions might be called ’agencies’. Within these classes may be things like ’bulk’ or ’interactive’.

For example, we may have a 10 megabit connection to ’the internet’ which is to be shared by our customers, and our corporate needs. We should not allow a few people at the office to steal away large amounts of bandwidth which we should sell to our customers.

On the other hand, our customers should not be able to drown out the traffic from our field offices to the customer database.

Previously, one way to solve this was either to use Frame relay/ATM and create virtual circuits. This works, but frame is not very fine grained, ATM is terribly inefficient at carrying IP traffic, and neither have standardised ways to segregate different types of traffic into different VCs.

However, if you do use ATM, Linux can also happily perform deft acts of fancy traffic classification for you too. Another way is to order separate connections, but this is not very practical and also not very elegant, and still does not solve all your problems.

CBQ to the rescue!

Clearly we have two main classes, ’ISP’ and ’Office’. Initially, we really don’t care what the divisions do with their bandwidth, so we don’t further subdivide their classes.

We decide that the customers should always be guaranteed 8 megabits of downstream traffic, and our office 2 megabits.

Setting up traffic control is done with the iproute2 tool tc.

     # tc qdisc add dev eth0 root handle 10: cbq bandwidth 10Mbit avpkt 1000

Ok, lots of numbers here. What has happened? We have configured the ’queueing discipline’ of eth0. With ’root’ we denote that this is the root discipline. We have given it the handle ’10:’. We want to do CBQ, so we mention that on the command line as well. We tell the kernel that it can allocate 10Mbit and that the average packet size is somewhere around 1000 octets.

Now we need to generate our root class, from which all others descend:

     # tc class add dev eth0 parent 10:0 classid 10:1 cbq bandwidth 10Mbit rate \
       10Mbit allot 1514 weight 1Mbit prio 8 maxburst 20 avpkt 1000

Even more numbers to worry about - the Linux CBQ implementation is very generic. With ’parent 10:0’ we indicate that this class descends from the root of qdisc handle ’10:’ we generated earlier. With ’classid 10:1’ we name this class.

We really don’t tell the kernel a lot more, we just generate a class that completely fills the available device. We also specify that the MTU (plus some overhead) is 1514 octets. We also ’weigh’ this class with 1Mbit - a tuning parameter.

We now generate our ISP class:

     # tc class add dev eth0 parent 10:1 classid 10:100 cbq bandwidth 10Mbit rate \
       8Mbit allot 1514 weight 800Kbit prio 5 maxburst 20 avpkt 1000 \
       bounded

We allocate 8Mbit, and indicate that this class must not exceed this by adding the ’bounded’ parameter. Otherwise this class would have started borrowing bandwidth from other classes, something we will discuss later on.

To top it off, we generate the root Office class:

     # tc class add dev eth0 parent 10:1 classid 10:200 cbq bandwidth 10Mbit rate \
       2Mbit allot 1514 weight 200Kbit prio 5 maxburst 20 avpkt 1000 \
       bounded

To make this a bit clearer, a diagram which shows our classes:

     +-------------[10: 10Mbit]-------------------------+
     |+-------------[10:1 root 10Mbit]-----------------+|
     ||                                                ||
     || +-----[10:100 8Mbit]---------+ [10:200 2Mbit]  ||
     || |                            | |            |  ||
     || |          ISP               | |   Office   |  ||
     || |                            | |            |  ||
     || +----------------------------+ +------------+  ||
     ||                                                ||
     |+------------------------------------------------+|
     +--------------------------------------------------+

Ok, now we have told the kernel what our classes are, but not yet how to manage the queues. We do this presently, in one fell swoop for both classes.

     # tc qdisc add dev eth0 parent 10:100 sfq quantum 1514b perturb 15
     # tc qdisc add dev eth0 parent 10:200 sfq quantum 1514b perturb 15

In this case we install the Stochastic Fairness Queueing discipline (sfq), which is not quite fair, but works well up to high bandwidths without burning up CPU cycles. There are other queueing disciplines available which are better, but need more CPU. The Token Bucket Filter is often used.

Now there is only one thing left to do and that is to explain to the kernel which packets belong to which class. Initially we will do this natively with iproute2, but more interesting applications are possible in combination with netfilter.

     # tc filter add dev eth0 parent 10:0 protocol ip prio 100 u32 match ip dst \
       150.151.23.24 flowid 10:200
     # tc filter add dev eth0 parent 10:0 protocol ip prio 25 u32 match ip dst \
       150.151.0.0/16 flowid 10:100

Here is is assumed that our office hides behind a firewall with IP address 150.151.23.24 and that all our other IP addresses should be considered to be part of the ISP.

The u32 match is a very simple one - more sophisticated matching rules are possible when using netfilter to mark our packets, which we can than match on in tc.

Now we have fairly divided the downstream bandwidth, we need to do the same for the upstream. For brevity’s sake, all in one go:

9. Using Class Based Queueing for bandwidth management 23

# tc qdisc add dev eth1 root handle 20: cbq bandwidth 10Mbit avpkt 1000
# tc class add dev eth1 parent 20:0 classid 20:1 cbq bandwidth 10Mbit rate \
10Mbit allot 1514 weight 1Mbit prio 8 maxburst 20 avpkt 1000
# tc class add dev eth1 parent 20:1 classid 20:100 cbq bandwidth 10Mbit rate \
8Mbit allot 1514 weight 800Kbit prio 5 maxburst 20 avpkt 1000 \
bounded
# tc class add dev eth1 parent 20:1 classid 20:200 cbq bandwidth 10Mbit rate \
2Mbit allot 1514 weight 200Kbit prio 5 maxburst 20 avpkt 1000 \
bounded
# tc qdisc add dev eth1 parent 20:100 sfq quantum 1514b perturb 15
# tc qdisc add dev eth1 parent 20:200 sfq quantum 1514b perturb 15
# tc filter add dev eth1 parent 20:0 protocol ip prio 100 u32 match ip src \
150.151.23.24 flowid 20:200
# tc filter add dev eth1 parent 20:0 protocol ip prio 25 u32 match ip src \
150.151.0.0/16 flowid 20:100

9.3 What to do with excess bandwidth

In our hypothetical case, we will find that even when the ISP customers are mostly offline (say, at 8AM), our office still gets only 2Mbit, which is rather wasteful.

By removing the ’bounded’ statements, classes will be able to borrow bandwidth from each other.

Some classes may not wish to borrow their bandwidth to other classes. Two rival ISPs on a single link may not want to offer each other freebees. In such a case, you can add the keyword ’isolated’ at the end of your ’tc class add’ lines.

9.4 Class subdivisions

FIXME: completely untested suppositions! Try this!

We can go further than this. Should the employees at the office decide to all fire up their ’napster’ clients, it is still possible that our database runs out of bandwidth. Therefore, we create two subclasses, ’Human’ and ’Database’.

Our database always needs 500Kbit, so we have 1.5Mbit left for Human consumption.

We now need to create two new classes, within our Office class:

# tc class add dev eth0 parent 10:200 classid 10:250 cbq bandwidth 10Mbit rate \
500Kbit allot 1514 weight 50Kbit prio 5 maxburst 20 avpkt 1000 \
bounded
# tc class add dev eth0 parent 10:200 classid 10:251 cbq bandwidth 10Mbit rate \
1500Kbit allot 1514 weight 150Kbit prio 5 maxburst 20 avpkt 1000 \
bounded

FIXME: Finish this example!

9.5 Loadsharing over multiple interfaces

There are several ways of doing this. One of the easiest and straightforward ways is ’TEQL’ - ”True” (or ”trivial”) link equalizer. Like most things having to do with queueing, loadsharing goes both ways. Both ends of a link may need to participate for full effect.

Imagine this situation:

                      +-------+   eth1   +-------+
                      |       |==========|       |
      'network 1' ----|   A   |          |   B   |---- 'network 2'
                      |       |==========|       |
                      +-------+   eth2   +-------+

A and B are routers, and for the moment we’ll assume both run Linux. If traffic is going from network 1 to network 2, router A needs to distribute the packets over both links to B. Router B needs to be configured to accept this. Same goes the other way around, when packets go from network 2 to network 1, router B needs to send the packets over both eth1 and eth2.

The distributing part is done by a ’TEQL’ device, like this (it couldn’t be easier):

     # tc qdisc add dev eth1 root teql0
     # tc qdisc add dev eth2 root teql0

This needs to be done on both hosts. The device teql0 is basically a roundrobbin distributor over eth1 and eth2, for sending packets. No data ever comes in over an teql device, that just appears on the ’raw’ eth1 and eth2.

But now we just have devices, we also need proper routing. One way to do this is to assign a /31 network to both links, and a /31 to the teql0 device as well:

FIXME: does this need something like ’nobroadcast’? A /31 is too small to house a network address and a broadcast address - if this doesn’t work as planned, try a /30, and adjust the ip adresses accordingly. You might even try to make eth1 and eth2 do without an IP address!

On router A:

     # ip addr add dev eth1 10.0.0.0/31
     # ip addr add dev eth2 10.0.0.2/31
     # ip addr add dev teql0 10.0.0.4/31

On router B:

     # ip addr add dev eth1 10.0.0.1/31
     # ip addr add dev eth2 10.0.0.3/31
     # ip addr add dev teql0 10.0.0.5/31

Router A should now be able to ping 10.0.0.1, 10.0.0.3 and 10.0.0.5 over the 2 real links and the 1 equalized device. Router B should be able to ping 10.0.0.0, 10.0.0.2 and 10.0.0.4 over the links.

If this works, Router A should make 10.0.0.5 its route for reaching network 2, and Router B should make 10.0.0.4 its route for reaching network 1. For the special case where network 1 is your network at home, and network 2 is the internet, Router A should make 10.0.0.5 its default gateway.

9.5.1 Caveats

Nothing is as easy as it seems. eth1 and eth2 on both router A and B need to have return path filtering turned off, because they will otherwise drop packets destined for ip addresses other than their own:

     # echo 0 > /proc/net/ipv4/conf/eth1/rp_filter
     # echo 0 > /proc/net/ipv4/conf/eth2/rp_filter

Then there is the nasty problem of packet reordering. Let’s say 6 packets need to be sent from A to B - eth1 might get 1, 3 and 5. eth2 would then do 2, 4 and 6. In an ideal world, router B would receive this in order, 1, 2, 3, 4, 5, 6. But the possibility is very real that the kernel gets it like this: 2, 1, 4, 3, 6, 5. The problem is that this confuses TCP/IP. While not a problem for links carrying many different TCP/IP sessions, you won’t be able to to a bundle multiple links and get to ftp a single file lots faster, except when your receiving or sending OS is Linux, which is not easily shaken by some simple reordering.

However, for lots of applications, link loadbalancing is a great idea.

10 More queueing disciplines

The Linux kernel offers us lots of queueing disciplines. By far the most widely used is the pfifo fast queue - this is the default. This also explains why these advanced features are so robust. They are nothing more than ’just another queue’.

Each of these queues has specific strengths and weaknesses. Not all of them may be as well tested.

10.1 pfifo fast

This queue is, as the name says, First In, First Out, which means that no packet receives special treatment. At least, not quite. This queue has 3 so called ’bands’. Within each band, FIFO rules apply. However, as long as there are packets waiting in band 0, band 1 won’t be processed. Same goes for band 1 and band 2.

10.2 Stochastic Fairness Queueing

SFQ, as said earlier, is not quite deterministic, but works (on average). Its main benefits are that it requires little CPU and memory. ’Real’ fair queueing requires that the kernel keep track of all running sessions.

Stochastic Fairness Queueing (SFQ) is a simple implementation of fair queueing algorithms family. It’s less accurate than others, but it also requires less calculations while being almost perfectly fair.

The key word in SFQ is conversation (or flow), being a sequence of data packets having enough common parameters to distinguish it from other conversations. The parameters used in case of IP packets are source and destination address, and the protocol number.

SFQ consists of dynamically allocated number of FIFO queues, one queue for one conversation. The discipline runs in round-robin, sending one packet from each FIFO in one turn, and this is why it’s called fair. The main advantage of SFQ is that it allows fair sharing the link between several applications and prevent bandwidth take-over by one client. SFQ however cannot determine interactive flows from bulk ones – one usually needs to do the selection with CBQ before, and then direct the bulk traffic into SFQ.

10.3 Token Bucket Filter

The Token Bucket Filter (TBF) is a simple queue, that only passes packets arriving at rate in bounds of some administratively set limit, with possibility to buffer short bursts.

The TBF implementation consists of a buffer (bucket), constatly filled by some virtual pieces of information called tokens, at specific rate (token rate). The most important parameter of the bucket is its size, that is number of tokens it can store.

Each arriving token lets one incoming data packet of out the queue and is then deleted from the bucket. Associating this algorithm with the two flows – token and data, gives us three possible scenarios:

• The data arrives into TBF at rate equal the rate of incoming tokens. In this case each incoming packet has its matching token and passes the queue without delay.

• The data arrives into TBF at rate smaller than the token rate. Only some tokens are deleted at output of each data packet sent out the queue, so the tokens accumulate, up to the bucket size. The saved tokens can be then used to send data over the token rate, if short data burst occurs.

• The data arrives into TBF at rate bigger than the token rate. In this case filter overrun occurs – incoming data can be only sent out without loss until all accumulated tokens are used. After that, overlimit packets are dropped.

The last scenario is very important, because it allows to administratively shape the bandwidth available to data, passing the filter. The accumulation of tokens allows short burst of overlimit data to be still passed without loss, but any lasting overload will cause packets to be constantly dropped.

The Linux kernel seems to go beyond this specification, and also allows us to limit the speed of the burst transmission. However, Alexey warns us:

     Note that the peak rate TBF is much more tough:  with MTU 1500 P crit = 150Kbytes/sec.
     So, if you need greater peak rates, use alpha with HZ=1000 :-)

FIXME: is this still true with TSC (pentium+)? Well sort of

FIXME: if not, add section on raising HZ

10.4 Random Early Detect

RED has some extra smartness built in. When a TCP/IP session starts, neither end knows the amount of bandwidth available. So TCP/IP starts to transmit slowly and goes faster and faster, though limited by the latency at which ACKs return.

Once a link is filling up, RED starts dropping packets, which indicate to TCP/IP that the link is congested, and that it should slow down. The smart bit is that RED simulates real congestion, and starts to drop some packets some time before the link is entirely filled up. Once the link is completely saturated, it behaves like a normal policer.

For more information on this, see the Backbone chapter.

10.5 Ingress policer qdisc

The Ingress qdisc comes in handy if you need to ratelimit a host without help from routers or other Linux boxes. You can police incoming bandwidth and drop packets when this bandwidth exceeds your desired rate. This can save your host from a SYN flood, for example, and also works to slow down TCP/IP, which responds to dropped packets by reducing speed.

FIXME: instead of dropping, can we also assign it to a real queue?

FIXME: shaping by dropping packets seems less desirable than using, for example, a token bucket filter. Not sure though, Cisco CAR works this way, and people appear happy with it.

See the reference to 20 (IOS Committed Access Rate) at the end of this document.

In short: you can use this to limit how fast your computer downloads files, thus leaving more of the available bandwidth for others.

See the section on protecting your host from SYN floods for an example on how this works.

10.6 DSMARK

This chapter was written by Esteve Camps <esteve@hades.udg.es>.

10.6.1 Introduction

First of all, first of all, it would be a great idea for you to read RFCs written about this (RFC2474, RFC2475, RFC2597 and RFC2598) at IETF DiffServ working Group web site <http://www.ietf.org/html.carters/

diffserv-charter.html> and Werner Almesberger web site <http://ica1www.epfl.ch/~almesber> (he

wrote the code to support Differentiated Services on Linux).

10.6.2 What is Dsmark related to?

Dsmark is a queueing discipline that offers the capabilities needed in Differentiated Services (also called DiffServ or, simply, DS). DiffServ is one of two actual QoS architectures (the other one is called Integrated Services) that is based on a value carried by packets in the DS field of the IP header.

One of the first solutions in IP designed to offer some QoS level was the Type of Service field (TOS byte) in IP header. Changing that value we could choose a high/low level of throughput, delay or reliability. But this didn’t provided sufficient flexibility to the needs of new services (such as real-time applications, interactive applications and others). After this, new architectures appeared. One of these was DiffServ which kept TOS bits and renamed DS field.

10.6.3 Differentiated Services guidelines

Differentiated Services is group-oriented. I mean, we don’t know nothing about flows (this will be the Integrated Services purpose); we know about flow aggregations and we will apply different behaviours depending on which aggregation a packet belongs to.

When a packet arrives to an edge node (entry node to a DiffServ domain) entering to a DiffServ Domain we’ll have to policy, shape and/or mark those packets (marking refers to assign a value to DS field. It’s just like the cows :-) ). This will be the mark/value that the internal/core nodes on our DiffServ Domain will look at to determine which behaviour or QoS level apply.

As you can deduce, Differentiated Services involves a domain on which all DS rules will have to be applied. In fact you can think "I will classify all the packets entering my domain. Once they enter my domain they will be subjected to the rules that my classification dictates and every traversed node will apply that QoS level".

In fact, you can apply your own policies into your local domains, but some Service Level Agreements should be considered when connecting to other DS domains.

At this point, you maybe have a lot of questions. DiffServ is more than I’ve explained. In fact, you can understand that I can not resume more than 3 RFC’s in just 50 lines :-).

10.6.4 Working with Dsmark

As the DiffServ bibliography specifies, we differentiate boundary nodes and interior nodes. These are two important points in the traffic path. Both types perform a classification when the packets arrive. Its result may be used in different places along the DS process before the packet is released to the network. It’s just because of this diffserv code supplies an structure called sk buff, including a new field called skb->tc index where we’ll store the result of initial classification that may be used in several points in DS treatment.

The skb->tc index value will be initially set by the DSMARK qdisc, retrieving it from the DS field in IP header of every received packet. Besides, cls tcindex classifier will read all or part of skb->tcindex value and use it to select classes.

But, first of all, take a look at DSMARK qdisc command and its parameters:

     ... dsmark indices INDICES [ default_index DEFAULT_INDEX ] [ set_tc_index ]

What do these parameters mean?

• indices: size of table of (mask,value) pairs. Maximum value is 2ˆ n, where n>=0.

• Default index: the default table entry index if classifier finds no match.

• Set tc index: instructs dsmark discipline to retrieve the DS field and store it onto skb->tc index.

Let’s see the DSMARK process.

10.6.5 How SCH DSMARK works.

This qdisc will apply the next steps:

• If we have declared set tc index option in qdisc command, DS field is retrieved and stored onto skb- >tc index variable.

• Classifier is invoked. The classifier will be executed and it will return a class ID that will be stored in skb->tc index variable.If no filter matches are found, we consider the default index option to be the classId to store. If neither set tc index nor default index has been declared results may be impredictibles.

• After been sent to internal qdisc’s where you can reuse the result of the filter, the classid returned by the internal qdisc is stored into skb->tc index. We will use this value in the future to index a maskvalue table. The final result to assign to the packet will be that resulting from next operation:

          New_Ds_field = ( Old_DS_field & mask ) | value

• Thus, new value will result from ”anding” ds field and mask values and next, this result ”ORed” with value parameter. See next diagram to understand all this process:

                              skb->ihp->tos
     - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - >
          |                                                       |     ^
          | -- If you declare set_tc_index, we set DS             |     |  <-----May change
          |    value into skb->tc_index variable                  |     |O       DS field
          |                                                      A|     |R
        +-|-+      +------+    +---+-+    Internal   +-+     +---N|-----|----+
        | | |      | tc   |--->|   | |-->  . . .  -->| |     |   D|     |    |
        | | |----->|index |--->|   | |     Qdisc     | |---->|    v     |    |
        | | |      |filter|--->| | | +---------------+ |   ---->(mask,value) |
     -->| O |      +------+    +-|-+--------------^----+  /  |  (.  ,  .)    |
        | | |          ^|                |       |  |  (.  ,  .)    |
        | | +----------|---------|----------------|-------|--+  (.  ,  .)    |
        | | sch_dsmark |         |                |       |                  |
        +-|------------|---------|----------------|-------|------------------+
          |            |         | <- tc_index -> |       |
          |            |(read)   |    may change  |       |  <--------------Index to the
          |            |         |                |       |                    (mask,value)
          v            |         v                v       |                    pairs table
     - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ->
                              skb->tc_index

How to do marking? Just change the mask and value of the class you want to remark. See next line of code:

     tc class change dev eth0 classid 1:1 dsmark mask 0x3 value 0xb8

This changes the (mask,value) pair in hash table, to remark packets belonging to class 1:1.You have to ”change” this values because of default values that (mask,value) gets initially (see table below).

Now, we’ll explain how TC INDEX filter works and how fits into this. Besides, TCINDEX filter can be used in other configurations rather than those including DS services.

10.6.6 TC INDEX Filter

This is the basic command to declare a TC INDEX filter:

     ... tcindex [ hash SIZE ] [ mask MASK ] [ shift SHIFT ]
                 [ pass_on | fall_through ]
                 [ classid CLASSID ] [ police POLICE_SPEC ]

Next, we show the example used to explain TC INDEX operation mode. Pay attention to bolded words:

tc qdisc add dev eth0 handle 1:0 root dsmark indices 64 set tc index tc filter add dev eth0 parent 1:0 protocol ip prio 1 tcindex mask 0xfc shift 2 tc qdisc add dev eth0 parent 1:0 handle 2:0 cbq bandwidth 10Mbit cell 8 avpkt 1000 mpu 64 # EF traffic class tc class add dev eth0 parent 2:0 classid 2:1 cbq bandwidth 10Mbit rate 1500Kbit avpkt 1000 prio 1 bounded isolated allot 1514 weight 1 maxburst 10 # Packet fifo qdisc for EF traffic tc qdisc add dev eth0 parent 2:1 pfifo limit 5 tc filter add dev eth0 parent 2:0 protocol ip prio 1 handle 0x2e tcindex classid 2:1 pass on

(This code is not complete. It’s just an extract from EFCBQ example included in iproute2 distribution).

First of all, supose we receive a packet marked as EF . If you read RFC2598, you’ll see that DSCP recommended value for EF traffic is 101110. This means that DS field will be 10111000 (remember that less signifiant bits in TOS byte are not used in DS) or 0xb8 in hexadecimal codification.

                   TC INDEX
                   FILTER
        +---+      +-------+    +---+-+    +------+                +-+    +-------+
        |   |      |       |    |   | |    |FILTER|  +-+    +-+    | |    |       |
        |   |----->| MASK  | -> |   | | -> |HANDLE|->| |    | | -> | | -> |       |
        |   |  .   | =0xfc |    |   | |    |0x2E  |  | +----+ |    | |    |       |
        |   |  .   |       |    |   | |    +------+  +--------+    | |    |       |
        |   |  .   |       |    |   | |                            | |    |       |
     -->|   |  .   | SHIFT |    |   | |                            | |    |       |-->
        |   |  .   | =2    |    |   | +----------------------------+ |    |       |
        |   |      |       |    |   |       CBQ 2:0                  |    |       |
        |   |      +-------+    +---+--------------------------------+    |       |
        |   |                                                             |       |
        |   +-------------------------------------------------------------+       |
        |                          DSMARK 1:0                                     |
        +-------------------------------------------------------------------------+

The packet arrives, then, set with 0xb8 value at DS field. As we explained before, dsmark qdisc identified by 1:0 id in the example, retrieves DS field and store it in skb->tc index variable. Next step in the example will correspond to the filter associated to this qdisc (second line in the example). This will perform next operations:

     Value1 = skb->tc_index & MASK
     Key = Value1 >> SHIFT

In the example, MASK=0xFC i SHIFT=2.

     Value1 = 10111000 & 11111100 = 10111000
     Key = 10111000 >> 2 = 00101110 -> 0x2E in hexadecimal

The returned value will correspond to a qdisc interal filter handle (in the example, identifier 2:0). If a filter with this id exists, policing and metering conditions will be verified (in case that filter includes this) and the classid will be returned (in our example, classid 2:1) and stored in skb->tc index variable.

But if any filter with that identifier is found, the result will depend on fall through flag declaration. If so, value key is returned as classid. If not, an error is returned and process continues with the rest filters. Be careful if you use fall through flag; this can be done if a simple relation exists between values of skb->tc index variable and class id’s.

The latest parameters to comment are hash and pass on. The first one relates to hash table size. Pass on will be used to indicate that if no classid equal to the result of this filter is found, try next filter. The default action is fall through (look at next table).

Finally, let’s see which possible values can be set to all this TCINDEX parameters:

     TC Name                 Value           Default
     -----------------------------------------------------------------
     Hash                    1...0x10000     Implementation dependent
     Mask                    0...0xffff      0xffff
     Shift                   0...15          0
     Fall through / Pass_on  Flag            Fall_through
     Classid                 Major:minor     None
     Police                  .....           None

This kind of filter is very powerfull. It’s necessary to explore all possibilities. Besides, this filter it’s not only used in DiffServ configurations. You can use it as any other kind of filter.

I recommend you to look at all DiffServ examples included in iproute2 distribution. I promise I will try to complement this text as soon as I can. Besides, all I have explained is the result of a lot of tests. I would thank you tell me if I’m wrong in any point.

11 Other information

Esteve Camps Chust <marvin@grn.es> This text is an extract from my thesis on ”QoS Support in Linux”, September 2000.

Source documents:

• Draft-almesberger-wajhak-diffserv-linux-01.txt <http://ica1www.epfl.ch/~almesber>.

• Examples in iproute2 distribution.

   • White Paper-QoS protocols and architectures <http://www.qosforum.com/white-papers/qosprot_
     v3.pdf> and IP QoS Frequently Asked Questions <http://www.qosforum.com/docs/faq> both by

Quality of Service Forum.

11.1 WRR

This qdisc is not included in the standard kernels but can be downloaded from <http://wipl-wrr.dkik. dk/wrr/>. Currently the qdisc is only tested with Linux 2.2 kernels but it will probably work with 2.4 kernels too.

The WRR qdisc distributes bandwidth between its classes using the weighted round robin scheme. That is, like the CBQ qdisc it contains classes into which arbitrary qdiscs can be plugged. All classes which have sufficient demand will get bandwidth proportional to the weights associated with the classes. The weights can be set manually using the tc program. But they can also be made automatically decreasing for classes transferring much data.

The qdisc has a build-in classifier which assigns packets coming from or sent to different machines to different classes. Either the MAC or IP and either source or destination addresses can be used. The MAC address can only be used when the Linux box is acting as an ethernet bridge, however. The classes are automatically assigned to machines based on the packets seen.

The qdisc can be very useful at sites such as dorms where a lot of unrelated individuals share an Internet connection. A set of scripts setting up a relevant behavior for such a site is a central part of the WRR distribution.

12 Netfilter & iproute - marking packets

So far we’ve seen how iproute works, and netfilter was mentioned a few times. This would be a good time to browse through Rusty’s Remarkably Unreliable Guides <http://netfilter.kernelnotes.org/

unreliable-guides/>. Netfilter itself can be found here <http://netfilter.filewatcher.org/>.

Netfilter allows us to filter packets, or mangle their headers. One special feature is that we can mark a packet with a number. This is done with the –set-mark facility.

As an example, this command marks all packets destined for port 25, outgoing mail:

     # iptables -A PREROUTING -i eth0 -t mangle -p tcp --dport 25 \
      -j MARK --set-mark 1

Let’s say that we have multiple connections, one that is fast (and expensive, per megabyte) and one that is slower, but flat fee. We would most certainly like outgoing mail to go via the cheap route.

We’ve already marked the packets with a ’1’, we now instruct the routing policy database to act on this:

     # echo 201 mail.out >> /etc/iproute2/rt_tables
     # ip rule add fwmark 1 table mail.out
     # ip rule ls
     0:      from all lookup local
     32764:  from all fwmark        1 lookup mail.out
     32766:  from all lookup main
     32767:  from all lookup default

Now we generate the mail.out table with a route to the slow but cheap link:

     # /sbin/ip route add default via 195.96.98.253 dev ppp0 table mail.out

And we are done. Should we want to make exceptions, there are lots of ways to achieve this. We can modify the netfilter statement to exclude certain hosts, or we can insert a rule with a lower priority that points to the main table for our excepted hosts.

We can also use this feature to honour TOS bits by marking packets with a different type of service with different numbers, and creating rules to act on that. This way you can even dedicate, say, an ISDN line to interactive sessions.

Needless to say, this also works fine on a host that’s doing NAT (’masquerading’).

IMPORTANT: We received a report that MASQ and SNAT at least collide with marking packets. Rusty Rus-

sell explains it in this posting <http://lists.samba.org/pipermail/netfilter/2000-November/006089.

html>. Turn off the reverse path filter to make it work properly.

Note: to mark packets, you need to have some options enabled in your kernel:

     IP: advanced router (CONFIG_IP_ADVANCED_ROUTER) [Y/n/?]
      IP: policy routing (CONFIG_IP_MULTIPLE_TABLES) [Y/n/?]
       IP: use netfilter MARK value as routing key (CONFIG_IP_ROUTE_FWMARK) [Y/n/?]

See also 16.5 (Transparent web-caching using netfilter, iproute2, ipchains and squid) in the Cookbook.

13 More classifiers

Classifiers are the way by which the kernel decides which queue a packet should be placed into. There are various different classifiers, each of which can be used for different purposes.

fw Bases the decision on how the firewall has marked the packet.

u32 Bases the decision on fields within the packet (i.e. source IP address, etc)

route Bases the decision on which route the packet will be routed by.

rsvp, rsvp6 Bases the decision on the target (destination,protocol) and optionally the source as well. (I think)

tcindex FIXME: Fill me in

Note that in general there are many ways in which you can classify packet and that it generally comes down to preference as to which system you wish to use.

Classifiers in general accept a few arguments in common. They are listed here for convenience:

protocol The protocol this classifier will accept. Generally you will only be accepting only IP traffic. Required. parent

The handle this classifier is to be attached to. This handle must be an already existing class. Required.

prio The priority of this classifier. Higher numbers get tested first.

handle This handle means different things to different filters. FIXME: Add more

All the following sections will assume you are trying to shape the traffic going to HostA. They will assume that the root class has been configured on 1: and that the class you want to send the selected traffic to is 1:1.

13.1 The ”fw” classifier

The ”fw” classifier relies on the firewall tagging the packets to be shaped. So, first we will setup the firewall to tag them:

     # iptables -I PREROUTING -t mangle -p tcp -d HostA \
      -j MARK --set-mark 1

Now all packets to that machine are tagged with the mark 1. Now we build the packet shaping rules to actually shape the packets. Now we just need to indicate that we want the packets that are tagged with the mark 1 to go to class 1:1. This is accomplished with the command:

     # tc filter add dev eth1 protocol ip parent 1:0 prio 1 handle 1 fw classid 1:1

This should be fairly self-explanatory. Attach to the 1:0 class a filter with priority 1 to filter all packet marked with 1 in the firewall to class 1:1. Note how the handle here is used to indicate what the mark should be.

That’s all there is to it! This is the (IMHO) easy way, the other ways are I think harder to understand. Note that you can apply the full power of the firewalling code with this classifier, including matching MAC addresses, user IDs and anything else the firewall can match.

13.2 The ”u32” classifier

The U32 filter is the most advanced filter available in the current implementation. It entirely based on hashing tables, which make it robust when there are many filter rules.

In its simplest form the U32 filter is a list of records, each consisting of two fields: a selector and an action. The selectors, described below, are compared with the currently processed IP packet until the first match and the associated action is performed. The simplest type of action would be directing the packet into defined CBQ class.

The commandline of tc filter program, used to configure the filter, consists of three parts: filter specification, a selector and an action. The filter specification can be defined as: