Clean up and fix Makefiles

[lartc.git] / lartc.db

<!DOCTYPE book PUBLIC "-//OASIS//DTD DocBook V4.1//EN">
<!-- $Id$ -->
<Book id="lartc">
<?dbhtml banner-text="Made possible by PowerDNS">
<?dbhtml banner-href="http://www.powerdns.com">

  <bookinfo>
    <Title>Linux Advanced Routing &amp; Traffic Control HOWTO</Title>
    <authorgroup>
      <author>
        <FirstName>Bert</FirstName><Surname>Hubert</Surname>
        <affiliation>
          <orgname>Netherlabs BV</orgname>
          <address><email>bert.hubert@netherlabs.nl</email></address>
        </affiliation>
      </author>

      <collab>
        <collabname>Thomas Graf (Section Author)</collabname>
        <affiliation>
          <address><email>tgraf%suug.ch</email></address>
        </affiliation>
     </collab>

      
      <collab>
        <collabname>Gregory Maxwell (Section Author)</collabname>
      </collab>

      
      <collab>
        <collabname>Remco van Mook (Section Author)</collabname>
        <affiliation>
          <address><email>remco@virtu.nl</email></address>
        </affiliation>
     </collab>
  
     <collab>
       <collabname>Martijn van Oosterhout (Section Author)</collabname>
        <affiliation>
          <address><email>kleptog@cupid.suninternet.com</email></address>
        </affiliation>
     </collab>
  
     <collab>
       <collabname>Paul B Schroeder (Section Author)</collabname>
        <affiliation>
          <address><email>paulsch@us.ibm.com</email></address>
        </affiliation>
     </collab>
  
     <collab>
       <collabname>Jasper Spaans (Section Author)</collabname>
        <affiliation>
          <address><email>jasper@spaans.ds9a.nl</email></address>
        </affiliation>
     </collab>
     <collab>
       <collabname>Pedro Larroy (Section Author)</collabname>
        <affiliation>
          <address><email>piotr%member.fsf.org</email></address>
        </affiliation>
     </collab>

  </authorgroup>
  
   <revhistory>
     <revision>
       <revnumber role="rcs">$Revision$</revnumber>
       <date role="rcs">$Date$</date>
       <revremark>DocBook Edition</revremark>
     </revision>
   </revhistory>
                                   
   <Abstract>
     <Para>A very hands-on approach to <application>iproute2</application>,
     traffic shaping and a bit of <application>netfilter</application>.
     </para>
   </Abstract>
  
</bookinfo>
<toc></toc>
<chapter id="lartc.dedication">
    <Title>Dedication</Title>

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

    <Para>

      <ItemizedList>
        <ListItem>
          <Para>
            Rusty Russell
          </Para>
        </ListItem>
        <ListItem>

          <Para>
            Alexey N. Kuznetsov
          </Para>
        </ListItem>
        <ListItem>
          
          <Para>
            The good folks from Google
          </Para>
        </ListItem>
        <ListItem>
          
          <Para>
            The staff of Casema Internet
          </Para>
        </ListItem>

      </ItemizedList>
        
    </Para>

  </chapter>

  <chapter id="lartc.intro">
    <Title>Introduction</Title>

<Para>
Welcome, gentle reader.
</Para>

<Para>
      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 <command>route</command> and 
      <command>ifconfig</command> are actually
      very thin wrappers for the very powerful iproute2 infrastructure.
</Para>

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

    <Para>
      You can always reach us by writing to the <ULink
        URL="mailto:HOWTO@ds9a.nl"
        >HOWTO team</ULink
        >. However, please consider posting to the mailing
      list (see the relevant section) if you have questions which are not directly
      related to this HOWTO. We are no free helpdesk, but we often will answer questions
      asked on the list.
</Para>

<Para>
Before losing your way in this HOWTO, if all you want to do is simple
traffic shaping, skip everything and head to the <citetitle><xref linkend="lartc.other"></citetitle> chapter, and read about CBQ.init.
</Para>

<Sect1 id="lartc.intro.disclaimer">
<Title>Disclaimer &amp; License</Title>

<Para>
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.
</Para>

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

<Para>
Copyright (c) 2002 by bert hubert, Gregory Maxwell, Martijn van
Oosterhout, Remco van Mook, Paul B. Schroeder and others. This material may
be distributed only subject to the terms and conditions set forth in the
Open Publication License, v1.0 or later (the latest version is presently
available at http://www.opencontent.org/openpub/).
</Para>

<Para>
Please freely copy and distribute (sell or give away) this document in any
format. It's requested that corrections and/or comments be forwarded to the
document maintainer. 
</Para>

<Para>
It is also requested that if you publish this HOWTO in hardcopy that you
send the authors some samples for <quote>review purposes</quote> :-) 
</Para>

</Sect1>

<Sect1 id="lartc.intro.prior">
  <Title>Prior knowledge</Title>

<Para>
As the title implies, this is the <quote>Advanced</quote> HOWTO.
While by no means rocket science, some prior knowledge is assumed. 
</Para>

<Para>
Here are some other references which might help teach you more:
<VariableList>
<VarListEntry>
  <Term>
    <ULink URL="http://netfilter.samba.org/unreliable-guides/networking-concepts-HOWTO/index.html">
      Rusty Russell's networking-concepts-HOWTO</ULink>
  </Term>
  <ListItem>
    <Para>Very nice introduction, explaining what a network is, and how it is
    connected to other networks.
    </Para>
  </ListItem>
</VarListEntry>
<VarListEntry>
  <Term>Linux Networking-HOWTO (Previously the Net-3 HOWTO)</Term>
  <ListItem>
    <Para>Great stuff, although very verbose. It teaches you a lot of stuff 
    that's already configured if you are able to connect to the Internet. 
    Should be located in <filename>/usr/doc/HOWTO/NET3-4-HOWTO.txt</filename>
 but can be also be found 
    <ULink URL="http://www.linuxports.com/howto/networking">online</ULink>.
    </Para>
  </ListItem>
</VarListEntry>
</VariableList>
</Para>

</Sect1>

<Sect1 id="lartc.intro.linux">
  <Title>What Linux can do for you</Title>

<Para>
A small list of things that are possible:
</Para>

<ItemizedList>
<ListItem>
  <Para>Throttle bandwidth for certain computers
  </Para>
</ListItem>
<ListItem>
  <Para>Throttle bandwidth TO certain computers
  </Para>
</ListItem>
<ListItem>
  <Para>Help you to fairly share your bandwidth
  </Para>
</ListItem>
<ListItem>
  <Para>Protect your network from DoS attacks
  </Para>
</ListItem>
<ListItem>
  <Para>Protect the Internet from your customers
  </Para>
</ListItem>
<ListItem>
  <Para>Multiplex several servers as one, for load balancing or
  enhanced availability
  </Para>
</ListItem>
<ListItem>
  <Para>Restrict access to your computers
  </Para>
</ListItem>
<ListItem>
  <Para>Limit access of your users to other hosts
  </Para>
</ListItem>
<ListItem>
  <Para>Do routing based on user id (yes!), MAC address, source IP
  address, port, type of service, time of day or content
  </Para>
</ListItem>
</ItemizedList>

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

</Sect1>

<Sect1 id="lartc.intro.houskeeping">
  <Title>Housekeeping notes</Title>

<Para>
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 realize that I'm not a native
speaker. Feel free to send suggestions.
</Para>

<Para>
If you feel 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.
</Para>

<Para>
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 in
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.
</Para>

<Para>
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.
</Para>

</Sect1>

<Sect1 id="lartc.intro.cvs">
  <Title>Access, CVS &amp; submitting updates</Title>

<Para>
The canonical location for the HOWTO is 
<ULink URL="http://www.ds9a.nl/lartc">here</ULink>.
</Para>

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

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

<Screen width="80">
$ 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/lartc.db
</Screen>

<Para>
If you made changes and want to contribute them, run <userinput>
cvs -z3 diff -uBb</userinput>,
and mail the output to <email>howto@ds9a.nl</email>, we
can then integrate it easily. Thanks! Please make sure that you edit the
.db file, by the way, the other files are generated from that one. 
</Para>

<Para>
A Makefile is supplied which should help you create postscript, dvi, pdf,
html and plain text. You may need to install 
<application>docbook</application>, <application>docbook-utils</application>,
<application>ghostscript</application> and <application>tetex</application> 
to get all formats.
</Para>

<para>
Be careful not to edit 2.4routing.sgml! It contains an older version of the
HOWTO. The right file is lartc.db.
</para>
</Sect1>

<Sect1 id="lartc.intro.mlist">
  <Title>Mailing list</Title>

<Para>
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
<ULink URL="http://mailman.ds9a.nl/mailman/listinfo/lartc">here</ULink>.
</Para>

<Para>
It should be pointed out that the authors are very hesitant of answering
questions not asked 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.
</Para>

</Sect1>

<Sect1 id="lartc.intro.layout">
  <Title>Layout of this document</Title>

<Para>
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.
</Para>

<Para>
Routing and filtering are two distinct things. Filtering is documented very
well by Rusty's HOWTOs, available here:
</Para>

<ItemizedList>
<ListItem>
  <Para><ULink URL="http://netfilter.samba.org/unreliable-guides/">
    Rusty's Remarkably Unreliable Guides</ULink>
  </Para>
</ListItem>
</ItemizedList>

<Para>We will be focusing mostly on what is possible by combining netfilter
and iproute2.
</Para>

</Sect1>

</chapter>

<chapter id="lartc.iproute2">
  <Title>Introduction to iproute2</Title>

<Sect1 id="lartc.iproute2.why">
  <Title>Why iproute2?</Title>

<Para>
Most Linux distributions, and most UNIX's, currently use the 
venerable <command>arp</command>, <command>ifconfig</command> and 
<command>route</command> 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.
</Para>

<Para>
With <application>iproute2</application>, tunnels are an integral part of 
the tool set.
</Para>

<Para>
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 than the one
provided by many dedicated routers and firewalls and traffic shaping
products.
</Para>

<Para>
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.  
</Para>

<Para>
This new framework makes it possible to clearly express features
previously beyond Linux's reach.
</Para>

</Sect1>

<Sect1 id="lartc.iproute2.tour">
  <Title>iproute2 tour</Title>

<Para>
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.
</Para>

<Para>
We'll start off with a tiny tour of iproute2 possibilities.
</Para>

</Sect1>

<Sect1 id="lartc.iproute2.package">
  <Title>Prerequisites</Title>

<Para>
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 <filename>ftp://ftp.inr.ac.ru/ip-routing/iproute2-2.2.4-now-ss??????.tar.gz"</filename>. 
</Para>

<Para>
You can also try 
<ULink URL="ftp://ftp.inr.ac.ru/ip-routing/iproute2-current.tar.gz">here</ULink> 
for the latest version.
</Para>

<Para>
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. 
</Para>

<Para>
RedHat 7.2 has everything in by default.
</Para>

<Para>
Also make sure that you have netlink support, should you choose to roll your
own kernel. Iproute2 needs it.
</Para>

</Sect1>

<Sect1 id="lartc.iproute2.explore">
  <Title>Exploring your current configuration</Title>

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

<Para>
The <command>ip</command> tool is central, and we'll ask it to display our interfaces
for us.
</Para>

<Sect2>
<Title><command>ip</command> shows us our links</Title>

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

</Screen>

<Para>
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.
</Para>

<Para>
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.
</Para>

<Para>
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 one serves my home ethernet segment.
Furthermore, we see a ppp0 interface.
</Para>

<Para>
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. 
</Para>

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

</Sect2>

<Sect2>
  <Title><command>ip</command> shows us our IP addresses</Title>

<Screen width="80">
[ahu@home ahu]$ ip address show        
1: lo: &#60;LOOPBACK,UP&#62; 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: &#60;BROADCAST,NOARP&#62; mtu 1500 qdisc noop 
    link/ether 00:00:00:00:00:00 brd ff:ff:ff:ff:ff:ff
3: eth0: &#60;BROADCAST,MULTICAST,PROMISC,UP&#62; 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: &#60;BROADCAST,MULTICAST,PROMISC,UP&#62; mtu 1500 qdisc pfifo_fast qlen 100
    link/ether 00:e0:4c:39:24:78 brd ff:ff:ff:ff:ff:ff
3764: ppp0: &#60;POINTOPOINT,MULTICAST,NOARP,UP&#62; mtu 1492 qdisc pfifo_fast qlen 10
    link/ppp 
    inet 212.64.94.251 peer 212.64.94.1/32 scope global ppp0
</Screen>

<Para>
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.
</Para>

<Para>
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.
</Para>

<Para>
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. 
</Para>

<Para>
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 there is, yet again, only one address,
212.64.94.1. The /32 tells us that there are no 'network bits'.
</Para>

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

<Para>
You may also note 'qdisc', which stands for Queueing Discipline. This will
become vital later on. 
</Para>

</Sect2>

<Sect2>
  <Title><command>ip</command> shows us our routes</Title>

<Para>
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.
</Para>

<Screen width="80">
[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 
</Screen>

<Para>
This is pretty much self explanatory. The first 3 lines of output explicitly
state what was already implied by <command>ip address show</command>, 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.
</Para>

<Para>
For reference, this is what the old <command>route</command> utility shows us:
</Para>

<Screen width="80">
[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
</Screen>

</Sect2>

</Sect1>

<Sect1 id="lartc.iproute2.arp">
  <Title>ARP</Title>

<Para>
ARP is the Address Resolution Protocol as described in
<ULink URL="http://www.faqs.org/rfcs/rfc826.html">RFC 826</ULink>.
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.
</Para>

<Para>
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
that's used to locate his friend on the network, foo is able to communicate
with bar until he (his arp cache) forgets where bar is (typically after
15 minutes on Unix).
</Para>

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

<Screen width="80">
[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
</Screen>

<Para>
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.
</Para>

<Screen width="80">
[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
</Screen>

<Para>
As a result of espa041 trying to contact espa043, espa043's hardware
address/location has now been added to the arp/neighbor 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.
</Para>

<Para>
Now let's delete espa043 from our arp cache:
</Para>

<Screen width="80">
[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
</Screen>

<Para>
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.
</Para>

</Sect1>

</chapter>

<chapter id="lartc.rpdb">
  <Title>Rules - routing policy database</Title>

<Para>
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. 
</Para>

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

<Para>
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).
</Para>

<Para>The default rules:
</Para>

<Screen width="80">
[ahu@home ahu]$ ip rule list
0:      from all lookup local 
32766:  from all lookup main 
32767:  from all lookup default
</Screen>

<Para>
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 is output by
<userinput>ip route ls</userinput>, but the 'local' and 'default' table are new.
</Para>

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

<Para>
For the exact semantics on what the kernel does when there are more matching
rules, see Alexey's ip-cref documentation. 
</Para>

<Sect1 id="lartc.rpdb.simple">
  <Title>Simple source policy routing</Title>

<Para>
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 they'll end up using the low-end cable modem.
</Para>

<Para>
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.
</Para>

<Para>The local table:
</Para>

<Screen width="80">
[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 
</Screen>

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

<Para>Let's view the 'main' table:
</Para>

<Screen width="80">
[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 
</Screen>

<Para>
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.
</Para>

<Screen width="80">
# echo 200 John &#62;&#62; /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
</Screen>

<Para>
Now all that is left is to generate John's table, and flush the route cache:
</Para>

<Screen width="80">
# ip route add default via 195.96.98.253 dev ppp2 table John
# ip route flush cache
</Screen>

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

</Sect1>

<sect1 id="lartc.rpdb.multiple-links">
  <title>Routing for multiple uplinks/providers</title>
<para>
A common configuration is the following, in which there are two providers
that connect a local network (or even a single machine) to the big Internet.

<screen>
                                                                 ________
                                          +------------+        /
                                          |            |       |
                            +-------------+ Provider 1 +-------
        __                  |             |            |     /
    ___/  \_         +------+-------+     +------------+    |
  _/        \__      |     if1      |                      /
 /             \     |              |                      |
| Local network -----+ Linux router |                      |     Internet
 \_           __/    |              |                      |
   \__     __/       |     if2      |                      \
      \___/          +------+-------+     +------------+    |
                            |             |            |     \
                            +-------------+ Provider 2 +-------
                                          |            |       |
                                          +------------+        \________
</screen>
</para>
<para>
There are usually two questions given this setup.
</para>
      <sect2><title>Split access</title>
        <para>
          The first is how to route answers to packets coming in over a
          particular provider, say Provider 1, back out again over that same provider.
        </para>
        <para>
          Let us first set some symbolical names. Let <command>$IF1</command> be the name of the
          first interface (if1 in the picture above) and <command>$IF2</command> the name of the
          second interface. Then let <command>$IP1</command> be the IP address associated with
          <command>$IF1</command> and <command>$IP2</command> the IP address associated with
          <command>$IF2</command>. Next, let <command>$P1</command> be the IP address of the gateway at
          Provider 1, and <command>$P2</command> the IP address of the gateway at provider 2.
          Finally, let <command>$P1_NET</command> be the IP network <command>$P1</command> is in,
          and <command>$P2_NET</command> the IP network <command>$P2</command> is in.
        </para>
        <para>
          One creates two additional routing tables, say <command>T1</command> and <command>T2</command>.
          These are added in /etc/iproute2/rt_tables. Then you set up routing in
          these tables as follows:
        </para>
        <para>
        <screen>
          ip route add $P1_NET dev $IF1 src $IP1 table T1
          ip route add default via $P1 table T1
          ip route add $P2_NET dev $IF2 src $IP2 table T2
          ip route add default via $P2 table T2
        </screen>
          
          Nothing spectacular, just build a route to the gateway and build a
          default route via that gateway, as you would do in the case of a single
          upstream provider, but put the routes in a separate table per provider.
          Note that the network route suffices, as it tells you how to find any host
          in that network, which includes the gateway, as specified above.
        </para>
        <para>
          Next you set up the main routing table. It is a good idea to route
          things to the direct neighbour through the interface connected to that
          neighbour. Note the `src' arguments, they make sure the right outgoing IP
          address is chosen.

          <screen>
            ip route add $P1_NET dev $IF1 src $IP1
            ip route add $P2_NET dev $IF2 src $IP2
          </screen>

          Then, your preference for default route:
          
          <screen>
            ip route add default via $P1
          </screen>

          Next, you set up the routing rules. These actually choose what routing table
          to route with. You want to make sure that you route out a given
          interface if you already have the corresponding source address:
          
          <screen>
            ip rule add from $IP1 table T1
            ip rule add from $IP2 table T2
          </screen>

          This set of commands makes sure all answers to traffic coming in on a
          particular interface get answered from that interface.
        </para>
        <para>
        <warning><para>
Reader Rod Roark notes: 'If $P0_NET is the local network and $IF0 is its interface,
the following additional entries are desirable:
<screen>
ip route add $P0_NET     dev $IF0 table T1
ip route add $P2_NET     dev $IF2 table T1
ip route add 127.0.0.0/8 dev lo   table T1
ip route add $P0_NET     dev $IF0 table T2
ip route add $P1_NET     dev $IF1 table T2
ip route add 127.0.0.0/8 dev lo   table T2                                      
</screen>'
</para></warning></para>
        <para>
          Now, this is just the very basic setup. It will work for all processes
          running on the router itself, and for the local network, if it is
          masqueraded. If it is not, then you either have IP space from both providers
          or you are going to want to masquerade to one of the two providers. In both
          cases you will want to add rules selecting which provider to route out from
          based on the IP address of the machine in the local network.
        </para>
      </sect2>
      <sect2><title>Load balancing</title>
        <para>
          The second question is how to balance traffic going out over the two providers.
          This is actually not hard if you already have set up split access as above.
          </para>
        <para>
          Instead of choosing one of the two providers as your default route,
          you now set up the default route to be a multipath route. In the default
          kernel this will balance routes over the two providers. It is done
          as follows (once more building on the example in the section on
          split-access):

          <screen>
            ip route add default scope global nexthop via $P1 dev $IF1 weight 1 \
            nexthop via $P2 dev $IF2 weight 1
          </screen>

          This will balance the routes over both providers. The <command>weight</command>
          parameters can be tweaked to favor one provider over the other.
        </para>
        <para>
          Note that balancing will not be perfect, as it is route based, and routes
          are cached. This means that routes to often-used sites will always
          be over the same provider.
        </para>
        <para>
          Furthermore, if you really want to do this, you probably also want to look
          at Julian Anastasov's patches at <ulink url="http://www.ssi.bg/~ja/#routes">http://www.ssi.bg/~ja/#routes 
            </ulink>, Julian's route patch page. They will make things nicer to work with.
        </para>
      </sect2>
    </sect1>
  </chapter>

<chapter id="lartc.tunnel">
   <Title>GRE and other tunnels</Title>

<Para>
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). 
</Para>

<Sect1 id="lartc.tunnel.remarks">
  <Title>A few general remarks about tunnels:</Title>

<Para>
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
<Emphasis>EXACTLY</Emphasis> 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.
</Para>

</Sect1>

<Sect1 id="lartc.tunnel.ip-ip">
  <Title>IP in IP tunneling</Title>

<Para>
This kind of tunneling has been available in Linux for a long time. It requires 2 kernel modules,
ipip.o and new_tunnel.o.
</Para>

<Para>
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:
</Para>

<Screen width="80">
network 10.0.1.0
netmask 255.255.255.0
router  10.0.1.1
</Screen>

<Para>The router has address 172.16.17.18 on network C.
</Para>

<Para>and network B:
</Para>

<Screen width="80">
network 10.0.2.0
netmask 255.255.255.0
router  10.0.2.1
</Screen>

<Para>The router has address 172.19.20.21 on network C.
</Para>

<Para>
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.
</Para>

<Para>Here's what you do:
</Para>

<Para>First, make sure the modules are installed:
</Para>

<Screen width="80">
insmod ipip.o
insmod new_tunnel.o
</Screen>

<Para>Then, on the router of network A, you do the following:
</Para>

<Screen width="80">
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
</Screen>

<Para>And on the router of network B:
</Para>

<Screen width="80">
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
</Screen>

<Para>And if you're finished with your tunnel:
</Para>

<Screen width="80">
ifconfig tunl0 down
</Screen>

<Para>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.
</Para>

</Sect1>

<Sect1 id="lartc.tunnel.gre">
  <Title>GRE tunneling</Title>

<Para>
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.
</Para>

<Para>
In Linux, you'll need the ip_gre.o module.
</Para>

<Sect2>
<Title>IPv4 Tunneling</Title>

<Para>
Let's do IPv4 tunneling first:
</Para>

<Para>
Let's say you have 3 networks: Internal networks A and B, and intermediate network C (or let's say, Internet). 
</Para>

<Para>
So we have network A:

<Screen width="80">
network 10.0.1.0
netmask 255.255.255.0
router  10.0.1.1
</Screen>

The router has address 172.16.17.18 on network C.
Let's call this network neta (ok, hardly original)
</Para>

<Para>
and network B:

<Screen width="80">
network 10.0.2.0
netmask 255.255.255.0
router  10.0.2.1
</Screen>

The router has address 172.19.20.21 on network C.
Let's call this network netb (still not original)
</Para>

<Para>
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.
</Para>

<Para>On the router of network A, you do the following:
</Para>

<Screen width="80">
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
</Screen>

<Para>
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).
</Para>

<Para>
The second line enables the device.
</Para>

<Para>
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).
</Para>

<Para>
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.
</Para>

<Para>
But enough about this, let's go on with the router of network B.

<Screen>
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
</Screen>

And when you want to remove the tunnel on router A:

<Screen>
ip link set netb down
ip tunnel del netb
</Screen>

Of course, you can replace netb with neta for router B.
</Para>

</Sect2>

<Sect2>
<Title>IPv6 Tunneling</Title>

<Para>
See Section 6 for a short bit about IPv6 Addresses.
</Para>

<Para>
On with the tunnels.
</Para>

<Para>
Let's assume that you have the following IPv6 network, and you want to connect it to 6bone, or a friend.
</Para>

<Para>

<Screen>
Network 3ffe:406:5:1:5:a:2:1/96
</Screen>

Your IPv4 address is 172.16.17.18, and the 6bone router has IPv4 address 172.22.23.24. 
</Para>

<Para>

<Screen>
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 
</Screen>

</Para>

<Para>
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.
</Para>

<Para>
GRE tunnels are currently the preferred type of tunneling. It's a standard that is also widely adopted outside the Linux community and therefore a Good Thing.
</Para>

</Sect2>

</Sect1>

<Sect1 id="lartc.tunnel.userland">
  <Title>Userland tunnels</Title>

<Para>
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.
</Para>

</Sect1>

</chapter>

<chapter id="lartc.ipv6-tunnel">
<Title>IPv6 tunneling with Cisco and/or 6bone</Title>

<Para>
By Marco Davids &lt;marco@sara.nl&gt;
</Para>

<Para>
NOTE to maintainer:
</Para>

<Para>
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.
</Para>

<Sect1 id="lartc.tunnel-ipv6.addressing">
  <Title>IPv6 Tunneling</Title>

<Para>
This is another application of the tunneling capabilities of Linux. It is
popular 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 tells us that
this is just the thing many people are after. Ten to one this applies to
you too ;-)
</Para>

<Para>
A short bit about IPv6 addresses:
</Para>

<Para>
IPv6 addresses are, compared to IPv4 addresses, really big: 128 bits
against 32 bits. And this provides us just with 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.
</Para>

<Para>
An example: 2002:836b:9820:0000:0000:0000:836b:9886
</Para>

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

<Para>

<ItemizedList>
<ListItem>

<Para>
Don't use leading zeroes. Same as in IPv4.

</Para>
</ListItem>
<ListItem>

<Para>
Use colons to separate every 16 bits or two bytes.

</Para>
</ListItem>
<ListItem>

<Para>
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.
</Para>
</ListItem>

</ItemizedList>

</Para>

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

<Para>
Another example, the address 3ffe:0000:0000:0000:0000:0020:34A1:F32C can be
written down as 3ffe::20:34A1:F32C, which is a lot shorter.
</Para>

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

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

<Para>
That is precisely where the tunnel steps in.
</Para>

<Para>
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:

<ItemizedList>
<ListItem>

<Para>
Get yourself a recent Linux distribution, with suitable glibc.
</Para>
</ListItem>
<ListItem>

<Para>
Then get yourself an up-to-date kernel source.
</Para>
</ListItem>

</ItemizedList>

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

<ItemizedList>
<ListItem>

<Para>
Go to /usr/src/linux and type:
</Para>
</ListItem>
<ListItem>

<Para>
make menuconfig
</Para>
</ListItem>
<ListItem>

<Para>
Choose "Networking Options"
</Para>
</ListItem>
<ListItem>

<Para>
Select "The IPv6 protocol", "IPv6: enable EUI-64 token format", "IPv6:
disable provider based addresses"
</Para>
</ListItem>

</ItemizedList>

HINT: Don't go for the 'module' option. Often this won't work well.
</Para>

<Para>
In other words, compile IPv6 as 'built-in' in your kernel.
You can then save your config like usual and go ahead with compiling
the kernel.
</Para>

<Para>
HINT: Before doing so, consider editing the Makefile:
EXTRAVERSION = -x ; --&#62; ; EXTRAVERSION = -x-IPv6
</Para>

<Para>
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.
</Para>

<Para>
The file /usr/src/linux/README might be a good start.
After you accomplished 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 ;-)
</Para>

<Para>
Now 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 for this particular purpose.
</Para>

<Para>
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 addresses.
</Para>

<Para>
Your IPv4 address is 145.100.24.181 and the 6bone router has IPv4 address
145.100.1.5
</Para>

<Screen width="80">
# ip tunnel add sixbone mode sit remote 145.100.1.5 [local 145.100.24.181 ttl 255]
# ip link set sixbone up
# ip addr add 3FFE:604:6:7::2/126 dev sixbone
# ip route add 3ffe::0/16 dev sixbone
</Screen>

<Para>
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. 
</Para>

<Para>
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:
</Para>

<Screen width="80">
# echo 1 &#62;/proc/sys/net/ipv6/conf/all/forwarding
# /usr/local/sbin/radvd
</Screen>

<Para>
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:
</Para>

<Screen width="80">
# /sbin/ip -f inet6 addr
</Screen>

<Para>
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:
</Para>

<Screen width="80">
# /sbin/ip -f inet6 addr
1: lo: &lt;LOOPBACK,UP&gt; mtu 3924 qdisc noqueue inet6 ::1/128 scope host

3: eth0: &lt;BROADCAST,MULTICAST,UP&gt; 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
</Screen>

<Para>
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.
</Para>

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

<Para>
On the Cisco side the configuration would be something like this:

<Screen>
!
interface Tunnel1
description IPv6 tunnel
no ip address
no ip directed-broadcast
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
</Screen>

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 search engine.
</Para>

</Sect1>

</chapter>

  <chapter id="lartc.ipsec">
    <Title>IPSEC: secure IP over the Internet</Title>
    <Para>

      There are two kinds of IPSEC available for Linux these days. For 2.2
      and 2.4, there is FreeS/WAN, which was the first major implementation. They

      have <ULink URL="http://www.freeswan.org/">an official site</ulink> and <ulink url="http://www.freeswan.ca">
        an unofficial one</ulink> that is actually maintained. FreeS/WAN has traditionally not been merged with
      the mainline kernel for a number of reasons. Most often mentioned are 'political' issues with Americans
      working on crypto tainting its exportability. Furthermore, it does not integrate too well with the Linux kernel,
      leading it to be a bad candidate for actual merging. 
    </para>
    <para>
      Additionally, <ulink
url="http://www.edlug.ed.ac.uk/archive/Sep2002/msg00244.html">many</ulink> parties <ulink
url="http://lists.freeswan.org/pipermail/design/2002-November/003901.html">have voiced
worries</ulink> about the quality of the code. To setup FreeS/WAN, a lot of
<ulink
url="http://www.freeswan.ca/docs/freeswan-1.99/doc/index.html">documentation</ulink>
is <ulink url="http://www.freeswan.org/doc.html">available</ulink>.
    </para>
    <para>
      As of Linux 2.5.47, there is a native IPSEC implementation in the kernel. It was written by Alexey Kuznetsov and
      Dave Miller, inspired by the work of the USAGI IPv6 group. With its merge, James Morris' CrypoAPI also became 
      part of the kernel - it does the actual crypting.
    </para>
    <para>
      This HOWTO will only document the 2.5+ version of IPSEC. FreeS/WAN is recommended for Linux 2.4 users for now, but be aware
      that its configuration will differ from the native IPSEC. In related
news, there are now <ulink
url="http://gondor.apana.org.au/~herbert/freeswan/">patches</ulink> to make the FreeS/WAN userspace code work with
the native Linux IPSEC.
    </para>
    <para>
        As of 2.5.49, IPSEC works without further patches.
        </para>
        <para>
      <note>
        <para>
          Userspace tools appear to be available <ulink
          url="http://sourceforge.net/projects/ipsec-tools">here</ulink>.
There are multiple programs available, the one linked here is based on
Racoon. 
        </para>
        <para>
        When compiling your kernel, be sure to turn on 'PF_KEY', 'AH', 'ESP' and
everything in the CryptoAPI!
        </para>
      </note>
      <warning>
        <para>
          The author of this chapter is a complete IPSEC nitwit! If you find the inevitable mistakes, please email
          bert hubert <email>ahu@ds9a.nl</email>. 
        </para>
      </warning>
    </Para>
    <para>
      First, we'll show how to manually setup secure communication between
      two hosts. A large part of this process can also be automated, but
here we'll do it by hand so as to acquaint ourselves with what is going on
'under the hood'. 
    </para>
    <para>
        Feel free to skip the following section if you are only interested
in automatic keying but be aware that some understanding of manual keying is
useful. 
    </para>
    <sect1 id="lartc.ipsec.intro"><title>Intro with Manual Keying</title>
      <para>
        IPSEC is a complicated subject. A lot of information is available online, this HOWTO will concentrate on getting you
        up and running and explaining the basic principles. All examples are
based on Racoon as found on the link above.
      </para>
      <para>
        <note>
          <para>
            Many iptables configurations drop IPSEC packets! To pass IPSEC, use: 'iptables -A xxx -p 50 -j ACCEPT' and 'iptables -A xxx -p 51 -j ACCEPT'
          </para>
        </note>
      </para>
      <para>
        IPSEC offers a secure version of the Internet Protocol. Security in this context means two different things: encryption and authentication. 
        A naive vision of security offers only encryption but it can easily be shown that is insufficient - you may be communicating encyphered,
        but no guarantee is offered that the remote party is the one you expect it to be.
      </para>
      <para>
        IPSEC supports 'Encapsulated Security Payload' (ESP) for encryption and 'Authentication Header' (AH) for authenticating the remote partner.
        You can configure both of them, or decided to do only either.
      </para>
      <para>
        Both ESP and AH rely on security associations. A security association (SA) consists of a source, a destination and an instruction. A sample 
        authentication SA may look like this:
        <screen>
          add 10.0.0.11 10.0.0.216 ah 15700 -A hmac-md5 "1234567890123456";
        </screen>
        This says 'traffic going from 10.0.0.11 to 10.0.0.216 that needs an AH can be signed using HMAC-MD5 using secret 1234567890123456'. This instruction
        is labelled with SPI ('Security Parameter Index') id '15700', more about that later.
        The interesting bit about SAs is that they are symmetrical. Both sides of a conversation share exactly the same SA, it is not mirrored on the
        other side. Do note however that there is no 'autoreverse' rule - this SA only describes a possible authentication from 10.0.0.11 to 
        10.0.0.216. For two-way traffic, two SAs are needed.
      </para>
      <para>
        A sample ESP SA:
        <screen>
add 10.0.0.11 10.0.0.216 esp 15701 -E 3des-cbc "123456789012123456789012";
        </screen>
        This says 'traffic going from 10.0.0.11 to 10.0.0.216 that needs encryption can be encyphered using 3des-cbc with key 123456789012123456789012'. The
        SPI id is '15701'.
      </para>
      <para>
        So far, we've seen that SAs describe possible instructions, but do not in fact describe policy as to when these need to be used. In fact,
        there could be an arbitrary number of nearly identical SAs with only differing SPI ids. Incidentally, SPI stands for Security Parameter Index.
        To do actual crypto, we need to describe a policy. This policy can include things as 'use ipsec if available' or 'drop traffic unless we have ispec'.
      </para>
      <para>
        A typical simple Security Policy (SP) looks like this:
        <screen>
spdadd 10.0.0.216 10.0.0.11 any -P out ipsec
   esp/transport//require
   ah/transport//require;
        </screen>
        If entered on host 10.0.0.216, this means that all traffic going out to 10.0.0.11 must be encrypted 
        and be wrapped in an AH authenticating header. Note that this does not describe which SA is to be used,
        that is left as an exercise for the kernel to determine.
      </para>
        <para>
        In other words, a Security Policy specifies WHAT we want; a Security
Association describes HOW we want it. 
</para>
      <para>
        Outgoing packets are labelled with the SA SPI ('the how') which the
        kernel used for encryption and authentication so the remote can
        lookup the corresponding verification and decryption instruction.
      </para>

      <para>
        What follows is a very simple configuration for talking from host 10.0.0.216 to 10.0.0.11 using 
        encryption and authentication. Note that the reverse path is plaintext in this first version and that
        this configuration should not be deployed.
      </para>
      <para>
        On host 10.0.0.216:
        <screen>
#!/sbin/setkey -f
add 10.0.0.216 10.0.0.11 ah 24500 -A hmac-md5 "1234567890123456";          
add 10.0.0.216 10.0.0.11 esp 24501 -E 3des-cbc "123456789012123456789012";

spdadd 10.0.0.216 10.0.0.11 any -P out ipsec
   esp/transport//require
   ah/transport//require;
        </screen>
      </para>
      <para>
        On host 10.0.0.11, the same Security Associations, no Security Policy:
        <screen>
#!/sbin/setkey -f
add 10.0.0.216 10.0.0.11 ah 24500 -A hmac-md5 "1234567890123456";
add 10.0.0.216 10.0.0.11 esp 24501 -E 3des-cbc "123456789012123456789012";
        </screen>
      </para>
      <para>
        With the above configuration in place (these files can be executed if 'setkey' is installed in /sbin),
        'ping 10.0.0.11' from 10.0.0.216 looks like this using tcpdump:
        <screen>
22:37:52 10.0.0.216 &gt; 10.0.0.11: AH(spi=0x00005fb4,seq=0xa): ESP(spi=0x00005fb5,seq=0xa) (DF)
22:37:52 10.0.0.11 &gt; 10.0.0.216: icmp: echo reply
        </screen>
        Note how the ping back from 10.0.0.11 is indeed plainly visible. The forward ping cannot be read by tcpdump
        of course, but it does show the Security Parameter Index of AH and ESP, which tells 10.0.0.11 how to 
        verify the authenticity of our packet and how to decrypt it.
      </para>
      <para>
        A few things must be mentioned however. The configuration above is shown in a lot of IPSEC examples and it is very dangerous.
        The problem is that the above contains policy on how 10.0.0.216 should treat packets going to 10.0.0.11, and that it explains how 10.0.0.11
        should treat those packets but it does NOT instruct 10.0.0.11 to discard unauthenticated or unencrypted traffic! 
      </para>
      <para>
        Anybody can now insert spoofed and completely unencrypted data and 10.0.0.11 will accept it. To remedy the above, we need an incoming 
        Security Policy on 10.0.0.11, as follows:
        <screen>
#!/sbin/setkey -f 
spdadd 10.0.0.216 10.0.0.11 any -P IN ipsec
   esp/transport//require
   ah/transport//require;
        </screen>
        This instructs 10.0.0.11 that any traffic coming to it from 10.0.0.216 is required to have valid ESP and AH.
      </para>
      <para>
        Now, to complete this configuration, we need return traffic to be encrypted and authenticated as well of course. The full configuration on
        10.0.0.216:
        <screen>
#!/sbin/setkey -f
flush;
spdflush;

# AH
add 10.0.0.11 10.0.0.216 ah 15700 -A hmac-md5 "1234567890123456";
add 10.0.0.216 10.0.0.11 ah 24500 -A hmac-md5 "1234567890123456";

# ESP
add 10.0.0.11 10.0.0.216 esp 15701 -E 3des-cbc "123456789012123456789012";
add 10.0.0.216 10.0.0.11 esp 24501 -E 3des-cbc "123456789012123456789012";

spdadd 10.0.0.216 10.0.0.11 any -P out ipsec
           esp/transport//require
           ah/transport//require;

spdadd 10.0.0.11 10.0.0.216 any -P in ipsec
           esp/transport//require
           ah/transport//require;
          
        </screen>
      </para>
      <para>
        And on 10.0.0.11:
        <screen>
#!/sbin/setkey -f
flush;
spdflush;

# AH
add 10.0.0.11 10.0.0.216 ah 15700 -A hmac-md5 "1234567890123456";
add 10.0.0.216 10.0.0.11 ah 24500 -A hmac-md5 "1234567890123456";

# ESP
add 10.0.0.11 10.0.0.216 esp 15701 -E 3des-cbc "123456789012123456789012";
add 10.0.0.216 10.0.0.11 esp 24501 -E 3des-cbc "123456789012123456789012";


spdadd 10.0.0.11 10.0.0.216 any -P out ipsec
           esp/transport//require
           ah/transport//require;

spdadd 10.0.0.216 10.0.0.11 any -P in ipsec
           esp/transport//require
           ah/transport//require;

        </screen>
      </para>
      <para>
        Note that in this example we used identical keys for both directions of traffic. This is not in any way required however.
      </para>
      <para>
        To examine the configuration we just created, execute <command>setkey -D</command>, which shows the Security Associations or 
        <command>setkey -DP</command> which shows the configured policies.
      </para>
    </sect1>
    <sect1 id="lartc.ipsec.automatic.keying"><title>Automatic keying</title>
      <para>
        In the previous section, encryption was configured using simple shared secrets. In other words, to remain secure,
        we need to transfer our encryption configuration over a trusted channel. If we were to configure the remote host 
        over telnet, any third party would know our shared secret and the setup would not be secure.
      </para>
      <para>
        Furthermore, because the secret is shared, it is not a secret. The remote can't do a lot with our secret, but we do 
        need to make sure that we use a different secret for communicating with all our partners. This requires a large number of keys,
        if there are 10 parties, this needs at least 50 different secrets. 
      </para>
      <para>
        Besides the symmetric key problem, there is also the need for key rollover. If a third party manages to sniff enough traffic,
        it may be in a position to reverse engineer the key. This is prevented by moving to a new key every once in a while but that is
        a process that needs to be automated.
      </para>
      <para>
        Another problem is that with manual keying as described above we exactly define the algorithms and key lengths used, something
        that requires a lot of coordination with the remote party. It is desirable to be able to have the ability to describe a 
        broader key policy such as 'We can do 3DES and Blowfish with at least the following key lengths'.
      </para>
      <para>
        To solve these isses, IPSEC provides Internet Key Exchange to automatically exchange randomly generated keys which are
        transmitted using asymmetric encryption technology, according to negotiated algorithm details.
      </para>
      <para>
        The Linux 2.5 IPSEC implementation works with the KAME 'racoon' IKE
        daemon. As of 9 November, the racoon version in Alexey's iptools
        distribution can be compiled, although you may need to remove 
#include &lt;net/route.h&gt; in two files. Alternatively, I've supplied a
<ulink url="http://ds9a.nl/ipsec/racoon.bz2">precompiled version</ulink>.
      </para>
        <para>
        <note>
          <para>
                IKE needs access to UDP port 500, be sure that iptables does
not block it.
          </para>
        </note>
        </para>
        <sect2 id="lartc.ipsec.keying.theory"><title>Theory</title>
        <para>
                As explained before, automatic keying does a lot of the work
for us. Specifically, it creates Security Associations on the fly. It does
not however set policy for us, which is as it should be.
        </para>
        <para>
        So, to benefit from IKE, setup a policy, but do not supply any
SAs. If the kernel discovers that there is an IPSEC policy, but no Security
Association, it will notify the IKE daemon, which then goes to work on
trying to negotiate one.
        </para>
        <para>
        Reiterating, a Security Policy specifies WHAT we want; a Security
Association describes HOW we want it. Using automatic keying lets us get
away with only specifying what we want.
        </para>
</sect2>
        <sect2 id="lartc.ipsec.automatic.keying.example"><title>Example</title>
        <para>
        Kame racoon comes with a grand host of options, most of which have
very fine default values, so we don't need to touch them. As described
above, the operator needs to define a Security Policy, but no Security
Associations. We leave their negotiation to the IKE daemon.
        </para>
        <para>
        In this example, 10.0.0.11 and 10.0.0.216 are once again going to
setup secure communications, but this time with help from racoon. For
simplicity this configuration will be using pre-shared keys, the
dreaded 'shared secrets'. X.509 certificates are discussed in a separate
section, see <xref linkend="lartc.ipsec.x509">.
</para>
<para> We're
going to stick to almost the default configuration, identical on both hosts:
        </para> 
        <para>
<screen>
path pre_shared_key "/usr/local/etc/racoon/psk.txt";

remote anonymous
{
        exchange_mode aggressive,main;
        doi ipsec_doi;
        situation identity_only;

        my_identifier address;

        lifetime time 2 min;   # sec,min,hour
        initial_contact on;
        proposal_check obey;    # obey, strict or claim

        proposal {
                encryption_algorithm 3des;
                hash_algorithm sha1;
                authentication_method pre_shared_key;
                dh_group 2 ;
        }
}
 
sainfo anonymous
{
        pfs_group 1;
        lifetime time 2 min;
        encryption_algorithm 3des ;
        authentication_algorithm hmac_sha1;
                compression_algorithm deflate ;
}
</screen>
        </para>
        <para>
        Lots of settings - I think yet more can be removed to get closer to
the default configuration. A few noteworthy things. We've configured two
anonymous settings which hold for all remotes, making further configuration
easy. There is no need for per-host stanzas here, unless we really want
them.
</para>
        <para>
        Furthermore, we've set it up such that we identify ourselves based
on our IP address ('my_identifier address'), and declare that we can do
3des, sha1, and that we will be using a pre-shared key, located in psk.txt.
        </para>
        <para>
        In psk.txt, we now setup two entries, which do differ on both hosts.
On 10.0.0.11:
<screen>
10.0.0.216      password2
</screen>
On 10.0.0.216:
<screen>
10.0.0.11       password2
</screen>
        Make sure these files are owned by root, and set to mode 0600,
racoon will not trust their contents otherwise. Note that these files are
mirrors from eachother.
        </para>
        <para>
        Now we are ready to setup our desired policy, which is simple
enough. On host 10.0.0.216:
<screen>
#!/sbin/setkey -f
flush;
spdflush;

spdadd 10.0.0.216 10.0.0.11 any -P out ipsec
        esp/transport//require;

spdadd 10.0.0.11 10.0.0.216 any -P in ipsec
        esp/transport//require;
</screen>
And on 10.0.0.11:
<screen>
#!/sbin/setkey -f
flush;
spdflush;

spdadd 10.0.0.11 10.0.0.216 any -P out ipsec
        esp/transport//require;

spdadd 10.0.0.216 10.0.0.11 any -P in ipsec
        esp/transport//require;
</screen>
Note how again these policies are mirrored.
        </para>
        <para>
        We are now ready to launch racoon! Once launched, the moment we try
to telnet from 10.0.0.11 to 10.0.0.216, or the other way around, racoon
will start negotiating:
<screen>
12:18:44: INFO: isakmp.c:1689:isakmp_post_acquire(): IPsec-SA
  request for 10.0.0.11 queued due to no phase1 found.
12:18:44: INFO: isakmp.c:794:isakmp_ph1begin_i(): initiate new
  phase 1 negotiation: 10.0.0.216[500]<=>10.0.0.11[500]
12:18:44: INFO: isakmp.c:799:isakmp_ph1begin_i(): begin Aggressive mode.
12:18:44: INFO: vendorid.c:128:check_vendorid(): received Vendor ID: 
  KAME/racoon
12:18:44: NOTIFY: oakley.c:2037:oakley_skeyid(): couldn't find
  the proper pskey, try to get one by the peer's address.
12:18:44: INFO: isakmp.c:2417:log_ph1established(): ISAKMP-SA
  established 10.0.0.216[500]-10.0.0.11[500] spi:044d25dede78a4d1:ff01e5b4804f0680
12:18:45: INFO: isakmp.c:938:isakmp_ph2begin_i(): initiate new phase 2 
  negotiation: 10.0.0.216[0]<=>10.0.0.11[0]
12:18:45: INFO: pfkey.c:1106:pk_recvupdate(): IPsec-SA established: 
  ESP/Transport 10.0.0.11->10.0.0.216 spi=44556347(0x2a7e03b)
12:18:45: INFO: pfkey.c:1318:pk_recvadd(): IPsec-SA established:
  ESP/Transport 10.0.0.216->10.0.0.11 spi=15863890(0xf21052)
</screen>
</para>
<para>
        If we now run setkey -D, which shows the Security Associations, they
are indeed there:
<screen>
10.0.0.216 10.0.0.11 
        esp mode=transport spi=224162611(0x0d5c7333) reqid=0(0x00000000)
        E: 3des-cbc  5d421c1b d33b2a9f 4e9055e3 857db9fc 211d9c95 ebaead04
        A: hmac-sha1  c5537d66 f3c5d869 bd736ae2 08d22133 27f7aa99
        seq=0x00000000 replay=4 flags=0x00000000 state=mature 
        created: Nov 11 12:28:45 2002   current: Nov 11 12:29:16 2002
        diff: 31(s)     hard: 600(s)    soft: 480(s)
        last: Nov 11 12:29:12 2002      hard: 0(s)      soft: 0(s)
        current: 304(bytes)     hard: 0(bytes)  soft: 0(bytes)
        allocated: 3    hard: 0 soft: 0
        sadb_seq=1 pid=17112 refcnt=0
10.0.0.11 10.0.0.216 
        esp mode=transport spi=165123736(0x09d79698) reqid=0(0x00000000)
        E: 3des-cbc  d7af8466 acd4f14c 872c5443 ec45a719 d4b3fde1 8d239d6a
        A: hmac-sha1  41ccc388 4568ac49 19e4e024 628e240c 141ffe2f
        seq=0x00000000 replay=4 flags=0x00000000 state=mature 
        created: Nov 11 12:28:45 2002   current: Nov 11 12:29:16 2002
        diff: 31(s)     hard: 600(s)    soft: 480(s)
        last:                           hard: 0(s)      soft: 0(s)
        current: 231(bytes)     hard: 0(bytes)  soft: 0(bytes)
        allocated: 2    hard: 0 soft: 0
        sadb_seq=0 pid=17112 refcnt=0
</screen>
As are the Security Policies we configured ourselves:
<screen>
10.0.0.11[any] 10.0.0.216[any] tcp
        in ipsec
        esp/transport//require
        created:Nov 11 12:28:28 2002 lastused:Nov 11 12:29:12 2002
        lifetime:0(s) validtime:0(s)
        spid=3616 seq=5 pid=17134
        refcnt=3
10.0.0.216[any] 10.0.0.11[any] tcp
        out ipsec
        esp/transport//require
        created:Nov 11 12:28:28 2002 lastused:Nov 11 12:28:44 2002
        lifetime:0(s) validtime:0(s)
        spid=3609 seq=4 pid=17134
        refcnt=3
</screen>
</para>
        <sect3><title>Problems and known defects</title>
        <para>
                If this does not work, check that all configuration files
are owned by root, and can only be read by root. To start racoon on the
foreground, use '-F'. To force it to read a certain configuration file,
instead of at the compiled location, use '-f'. For staggering amounts of
detail, add a 'log debug;' statement to racoon.conf.
        </para>
        </sect3>
        </sect2>
        <sect2 id="lartc.ipsec.x509"><title>Automatic keying using X.509 certificates</title>
        <para>
        As mentioned before, the use of shared secrets is hard because they
aren't easily shared and once shared, are no longer secret. Luckily, there
is asymmetric encryption technology to help resolve this.
        </para>
        <para>
        If each IPSEC participant makes a public and a private key, secure
communications can be setup by both parties publishing their public key, and
configuring policy.
        </para>
        <para>
        Building a key is relatively easy, although it requires some work.
The following is based on the 'openssl' tool. 
        </para>
        <sect3><title>Building an X.509 certificate for your host</title>
        <para>
        OpenSSL has a lot of infrastructure for keys that may or may not be
signed by certificate authorities. Right now, we need to circumvent all that
infrastructure and practice some good old Snake Oil security, and do without
a certificate authority.
        </para>
        <para>
        First we issue a 'certificate request' for our host, called
'laptop':
<screen>
$ openssl req -new -nodes -newkey rsa:1024 -sha1 -keyform PEM -keyout \
  laptop.private -outform PEM -out request.pem
</screen>
This asks us some questions:
<screen>
Country Name (2 letter code) [AU]:NL
State or Province Name (full name) [Some-State]:.
Locality Name (eg, city) []:Delft
Organization Name (eg, company) [Internet Widgits Pty Ltd]:Linux Advanced
Routing & Traffic Control
Organizational Unit Name (eg, section) []:laptop
Common Name (eg, YOUR name) []:bert hubert
Email Address []:ahu@ds9a.nl

Please enter the following 'extra' attributes
to be sent with your certificate request
A challenge password []:
An optional company name []:
</screen>
        It is left to your own discretion how completely you want to fill
this out. You may or may not want to put your hostname in there, depending
on your security needs. In this example, we have.
</para>
        <para>
        We'll now 'self sign' this request:
<screen>
$ openssl x509 -req -in request.pem -signkey laptop.private -out \
  laptop.public
Signature ok
subject=/C=NL/L=Delft/O=Linux Advanced Routing &amp; Traffic \
  Control/OU=laptop/CN=bert hubert/Email=ahu@ds9a.nl
Getting Private key
</screen>       
        The 'request.pem' file can now be discarded. 
        </para>
        <para>
        Repeat this procedure for all hosts you need a key for. You can
distribute the '.public' file with impunity, but keep the '.private' one
private!
        </para>
        </sect3>
        <sect3><title>Setting up and launching</title>
        <para>
        Once we have a public and a private key for our hosts we can tell
        racoon to use them.
        </para>
        <para>
        We return to our previous configuration and the two hosts, 10.0.0.11
('upstairs') and 10.0.0.216 ('laptop').
        </para>
        <para>
        To the <filename>racoon.conf</filename> file on 10.0.0.11, we add:
<screen>
path certificate "/usr/local/etc/racoon/certs";

remote 10.0.0.216
{
        exchange_mode aggressive,main;
        my_identifier asn1dn;
        peers_identifier asn1dn;

        certificate_type x509 "upstairs.public" "upstairs.private";

        peers_certfile "laptop.public";
        proposal {
                encryption_algorithm 3des;
                hash_algorithm sha1;
                authentication_method rsasig;
                dh_group 2 ;
        }
}
</screen>
        This tells racoon that certificates are to be found in
<filename>/usr/local/etc/racoon/certs/</filename>. Furthermore, it contains
configuration items specific for remote 10.0.0.216.
        </para>
        <para>
        The 'asn1dn' lines tell racoon that the identifier for both the
local and remote ends are to be extracted from the public keys. This is the
'subject=/C=NL/L=Delft/O=Linux Advanced Routing &amp; Traffic 
  Control/OU=laptop/CN=bert hubert/Email=ahu@ds9a.nl' output from above.
        </para>
        <para>
        The <command>certificate_type</command> line configures the local
public and private key. The <command>peers_certfile</command> statement
configures racoon to read the public key of the remote peer from the file
<filename>laptop.public</filename>.
        </para>
        <para>
        The <command>proposal</command> stanza is unchanged from what we've
seen earlier, with the exception that the
<command>authentication_method</command> is now <command>rsasig</command>,
indicating the use of RSA public/private keys for authentication.
        </para>
        <para>
        The addition to the configuration of 10.0.0.216 is nearly identical, except for the
usual mirroring:
<screen>
path certificate "/usr/local/etc/racoon/certs";

remote 10.0.0.11
{
        exchange_mode aggressive,main;
        my_identifier asn1dn;
        peers_identifier asn1dn;

        certificate_type x509 "laptop.public" "laptop.private";
 
        peers_certfile "upstairs.public";

        proposal {
                encryption_algorithm 3des;
                hash_algorithm sha1;
                authentication_method rsasig;
                dh_group 2 ;
        }
}
</screen>
</para>
        <para>
        Now that we've added these statements to both hosts, we only need to
move the key files in place. The 'upstairs' machine needs 
<filename>upstairs.private</filename>, <filename>upstairs.public</filename>, 
and <filename>laptop.public</filename> in
<filename>/usr/local/etc/racoon/certs</filename>. Make sure that this
directory is owned by root and has mode 0700 or racoon may refuse to read
it!
</para>
<para>
The 'laptop' machine needs 
<filename>laptop.private</filename>, <filename>laptop.public</filename>, 
and <filename>upstairs.public</filename> in
<filename>/usr/local/etc/racoon/certs</filename>. In other words, each host
needs its own public and private key and additionally, the public key of the
remote.
</para>
<para>
        Verify that a Security Policy is in place (execute the 'spdadd' lines in
<xref linkend="lartc.ipsec.automatic.keying.example">). Then launch racoon and everything should
work.
</para>
        </sect3>
        <sect3><title>How to setup tunnels securely</title>
        <para>
        To setup secure communications with a remote party, we must exchange
public keys. While the public key does not need to be kept a secret, on the
contrary, it is very important to be sure that it is in fact the unaltered
key. In other words, you need to be certain there is no 'man in the middle'.
        </para>
        <para>
To make this easy, OpenSSL provides the 'digest' command:
<screen>
$ openssl dgst upstairs.public 
MD5(upstairs.public)= 78a3bddafb4d681c1ca8ed4d23da4ff1
</screen>
</para>
        <para>
        Now all we need to do is verify if our remote partner sees the same
digest. This might be done by meeting in real life or perhaps over the
phone, making sure the number of the remote party was not in fact sent over
the same email containing the key!
        </para>
        <para>
        Another way of doing this is the use of a Trusted Third Party which
runs a Certificate Authority. This CA would then sign your key, which we've
done ourselves above.
        </para>
        
        </sect3>
    </sect2>

    </sect1>
    <sect1 id="lartc.ipsec.tunnel"><title>IPSEC tunnels</title>
      <para>
        So far, we've only seen IPSEC in so called 'transport' mode where both endpoints understand IPSEC directly. As this is often not
        the case, it may be necessary to have only routers understand IPSEC, and have them do the work for the hosts behind them. 
        This is called 'tunnel mode'.
      </para>
      <para>
        Setting this up is a breeze. To tunnel all traffic to 130.161.0.0/16 from 10.0.0.216 via 10.0.0.11, we issue the following on
        10.0.0.216:
<screen>
#!/sbin/setkey -f
flush;
spdflush;

add 10.0.0.216 10.0.0.11 esp 34501
        -m tunnel
        -E 3des-cbc "123456789012123456789012";

spdadd 10.0.0.0/24 130.161.0.0/16 any -P out ipsec
           esp/tunnel/10.0.0.216-10.0.0.11/require;
</screen>
        Note the '-m tunnel', it is vitally important! This first configures an ESP encryption SA between our tunnel endpoints,
        10.0.0.216 and 10.0.0.11. 
      </para>
      <para>
        Next the actual tunnel is configured. It instructs the kernel to encrypt all traffic it has to route from 10.0.0.0/24 to
        130.161.0.0. Furthermore, this traffic then has to be shipped to 10.0.0.11.
      </para>
      <para>
        10.0.0.11 also needs some configuration:
<screen>
#!/sbin/setkey -f
flush;
spdflush;

add 10.0.0.216 10.0.0.11 esp 34501
        -m tunnel
        -E 3des-cbc "123456789012123456789012";

spdadd 10.0.0.0/24 130.161.0.0/16 any -P in ipsec
           esp/tunnel/10.0.0.216-10.0.0.11/require;
</screen>
        Note that this is exactly identical, except for the change from '-P out' to '-P in'. As with earlier examples,
        we've now only configured traffic going one way. Completing the other half of the tunnel is left as an
        exercise for the reader.
      </para>
      <para>
        Another name for this setup is 'proxy ESP', which is somewhat clearer.
      </para>
      <para>
        <note>
          <para>
            The IPSEC tunnel needs to have IP Forwarding enabled in the kernel!
          </para>
        </note>
      </para>
    </sect1>
    <sect1 id="lartc.ipsec.other"><title>Other IPSEC software</title>
      <para>
        Thomas Walpuski reports that he wrote a patch to make OpenBSD isakpmd work with Linux 2.5 IPSEC.
Furthermore, the main isakpmd CVS repository now contains this code!
        Some notes are <ulink
url="http://bender.thinknerd.de/~thomas/IPsec/isakmpd-linux.html">on his page</ulink>.
      </para>
      <para>

        isakpmd is quite different from racoon mentioned above but many
        people like it. It can be found <ulink
url="http://www.openbsd.org/cgi-bin/cvsweb/src/sbin/isakmpd/">here</ulink>.
Read more about OpenBSD CVS <ulink
url="http://www.openbsd.org/anoncvs.html">here</ulink>. Thomas also made a
<ulink
url="http://bender.thinknerd.de/~thomas/IPsec/isakmpd.tgz">tarball</ulink>
available for those uncomfortable with CVS or patch.

      </para>
      <para>
        Furthermore, there are patches to make the FreeS/WAN userspace tools
work with the native Linux 2.5 IPSEC, you can find them <ulink
url="http://gondor.apana.org.au/~herbert/freeswan/">here</ulink>.
      </para>
    </sect1>
    <sect1 id="lartc.ipsec.interop"><title>IPSEC interoperation with other systems</title>
      <para>
        FIXME: Write this
      </para>
      <sect2 id="lartc.ipsec.interop.win32"><title>Windows</title>
        <para>
        Andreas Jellinghaus &lt;aj@dungeon.inka.de&gt; reports: "win2k: it works. pre_shared key with ip address for authentication (I don't
think windows supports fqdn or userfqdn strings).  Certificates should also work, didn't
try.".

        </para>
      </sect2>

      <sect2 id="lartc.ipsec.interop.checkpoint"><title> Check Point VPN-1
NG</title>
        <para>
        Peter Bieringer reports: 
<screen>
Here are some results (tunnel mode only tested, auth=SHA1):

DES:     ok 
3DES:    ok 
AES-128: ok 
AES-192: not supported by CP VPN-1
AES-256: ok 
CAST* :  not supported by used Linux kernel

Tested version: FP4 aka R54 aka w/AI
</screen>
        </para>
        <para>
        More information <ulink
url="http://www.fw-1.de/aerasec/ng/vpn-racoon/CP-VPN1-NG-Linux-racoon.html">here</ulink>.
        </para>
      </sect2>
    </sect1>

  </chapter>

<chapter id="lartc.multicast">
<Title>Multicast routing</Title>

<Para>
FIXME: Editor Vacancy!
</Para>

<Para>
The Multicast-HOWTO is ancient (relatively-speaking) and may be inaccurate
or misleading in places, for that reason.
</Para>

<Para>
Before you can do any multicast routing, you need to configure the Linux
kernel to support the type of multicast routing you want to do. This, in
turn, requires you to decide what type of multicast routing you expect to
be using. There are essentially four "common" types - DVMRP (the Multicast
version of the RIP unicast protocol), MOSPF (the same, but for OSPF), PIM-SM
("Protocol Independent Multicasting - Sparse Mode", which assumes that users
of any multicast group are spread out, rather than clumped) and PIM-DM (the
same, but "Dense Mode", which assumes that there will be significant clumps
of users of the same multicast group).
</Para>

<Para>
In the Linux kernel, you will notice that these options don't appear. This is
because the protocol itself is handled by a routing application, such as
Zebra, mrouted, or pimd. However, you still have to have a good idea of which
you're going to use, to select the right options in the kernel.
</Para>

<Para>
For all multicast routing, you will definitely need to enable "multicasting"
and "multicast routing". For DVMRP and MOSPF, this is sufficient. If you are
going to use PIM, you must also enable PIMv1 or PIMv2, depending on whether
the network you are connecting to uses version 1 or 2 of the PIM protocol.
</Para>

<Para>
Once you have all that sorted out, and your new Linux kernel compiled, you
will see that the IP protocols listed, at boot time, now include IGMP. This
is a protocol for managing multicast groups. At the time of writing, Linux
supports IGMP versions 1 and 2 only, although version 3 does exist and has
been documented. This doesn't really affect us that much, as IGMPv3 is still
new enough that the extra capabilities of IGMPv3 aren't going to be that
much use. Because IGMP deals with groups, only the features present in the
simplest version of IGMP over the entire group are going to be used. For the
most part, that will be IGMPv2, although IGMPv1 is sill going to be
encountered.
</Para>

<Para>
So far, so good. We've enabled multicasting. Now, we have to tell the Linux
kernel to actually do something with it, so we can start routing. This means
adding the Multicast virtual network to the router table:
</Para>

<Para>
ip route add 224.0.0.0/4 dev eth0
</Para>

<Para>
(Assuming, of course, that you're multicasting over eth0! Substitute the
device of your choice, for this.)
</Para>

<Para>
Now, tell Linux to forward packets...
</Para>

<Para>
echo 1 &#62; /proc/sys/net/ipv4/ip_forward
</Para>

<Para>
At this point, you may be wondering if this is ever going to do anything. So,
to test our connection, we ping the default group, 224.0.0.1, to see if anyone
is alive. All machines on your LAN with multicasting enabled <Emphasis>should</Emphasis>
respond, but nothing else. You'll notice that none of the machines that
respond have an IP address of 224.0.0.1. What a surprise! :) This is a group
address (a "broadcast" to subscribers), and all members of the group will
respond with their own address, not the group address.
</Para>

<Para>
ping -c 2 224.0.0.1
</Para>

<Para>
At this point, you're ready to do actual multicast routing. Well, assuming
that you have two networks to route between.
</Para>

<Para>
(To Be Continued!)
</Para>

</chapter>

<chapter id="lartc.qdisc">
<Title>Queueing Disciplines for Bandwidth Management</Title>

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

<Para>
Linux even goes far beyond what Frame and ATM provide. 
</Para>

<Para>Just to prevent confusion, <command>tc</command> uses the following 
rules for bandwith specification:
 
<literallayout class='monospaced'>
mbps = 1024 kbps = 1024 * 1024 bps =&#62; byte/s
mbit = 1024 kbit =&#62; kilo bit/s.
mb = 1024 kb = 1024 * 1024 b =&#62; byte
mbit = 1024 kbit =&#62; kilo bit.
</literallayout>

Internally, the number is stored in bps and b.
</Para>

<Para>But when <command>tc</command> prints the rate, it uses following :
</Para>

<literallayout class='monospaced'>
1Mbit = 1024 Kbit = 1024 * 1024 bps =&#62; byte/s
</literallayout>

<Sect1 id="lartc.qdisc.explain">
  <Title>Queues and Queueing Disciplines explained</Title>

<Para>
With queueing we determine the way in which data is <Emphasis>SENT</Emphasis>.
It is important to realise that we can only shape data that we transmit.
</Para>

<Para>
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.
</Para>

<Para>
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. In fact it is a bit smarter than this, but
more about that later.
</Para>

<Para>
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 :-)
</Para>

<Para>
If you have a router and wish to prevent certain hosts within your network
from downloading too fast, you need to do your shaping on the *inner* interface
of your router, the one that sends data to your own computers.
</Para>

<Para>
You also have to be sure you are controlling the bottleneck of the link.
If you have a 100Mbit NIC and you have a router that has a 256kbit link,
you have to make sure you are not sending more data than your router can
handle.  Otherwise, it will be the router who is controlling the link and
shaping the available bandwith. We need to 'own the queue' so to speak, and
be the slowest link in the chain. Luckily this is easily possible.
</Para>

</Sect1>

<Sect1 id="lartc.qdisc.classless">
  <Title>Simple, classless Queueing Disciplines</Title>

<Para>
As said, with queueing disciplines, we change the way data is sent.
Classless queueing disciplines are those that, by and large accept data and
only reschedule, delay or drop it.
</Para>

<Para>
These can be used to shape traffic for an entire interface, without any
subdivisions. It is vital that you understand this part of queueing before
we go on the classful qdisc-containing-qdiscs!
</Para>

<Para>
By far the most widely used discipline is the pfifo_fast qdisc - this is the
default. This also explains why these advanced features are so robust. They
are nothing more than 'just another queue'.
</Para>

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

<Sect2>
<Title>pfifo_fast</Title>

<Para>
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.
</Para>

<Para>
The kernel honors the so called Type of Service flag of packets, and takes
care to insert 'minimum delay' packets in band 0. 
</Para>

<Para>
Do not confuse this classless simple qdisc with the classful PRIO one!
Although they behave similarly, pfifo_fast is classless and you cannot add
other qdiscs to it with the tc command.
</Para>

<Sect3>
<Title>Parameters &amp; usage</Title>

<Para>
You can't configure the pfifo_fast qdisc as it is the hardwired default.
This is how it is configured by default:
<VariableList>

<VarListEntry>
<Term>priomap</Term>
<ListItem>
<Para>
Determines how packet priorities, as assigned by the kernel, map to bands.
Mapping occurs based on the TOS octet of the packet, which looks like this:
</Para>

<Para>

<Screen>
   0     1     2     3     4     5     6     7
+-----+-----+-----+-----+-----+-----+-----+-----+
|                 |                       |     |
|   PRECEDENCE    |          TOS          | MBZ |
|                 |                       |     |
+-----+-----+-----+-----+-----+-----+-----+-----+
</Screen>

</Para>

<Para>
The four TOS bits (the 'TOS field') are defined as:

<Screen>
Binary Decimcal  Meaning
-----------------------------------------
1000   8         Minimize delay (md)
0100   4         Maximize throughput (mt)
0010   2         Maximize reliability (mr)
0001   1         Minimize monetary cost (mmc)
0000   0         Normal Service
</Screen>

</Para>

<Para>
As there is 1 bit to the right of these four bits, the actual value of the
TOS field is double the value of the TOS bits. Tcpdump -v -v shows you the
value of the entire TOS field, not just the four bits. It is the value you
see in the first column of this table:
</Para>

<Para>

<Screen>
TOS     Bits  Means                    Linux Priority    Band
------------------------------------------------------------
0x0     0     Normal Service           0 Best Effort     1
0x2     1     Minimize Monetary Cost   1 Filler          2
0x4     2     Maximize Reliability     0 Best Effort     1
0x6     3     mmc+mr                   0 Best Effort     1
0x8     4     Maximize Throughput      2 Bulk            2
0xa     5     mmc+mt                   2 Bulk            2
0xc     6     mr+mt                    2 Bulk            2
0xe     7     mmc+mr+mt                2 Bulk            2
0x10    8     Minimize Delay           6 Interactive     0
0x12    9     mmc+md                   6 Interactive     0
0x14    10    mr+md                    6 Interactive     0
0x16    11    mmc+mr+md                6 Interactive     0
0x18    12    mt+md                    4 Int. Bulk       1
0x1a    13    mmc+mt+md                4 Int. Bulk       1
0x1c    14    mr+mt+md                 4 Int. Bulk       1
0x1e    15    mmc+mr+mt+md             4 Int. Bulk       1
</Screen>

</Para>

<Para>
Lots of numbers. The second column contains the value of the relevant four
TOS bits, followed by their translated meaning. For example, 15 stands for a
packet wanting Minimal Monetary Cost, Maximum Reliability, Maximum
Throughput AND Minimum Delay. I would call this a 'Dutch Packet'.
</Para>

<Para>
The fourth column lists the way the Linux kernel interprets the TOS bits, by
showing to which Priority they are mapped. 
</Para>

<Para>
The last column shows the result of the default priomap. On the command line,
the default priomap looks like this:

<Screen>
1, 2, 2, 2, 1, 2, 0, 0 , 1, 1, 1, 1, 1, 1, 1, 1
</Screen>

</Para>

<Para>
This means that priority 4, for example, gets mapped to band number 1. The
priomap also allows you to list higher priorities (&gt; 7) which do not
correspond to TOS mappings, but which are set by other means.
</Para>

<Para>
This table from RFC 1349 (read it for more details) tells you how
applications might very well set their TOS bits:

<Screen>
TELNET                   1000           (minimize delay)
FTP
        Control          1000           (minimize delay)
        Data             0100           (maximize throughput)

TFTP                     1000           (minimize delay)

SMTP 
        Command phase    1000           (minimize delay)
        DATA phase       0100           (maximize throughput)

Domain Name Service
        UDP Query        1000           (minimize delay)
        TCP Query        0000
        Zone Transfer    0100           (maximize throughput)

NNTP                     0001           (minimize monetary cost)

ICMP
        Errors           0000
        Requests         0000 (mostly)
        Responses        &#60;same as request&#62; (mostly)
</Screen>

</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>txqueuelen</Term>
<ListItem>
<Para>
The length of this queue is gleaned from the interface configuration, which
you can see and set with ifconfig and ip. To set the queue length to 10,
execute: ifconfig eth0 txqueuelen 10
</Para>

<Para>
You can't set this parameter with tc!
</Para></ListItem>
</VarListEntry>
</VariableList>
</Para>

</Sect3>

</Sect2>

<Sect2>
<Title>Token Bucket Filter</Title>

<Para>
The Token Bucket Filter (TBF) is a simple qdisc that only passes packets
arriving at a rate which is not exceeding some administratively set rate, but
with the possibility to allow short bursts in excess of this rate.
</Para>

<Para>
TBF is very precise, network- and processor friendly. It should be your
first choice if you simply want to slow an interface down!
</Para>

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

<Para>
Each arriving token collects one incoming data packet from the data queue
and is then deleted from the bucket. Associating this algorithm
with the two flows -- token and data, gives us three possible scenarios:
</Para>

<Para>

<ItemizedList>
<ListItem>

<Para>
 The data arrives in TBF at a rate that's <Emphasis>equal</Emphasis> to the rate
of incoming tokens. In this case each incoming packet has its matching token
and passes the queue without delay.

</Para>
</ListItem>
<ListItem>

<Para>
 The data arrives in TBF at a rate that's <Emphasis>smaller</Emphasis> than the
token rate. Only a part of the tokens are deleted at output of each data packet
that's sent out the queue, so the tokens accumulate, up to the bucket size.
The unused tokens can then be used to send data at a speed that's exceeding the
standard token rate, in case short data bursts occur.

</Para>
</ListItem>
<ListItem>

<Para>
 The data arrives in TBF at a rate <Emphasis>bigger</Emphasis> than the token rate.
This means that the bucket will soon be devoid of tokens, which causes the
TBF to throttle itself for a while. This is called an 'overlimit situation'.
If packets keep coming in, packets will start to get dropped.
</Para>
</ListItem>

</ItemizedList>

</Para>

<Para>
The last scenario is very important, because it allows to
administratively shape the bandwidth available to data that's passing
the filter.
</Para>

<Para>
The accumulation of tokens allows a short burst of overlimit data to be
still passed without loss, but any lasting overload will cause packets to be
constantly delayed, and then dropped.
</Para>

<Para>
Please note that in the actual implementation, tokens correspond to bytes,
not packets.
</Para>

<Sect3>
<Title>Parameters &amp; usage</Title>

<Para>
Even though you will probably not need to change them, tbf has some knobs
available. First the parameters that are always available:
<VariableList>

<VarListEntry>
<Term>limit or latency</Term>
<ListItem>
<Para>
Limit is the number of bytes that can be queued waiting for tokens to become
available. You can also specify this the other way around by setting the
latency parameter, which specifies the maximum amount of time a packet can
sit in the TBF. The latter calculation takes into account the size of the
bucket, the rate and possibly the peakrate (if set).
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>burst/buffer/maxburst</Term>
<ListItem>
<Para>
Size of the bucket, in bytes. This is the maximum amount of bytes that
tokens can be available for instantaneously. In general, larger shaping
rates require a larger buffer. For 10mbit/s on Intel, you need at least
10kbyte buffer if you want to reach your configured rate!
</Para>

<Para>
If your buffer is too small, packets may be dropped because more tokens
arrive per timer tick than fit in your bucket.
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>mpu</Term>
<ListItem>
<Para>
A zero-sized packet does not use zero bandwidth. For ethernet, no packet
uses less than 64 bytes. The Minimum Packet Unit determines the minimal
token usage for a packet.
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>rate</Term>
<ListItem>
<Para>
The speedknob. See remarks above about limits!
</Para></ListItem>
</VarListEntry>
</VariableList>
</Para>

<Para>
If the bucket contains tokens and is allowed to empty, by default it does so
at infinite speed. If this is unacceptable, use the following parameters:
</Para>

<Para>
<VariableList>

<VarListEntry>
<Term>peakrate</Term>
<ListItem>
<Para>
If tokens are available, and packets arrive, they are sent out immediately
by default, at 'lightspeed' so to speak. That may not be what you want,
especially if you have a large bucket. 
</Para>

<Para>
The peakrate can be used to specify how quickly the bucket is allowed to be
depleted. If doing everything by the book, this is achieved by releasing a
packet, and then wait just long enough, and release the next. We calculated
our waits so we send just at peakrate.
</Para>

<Para>
However, due to the default 10ms timer resolution of Unix, with 10.000 bits
average packets, we are limited to 1mbit/s of peakrate!
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>mtu/minburst</Term>
<ListItem>
<Para>
The 1mbit/s peakrate is not very useful if your regular rate is more than
that. A higher peakrate is possible by sending out more packets per
timertick, which effectively means that we create a second bucket!
</Para>

<Para>
This second bucket defaults to a single packet, which is not a bucket at
all.
</Para>

<Para>
To calculate the maximum possible peakrate, multiply the configured mtu by
100 (or more correctly, HZ, which is 100 on Intel, 1024 on Alpha).
</Para></ListItem>
</VarListEntry>
</VariableList>
</Para>

</Sect3>

<Sect3>
<Title>Sample configuration</Title>

<Para>
A simple but *very* useful configuration is this:

<Screen>
# tc qdisc add dev ppp0 root tbf rate 220kbit latency 50ms burst 1540
</Screen>

</Para>

<Para>
Ok, why is this useful? If you have a networking device with a large queue,
like a DSL modem or a cable modem, and you talk to it over a fast device,
like over an ethernet interface, you will find that uploading absolutely
destroys interactivity.
</Para>

<Para>
This is because uploading will fill the queue in the modem, which is
probably *huge* because this helps actually achieving good data throughput
uploading. But this is not what you want, you want to have the queue not too
big so interactivity remains and you can still do other stuff while sending
data.
</Para>

<Para>
The line above slows down sending to a rate that does not lead to a queue in
the modem - the queue will be in Linux, where we can control it to a limited
size.
</Para>

<Para>
Change 220kbit to your uplink's *actual* speed, minus a few percent. If you
have a really fast modem, raise 'burst' a bit. 
</Para>

</Sect3>

</Sect2>

<Sect2 id="lartc.sfq">
<Title>Stochastic Fairness Queueing</Title>

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

<Para>
The key word in SFQ is conversation (or flow), which mostly corresponds to a
TCP session or a UDP stream. Traffic is divided into a pretty large number
of FIFO queues, one for each conversation. Traffic is then sent in a round
robin fashion, giving each session the chance to send data in turn.
</Para>

<Para>
This leads to very fair behaviour and disallows any single conversation from
drowning out the rest. SFQ is called 'Stochastic' because it doesn't really
allocate a queue for each session, it has an algorithm which divides traffic
over a limited number of queues using a hashing algorithm. 
</Para>

<Para>
Because of the hash, multiple sessions might end up in the same bucket, which
would halve each session's chance of sending a packet, thus halving the
effective speed available. To prevent this situation from becoming
noticeable, SFQ changes its hashing algorithm quite often so that any two
colliding sessions will only do so for a small number of seconds.
</Para>

<Para>
It is important to note that SFQ is only useful in case your actual outgoing
interface is really full! If it isn't then there will be no queue on your
linux machine and hence no effect. Later on we will describe how to combine
SFQ with other qdiscs to get a best-of-both worlds situation.
</Para>

<Para>
Specifically, setting SFQ on the ethernet interface heading to your
cable modem or DSL router is pointless without further shaping!
</Para>

<Sect3>
<Title>Parameters &amp; usage</Title>

<Para>
The SFQ is pretty much self tuning:
<VariableList>

<VarListEntry>
<Term>perturb</Term>
<ListItem>
<Para>
Reconfigure hashing once this many seconds. If unset, hash will never be
reconfigured. Not recommended. 10 seconds is probably a good value.
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>quantum</Term>
<ListItem>
<Para>
Amount of bytes a stream is allowed to dequeue before the next queue gets a
turn. Defaults to 1 maximum sized packet (MTU-sized). Do not set below the
MTU!
</Para></ListItem>
</VarListEntry>
<VarListEntry>
 <Term>limit</Term>
 <ListItem>
   <Para>
   The total number of packets that will be queued by this SFQ (after that it
   starts dropping them).
   </Para>
 </ListItem>
</VarListEntry>
</VariableList>
</Para>

</Sect3>

<Sect3>
<Title>Sample configuration</Title>

<Para>
If you have a device which has identical link speed and actual available
rate, like a phone modem, this configuration will help promote fairness:

<Screen>
# tc qdisc add dev ppp0 root sfq perturb 10
# tc -s -d qdisc ls
qdisc sfq 800c: dev ppp0 quantum 1514b limit 128p flows 128/1024 perturb 10sec 
 Sent 4812 bytes 62 pkts (dropped 0, overlimits 0) 
</Screen>

</Para>

<Para>
The number 800c: is the automatically assigned handle number, limit means
that 128 packets can wait in this queue. There are 1024 hashbuckets
available for accounting, of which 128 can be active at a time (no more
packets fit in the queue!) Once every 10 seconds, the hashes are
reconfigured.
</Para>

</Sect3>

</Sect2>

</Sect1>

<Sect1 id="lartc.qdisc.advice">
  <Title>Advice for when to use which queue</Title>

<Para>
Summarizing, these are the simple queues that actually manage traffic by
reordering, slowing or dropping packets.
</Para>

<Para>
The following tips may help in choosing which queue to use. It mentions some
qdiscs described in the
<citetitle><xref linkend="lartc.adv-qdisc"></citetitle> chapter.
</Para>

<ItemizedList>
<ListItem>
<Para>
To purely slow down outgoing traffic, use the Token Bucket Filter. Works up
to huge bandwidths, if you scale the bucket.
</Para>
</ListItem>
<ListItem>

<Para>
If your link is truly full and you want to make sure that no single session
can dominate your outgoing bandwidth, use Stochastical Fairness Queueing.
</Para>
</ListItem>
<ListItem>

<Para>
If you have a big backbone and know what you are doing, consider Random
Early Drop (see Advanced chapter).
</Para>
</ListItem>
<ListItem>

<Para>
To 'shape' incoming traffic which you are not forwarding, use the Ingress
Policer. Incoming shaping is called 'policing', by the way, not 'shaping'.  
</Para>
</ListItem>
<ListItem>

<Para>
If you *are* forwarding it, use a TBF on the interface you are forwarding
the data to. Unless you want to shape traffic that may go out over several
interfaces, in which case the only common factor is the incoming interface.
In that case use the Ingress Policer.
</Para>
</ListItem>
<ListItem>

<Para>
If you don't want to shape, but only want to see if your interface is so
loaded that it has to queue, use the pfifo queue (not pfifo_fast). It lacks
internal bands but does account the size of its backlog.
</Para>
</ListItem>
<ListItem>
<Para>
Finally - you can also do <quote>social shaping</quote>.
You may not always be able to use technology to achieve what you want.
Users experience technical constraints as hostile.
A kind word may also help with getting your bandwidth to be divided right!
</Para>
</ListItem>
</ItemizedList>

</Sect1>

<Sect1 id="lartc.qdisc.terminology">
  <Title>Terminology</Title>

<Para>
To properly understand more complicated configurations it is necessary to
explain a few concepts first. Because of the complexity and the relative
youth of the subject, a lot of different words are used when people in fact
mean the same thing.
</Para>

<Para>
The following is loosely based on 
<filename>draft-ietf-diffserv-model-06.txt</filename>,
<citetitle>An Informal Management Model for Diffserv Routers</citetitle>.
It can currently be found at 
<ulink url="http://www.ietf.org/internet-drafts/draft-ietf-diffserv-model-06.txt">
  http://www.ietf.org/internet-drafts/draft-ietf-diffserv-model-06.txt
</ulink>.
</Para>

<Para>
Read it for the strict definitions of the terms used.
<VariableList>

<VarListEntry>
<Term>Queueing Discipline (qdisc)</Term>
<ListItem>
<Para>
An algorithm that manages the queue of a device, either incoming (ingress)
or outgoing (egress).
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>root qdisc</Term>
<ListItem>
<Para>
The root qdisc is the qdisc attached to the device.
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>Classless qdisc</Term>
<ListItem>
<Para>
A qdisc with no configurable internal subdivisions. 
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>Classful qdisc</Term>
<ListItem>
<Para>
A classful qdisc contains multiple classes. Some of these classes contains a
further qdisc, which may again be classful, but need not be. According to
the strict definition, pfifo_fast *is* classful, because it contains three
bands which are, in fact, classes. However, from the user's configuration
perspective, it is classless as the classes can't be touched with the tc
tool. 
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>Classes</Term>
<ListItem>
<Para>
A classful qdisc may have many classes, each of which is internal to the
qdisc.  A class, in turn, may have several classes added to it.  So a class
can have a qdisc as parent or an other class.

A leaf class is a class with no child classes.  This class has 1 qdisc attached
to it.  This qdisc is responsible to send the data from that class.  When
you create a class, a fifo qdisc is attached to it.  When you add a child class,
this qdisc is removed.
For a leaf class, this fifo qdisc can be replaced with
an other more suitable qdisc.  You can even replace this fifo qdisc with a
classful qdisc so you can add extra classes.
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>Classifier</Term>
<ListItem>
<Para>
Each classful qdisc needs to determine to which class it needs to send a
packet. This is done using the classifier.
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>Filter</Term>
<ListItem>
<Para>
Classification can be performed using filters. A filter contains a number of
conditions which if matched, make the filter match.
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>Scheduling</Term>
<ListItem>
<Para>
A qdisc may, with the help of a classifier, decide that some packets need to
go out earlier than others. This process is called Scheduling, and is
performed for example by the pfifo_fast qdisc mentioned earlier. Scheduling
is also called 'reordering', but this is confusing.
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>Shaping</Term>
<ListItem>
<Para>
The process of delaying packets before they go out to make traffic confirm
to a configured maximum rate. Shaping is performed on egress. Colloquially, 
dropping packets to slow traffic down is also often called Shaping.
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>Policing</Term>
<ListItem>
<Para>
Delaying or dropping packets in order to make traffic stay below a
configured bandwidth. In Linux, policing can only drop a packet and not
delay it - there is no 'ingress queue'.
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>Work-Conserving</Term>
<ListItem>
<Para>
A work-conserving qdisc always delivers a packet if one is available. In
other words, it never delays a packet if the network adaptor is ready to
send one (in the case of an egress qdisc).
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>non-Work-Conserving</Term>
<ListItem>
<Para>
Some queues, like for example the Token Bucket Filter, may need to hold on
to a packet for a certain time in order to limit the bandwidth. This means
that they sometimes refuse to pass a packet, even though they have one
available.
</Para></ListItem>
</VarListEntry>
</VariableList>
</Para>

<Para>
Now that we have our terminology straight, let's see where all these things
are.
</Para>

<Para>

<Screen width="80">
                Userspace programs
                     ^
                     |
     +---------------+-----------------------------------------+
     |               Y                                         |
     |    -------&#62; IP Stack                                    |
     |   |              |                                      |
     |   |              Y                                      |
     |   |              Y                                      |
     |   ^              |                                      |
     |   |  / ----------&#62; Forwarding -&#62;                        |
     |   ^ /                           |                       |
     |   |/                            Y                       |
     |   |                             |                       |
     |   ^                             Y          /-qdisc1-\   |
     |   |                            Egress     /--qdisc2--\  |
  ---&#62;-&#62;Ingress                       Classifier ---qdisc3---- | -&#62;
     |   Qdisc                                   \__qdisc4__/  |
     |                                            \-qdiscN_/   |
     |                                                         |
     +----------------------------------------------------------+
</Screen>

Thanks to Jamal Hadi Salim for this ASCII representation.
</Para>

<Para>
The big block represents the kernel. The leftmost arrow represents traffic
entering your machine from the network. It is then fed to the Ingress
Qdisc which may apply Filters to a packet, and decide to drop it. This
is called 'Policing'.
</Para>

<Para>
This happens at a very early stage, before it has seen a lot of the kernel.
It is therefore a very good place to drop traffic very early, without
consuming a lot of CPU power.
</Para>

<Para>
If the packet is allowed to continue, it may be destined for a local
application, in which case it enters the IP stack in order to be processed,
and handed over to a userspace program. The packet may also be forwarded
without entering an application, in which case it is destined for egress.
Userspace programs may also deliver data, which is then examined and
forwarded to the Egress Classifier.
</Para>

<Para>
There it is investigated and enqueued to any of a number of qdiscs. In the
unconfigured default case, there is only one egress qdisc installed, the
pfifo_fast, which always receives the packet. This is called 'enqueueing'.
</Para>

<Para>
The packet now sits in the qdisc, waiting for the kernel to ask for
it for transmission over the network interface. This is called 'dequeueing'.
</Para>

<Para>
This picture also holds in case there is only one network adaptor - the
arrows entering and leaving the kernel should not be taken too literally.
Each network adaptor has both ingress and egress hooks.
</Para>

</Sect1>

<Sect1 id="lartc.qdisc.classful">
  <Title>Classful Queueing Disciplines</Title>

<Para>
Classful qdiscs are very useful if you have different kinds of traffic which
should have differing treatment. One of the classful qdiscs is called 'CBQ',
'Class Based Queueing' and it is so widely mentioned that people identify
queueing with classes solely with CBQ, but this is not the case.
</Para>

<Para>
CBQ is merely the oldest kid on the block - and also the most complex one.
It may not always do what you want.  This may come as something of a shock
to many who fell for the 'sendmail effect', which teaches us that any
complex technology which doesn't come with documentation must be the best
available.
</Para>

<Para>
More about CBQ and its alternatives shortly.
</Para>

<Sect2>
<Title>Flow within classful qdiscs &amp; classes</Title>

<Para>
When traffic enters a classful qdisc, it needs to be sent to any of the
classes within - it needs to be 'classified'. To determine what to do with a
packet, the so called 'filters' are consulted. It is important to know that
the filters are called from within a qdisc, and not the other way around!
</Para>

<Para>
The filters attached to that qdisc then return with a decision, and the
qdisc uses this to enqueue the packet into one of the classes. Each subclass
may try other filters to see if further instructions apply. If not, the
class enqueues the packet to the qdisc it contains.
</Para>

<Para>
Besides containing other qdiscs, most classful qdiscs also perform shaping.
This is useful to perform both packet scheduling (with SFQ, for example) and
rate control. You need this in cases where you have a high speed
interface (for example, ethernet) to a slower device (a cable modem).
</Para>

<Para>
If you were only to run SFQ, nothing would happen, as packets enter &amp;
leave your router without delay: the output interface is far faster than
your actual link speed. There is no queue to schedule then.
</Para>

</Sect2>

<Sect2>
<Title>The qdisc family: roots, handles, siblings and parents</Title>

<Para>
Each interface has one egress 'root qdisc'. By default, it is the earlier mentioned
classless pfifo_fast queueing discipline. Each qdisc and class is assigned a
handle, which can be used by later configuration statements to refer to that
qdisc. Besides an egress qdisc, an interface may also have an ingress qdisc ,
which polices traffic coming in.
</Para>

<Para>
The handles of these qdiscs consist of two parts, a major number and a minor
number : &lt;major&gt;:&lt;minor&gt;. It is customary to name the root qdisc '1:', which
is equal to '1:0'.  The minor number of a qdisc is always 0. 
</Para>

<Para>
Classes need to have the same major number as their parent.  This major number
must be unique within a egress or ingress setup.  The minor number must be
unique within a qdisc and his classes.
</Para>

<Sect3>
<Title>How filters are used to classify traffic </Title>

<Para>
Recapping, a typical hierarchy might look like this:

<Screen>
                     1:   root qdisc
                      |
                     1:1    child class
                   /  |  \
                  /   |   \
                 /    |    \
                 /    |    \
              1:10  1:11  1:12   child classes
               |      |     | 
               |     11:    |    leaf class
               |            | 
               10:         12:   qdisc
              /   \       /   \
           10:1  10:2   12:1  12:2   leaf classes
</Screen>

</Para>

<Para>
But don't let this tree fool you! You should *not* imagine the kernel to be
at the apex of the tree and the network below, that is just not the case.
Packets get enqueued and dequeued at the root qdisc, which is the only thing
the kernel talks to. 
</Para>

<Para>
A packet might get classified in a chain like this:
</Para>

<Para>
1: -&#62; 1:1 -&#62; 1:12 -&#62; 12: -&#62; 12:2
</Para>

<Para>
The packet now resides in a queue in a qdisc attached to class 12:2. In this
example, a filter was attached to each 'node' in the tree, each choosing a
branch to take next. This can make sense. However, this is also possible:
</Para>

<Para>
1: -&#62; 12:2
</Para>

<Para>
In this case, a filter attached to the root decided to send the packet
directly to 12:2.
</Para>

</Sect3>

<Sect3>
<Title>How packets are dequeued to the hardware</Title>

<Para>
When the kernel decides that it needs to extract packets to send to the
interface, the root qdisc 1: gets a dequeue request, which is passed to
1:1, which is in turn passed to 10:, 11: and 12:, each of which queries its
siblings, and tries to dequeue() from them. In this case, the kernel needs to
walk the entire tree, because only 12:2 contains a packet. 
</Para>

<Para>
In short, nested classes ONLY talk to their parent qdiscs, never to an
interface. Only the root qdisc gets dequeued by the kernel!
</Para>

<Para>
The upshot of this is that classes never get dequeued faster than their
parents allow. And this is exactly what we want: this way we can have SFQ in
an inner class, which doesn't do any shaping, only scheduling, and have a
shaping outer qdisc, which does the shaping.
</Para>

</Sect3>

</Sect2>

<Sect2>
<Title>The PRIO qdisc</Title>

<Para>
The PRIO qdisc doesn't actually shape, it only subdivides traffic based on
how you configured your filters. You can consider the PRIO qdisc a kind
of pfifo_fast on steroids, whereby each band is a separate class instead of
a simple FIFO.
</Para>

<Para>
When a packet is enqueued to the PRIO qdisc, a class is chosen based on the
filter commands you gave. By default, three classes are created. These
classes by default contain pure FIFO qdiscs with no internal
structure, but you can replace these by any qdisc you have available.
</Para>

<Para>
Whenever a packet needs to be dequeued, class :1 is tried first. Higher
classes are only used if lower bands all did not give up a packet.
</Para>

<Para>
This qdisc is very useful in case you want to prioritize certain kinds of
traffic without using only TOS-flags but using all the power of the tc
filters. You can also add an other qdisc to the 3 predefined classes,
whereas pfifo_fast is limited to simple fifo qdiscs.
</Para>

<Para>
Because it doesn't actually shape, the same warning as for SFQ holds: either
use it only if your physical link is really full or wrap it inside a
classful qdisc that does shape. The latter holds for almost all cable modems
and DSL devices.
</Para>

<Para>
In formal words, the PRIO qdisc is a Work-Conserving scheduler.
</Para>

<Sect3>
<Title>PRIO parameters &amp; usage</Title>

<Para>
The following parameters are recognized by tc:
<VariableList>

<VarListEntry>
<Term>bands</Term>
<ListItem>
<Para>
Number of bands to create. Each band is in fact a class. If you change this
number, you must also change:
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>priomap</Term>
<ListItem>
<Para>
If you do not provide tc filters to classify traffic, the PRIO qdisc looks
at the TC_PRIO priority to decide how to enqueue traffic. 
</Para>

<Para>
This works just like with the pfifo_fast qdisc mentioned earlier, see there
for lots of detail.
</Para></ListItem>
</VarListEntry>
</VariableList>
The bands are classes, and are called major:1 to major:3 by default, so if
your PRIO qdisc is called 12:, tc filter traffic to 12:1 to grant it more
priority.
</Para>

<Para>
Reiterating, band 0 goes to minor number 1! Band 1 to minor number 2, etc.
</Para>

</Sect3>

<Sect3>
<Title>Sample configuration</Title>

<Para>
We will create this tree:

<Screen>
          1:   root qdisc
         / | \ 
       /   |   \
       /   |   \
     1:1  1:2  1:3    classes
      |    |    |
     10:  20:  30:    qdiscs    qdiscs
     sfq  tbf  sfq
band  0    1    2
</Screen>

</Para>

<Para>
Bulk traffic will go to 30:, interactive traffic to 20: or 10:.
</Para>

<Para>
Command lines:

<Screen>
# tc qdisc add dev eth0 root handle 1: prio 
## This *instantly* creates classes 1:1, 1:2, 1:3
  
# tc qdisc add dev eth0 parent 1:1 handle 10: sfq
# tc qdisc add dev eth0 parent 1:2 handle 20: tbf rate 20kbit buffer 1600 limit 3000
# tc qdisc add dev eth0 parent 1:3 handle 30: sfq                                
</Screen>

</Para>

<Para>
Now let's see what we created:

<Screen>
# tc -s qdisc ls dev eth0 
qdisc sfq 30: quantum 1514b 
 Sent 0 bytes 0 pkts (dropped 0, overlimits 0) 

 qdisc tbf 20: rate 20Kbit burst 1599b lat 667.6ms 
 Sent 0 bytes 0 pkts (dropped 0, overlimits 0) 

 qdisc sfq 10: quantum 1514b 
 Sent 132 bytes 2 pkts (dropped 0, overlimits 0) 

 qdisc prio 1: bands 3 priomap  1 2 2 2 1 2 0 0 1 1 1 1 1 1 1 1
 Sent 174 bytes 3 pkts (dropped 0, overlimits 0) 
</Screen>

As you can see, band 0 has already had some traffic, and one packet was sent
while running this command!
</Para>

<Para>
We now do some bulk data transfer with a tool that properly sets TOS flags,
and take another look:

<Screen>
# scp tc ahu@10.0.0.11:./
ahu@10.0.0.11's password: 
tc                   100% |*****************************|   353 KB    00:00    
# tc -s qdisc ls dev eth0
qdisc sfq 30: quantum 1514b 
 Sent 384228 bytes 274 pkts (dropped 0, overlimits 0) 

 qdisc tbf 20: rate 20Kbit burst 1599b lat 667.6ms 
 Sent 2640 bytes 20 pkts (dropped 0, overlimits 0) 

 qdisc sfq 10: quantum 1514b 
 Sent 2230 bytes 31 pkts (dropped 0, overlimits 0) 

 qdisc prio 1: bands 3 priomap  1 2 2 2 1 2 0 0 1 1 1 1 1 1 1 1
 Sent 389140 bytes 326 pkts (dropped 0, overlimits 0) 
</Screen>

As you can see, all traffic went to handle 30:, which is the lowest priority
band, just as intended. Now to verify that interactive traffic goes to
higher bands, we create some interactive traffic:
</Para>

<Para>

<Screen>
# tc -s qdisc ls dev eth0
qdisc sfq 30: quantum 1514b 
 Sent 384228 bytes 274 pkts (dropped 0, overlimits 0) 

 qdisc tbf 20: rate 20Kbit burst 1599b lat 667.6ms 
 Sent 2640 bytes 20 pkts (dropped 0, overlimits 0) 

 qdisc sfq 10: quantum 1514b 
 Sent 14926 bytes 193 pkts (dropped 0, overlimits 0) 

 qdisc prio 1: bands 3 priomap  1 2 2 2 1 2 0 0 1 1 1 1 1 1 1 1
 Sent 401836 bytes 488 pkts (dropped 0, overlimits 0) 
</Screen>

</Para>

<Para>
It worked - all additional traffic has gone to 10:, which is our highest
priority qdisc. No traffic was sent to the lowest priority, which previously
received our entire scp.
</Para>

</Sect3>

</Sect2>

<Sect2>
<Title>The famous CBQ qdisc</Title>

<Para>
As said before, CBQ is the most complex qdisc available, the most hyped, the
least understood, and probably the trickiest one to get right. This is not
because the authors are evil or incompetent, far from it, it's just that the
CBQ algorithm isn't all that precise and doesn't really match the way Linux
works.
</Para>

<Para>
Besides being classful, CBQ is also a shaper and it is in that aspect that
it really doesn't work very well. It should work like this. If you try to
shape a 10mbit/s connection to 1mbit/s, the link should be idle 90% of the
time. If it isn't, we need to throttle so that it IS idle 90% of the time.
</Para>

<Para>
This is pretty hard to measure, so CBQ  instead derives the idle time from
the number of microseconds that elapse between requests from the hardware
layer for more data. Combined, this can be used to approximate how full or
empty the link is.<!--which is combined with which?-->
</Para>

<Para>
This is rather tortuous and doesn't always arrive at proper results. For
example, what if the actual link speed of an interface that is not really
able to transmit the full 100mbit/s of data, perhaps because of a badly
implemented driver? A PCMCIA network card will also never achieve 100mbit/s
because of the way the bus is designed - again, how do we calculate the idle
time?
</Para>

<Para>
It gets even worse if we consider not-quite-real network devices like PPP
over Ethernet or PPTP over TCP/IP. The effective bandwidth in that case is
probably determined by the efficiency of pipes to userspace - which is huge.
</Para>

<Para>
People who have done measurements discover that CBQ is not always very
accurate and sometimes completely misses the mark.
</Para>

<Para>
In many circumstances however it works well. With the documentation provided
here, you should be able to configure it to work well in most cases.
</Para>

<Sect3>
<Title>CBQ shaping in detail</Title>

<Para>
As said before, CBQ works by making sure that the link is idle just long
enough to bring down the real bandwidth to the configured rate. To do so, it
calculates the time that should pass between average packets. 
</Para>

<Para>
During operations, the effective idletime is measured using an exponential
weighted moving average (EWMA), which considers recent packets to be
exponentially more important than past ones. The UNIX loadaverage is
calculated in the same way.
</Para>

<Para>
The calculated idle time is subtracted from the EWMA measured one, the
resulting number is called 'avgidle'. A perfectly loaded link has an avgidle
of zero: packets arrive exactly once every calculated interval.  
</Para>

<Para>
An overloaded link has a negative avgidle and if it gets too negative, CBQ
shuts down for a while and is then 'overlimit'.
</Para>

<Para>
Conversely, an idle link might amass a huge avgidle, which would then allow
infinite bandwidths after a few hours of silence. To prevent this, avgidle is
capped at maxidle.
</Para>

<Para>
If overlimit, in theory, the CBQ could throttle itself for exactly the
amount of time that was calculated to pass between packets, and then pass
one packet, and throttle again. But see the 'minburst' parameter below.
</Para>

<Para>
These are parameters you can specify in order to configure shaping:
<VariableList>

<VarListEntry>
<Term>avpkt</Term>
<ListItem>
<Para>
Average size of a packet, measured in bytes. Needed for calculating maxidle,
which is derived from maxburst, which is specified in packets.
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>bandwidth</Term>
<ListItem>
<Para>
The physical bandwidth of your device, needed for idle time
calculations.
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>cell</Term>
<ListItem>
<Para>
The time a packet takes to be transmitted over a device may grow in steps,
based on the packet size. An 800 and an 806 size packet may take just as long
to send, for example - this sets the granularity. Most often set to '8'.
Must be an integral power of two.
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>maxburst</Term>
<ListItem>
<Para>
This number of packets is used to calculate maxidle so that when avgidle is
at maxidle, this number of average packets can be burst before avgidle drops
to 0. Set it higher to be more tolerant of bursts. You can't set maxidle
directly, only via this parameter.
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>minburst</Term>
<ListItem>
<Para>
As mentioned before, CBQ needs to throttle in case of overlimit. The ideal
solution is to do so for exactly the calculated idle time, and pass 1
packet. For Unix kernels, however, it is generally hard to schedule events
shorter than 10ms, so it is better to throttle for a longer period, and then
pass minburst packets in one go, and then sleep minburst times longer.
</Para>

<Para>
The time to wait is called the offtime. Higher values of minburst lead to
more accurate shaping in the long term, but to bigger bursts at millisecond
timescales.
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>minidle</Term>
<ListItem>
<Para>
If avgidle is below 0, we are overlimits and need to wait until avgidle will
be big enough to send one packet. To prevent a sudden burst from shutting
down the link for a prolonged period of time, avgidle is reset to minidle if
it gets too low.
</Para>

<Para>
Minidle is specified in negative microseconds, so 10 means that avgidle is
capped at -10us.
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>mpu</Term>
<ListItem>
<Para>
Minimum packet size - needed because even a zero size packet is padded
to 64 bytes on ethernet, and so takes a certain time to transmit. CBQ needs
to know this to accurately calculate the idle time.
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>rate</Term>
<ListItem>
<Para>
Desired rate of traffic leaving this qdisc - this is the 'speed knob'!
</Para></ListItem>
</VarListEntry>
</VariableList>
</Para>

<Para>
Internally, CBQ has a lot of fine tuning. For example, classes which are
known not to have data enqueued to them aren't queried. Overlimit classes
are penalized by lowering their effective priority. All very smart &amp;
complicated.
</Para>

</Sect3>

<Sect3>
<Title>CBQ classful behaviour</Title>

<Para>
Besides shaping, using the aforementioned idletime approximations, CBQ also
acts like the PRIO queue in the sense that classes can have differing
priorities and that lower priority numbers will be polled before the higher
priority ones.
</Para>

<Para>
Each time a packet is requested by the hardware layer to be sent out to the
network, a weighted round robin process ('WRR') starts, beginning with the
lower-numbered priority classes.
</Para>

<Para>
These are then grouped and queried if they have data available. If so, it is
returned. After a class has been allowed to dequeue a number of bytes, the
next class within that priority is tried.
</Para>

<Para>
The following parameters control the WRR process:
<VariableList>

<VarListEntry>
<Term>allot</Term>
<ListItem>
<Para>
When the outer CBQ is asked for a packet to send out on the interface, it
will try all inner qdiscs (in the classes) in turn, in order of 
the 'priority' parameter. Each time a class gets its turn, it can only send out
a limited amount of data. 'Allot' is the base unit of this amount. See 
the 'weight' parameter for more information.
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>prio</Term>
<ListItem>
<Para>
The CBQ can also act like the PRIO device. Inner classes with higher priority
are tried first and as long as they have traffic, other classes are not
polled for traffic.
</Para></ListItem>
</VarListEntry>
<!--It is rather confusing between high/low "priority" and
    "priorigy number" around here.
    How about using large/small for the latter?-->
<VarListEntry>
<Term>weight</Term>
<ListItem>
<Para>
Weight helps in the Weighted Round Robin process. Each class gets a chance
to send in turn. If you have classes with significantly more bandwidth than
other classes, it makes sense to allow them to send more data in one round
than the others.
</Para>

<Para>
A CBQ adds up all weights under a class, and normalizes them, so you can use
arbitrary numbers: only the ratios are important. People have been 
using 'rate/10' as a rule of thumb and it appears to work well. The renormalized
weight is multiplied by the 'allot' parameter to determine how much data can
be sent in one round. 
</Para></ListItem>
</VarListEntry>
</VariableList>
</Para>

<Para>
Please note that all classes within an CBQ hierarchy need to share the same
major number!
</Para>

</Sect3>

<Sect3>
<Title>CBQ parameters that determine link sharing &amp; borrowing</Title>

<Para>
Besides purely limiting certain kinds of traffic, it is also possible to
specify which classes can borrow capacity from other classes or, conversely,
lend out bandwidth.
</Para>

<Para>
<VariableList>

<VarListEntry>
<Term>Isolated/sharing</Term>
<ListItem>
<Para>
A class that is configured with 'isolated' will not lend out bandwidth to
sibling classes. Use this if you have competing or mutually-unfriendly
agencies on your link who do not want to give each other freebies.
</Para>

<Para>
The control program tc also knows about 'sharing', which is the reverse 
of 'isolated'.
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>bounded/borrow</Term>
<ListItem>
<Para>
A class can also be 'bounded', which means that it will not try to borrow
bandwidth from sibling classes. tc also knows about 'borrow', which is the
reverse of 'bounded'.
</Para></ListItem>
</VarListEntry>
</VariableList>
A typical situation might be where you have two agencies on your link which
are both 'isolated' and 'bounded', which means that they are really limited
to their assigned rate, and also won't allow each other to borrow.
</Para>

<Para>
Within such an agency class, there might be other classes which are allowed
to swap bandwidth.
</Para>

</Sect3>

<Sect3>
<Title>Sample configuration</Title>
<Screen>

               1:           root qdisc
               |
              1:1           child class
             /   \
            /     \
          1:3     1:4       leaf classes
           |       |
          30:     40:       qdiscs
         (sfq)   (sfq)
</Screen>

<Para>
This configuration limits webserver traffic to 5mbit and SMTP traffic to 3
mbit. Together, they may not get more than 6mbit. We have a 100mbit NIC and
the classes may borrow bandwidth from each other.

<Screen>
# tc qdisc add dev eth0 root handle 1:0 cbq bandwidth 100Mbit         \
  avpkt 1000 cell 8
# tc class add dev eth0 parent 1:0 classid 1:1 cbq bandwidth 100Mbit  \
  rate 6Mbit weight 0.6Mbit prio 8 allot 1514 cell 8 maxburst 20      \
  avpkt 1000 bounded
</Screen>

This part installs the root and the customary 1:1 class. The 1:1 class is
bounded, so the total bandwidth can't exceed 6mbit.
</Para>

<Para>
As said before, CBQ requires a *lot* of knobs. All parameters are explained
above, however. The corresponding HTB configuration is lots simpler.
</Para>

<Para>

<Screen>
# tc class add dev eth0 parent 1:1 classid 1:3 cbq bandwidth 100Mbit  \
  rate 5Mbit weight 0.5Mbit prio 5 allot 1514 cell 8 maxburst 20      \
  avpkt 1000                       
# tc class add dev eth0 parent 1:1 classid 1:4 cbq bandwidth 100Mbit  \
  rate 3Mbit weight 0.3Mbit prio 5 allot 1514 cell 8 maxburst 20      \
  avpkt 1000
</Screen>

</Para>

<Para>
These are our two leaf classes. Note how we scale the weight with the configured
rate. Both classes are not bounded, but they are connected to class 1:1
which is bounded.  So the sum of bandwith of the 2 classes will never be
more than 6mbit. The classids need to be within the same major number as
the parent qdisc, by the way!
</Para>

<Para>

<Screen>
# tc qdisc add dev eth0 parent 1:3 handle 30: sfq
# tc qdisc add dev eth0 parent 1:4 handle 40: sfq
</Screen>

</Para>

<Para>
Both classes have a FIFO qdisc by default.  But we replaced these with an SFQ
queue so each flow of data is treated equally.

<Screen>
# tc filter add dev eth0 parent 1:0 protocol ip prio 1 u32 match ip \
  sport 80 0xffff flowid 1:3
# tc filter add dev eth0 parent 1:0 protocol ip prio 1 u32 match ip \
  sport 25 0xffff flowid 1:4
</Screen>

</Para>

<Para>
These commands, attached directly to the root, send traffic to the right
qdiscs.
</Para>

<Para>
Note that we use 'tc class add' to CREATE classes within a qdisc, but that
we use 'tc qdisc add' to actually add qdiscs to these classes.
</Para>

<Para>
You may wonder what happens to traffic that is not classified by any of the
two rules. It appears that in this case, data will then be processed within
1:0, and be unlimited. 
</Para>

<Para>
If SMTP+web together try to exceed the set limit of 6mbit/s, bandwidth will
be divided according to the weight parameter, giving 5/8 of traffic to  the
webserver and 3/8 to the mail server.
</Para>

<Para>
With this configuration you can also say that webserver traffic will always
get at minimum 5/8 * 6 mbit = 3.75 mbit.
</Para>

</Sect3>

<Sect3>
<Title>Other CBQ parameters: split &amp; defmap</Title>

<Para>
As said before, a classful qdisc needs to call filters to determine
which class a packet will be enqueued to. 
</Para>

<Para>
Besides calling the filter, CBQ offers other options, defmap &amp; split.
This is pretty complicated to understand, and it is not vital. But as this
is the only known place where defmap &amp; split are properly explained, I'm
doing my best. 
</Para>

<Para>
As you will often want to filter on the Type of Service field only, a special
syntax is provided. Whenever the CBQ needs to figure out where a packet
needs to be enqueued, it checks if this node is a 'split node'. If so, one
of the sub-qdiscs has indicated that it wishes to receive all packets with
a certain configured priority, as might be derived from the TOS field, or
socket options set by applications.
</Para>

<Para>
The packets' priority bits are and-ed with the defmap field to see if a match
exists. In other words, this is a short-hand way of creating a very fast
filter, which only matches certain priorities. A defmap of ff (hex) will
match everything, a map of 0 nothing. A sample configuration may help make
things clearer:
</Para>

<Para>

<Screen>
# tc qdisc add dev eth1 root handle 1: cbq bandwidth 10Mbit allot 1514 \
  cell 8 avpkt 1000 mpu 64
 
# tc class add dev eth1 parent 1:0 classid 1:1 cbq bandwidth 10Mbit    \
  rate 10Mbit allot 1514 cell 8 weight 1Mbit prio 8 maxburst 20        \
  avpkt 1000
</Screen>

Standard CBQ preamble. I never get used to the sheer amount of numbers
required!
</Para>

<Para>
Defmap refers to TC_PRIO bits, which are defined as follows:
</Para>

<Para>

<Screen>
TC_PRIO..          Num  Corresponds to TOS
-------------------------------------------------
BESTEFFORT         0    Maximize Reliablity        
FILLER             1    Minimize Cost              
BULK               2    Maximize Throughput (0x8)  
INTERACTIVE_BULK   4                               
INTERACTIVE        6    Minimize Delay (0x10)      
CONTROL            7                               
</Screen>

</Para>

<Para>
The TC_PRIO.. number corresponds to bits, counted from the right. See the
pfifo_fast section for more details how TOS bits are converted to
priorities.
</Para>

<Para>
Now the interactive and the bulk classes:
</Para>

<Para>

<Screen>
# tc class add dev eth1 parent 1:1 classid 1:2 cbq bandwidth 10Mbit     \
  rate 1Mbit allot 1514 cell 8 weight 100Kbit prio 3 maxburst 20        \
  avpkt 1000 split 1:0 defmap c0

# tc class add dev eth1 parent 1:1 classid 1:3 cbq bandwidth 10Mbit     \
  rate 8Mbit allot 1514 cell 8 weight 800Kbit prio 7 maxburst 20        \
  avpkt 1000 split 1:0 defmap 3f
</Screen>

</Para>

<Para>
The 'split qdisc' is 1:0, which is where the choice will be made. C0 is
binary for 11000000, 3F for 00111111, so these two together will match
everything. The first class matches bits 7 &#38; 6, and thus corresponds 
to 'interactive' and 'control' traffic. The second class matches the rest.
</Para>

<Para>
Node 1:0 now has a table like this:

<Screen>
priority        send to
0               1:3
1               1:3
2               1:3
3               1:3
4               1:3
5               1:3
6               1:2
7               1:2
</Screen>

</Para>

<Para>
For additional fun, you can also pass a 'change mask', which indicates
exactly which priorities you wish to change. You only need to use this if you
are running 'tc class change'. For example, to add best effort traffic to
1:2, we could run this:
</Para>

<Para>

<Screen>
# tc class change dev eth1 classid 1:2 cbq defmap 01/01
</Screen>

</Para>

<Para>
The priority map at 1:0 now looks like this:
</Para>

<Para>

<Screen>
priority        send to
0               1:2
1               1:3
2               1:3
3               1:3
4               1:3
5               1:3
6               1:2
7               1:2
</Screen>

</Para>

<Para>
FIXME: did not test 'tc class change', only looked at the source.
</Para>

</Sect3>

</Sect2>

<Sect2>
<Title>Hierarchical Token Bucket </Title>

<Para>
Martin Devera (&lt;devik&gt;) rightly realised that CBQ is complex and does
not seem optimized for many typical situations. His Hierarchical approach is
well suited for setups where you have a fixed amount of bandwidth which you
want to divide for different purposes, giving each purpose a guaranteed
bandwidth, with the possibility of specifying how much bandwidth can be
borrowed.
</Para>

<Para>
HTB works just like CBQ but does not resort to idle time calculations to
shape. Instead, it is a classful Token Bucket Filter - hence the name. It
has only a few parameters, which are well documented on his 
<ULink
URL="http://luxik.cdi.cz/~devik/qos/htb/"
>site</ULink
>.
</Para>

<Para>
As your HTB configuration gets more complex, your configuration scales
well. With CBQ it is already complex even in simple cases! HTB3 (check
<ulink url="http://luxik.cdi.cz/~devik/qos/htb/">its homepage</ulink> for
details on HTB versions) is now part of the official kernel sources 
(from 2.4.20-pre1 and 2.5.31 onwards). However, maybe you still need to
get a HTB3 patched version of 'tc': HTB kernel and userspace parts must
be the same major version, or 'tc' will not work with HTB.

</Para>

<Para>
If you already have a modern kernel, or are in a position to patch your 
kernel, by all means consider HTB.
</para>


<Sect3>
<Title>Sample configuration</Title>

<Para>
Functionally almost identical to the CBQ sample configuration above:
</Para>

<Para>

<Screen>
# tc qdisc add dev eth0 root handle 1: htb default 30

# tc class add dev eth0 parent 1: classid 1:1 htb rate 6mbit burst 15k

# tc class add dev eth0 parent 1:1 classid 1:10 htb rate 5mbit burst 15k
# tc class add dev eth0 parent 1:1 classid 1:20 htb rate 3mbit ceil 6mbit burst 15k
# tc class add dev eth0 parent 1:1 classid 1:30 htb rate 1kbit ceil 6mbit burst 15k
</Screen>

</Para>

<Para>
The author then recommends SFQ for beneath these classes:

<Screen>
# tc qdisc add dev eth0 parent 1:10 handle 10: sfq perturb 10
# tc qdisc add dev eth0 parent 1:20 handle 20: sfq perturb 10
# tc qdisc add dev eth0 parent 1:30 handle 30: sfq perturb 10
</Screen>
 
</Para>

<Para>
Add the filters which direct traffic to the right classes:

<Screen>
# U32="tc filter add dev eth0 protocol ip parent 1:0 prio 1 u32"
# $U32 match ip dport 80 0xffff flowid 1:10
# $U32 match ip sport 25 0xffff flowid 1:20
</Screen>

And that's it - no unsightly unexplained numbers, no undocumented
parameters. 
</Para>

<Para>
HTB certainly looks wonderful - if 10: and 20: both have their guaranteed
bandwidth, and more is left to divide, they borrow in a 5:3 ratio, just as
you would expect.
</Para>

<Para>
Unclassified traffic gets routed to 30:, which has little bandwidth of its
own but can borrow everything that is left over. Because we chose SFQ
internally, we get fairness thrown in for free!
</Para>

</Sect3>

</Sect2>

</Sect1>

<Sect1 id="lartc.qdisc.filters">
  <Title>Classifying packets with filters</Title>

<Para>
To determine which class shall process a packet, the so-called 'classifier
chain' is called each time a choice needs to be made. This chain consists of
all filters attached to the classful qdisc that needs to decide.
</Para>

<Para>To reiterate the tree, which is not a tree:
</Para>

<Screen width="80">
                    root 1:
                      |
                    _1:1_
                   /  |  \
                  /   |   \
                 /    |    \
               10:   11:   12:
              /   \       /   \
           10:1  10:2   12:1  12:2
</Screen>

<Para>
When enqueueing a packet, at each branch the filter chain is consulted for a
relevant instruction. A typical setup might be to have a filter in 1:1 that
directs a packet to 12: and a filter on 12: that sends the packet to 12:2.
</Para>

<Para>
You might also attach this latter rule to 1:1, but you can make efficiency
gains by having more specific tests lower in the chain.
</Para>

<Para>
You can't filter a packet 'upwards', by the way. Also, with HTB, you should
attach all filters to the root!
</Para>

<Para>
And again - packets are only enqueued downwards! When they are dequeued,
they go up again, where the interface lives. They do NOT fall off the end of
the tree to the network adaptor!
</Para>

<Sect2>
<Title>Some simple filtering examples</Title>

<Para>
As explained in the Classifier chapter, you can match on literally anything,
using a very complicated syntax. To start, we will show how to do the
obvious things, which luckily are quite easy.
</Para>

<Para>
Let's say we have a PRIO qdisc called '10:' which contains three classes, and
we want to assign all traffic from and to port 22 to the highest priority
band, the filters would be:
</Para>

<Para>

<Screen>
# tc filter add dev eth0 protocol ip parent 10: prio 1 u32 match \ 
  ip dport 22 0xffff flowid 10:1
# tc filter add dev eth0 protocol ip parent 10: prio 1 u32 match \
  ip sport 80 0xffff flowid 10:1
# tc filter add dev eth0 protocol ip parent 10: prio 2 flowid 10:2
</Screen>

</Para>

<Para>
What does this say? It says: attach to eth0, node 10: a  priority 1 u32
filter that matches on IP destination port 22 *exactly* and send it to band
10:1. And it then repeats the same for source port 80. The last command says
that anything unmatched so far should go to band 10:2, the next-highest
priority.
</Para>

<Para>
You need to add 'eth0', or whatever your interface is called, because each
interface has a unique namespace of handles.
</Para>

<Para>
To select on an IP address, use this:

<Screen>
# tc filter add dev eth0 parent 10:0 protocol ip prio 1 u32 \ 
  match ip dst 4.3.2.1/32 flowid 10:1
# tc filter add dev eth0 parent 10:0 protocol ip prio 1 u32 \
  match ip src 1.2.3.4/32 flowid 10:1
# tc filter add dev eth0 protocol ip parent 10: prio 2      \
  flowid 10:2
</Screen>

</Para>

<Para>
This assigns traffic to 4.3.2.1 and traffic from 1.2.3.4 to the highest
priority queue, and the rest to the next-highest one.
</Para>

<Para>
You can concatenate matches, to match on traffic from 1.2.3.4 and from port
80, do this:

<Screen>
# tc filter add dev eth0 parent 10:0 protocol ip prio 1 u32 match ip src 4.3.2.1/32 \
  match ip sport 80 0xffff flowid 10:1
</Screen>

</Para>

</Sect2>

<Sect2 id="lartc.filtering.simple">
<Title>All the filtering commands you will normally need</Title>

<Para>
Most shaping commands presented here start with this preamble:

<Screen>
# tc filter add dev eth0 parent 1:0 protocol ip prio 1 u32 ..
</Screen>

These are the so called 'u32' matches, which can match on ANY part of a
packet.
<VariableList>

<VarListEntry>
<Term>On source/destination address</Term>
<ListItem>
<Para>
Source mask 'match ip src 1.2.3.0/24', destination mask 'match ip dst
4.3.2.0/24'. To match a single host, use /32, or omit the mask.
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>On source/destination port, all IP protocols</Term>
<ListItem>
<Para>
Source: 'match ip sport 80 0xffff', destination: 'match ip dport 80 0xffff'
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>On ip protocol (tcp, udp, icmp, gre, ipsec)</Term>
<ListItem>
<Para>
Use the numbers from /etc/protocols, for example, icmp is 1: 'match ip
protocol 1 0xff'. 
</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>On fwmark</Term>
<ListItem>
<Para>
You can mark packets with either ipchains or iptables and have that mark
survive routing across interfaces. This is really useful to for example only
shape traffic on eth1 that came in on eth0. Syntax:
<screen>
# tc filter add dev eth1 protocol ip parent 1:0 prio 1 handle 6 fw flowid 1:1
</screen>
Note that this is not a u32 match!
</Para>

<Para>
You can place a mark like this:

<Screen>
# iptables -A PREROUTING -t mangle -i eth0 -j MARK --set-mark 6
</Screen>

The number 6 is arbitrary.
</Para>

<Para>
If you don't want to understand the full tc filter syntax, just use
iptables, and only learn to select on fwmark. You can also have iptables
print basic statistics that will help you debug your rules.
The following command will show you all the rules that mark packages
in the mangle table, also how many packages and bytes have matched.

<Screen>
# iptables -L -t mangle -n -v
</Screen>


</Para></ListItem>
</VarListEntry>
<VarListEntry>
<Term>On the TOS field</Term>
<ListItem>
<Para>
To select interactive, minimum delay traffic:

<Screen>
# tc filter add dev ppp0 parent 1:0 protocol ip prio 10 u32 \
      match ip tos 0x10 0xff \
     flowid 1:4
</Screen>

Use 0x08 0xff for bulk traffic.
</Para></ListItem>
</VarListEntry>
</VariableList>
</Para>

<Para>
For more filtering commands, see the Advanced Filters chapter.
</Para>

</Sect2>

</Sect1>
<Sect1 id="lartc.imq">
<Title>The Intermediate queueing device (IMQ)</Title>

<Para>
The Intermediate queueing device is not a qdisc but its usage is tightly bound
to qdiscs. Within linux, qdiscs are attached to network devices and everything
that is queued to the device is first queued to the qdisc. From this concept,
two limitations arise:
</Para>

<Orderedlist>
<Listitem>
<Para>
Only egress shaping is possible (an ingress qdisc exists, but its
possibilities are very limited compared to classful qdiscs).
</Para>
</Listitem>
<Listitem>
<Para>
A qdisc can only see traffic of one interface, global limitations can't be
placed.
</Para>
</Listitem>
</Orderedlist>

<Para>
IMQ is there to help solve those two limitations. In short, you can put 
everything you choose in a qdisc. Specially marked packets get intercepted
in netfilter NF_IP_PRE_ROUTING and NF_IP_POST_ROUTING hooks and pass through
the qdisc attached to an imq device. An iptables target is used for marking
the packets.
</Para>

<Para>
This enables you to do ingress shaping as you can just mark packets coming in from somewhere and/or treat interfaces as classes to set global limits.
You can also do lots of other stuff like just putting your http traffic in a
qdisc, put new connection requests in a qdisc, ...
</Para>

<Sect2>
<Title>Sample configuration</Title>

<Para>
The first thing that might come to mind is use ingress shaping to give yourself
a high guaranteed bandwidth. ;)
Configuration is just like with any other interface:

<Screen>
tc qdisc add dev imq0 root handle 1: htb default 20

tc class add dev imq0 parent 1: classid 1:1 htb rate 2mbit burst 15k

tc class add dev imq0 parent 1:1 classid 1:10 htb rate 1mbit
tc class add dev imq0 parent 1:1 classid 1:20 htb rate 1mbit

tc qdisc add dev imq0 parent 1:10 handle 10: pfifo
tc qdisc add dev imq0 parent 1:20 handle 20: sfq

tc filter add dev imq0 parent 10:0 protocol ip prio 1 u32 match \
                ip dst 10.0.0.230/32 flowid 1:10
</Screen>

In this example u32 is used for classification. Other classifiers should work as
expected.
Next traffic has to be selected and marked to be enqueued to imq0.

<Screen>
iptables -t mangle -A PREROUTING -i eth0 -j IMQ --todev 0

ip link set imq0 up
</Screen>

</Para>

<Para>
The IMQ iptables targets is valid in the PREROUTING and POSTROUTING chains of
the mangle table. It's syntax is 

<Screen>
IMQ [ --todev n ]       n : number of imq device
</Screen>

An ip6tables target is also provided.
</Para>

<Para>
Please note traffic is not enqueued when the target is hit but afterwards.
The exact location where traffic enters the imq device depends on the
direction of the traffic (in/out).
These are the predefined netfilter hooks used by iptables:

<Screen>
enum nf_ip_hook_priorities {
        NF_IP_PRI_FIRST = INT_MIN,
        NF_IP_PRI_CONNTRACK = -200,
        NF_IP_PRI_MANGLE = -150,
        NF_IP_PRI_NAT_DST = -100,
        NF_IP_PRI_FILTER = 0,
        NF_IP_PRI_NAT_SRC = 100,
        NF_IP_PRI_LAST = INT_MAX,
};
</Screen>

</Para>

<Para>
For ingress traffic, imq registers itself with NF_IP_PRI_MANGLE + 1 priority
which means packets enter the imq device directly after the mangle PREROUTING
chain has been passed.
</Para>

<Para>
For egress imq uses NF_IP_PRI_LAST which honours the fact that packets dropped
by the filter table won't occupy bandwidth.
</Para>

<Para>
The patches and some more information can be found at the
<ULink
URL="http://luxik.cdi.cz/~patrick/imq/"
>imq site</ULink>.
</Para>

</Sect2>

</Sect1>

</chapter>

<chapter id="lartc.loadshare">
<Title>Load sharing over multiple interfaces</Title>

<Para>
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, load sharing goes both ways. Both ends of a link
may need to participate for full effect.
</Para>

<Para>
Imagine this situation:
</Para>

<Para>

<Screen>
                 +-------+   eth1   +-------+
                 |       |==========|       |
 'network 1' ----|   A   |          |   B   |---- 'network 2'
                 |       |==========|       |
                 +-------+   eth2   +-------+
</Screen>

</Para>

<Para>
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.
</Para>

<Para>
The distributing part is done by a 'TEQL' device, like this (it couldn't be
easier):
</Para>

<Para>

<Screen>
# tc qdisc add dev eth1 root teql0
# tc qdisc add dev eth2 root teql0
# ip link set dev teql0 up
</Screen>

</Para>

<Para>
Don't forget the 'ip link set up' command!
</Para>

<Para>
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.
</Para>

<Para>
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:
</Para>

<Para>
On router A:

<Screen>
# 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
</Screen>

</Para>

<Para>
On router B:

<Screen>
# 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
</Screen>

</Para>

<Para>
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.
</Para>

<Para>
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.
</Para>

<Sect1 id="lartc.loadshare.caveats">
  <Title>Caveats</Title>

<Para>
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:
</Para>

<Para>

<Screen>
# echo 0 &#62; /proc/sys/net/ipv4/conf/eth1/rp_filter
# echo 0 &#62; /proc/sys/net/ipv4/conf/eth2/rp_filter
</Screen>

</Para>

<Para>
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 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.
</Para>

<Para>
However, for lots of applications, link load balancing is a great idea.
</Para>

</Sect1>
<Sect1 id="lartc.loadshare.other">
  <Title>Other possibilities</Title>
<para>
William Stearns has used an advanced tunneling setup to achieve good use of
multiple, unrelated, internet connections together. It can be found on
<ULink
URL="http://www.stearns.org/tunnel/">his tunneling page</ULink>.
</para>
<para>
The HOWTO may feature more about this in the future.
</para>
</Sect1>
</chapter>

<chapter id="lartc.netfilter">
<Title>Netfilter &amp; iproute - marking packets</Title>

<Para>
So far we've seen how iproute works, and netfilter was mentioned a few
times. This would be a good time to browse through <ULink
URL="http://netfilter.samba.org/unreliable-guides/"
>Rusty's Remarkably Unreliable Guides</ULink
>. Netfilter itself
can be found <ULink
URL="http://netfilter.filewatcher.org/"
>here</ULink
>.
</Para>

<Para>
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. 
</Para>

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

<Para>

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

</Para>

<Para>
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.
</Para>

<Para>
We've already marked the packets with a '1', we now instruct the routing
policy database to act on this:
</Para>

<Para>

<Screen>
# echo 201 mail.out &#62;&#62; /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 
</Screen>

</Para>

<Para>
Now we generate a route to the slow but cheap link in the mail.out table:

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

</Para>

<Para>
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.
</Para>

<Para>
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