An awful lot of small fixes. (NAKANO Takeo nakano@apm.seikei.ac.jp)
[lartc.git] / lartc.db
blobda7d8586ef86de7f3a348848b2bc677acb22e120
1 <!DOCTYPE book PUBLIC "-//OASIS//DTD DocBook V4.1//EN">
2 <!-- $Id$ -->
3 <Book id="lartc">
4 <?dbhtml banner-text="Made possible by PowerDNS">
5 <?dbhtml banner-href="http://www.powerdns.com">
7   <bookinfo>
8     <Title>Linux Advanced Routing &amp; Traffic Control HOWTO</Title>
9     <authorgroup>
10       <author>
11         <FirstName>Bert</FirstName><Surname>Hubert</Surname>
12         <affiliation>
13           <orgname>Netherlabs BV</orgname>
14           <address><email>bert.hubert@netherlabs.nl</email></address>
15         </affiliation>
16       </author>
18       <collab>
19         <collabname>Thomas Graf (Section Author)</collabname>
20         <affiliation>
21           <address><email>tgraf%suug.ch</email></address>
22         </affiliation>
23      </collab>
25       
26       <collab>
27         <collabname>Gregory Maxwell (Section Author)</collabname>
28       </collab>
30       
31       <collab>
32         <collabname>Remco van Mook (Section Author)</collabname>
33         <affiliation>
34           <address><email>remco@virtu.nl</email></address>
35         </affiliation>
36      </collab>
37   
38      <collab>
39        <collabname>Martijn van Oosterhout (Section Author)</collabname>
40         <affiliation>
41           <address><email>kleptog@cupid.suninternet.com</email></address>
42         </affiliation>
43      </collab>
44   
45      <collab>
46        <collabname>Paul B Schroeder (Section Author)</collabname>
47         <affiliation>
48           <address><email>paulsch@us.ibm.com</email></address>
49         </affiliation>
50      </collab>
51   
52      <collab>
53        <collabname>Jasper Spaans (Section Author)</collabname>
54         <affiliation>
55           <address><email>jasper@spaans.ds9a.nl</email></address>
56         </affiliation>
57      </collab>
58      <collab>
59        <collabname>Pedro Larroy (Section Author)</collabname>
60         <affiliation>
61           <address><email>piotr%member.fsf.org</email></address>
62         </affiliation>
63      </collab>
65   </authorgroup>
66   
67    <revhistory>
68      <revision>
69        <revnumber role="rcs">$Revision$</revnumber>
70        <date role="rcs">$Date$</date>
71        <revremark>DocBook Edition</revremark>
72      </revision>
73    </revhistory>
74                                    
75    <Abstract>
76      <Para>A very hands-on approach to <application>iproute2</application>,
77      traffic shaping and a bit of <application>netfilter</application>.
78      </para>
79    </Abstract>
80   
81 </bookinfo>
82 <toc></toc>
83 <chapter id="lartc.dedication">
84     <Title>Dedication</Title>
86     <Para>
87       This document is dedicated to lots of people, and is my attempt to do
88       something back. To list but a few:
89     </Para>
91     <Para>
93       <ItemizedList>
94         <ListItem>
95           <Para>
96             Rusty Russell
97           </Para>
98         </ListItem>
99         <ListItem>
101           <Para>
102             Alexey N. Kuznetsov
103           </Para>
104         </ListItem>
105         <ListItem>
106           
107           <Para>
108             The good folks from Google
109           </Para>
110         </ListItem>
111         <ListItem>
112           
113           <Para>
114             The staff of Casema Internet
115           </Para>
116         </ListItem>
118       </ItemizedList>
119         
120     </Para>
122   </chapter>
124   <chapter id="lartc.intro">
125     <Title>Introduction</Title>
127 <Para>
128 Welcome, gentle reader.
129 </Para>
131 <Para>
132       This document hopes to enlighten you on how to do more with Linux 2.2/2.4
133       routing. Unbeknownst to most users, you already run tools which allow you to
134       do spectacular things. Commands like <command>route</command> and 
135       <command>ifconfig</command> are actually
136       very thin wrappers for the very powerful iproute2 infrastructure.
137 </Para>
139     <Para>
140       I hope that this HOWTO will become as readable as the ones by Rusty Russell
141       of (amongst other things) netfilter fame.
142     </Para>
144     <Para>
145       You can always reach us by writing to the <ULink
146         URL="mailto:HOWTO@ds9a.nl"
147         >HOWTO team</ULink
148         >. However, please consider posting to the mailing
149       list (see the relevant section) if you have questions which are not directly
150       related to this HOWTO. We are no free helpdesk, but we often will answer questions
151       asked on the list.
152 </Para>
154 <Para>
155 Before losing your way in this HOWTO, if all you want to do is simple
156 traffic shaping, skip everything and head to the <citetitle><xref linkend="lartc.other"></citetitle> chapter, and read about CBQ.init.
157 </Para>
159 <Sect1 id="lartc.intro.disclaimer">
160 <Title>Disclaimer &amp; License</Title>
162 <Para>
163 This document is distributed in the hope that it will be useful,
164 but WITHOUT ANY WARRANTY; without even the implied warranty of
165 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
166 </Para>
168 <Para>
169 In short, if your STM-64 backbone breaks down and distributes pornography to
170 your most esteemed customers - it's never our fault. Sorry.
171 </Para>
173 <Para>
174 Copyright (c) 2002 by bert hubert, Gregory Maxwell, Martijn van
175 Oosterhout, Remco van Mook, Paul B. Schroeder and others. This material may
176 be distributed only subject to the terms and conditions set forth in the
177 Open Publication License, v1.0 or later (the latest version is presently
178 available at http://www.opencontent.org/openpub/).
179 </Para>
181 <Para>
182 Please freely copy and distribute (sell or give away) this document in any
183 format. It's requested that corrections and/or comments be forwarded to the
184 document maintainer. 
185 </Para>
187 <Para>
188 It is also requested that if you publish this HOWTO in hardcopy that you
189 send the authors some samples for <quote>review purposes</quote> :-) 
190 </Para>
192 </Sect1>
194 <Sect1 id="lartc.intro.prior">
195   <Title>Prior knowledge</Title>
197 <Para>
198 As the title implies, this is the <quote>Advanced</quote> HOWTO.
199 While by no means rocket science, some prior knowledge is assumed. 
200 </Para>
202 <Para>
203 Here are some other references which might help teach you more:
204 <VariableList>
205 <VarListEntry>
206   <Term>
207     <ULink URL="http://netfilter.samba.org/unreliable-guides/networking-concepts-HOWTO/index.html">
208       Rusty Russell's networking-concepts-HOWTO</ULink>
209   </Term>
210   <ListItem>
211     <Para>Very nice introduction, explaining what a network is, and how it is
212     connected to other networks.
213     </Para>
214   </ListItem>
215 </VarListEntry>
216 <VarListEntry>
217   <Term>Linux Networking-HOWTO (Previously the Net-3 HOWTO)</Term>
218   <ListItem>
219     <Para>Great stuff, although very verbose. It teaches you a lot of stuff 
220     that's already configured if you are able to connect to the Internet. 
221     Should be located in <filename>/usr/doc/HOWTO/NET3-4-HOWTO.txt</filename>
222  but can be also be found 
223     <ULink URL="http://www.linuxports.com/howto/networking">online</ULink>.
224     </Para>
225   </ListItem>
226 </VarListEntry>
227 </VariableList>
228 </Para>
230 </Sect1>
232 <Sect1 id="lartc.intro.linux">
233   <Title>What Linux can do for you</Title>
235 <Para>
236 A small list of things that are possible:
237 </Para>
239 <ItemizedList>
240 <ListItem>
241   <Para>Throttle bandwidth for certain computers
242   </Para>
243 </ListItem>
244 <ListItem>
245   <Para>Throttle bandwidth TO certain computers
246   </Para>
247 </ListItem>
248 <ListItem>
249   <Para>Help you to fairly share your bandwidth
250   </Para>
251 </ListItem>
252 <ListItem>
253   <Para>Protect your network from DoS attacks
254   </Para>
255 </ListItem>
256 <ListItem>
257   <Para>Protect the Internet from your customers
258   </Para>
259 </ListItem>
260 <ListItem>
261   <Para>Multiplex several servers as one, for load balancing or
262   enhanced availability
263   </Para>
264 </ListItem>
265 <ListItem>
266   <Para>Restrict access to your computers
267   </Para>
268 </ListItem>
269 <ListItem>
270   <Para>Limit access of your users to other hosts
271   </Para>
272 </ListItem>
273 <ListItem>
274   <Para>Do routing based on user id (yes!), MAC address, source IP
275   address, port, type of service, time of day or content
276   </Para>
277 </ListItem>
278 </ItemizedList>
280 <Para>
281 Currently, not many people are using these advanced features. This is for
282 several reasons. While the provided documentation is verbose, it is not very
283 hands-on. Traffic control is almost undocumented.
284 </Para>
286 </Sect1>
288 <Sect1 id="lartc.intro.houskeeping">
289   <Title>Housekeeping notes</Title>
291 <Para>
292 There are several things which should be noted about this document. While I
293 wrote most of it, I really don't want it to stay that way. I am a strong
294 believer in Open Source, so I encourage you to send feedback, updates,
295 patches etcetera. Do not hesitate to inform me of typos or plain old errors.
296 If my English sounds somewhat wooden, please realize that I'm not a native
297 speaker. Feel free to send suggestions.
298 </Para>
300 <Para>
301 If you feel to you are better qualified to maintain a section, or think that
302 you can author and maintain new sections, you are welcome to do so. The SGML
303 of this HOWTO is available via CVS, I very much envision more people
304 working on it.
305 </Para>
307 <Para>
308 In aid of this, you will find lots of FIXME notices. Patches are always
309 welcome! Wherever you find a FIXME, you should know that you are treading in
310 unknown territory. This is not to say that there are no errors elsewhere,
311 but be extra careful. If you have validated something, please let us know so
312 we can remove the FIXME notice.
313 </Para>
315 <Para>
316 About this HOWTO, I will take some liberties along the road. For example, I
317 postulate a 10Mbit Internet connection, while I know full well that those
318 are not very common.
319 </Para>
321 </Sect1>
323 <Sect1 id="lartc.intro.cvs">
324   <Title>Access, CVS &amp; submitting updates</Title>
326 <Para>
327 The canonical location for the HOWTO is 
328 <ULink URL="http://www.ds9a.nl/lartc">here</ULink>.
329 </Para>
331 <Para>
332 We now have anonymous CVS access available to the world at large. This is
333 good in a number of ways. You can easily upgrade to newer versions of this
334 HOWTO and submitting patches is no work at all.
335 </Para>
337 <Para>
338 Furthermore, it allows the authors to work on the source independently,
339 which is good too.
340 </Para>
342 <Screen width="80">
343 $ export CVSROOT=:pserver:anon@outpost.ds9a.nl:/var/cvsroot
344 $ cvs login
345 CVS password: [enter 'cvs' (without 's)]
346 $ cvs co 2.4routing
347 cvs server: Updating 2.4routing
348 U 2.4routing/lartc.db
349 </Screen>
351 <Para>
352 If you made changes and want to contribute them, run <userinput>
353 cvs -z3 diff -uBb</userinput>,
354 and mail the output to <email>howto@ds9a.nl</email>, we
355 can then integrate it easily. Thanks! Please make sure that you edit the
356 .db file, by the way, the other files are generated from that one. 
357 </Para>
359 <Para>
360 A Makefile is supplied which should help you create postscript, dvi, pdf,
361 html and plain text. You may need to install 
362 <application>docbook</application>, <application>docbook-utils</application>,
363 <application>ghostscript</application> and <application>tetex</application> 
364 to get all formats.
365 </Para>
367 <para>
368 Be careful not to edit 2.4routing.sgml! It contains an older version of the
369 HOWTO. The right file is lartc.db.
370 </para>
371 </Sect1>
373 <Sect1 id="lartc.intro.mlist">
374   <Title>Mailing list</Title>
376 <Para>
377 The authors receive an increasing amount of mail about this HOWTO. Because
378 of the clear interest of the community, it has been decided to start a
379 mailinglist where people can talk to each other about Advanced Routing and
380 Traffic Control. You can subscribe to the list
381 <ULink URL="http://mailman.ds9a.nl/mailman/listinfo/lartc">here</ULink>.
382 </Para>
384 <Para>
385 It should be pointed out that the authors are very hesitant of answering
386 questions not asked on the list. We would like the archive of the list to
387 become some kind of knowledge base. If you have a question, please search
388 the archive, and then post to the mailinglist.
389 </Para>
391 </Sect1>
393 <Sect1 id="lartc.intro.layout">
394   <Title>Layout of this document</Title>
396 <Para>
397 We will be doing interesting stuff almost immediately, which also means that
398 there will initially be parts that are explained incompletely or are not
399 perfect. Please gloss over these parts and assume that all will become clear.
400 </Para>
402 <Para>
403 Routing and filtering are two distinct things. Filtering is documented very
404 well by Rusty's HOWTOs, available here:
405 </Para>
407 <ItemizedList>
408 <ListItem>
409   <Para><ULink URL="http://netfilter.samba.org/unreliable-guides/">
410     Rusty's Remarkably Unreliable Guides</ULink>
411   </Para>
412 </ListItem>
413 </ItemizedList>
415 <Para>We will be focusing mostly on what is possible by combining netfilter
416 and iproute2.
417 </Para>
419 </Sect1>
421 </chapter>
423 <chapter id="lartc.iproute2">
424   <Title>Introduction to iproute2</Title>
426 <Sect1 id="lartc.iproute2.why">
427   <Title>Why iproute2?</Title>
429 <Para>
430 Most Linux distributions, and most UNIX's, currently use the 
431 venerable <command>arp</command>, <command>ifconfig</command> and 
432 <command>route</command> commands.
433 While these tools work, they show some unexpected behaviour under Linux 2.2 
434 and up.
435 For example, GRE tunnels are an integral part of routing these days, but 
436 require completely different tools.
437 </Para>
439 <Para>
440 With <application>iproute2</application>, tunnels are an integral part of 
441 the tool set.
442 </Para>
444 <Para>
445 The 2.2 and above Linux kernels include a completely redesigned network
446 subsystem. This new networking code brings Linux performance and a feature
447 set with little competition in the general OS arena. In fact, the new
448 routing, filtering, and classifying code is more featureful than the one
449 provided by many dedicated routers and firewalls and traffic shaping
450 products.
451 </Para>
453 <Para>
454 As new networking concepts have been invented, people have found ways to
455 plaster them on top of the existing framework in existing OSes. This
456 constant layering of cruft has lead to networking code that is filled with
457 strange behaviour, much like most human languages. In the past, Linux
458 emulated SunOS's handling of many of these things, which was not ideal.  
459 </Para>
461 <Para>
462 This new framework makes it possible to clearly express features
463 previously beyond Linux's reach.
464 </Para>
466 </Sect1>
468 <Sect1 id="lartc.iproute2.tour">
469   <Title>iproute2 tour</Title>
471 <Para>
472 Linux has a sophisticated system for bandwidth provisioning called Traffic
473 Control. This system supports various method for classifying, prioritizing,
474 sharing, and limiting both inbound and outbound traffic.
475 </Para>
477 <Para>
478 We'll start off with a tiny tour of iproute2 possibilities.
479 </Para>
481 </Sect1>
483 <Sect1 id="lartc.iproute2.package">
484   <Title>Prerequisites</Title>
486 <Para>
487 You should make sure that you have the userland tools installed. This
488 package is called 'iproute' on both RedHat and Debian, and may otherwise be
489 found at <filename>ftp://ftp.inr.ac.ru/ip-routing/iproute2-2.2.4-now-ss??????.tar.gz"</filename>. 
490 </Para>
492 <Para>
493 You can also try 
494 <ULink URL="ftp://ftp.inr.ac.ru/ip-routing/iproute2-current.tar.gz">here</ULink> 
495 for the latest version.
496 </Para>
498 <Para>
499 Some parts of iproute require you to have certain kernel options enabled. It
500 should also be noted that all releases of RedHat up to and including 6.2
501 come without most of the traffic control features in the default kernel. 
502 </Para>
504 <Para>
505 RedHat 7.2 has everything in by default.
506 </Para>
508 <Para>
509 Also make sure that you have netlink support, should you choose to roll your
510 own kernel. Iproute2 needs it.
511 </Para>
513 </Sect1>
515 <Sect1 id="lartc.iproute2.explore">
516   <Title>Exploring your current configuration</Title>
518 <Para>
519 This may come as a surprise, but iproute2 is already configured! The current
520 commands <command>ifconfig</command> and <command>route</command> are already using the advanced
521 syscalls, but mostly with very default (ie. boring) settings.
522 </Para>
524 <Para>
525 The <command>ip</command> tool is central, and we'll ask it to display our interfaces
526 for us.
527 </Para>
529 <Sect2>
530 <Title><command>ip</command> shows us our links</Title>
532 <Screen width="80">
533 [ahu@home ahu]$ ip link list
534 1: lo: &#60;LOOPBACK,UP&#62; mtu 3924 qdisc noqueue 
535     link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00
536 2: dummy: &#60;BROADCAST,NOARP&#62; mtu 1500 qdisc noop 
537     link/ether 00:00:00:00:00:00 brd ff:ff:ff:ff:ff:ff
538 3: eth0: &#60;BROADCAST,MULTICAST,PROMISC,UP&#62; mtu 1400 qdisc pfifo_fast qlen 100
539     link/ether 48:54:e8:2a:47:16 brd ff:ff:ff:ff:ff:ff
540 4: eth1: &#60;BROADCAST,MULTICAST,PROMISC,UP&#62; mtu 1500 qdisc pfifo_fast qlen 100
541     link/ether 00:e0:4c:39:24:78 brd ff:ff:ff:ff:ff:ff
542 3764: ppp0: &#60;POINTOPOINT,MULTICAST,NOARP,UP&#62; mtu 1492 qdisc pfifo_fast qlen 10
543     link/ppp 
545 </Screen>
547 <Para>
548 Your mileage may vary, but this is what it shows on my NAT router at
549 home. I'll only explain part of the output as not everything is directly
550 relevant.
551 </Para>
553 <Para>
554 We first see the loopback interface. While your computer may function
555 somewhat without one, I'd advise against it. The MTU size (Maximum Transfer
556 Unit) is 3924 octets, and it is not supposed to queue. Which makes sense
557 because the loopback interface is a figment of your kernel's imagination.
558 </Para>
560 <Para>
561 I'll skip the dummy interface for now, and it may not be present on your
562 computer. Then there are my two physical network interfaces, one at the side
563 of my cable modem, the other one serves my home ethernet segment.
564 Furthermore, we see a ppp0 interface.
565 </Para>
567 <Para>
568 Note the absence of IP addresses. iproute disconnects the concept of 'links'
569 and 'IP addresses'. With IP aliasing, the concept of 'the' IP address had
570 become quite irrelevant anyhow. 
571 </Para>
573 <Para>
574 It does show us the MAC addresses though, the hardware identifier of our
575 ethernet interfaces.
576 </Para>
578 </Sect2>
580 <Sect2>
581   <Title><command>ip</command> shows us our IP addresses</Title>
583 <Screen width="80">
584 [ahu@home ahu]$ ip address show        
585 1: lo: &#60;LOOPBACK,UP&#62; mtu 3924 qdisc noqueue 
586     link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00
587     inet 127.0.0.1/8 brd 127.255.255.255 scope host lo
588 2: dummy: &#60;BROADCAST,NOARP&#62; mtu 1500 qdisc noop 
589     link/ether 00:00:00:00:00:00 brd ff:ff:ff:ff:ff:ff
590 3: eth0: &#60;BROADCAST,MULTICAST,PROMISC,UP&#62; mtu 1400 qdisc pfifo_fast qlen 100
591     link/ether 48:54:e8:2a:47:16 brd ff:ff:ff:ff:ff:ff
592     inet 10.0.0.1/8 brd 10.255.255.255 scope global eth0
593 4: eth1: &#60;BROADCAST,MULTICAST,PROMISC,UP&#62; mtu 1500 qdisc pfifo_fast qlen 100
594     link/ether 00:e0:4c:39:24:78 brd ff:ff:ff:ff:ff:ff
595 3764: ppp0: &#60;POINTOPOINT,MULTICAST,NOARP,UP&#62; mtu 1492 qdisc pfifo_fast qlen 10
596     link/ppp 
597     inet 212.64.94.251 peer 212.64.94.1/32 scope global ppp0
598 </Screen>
600 <Para>
601 This contains more information. It shows all our addresses, and to which
602 cards they belong. 'inet' stands for Internet (IPv4). There are lots of other
603 address families, but these don't concern us right now.
604 </Para>
606 <Para>
607 Let's examine eth0 somewhat closer. It says that it is related to the inet
608 address '10.0.0.1/8'. What does this mean? The /8 stands for the number of
609 bits that are in the Network Address. There are 32 bits, so we have 24 bits
610 left that are part of our network. The first 8 bits of 10.0.0.1 correspond
611 to 10.0.0.0, our Network Address, and our netmask is 255.0.0.0.
612 </Para>
614 <Para>
615 The other bits are connected to this interface, so 10.250.3.13 is directly
616 available on eth0, as is 10.0.0.1 for example. 
617 </Para>
619 <Para>
620 With ppp0, the same concept goes, though the numbers are different. Its
621 address is 212.64.94.251, without a subnet mask. This means that we have a
622 point-to-point connection and that every address, with the exception of
623 212.64.94.251, is remote. There is more information, however. It tells us
624 that on the other side of the link there is, yet again, only one address,
625 212.64.94.1. The /32 tells us that there are no 'network bits'.
626 </Para>
628 <Para>
629 It is absolutely vital that you grasp these concepts. Refer to the
630 documentation mentioned at the beginning of this HOWTO if you have trouble.
631 </Para>
633 <Para>
634 You may also note 'qdisc', which stands for Queueing Discipline. This will
635 become vital later on. 
636 </Para>
638 </Sect2>
640 <Sect2>
641   <Title><command>ip</command> shows us our routes</Title>
643 <Para>
644 Well, we now know how to find 10.x.y.z addresses, and we are able to reach
645 212.64.94.1. This is not enough however, so we need instructions on how to
646 reach the world. The Internet is available via our ppp connection, and it
647 appears that 212.64.94.1 is willing to spread our packets around the
648 world, and deliver results back to us.
649 </Para>
651 <Screen width="80">
652 [ahu@home ahu]$ ip route show
653 212.64.94.1 dev ppp0  proto kernel  scope link  src 212.64.94.251 
654 10.0.0.0/8 dev eth0  proto kernel  scope link  src 10.0.0.1 
655 127.0.0.0/8 dev lo  scope link 
656 default via 212.64.94.1 dev ppp0 
657 </Screen>
659 <Para>
660 This is pretty much self explanatory. The first 3 lines of output explicitly
661 state what was already implied by <command>ip address show</command>, the last line
662 tells us that the rest of the world can be found via 212.64.94.1, our
663 default gateway. We can see that it is a gateway because of the word
664 via, which tells us that we need to send packets to 212.64.94.1, and that it
665 will take care of things.
666 </Para>
668 <Para>
669 For reference, this is what the old <command>route</command> utility shows us:
670 </Para>
672 <Screen width="80">
673 [ahu@home ahu]$ route -n
674 Kernel IP routing table
675 Destination     Gateway         Genmask         Flags Metric Ref    Use
676 Iface
677 212.64.94.1     0.0.0.0         255.255.255.255 UH    0      0        0 ppp0
678 10.0.0.0        0.0.0.0         255.0.0.0       U     0      0        0 eth0
679 127.0.0.0       0.0.0.0         255.0.0.0       U     0      0        0 lo
680 0.0.0.0         212.64.94.1     0.0.0.0         UG    0      0        0 ppp0
681 </Screen>
683 </Sect2>
685 </Sect1>
687 <Sect1 id="lartc.iproute2.arp">
688   <Title>ARP</Title>
690 <Para>
691 ARP is the Address Resolution Protocol as described in
692 <ULink URL="http://www.faqs.org/rfcs/rfc826.html">RFC 826</ULink>.
693 ARP is used by a networked machine to resolve the hardware location/address of
694 another machine on the same
695 local network.  Machines on the Internet are generally known by their names
696 which resolve to IP
697 addresses.  This is how a machine on the foo.com network is able to communicate
698 with another machine which is on the bar.net network.  An IP address, though,
699 cannot tell you the physical location of a machine.  This is where ARP comes
700 into the picture.
701 </Para>
703 <Para>
704 Let's take a very simple example.  Suppose I have a network composed of several
705 machines.  Two of the machines which are currently on my network are foo
706 with an IP address of 10.0.0.1 and bar with an IP address of 10.0.0.2.
707 Now foo wants to ping bar to see that he is alive, but alas, foo has no idea
708 where bar is.  So when foo decides to ping bar he will need to send
709 out an ARP request.
710 This ARP request is akin to foo shouting out on the network "Bar (10.0.0.2)!
711 Where are you?"  As a result of this every machine on the network will hear
712 foo shouting, but only bar (10.0.0.2) will respond.  Bar will then send an
713 ARP reply directly back to foo which is akin
714 bar saying,
715 "Foo (10.0.0.1) I am here at 00:60:94:E9:08:12."  After this simple transaction
716 that's used to locate his friend on the network, foo is able to communicate
717 with bar until he (his arp cache) forgets where bar is (typically after
718 15 minutes on Unix).
719 </Para>
721 <Para>
722 Now let's see how this works.
723 You can view your machines current arp/neighbor cache/table like so:
724 </Para>
726 <Screen width="80">
727 [root@espa041 /home/src/iputils]# ip neigh show
728 9.3.76.42 dev eth0 lladdr 00:60:08:3f:e9:f9 nud reachable
729 9.3.76.1 dev eth0 lladdr 00:06:29:21:73:c8 nud reachable
730 </Screen>
732 <Para>
733 As you can see my machine espa041 (9.3.76.41) knows where to find espa042 
734 (9.3.76.42) and
735 espagate (9.3.76.1).  Now let's add another machine to the arp cache.
736 </Para>
738 <Screen width="80">
739 [root@espa041 /home/paulsch/.gnome-desktop]# ping -c 1 espa043
740 PING espa043.austin.ibm.com (9.3.76.43) from 9.3.76.41 : 56(84) bytes of data.
741 64 bytes from 9.3.76.43: icmp_seq=0 ttl=255 time=0.9 ms
743 --- espa043.austin.ibm.com ping statistics ---
744 1 packets transmitted, 1 packets received, 0% packet loss
745 round-trip min/avg/max = 0.9/0.9/0.9 ms
747 [root@espa041 /home/src/iputils]# ip neigh show
748 9.3.76.43 dev eth0 lladdr 00:06:29:21:80:20 nud reachable
749 9.3.76.42 dev eth0 lladdr 00:60:08:3f:e9:f9 nud reachable
750 9.3.76.1 dev eth0 lladdr 00:06:29:21:73:c8 nud reachable
751 </Screen>
753 <Para>
754 As a result of espa041 trying to contact espa043, espa043's hardware
755 address/location has now been added to the arp/neighbor cache.
756 So until the entry for
757 espa043 times out (as a result of no communication between the two) espa041
758 knows where to find espa043 and has no need to send an ARP request.
759 </Para>
761 <Para>
762 Now let's delete espa043 from our arp cache:
763 </Para>
765 <Screen width="80">
766 [root@espa041 /home/src/iputils]# ip neigh delete 9.3.76.43 dev eth0
767 [root@espa041 /home/src/iputils]# ip neigh show
768 9.3.76.43 dev eth0  nud failed
769 9.3.76.42 dev eth0 lladdr 00:60:08:3f:e9:f9 nud reachable
770 9.3.76.1 dev eth0 lladdr 00:06:29:21:73:c8 nud stale
771 </Screen>
773 <Para>
774 Now espa041 has again forgotten where to find espa043 and will need to send
775 another ARP request the next time he needs to communicate with espa043.
776 You can also see from the above output that espagate (9.3.76.1) has been
777 changed to the "stale" state.  This means that the location shown is still
778 valid, but it will have to be confirmed at the first transaction to that
779 machine.
780 </Para>
782 </Sect1>
784 </chapter>
786 <chapter id="lartc.rpdb">
787   <Title>Rules - routing policy database</Title>
789 <Para>
790 If you have a large router, you may well cater for the needs of different
791 people, who should be served differently. The routing policy database allows
792 you to do this by having multiple sets of routing tables. 
793 </Para>
795 <Para>
796 If you want to use this feature, make sure that your kernel is compiled with
797 the "IP: advanced router" and "IP: policy routing" features.
798 </Para>
800 <Para>
801 When the kernel needs to make a routing decision, it finds out which table
802 needs to be consulted. By default, there are three tables. The old 'route'
803 tool modifies the main and local tables, as does the ip tool (by default).
804 </Para>
806 <Para>The default rules:
807 </Para>
809 <Screen width="80">
810 [ahu@home ahu]$ ip rule list
811 0:      from all lookup local 
812 32766:  from all lookup main 
813 32767:  from all lookup default
814 </Screen>
816 <Para>
817 This lists the priority of all rules. We see that all rules apply to all
818 packets ('from all'). We've seen the 'main' table before, it is output by
819 <userinput>ip route ls</userinput>, but the 'local' and 'default' table are new.
820 </Para>
822 <Para>
823 If we want to do fancy things, we generate rules which point to different
824 tables which allow us to override system wide routing rules.
825 </Para>
827 <Para>
828 For the exact semantics on what the kernel does when there are more matching
829 rules, see Alexey's ip-cref documentation. 
830 </Para>
832 <Sect1 id="lartc.rpdb.simple">
833   <Title>Simple source policy routing</Title>
835 <Para>
836 Let's take a real example once again, I have 2 (actually 3, about time I
837 returned them) cable modems, connected to a Linux NAT ('masquerading')
838 router. People living here pay me to use the Internet. Suppose one of my
839 house mates only visits hotmail and wants to pay less. This is fine with me,
840 but they'll end up using the low-end cable modem.
841 </Para>
843 <Para>
844 The 'fast' cable modem is known as 212.64.94.251 and is a PPP link to
845 212.64.94.1. The 'slow' cable modem is known by various ip addresses,
846 212.64.78.148 in this example and is a link to 195.96.98.253.
847 </Para>
849 <Para>The local table:
850 </Para>
852 <Screen width="80">
853 [ahu@home ahu]$ ip route list table local
854 broadcast 127.255.255.255 dev lo  proto kernel  scope link  src 127.0.0.1 
855 local 10.0.0.1 dev eth0  proto kernel  scope host  src 10.0.0.1 
856 broadcast 10.0.0.0 dev eth0  proto kernel  scope link  src 10.0.0.1 
857 local 212.64.94.251 dev ppp0  proto kernel  scope host  src 212.64.94.251 
858 broadcast 10.255.255.255 dev eth0  proto kernel  scope link  src 10.0.0.1 
859 broadcast 127.0.0.0 dev lo  proto kernel  scope link  src 127.0.0.1 
860 local 212.64.78.148 dev ppp2  proto kernel  scope host  src 212.64.78.148 
861 local 127.0.0.1 dev lo  proto kernel  scope host  src 127.0.0.1 
862 local 127.0.0.0/8 dev lo  proto kernel  scope host  src 127.0.0.1 
863 </Screen>
865 <Para>
866 Lots of obvious things, but things that need to be specified somewhere.
867 Well, here they are. The default table is empty.
868 </Para>
870 <Para>Let's view the 'main' table:
871 </Para>
873 <Screen width="80">
874 [ahu@home ahu]$ ip route list table main 
875 195.96.98.253 dev ppp2  proto kernel  scope link  src 212.64.78.148 
876 212.64.94.1 dev ppp0  proto kernel  scope link  src 212.64.94.251 
877 10.0.0.0/8 dev eth0  proto kernel  scope link  src 10.0.0.1 
878 127.0.0.0/8 dev lo  scope link 
879 default via 212.64.94.1 dev ppp0 
880 </Screen>
882 <Para>
883 We now generate a new rule which we call 'John', for our hypothetical
884 house mate. Although we can work with pure numbers, it's far easier if we add
885 our tables to /etc/iproute2/rt_tables.
886 </Para>
888 <Screen width="80">
889 # echo 200 John &#62;&#62; /etc/iproute2/rt_tables
890 # ip rule add from 10.0.0.10 table John
891 # ip rule ls
892 0:      from all lookup local 
893 32765:  from 10.0.0.10 lookup John
894 32766:  from all lookup main 
895 32767:  from all lookup default
896 </Screen>
898 <Para>
899 Now all that is left is to generate John's table, and flush the route cache:
900 </Para>
902 <Screen width="80">
903 # ip route add default via 195.96.98.253 dev ppp2 table John
904 # ip route flush cache
905 </Screen>
907 <Para>
908 And we are done. It is left as an exercise for the reader to implement this
909 in ip-up.
910 </Para>
912 </Sect1>
914 <sect1 id="lartc.rpdb.multiple-links">
915   <title>Routing for multiple uplinks/providers</title>
916 <para>
917 A common configuration is the following, in which there are two providers
918 that connect a local network (or even a single machine) to the big Internet.
920 <screen>
921                                                                  ________
922                                           +------------+        /
923                                           |            |       |
924                             +-------------+ Provider 1 +-------
925         __                  |             |            |     /
926     ___/  \_         +------+-------+     +------------+    |
927   _/        \__      |     if1      |                      /
928  /             \     |              |                      |
929 | Local network -----+ Linux router |                      |     Internet
930  \_           __/    |              |                      |
931    \__     __/       |     if2      |                      \
932       \___/          +------+-------+     +------------+    |
933                             |             |            |     \
934                             +-------------+ Provider 2 +-------
935                                           |            |       |
936                                           +------------+        \________
937 </screen>
938 </para>
939 <para>
940 There are usually two questions given this setup.
941 </para>
942       <sect2><title>Split access</title>
943         <para>
944           The first is how to route answers to packets coming in over a
945           particular provider, say Provider 1, back out again over that same provider.
946         </para>
947         <para>
948           Let us first set some symbolical names. Let <command>$IF1</command> be the name of the
949           first interface (if1 in the picture above) and <command>$IF2</command> the name of the
950           second interface. Then let <command>$IP1</command> be the IP address associated with
951           <command>$IF1</command> and <command>$IP2</command> the IP address associated with
952           <command>$IF2</command>. Next, let <command>$P1</command> be the IP address of the gateway at
953           Provider 1, and <command>$P2</command> the IP address of the gateway at provider 2.
954           Finally, let <command>$P1_NET</command> be the IP network <command>$P1</command> is in,
955           and <command>$P2_NET</command> the IP network <command>$P2</command> is in.
956         </para>
957         <para>
958           One creates two additional routing tables, say <command>T1</command> and <command>T2</command>.
959           These are added in /etc/iproute2/rt_tables. Then you set up routing in
960           these tables as follows:
961         </para>
962         <para>
963         <screen>
964           ip route add $P1_NET dev $IF1 src $IP1 table T1
965           ip route add default via $P1 table T1
966           ip route add $P2_NET dev $IF2 src $IP2 table T2
967           ip route add default via $P2 table T2
968         </screen>
969           
970           Nothing spectacular, just build a route to the gateway and build a
971           default route via that gateway, as you would do in the case of a single
972           upstream provider, but put the routes in a separate table per provider.
973           Note that the network route suffices, as it tells you how to find any host
974           in that network, which includes the gateway, as specified above.
975         </para>
976         <para>
977           Next you set up the main routing table. It is a good idea to route
978           things to the direct neighbour through the interface connected to that
979           neighbour. Note the `src' arguments, they make sure the right outgoing IP
980           address is chosen.
982           <screen>
983             ip route add $P1_NET dev $IF1 src $IP1
984             ip route add $P2_NET dev $IF2 src $IP2
985           </screen>
987           Then, your preference for default route:
988           
989           <screen>
990             ip route add default via $P1
991           </screen>
993           Next, you set up the routing rules. These actually choose what routing table
994           to route with. You want to make sure that you route out a given
995           interface if you already have the corresponding source address:
996           
997           <screen>
998             ip rule add from $IP1 table T1
999             ip rule add from $IP2 table T2
1000           </screen>
1002           This set of commands makes sure all answers to traffic coming in on a
1003           particular interface get answered from that interface.
1004         </para>
1005         <para>
1006         <warning><para>
1007 Reader Rod Roark notes: 'If $P0_NET is the local network and $IF0 is its interface,
1008 the following additional entries are desirable:
1009 <screen>
1010 ip route add $P0_NET     dev $IF0 table T1
1011 ip route add $P2_NET     dev $IF2 table T1
1012 ip route add 127.0.0.0/8 dev lo   table T1
1013 ip route add $P0_NET     dev $IF0 table T2
1014 ip route add $P1_NET     dev $IF1 table T2
1015 ip route add 127.0.0.0/8 dev lo   table T2                                      
1016 </screen>'
1017 </para></warning</para>
1018         <para>
1019           Now, this is just the very basic setup. It will work for all processes
1020           running on the router itself, and for the local network, if it is
1021           masqueraded. If it is not, then you either have IP space from both providers
1022           or you are going to want to masquerade to one of the two providers. In both
1023           cases you will want to add rules selecting which provider to route out from
1024           based on the IP address of the machine in the local network.
1025         </para>
1026       </sect2>
1027       <sect2><title>Load balancing</title>
1028         <para>
1029           The second question is how to balance traffic going out over the two providers.
1030           This is actually not hard if you already have set up split access as above.
1031           </para>
1032         <para>
1033           Instead of choosing one of the two providers as your default route,
1034           you now set up the default route to be a multipath route. In the default
1035           kernel this will balance routes over the two providers. It is done
1036           as follows (once more building on the example in the section on
1037           split-access):
1039           <screen>
1040             ip route add default scope global nexthop via $P1 dev $IF1 weight 1 \
1041             nexthop via $P2 dev $IF2 weight 1
1042           </screen>
1044           This will balance the routes over both providers. The <command>weight</command>
1045           parameters can be tweaked to favor one provider over the other.
1046         </para>
1047         <para>
1048           Note that balancing will not be perfect, as it is route based, and routes
1049           are cached. This means that routes to often-used sites will always
1050           be over the same provider.
1051         </para>
1052         <para>
1053           Furthermore, if you really want to do this, you probably also want to look
1054           at Julian Anastasov's patches at <ulink url="http://www.ssi.bg/~ja/#routes">http://www.ssi.bg/~ja/#routes 
1055             </ulink>, Julian's route patch page. They will make things nicer to work with.
1056         </para>
1057       </sect2>
1058     </sect1>
1059   </chapter>
1061 <chapter id="lartc.tunnel">
1062    <Title>GRE and other tunnels</Title>
1064 <Para>
1065 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). 
1066 </Para>
1068 <Sect1 id="lartc.tunnel.remarks">
1069   <Title>A few general remarks about tunnels:</Title>
1071 <Para>
1072 Tunnels can be used to do some very unusual and very cool stuff. They can
1073 also make things go horribly wrong when you don't configure them right.
1074 Don't point your default route to a tunnel device unless you know
1075 <Emphasis>EXACTLY</Emphasis> what you are doing :-). Furthermore, tunneling increases
1076 overhead, because it needs an extra set of IP headers. Typically this is 20
1077 bytes per packet, so if the normal packet size (MTU) on a network is 1500
1078 bytes, a packet that is sent through a tunnel can only be 1480 bytes big.
1079 This is not necessarily a problem, but be sure to read up on IP packet
1080 fragmentation/reassembly when you plan to connect large networks with
1081 tunnels. Oh, and of course, the fastest way to dig a tunnel is to dig at
1082 both sides.
1083 </Para>
1085 </Sect1>
1087 <Sect1 id="lartc.tunnel.ip-ip">
1088   <Title>IP in IP tunneling</Title>
1090 <Para>
1091 This kind of tunneling has been available in Linux for a long time. It requires 2 kernel modules,
1092 ipip.o and new_tunnel.o.
1093 </Para>
1095 <Para>
1096 Let's say you have 3 networks: Internal networks A and B, and intermediate network C (or let's say, Internet). 
1097 So we have network A:
1098 </Para>
1100 <Screen width="80">
1101 network 10.0.1.0
1102 netmask 255.255.255.0
1103 router  10.0.1.1
1104 </Screen>
1106 <Para>The router has address 172.16.17.18 on network C.
1107 </Para>
1109 <Para>and network B:
1110 </Para>
1112 <Screen width="80">
1113 network 10.0.2.0
1114 netmask 255.255.255.0
1115 router  10.0.2.1
1116 </Screen>
1118 <Para>The router has address 172.19.20.21 on network C.
1119 </Para>
1121 <Para>
1122 As far as network C is concerned, we assume that it will pass any packet sent
1123 from A to B and vice versa. You might even use the Internet for this.
1124 </Para>
1126 <Para>Here's what you do:
1127 </Para>
1129 <Para>First, make sure the modules are installed:
1130 </Para>
1132 <Screen width="80">
1133 insmod ipip.o
1134 insmod new_tunnel.o
1135 </Screen>
1137 <Para>Then, on the router of network A, you do the following:
1138 </Para>
1140 <Screen width="80">
1141 ifconfig tunl0 10.0.1.1 pointopoint 172.19.20.21
1142 route add -net 10.0.2.0 netmask 255.255.255.0 dev tunl0
1143 </Screen>
1145 <Para>And on the router of network B:
1146 </Para>
1148 <Screen width="80">
1149 ifconfig tunl0 10.0.2.1 pointopoint 172.16.17.18
1150 route add -net 10.0.1.0 netmask 255.255.255.0 dev tunl0
1151 </Screen>
1153 <Para>And if you're finished with your tunnel:
1154 </Para>
1156 <Screen width="80">
1157 ifconfig tunl0 down
1158 </Screen>
1160 <Para>Presto, you're done. You can't forward broadcast or IPv6 traffic through
1161 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.
1162 </Para>
1164 </Sect1>
1166 <Sect1 id="lartc.tunnel.gre">
1167   <Title>GRE tunneling</Title>
1169 <Para>
1170 GRE is a tunneling protocol that was originally developed by Cisco, and it
1171 can do a few more things than IP-in-IP tunneling. For example, you can also
1172 transport multicast traffic and IPv6 through a GRE tunnel.
1173 </Para>
1175 <Para>
1176 In Linux, you'll need the ip_gre.o module.
1177 </Para>
1179 <Sect2>
1180 <Title>IPv4 Tunneling</Title>
1182 <Para>
1183 Let's do IPv4 tunneling first:
1184 </Para>
1186 <Para>
1187 Let's say you have 3 networks: Internal networks A and B, and intermediate network C (or let's say, Internet). 
1188 </Para>
1190 <Para>
1191 So we have network A:
1193 <Screen width="80">
1194 network 10.0.1.0
1195 netmask 255.255.255.0
1196 router  10.0.1.1
1197 </Screen>
1199 The router has address 172.16.17.18 on network C.
1200 Let's call this network neta (ok, hardly original)
1201 </Para>
1203 <Para>
1204 and network B:
1206 <Screen width="80">
1207 network 10.0.2.0
1208 netmask 255.255.255.0
1209 router  10.0.2.1
1210 </Screen>
1212 The router has address 172.19.20.21 on network C.
1213 Let's call this network netb (still not original)
1214 </Para>
1216 <Para>
1217 As far as network C is concerned, we assume that it will pass any packet sent
1218 from A to B and vice versa. How and why, we do not care.
1219 </Para>
1221 <Para>On the router of network A, you do the following:
1222 </Para>
1224 <Screen width="80">
1225 ip tunnel add netb mode gre remote 172.19.20.21 local 172.16.17.18 ttl 255
1226 ip link set netb up
1227 ip addr add 10.0.1.1 dev netb
1228 ip route add 10.0.2.0/24 dev netb
1229 </Screen>
1231 <Para>
1232 Let's discuss this for a bit. In line 1, we added a tunnel device, and
1233 called it netb (which is kind of obvious because that's where we want it to
1234 go). Furthermore we told it to use the GRE protocol (mode gre), that the
1235 remote address is 172.19.20.21 (the router at the other end), that our
1236 tunneling packets should originate from 172.16.17.18 (which allows your
1237 router to have several IP addresses on network C and let you decide which
1238 one to use for tunneling) and that the TTL field of the packet should be set
1239 to 255 (ttl 255).
1240 </Para>
1242 <Para>
1243 The second line enables the device.
1244 </Para>
1246 <Para>
1247 In the third line we gave the newly born interface netb the address
1248 10.0.1.1. This is OK for smaller networks, but when you're starting up a
1249 mining expedition (LOTS of tunnels), you might want to consider using
1250 another IP range for tunneling interfaces (in this example, you could use
1251 10.0.3.0).
1252 </Para>
1254 <Para>
1255 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.
1256 </Para>
1258 <Para>
1259 But enough about this, let's go on with the router of network B.
1261 <Screen>
1262 ip tunnel add neta mode gre remote 172.16.17.18 local 172.19.20.21 ttl 255
1263 ip link set neta up
1264 ip addr add 10.0.2.1 dev neta
1265 ip route add 10.0.1.0/24 dev neta
1266 </Screen>
1268 And when you want to remove the tunnel on router A:
1270 <Screen>
1271 ip link set netb down
1272 ip tunnel del netb
1273 </Screen>
1275 Of course, you can replace netb with neta for router B.
1276 </Para>
1278 </Sect2>
1280 <Sect2>
1281 <Title>IPv6 Tunneling</Title>
1283 <Para>
1284 See Section 6 for a short bit about IPv6 Addresses.
1285 </Para>
1287 <Para>
1288 On with the tunnels.
1289 </Para>
1291 <Para>
1292 Let's assume that you have the following IPv6 network, and you want to connect it to 6bone, or a friend.
1293 </Para>
1295 <Para>
1297 <Screen>
1298 Network 3ffe:406:5:1:5:a:2:1/96
1299 </Screen>
1301 Your IPv4 address is 172.16.17.18, and the 6bone router has IPv4 address 172.22.23.24. 
1302 </Para>
1304 <Para>
1306 <Screen>
1307 ip tunnel add sixbone mode sit remote 172.22.23.24 local 172.16.17.18 ttl 255
1308 ip link set sixbone up
1309 ip addr add 3ffe:406:5:1:5:a:2:1/96 dev sixbone
1310 ip route add 3ffe::/15 dev sixbone 
1311 </Screen>
1313 </Para>
1315 <Para>
1316 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.
1317 </Para>
1319 <Para>
1320 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.
1321 </Para>
1323 </Sect2>
1325 </Sect1>
1327 <Sect1 id="lartc.tunnel.userland">
1328   <Title>Userland tunnels</Title>
1330 <Para>
1331 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.
1332 </Para>
1334 </Sect1>
1336 </chapter>
1338 <chapter id="lartc.ipv6-tunnel">
1339 <Title>IPv6 tunneling with Cisco and/or 6bone</Title>
1341 <Para>
1342 By Marco Davids &lt;marco@sara.nl&gt;
1343 </Para>
1345 <Para>
1346 NOTE to maintainer:
1347 </Para>
1349 <Para>
1350 As far as I am concerned, this IPv6-IPv4 tunneling is not per definition
1351 GRE tunneling. You could tunnel IPv6 over IPv4 by means of GRE tunnel devices
1352 (GRE tunnels ANY to IPv4), but the device used here ("sit") only tunnels
1353 IPv6 over IPv4 and is therefore something different.
1354 </Para>
1356 <Sect1 id="lartc.tunnel-ipv6.addressing">
1357   <Title>IPv6 Tunneling</Title>
1359 <Para>
1360 This is another application of the tunneling capabilities of Linux. It is
1361 popular among the IPv6 early adopters, or pioneers if you like.
1362 The 'hands-on' example described below is certainly not the only way
1363 to do IPv6 tunneling. However, it is the method that is often used to tunnel
1364 between Linux and a Cisco IPv6 capable router and experience tells us that
1365 this is just the thing many people are after. Ten to one this applies to
1366 you too ;-)
1367 </Para>
1369 <Para>
1370 A short bit about IPv6 addresses:
1371 </Para>
1373 <Para>
1374 IPv6 addresses are, compared to IPv4 addresses, really big: 128 bits
1375 against 32 bits. And this provides us just with the thing we need: many, many
1376 IP-addresses: 340,282,266,920,938,463,463,374,607,431,768,211,465 to be
1377 precise. Apart from this, IPv6 (or IPng, for IP Next Generation) is supposed
1378 to provide for smaller routing tables on the Internet's backbone routers,
1379 simpler configuration of equipment, better security at the IP level and
1380 better support for QoS.
1381 </Para>
1383 <Para>
1384 An example: 2002:836b:9820:0000:0000:0000:836b:9886
1385 </Para>
1387 <Para>
1388 Writing down IPv6 addresses can be quite a burden. Therefore, to make
1389 life easier there are some rules:
1390 </Para>
1392 <Para>
1394 <ItemizedList>
1395 <ListItem>
1397 <Para>
1398 Don't use leading zeroes. Same as in IPv4.
1400 </Para>
1401 </ListItem>
1402 <ListItem>
1404 <Para>
1405 Use colons to separate every 16 bits or two bytes.
1407 </Para>
1408 </ListItem>
1409 <ListItem>
1411 <Para>
1412 When you have lots of consecutive zeroes,
1413 you can write this down as ::. You can only do this once in an
1414 address and only for quantities of 16 bits, though.
1415 </Para>
1416 </ListItem>
1418 </ItemizedList>
1420 </Para>
1422 <Para>
1423 The address 2002:836b:9820:0000:0000:0000:836b:9886 can be written down
1424 as 2002:836b:9820::836b:9886, which is somewhat friendlier.
1425 </Para>
1427 <Para>
1428 Another example, the address 3ffe:0000:0000:0000:0000:0020:34A1:F32C can be
1429 written down as 3ffe::20:34A1:F32C, which is a lot shorter.
1430 </Para>
1432 <Para>
1433 IPv6 is intended to be the successor of the current IPv4. Because it
1434 is relatively new technology, there is no worldwide native IPv6 network
1435 yet. To be able to move forward swiftly, the 6bone was introduced. 
1436 </Para>
1438 <Para>
1439 Native IPv6 networks are connected to each other by encapsulating the IPv6
1440 protocol in IPv4 packets and sending them over the existing IPv4 infrastructure
1441 from one IPv6 site to another. 
1442 </Para>
1444 <Para>
1445 That is precisely where the tunnel steps in.
1446 </Para>
1448 <Para>
1449 To be able to use IPv6, we should have a kernel that supports it. There
1450 are many good documents on how to achieve this. But it all comes down to
1451 a few steps:
1453 <ItemizedList>
1454 <ListItem>
1456 <Para>
1457 Get yourself a recent Linux distribution, with suitable glibc.
1458 </Para>
1459 </ListItem>
1460 <ListItem>
1462 <Para>
1463 Then get yourself an up-to-date kernel source.
1464 </Para>
1465 </ListItem>
1467 </ItemizedList>
1469 If you are all set, then you can go ahead and compile an IPv6 capable
1470 kernel:
1472 <ItemizedList>
1473 <ListItem>
1475 <Para>
1476 Go to /usr/src/linux and type:
1477 </Para>
1478 </ListItem>
1479 <ListItem>
1481 <Para>
1482 make menuconfig
1483 </Para>
1484 </ListItem>
1485 <ListItem>
1487 <Para>
1488 Choose "Networking Options"
1489 </Para>
1490 </ListItem>
1491 <ListItem>
1493 <Para>
1494 Select "The IPv6 protocol", "IPv6: enable EUI-64 token format", "IPv6:
1495 disable provider based addresses"
1496 </Para>
1497 </ListItem>
1499 </ItemizedList>
1501 HINT: Don't go for the 'module' option. Often this won't work well.
1502 </Para>
1504 <Para>
1505 In other words, compile IPv6 as 'built-in' in your kernel.
1506 You can then save your config like usual and go ahead with compiling
1507 the kernel.
1508 </Para>
1510 <Para>
1511 HINT: Before doing so, consider editing the Makefile:
1512 EXTRAVERSION = -x ; --&#62; ; EXTRAVERSION = -x-IPv6
1513 </Para>
1515 <Para>
1516 There is a lot of good documentation about compiling and installing
1517 a kernel, however this document is about something else. If you run into
1518 problems at this stage, go and look for documentation about compiling a
1519 Linux kernel according to your own specifications.
1520 </Para>
1522 <Para>
1523 The file /usr/src/linux/README might be a good start.
1524 After you accomplished all this, and rebooted with your brand new kernel,
1525 you might want to issue an '/sbin/ifconfig -a' and notice the brand 
1526 new 'sit0-device'. SIT stands for Simple Internet Transition. You may give
1527 yourself a compliment; you are now one major step closer to IP, the Next
1528 Generation ;-)
1529 </Para>
1531 <Para>
1532 Now on to the next step. You want to connect your host, or maybe even
1533 your entire LAN to another IPv6 capable network. This might be the "6bone"
1534 that is setup especially for this particular purpose.
1535 </Para>
1537 <Para>
1538 Let's assume that you have the following IPv6 network: 3ffe:604:6:8::/64 and
1539 you want to connect it to 6bone, or a friend. Please note that the /64
1540 subnet notation works just like with regular IP addresses.
1541 </Para>
1543 <Para>
1544 Your IPv4 address is 145.100.24.181 and the 6bone router has IPv4 address
1545 145.100.1.5
1546 </Para>
1548 <Screen width="80">
1549 # ip tunnel add sixbone mode sit remote 145.100.1.5 [local 145.100.24.181 ttl 255]
1550 # ip link set sixbone up
1551 # ip addr add 3FFE:604:6:7::2/126 dev sixbone
1552 # ip route add 3ffe::0/16 dev sixbone
1553 </Screen>
1555 <Para>
1556 Let's discuss this. In the first line, we created a tunnel device called
1557 sixbone. We gave it mode sit (which is IPv6 in IPv4 tunneling) and told it
1558 where to go to (remote) and where to come from (local). TTL is set to
1559 maximum, 255. 
1560 </Para>
1562 <Para>
1563 Next, we made the device active (up). After that, we added our own network
1564 address, and set a route for 3ffe::/15 (which is currently all of 6bone)
1565 through the tunnel. If the particular machine you run this on is your IPv6
1566 gateway, then consider adding the following lines:
1567 </Para>
1569 <Screen width="80">
1570 # echo 1 &#62;/proc/sys/net/ipv6/conf/all/forwarding
1571 # /usr/local/sbin/radvd
1572 </Screen>
1574 <Para>
1575 The latter, radvd is -like zebra- a router advertisement daemon, to
1576 support IPv6's autoconfiguration features. Search for it with your favourite
1577 search-engine if you like.
1578 You can check things like this:
1579 </Para>
1581 <Screen width="80">
1582 # /sbin/ip -f inet6 addr
1583 </Screen>
1585 <Para>
1586 If you happen to have radvd running on your IPv6 gateway and boot your
1587 IPv6 capable Linux on a machine on your local LAN, you would be able to
1588 enjoy the benefits of IPv6 autoconfiguration:
1589 </Para>
1591 <Screen width="80">
1592 # /sbin/ip -f inet6 addr
1593 1: lo: &lt;LOOPBACK,UP&gt; mtu 3924 qdisc noqueue inet6 ::1/128 scope host
1595 3: eth0: &lt;BROADCAST,MULTICAST,UP&gt; mtu 1500 qdisc pfifo_fast qlen 100
1596 inet6 3ffe:604:6:8:5054:4cff:fe01:e3d6/64 scope global dynamic
1597 valid_lft forever preferred_lft 604646sec inet6 fe80::5054:4cff:fe01:e3d6/10 
1598 scope link
1599 </Screen>
1601 <Para>
1602 You could go ahead and configure your bind for IPv6 addresses. The A
1603 type has an equivalent for IPv6: AAAA. The in-addr.arpa's equivalent is:
1604 ip6.int. There's a lot of information available on this topic.
1605 </Para>
1607 <Para>
1608 There is an increasing number of IPv6-aware applications available,
1609 including secure shell, telnet, inetd, Mozilla the browser, Apache the
1610 webserver and a lot of others. But this is all outside the scope of this
1611 Routing document ;-)
1612 </Para>
1614 <Para>
1615 On the Cisco side the configuration would be something like this:
1617 <Screen>
1619 interface Tunnel1
1620 description IPv6 tunnel
1621 no ip address
1622 no ip directed-broadcast
1623 ipv6 address 3FFE:604:6:7::1/126
1624 tunnel source Serial0
1625 tunnel destination 145.100.24.181
1626 tunnel mode ipv6ip
1628 ipv6 route 3FFE:604:6:8::/64 Tunnel1
1629 </Screen>
1631 But if you don't have a Cisco at your disposal, try one of the many
1632 IPv6 tunnel brokers available on the Internet. They are willing to configure
1633 their Cisco with an extra tunnel for you. Mostly by means of a friendly
1634 web interface. Search for "ipv6 tunnel broker" on your favourite search engine.
1635 </Para>
1637 </Sect1>
1639 </chapter>
1641   <chapter id="lartc.ipsec">
1642     <Title>IPSEC: secure IP over the Internet</Title>
1643     <Para>
1645       There are two kinds of IPSEC available for Linux these days. For 2.2
1646       and 2.4, there is FreeS/WAN, which was the first major implementation. They
1648       have <ULink URL="http://www.freeswan.org/">an official site</ulink> and <ulink url="http://www.freeswan.ca">
1649         an unofficial one</ulink> that is actually maintained. FreeS/WAN has traditionally not been merged with
1650       the mainline kernel for a number of reasons. Most often mentioned are 'political' issues with Americans
1651       working on crypto tainting its exportability. Furthermore, it does not integrate too well with the Linux kernel,
1652       leading it to be a bad candidate for actual merging. 
1653     </para>
1654     <para>
1655       Additionally, <ulink
1656 url="http://www.edlug.ed.ac.uk/archive/Sep2002/msg00244.html">many</ulink> parties <ulink
1657 url="http://lists.freeswan.org/pipermail/design/2002-November/003901.html">have voiced
1658 worries</ulink> about the quality of the code. To setup FreeS/WAN, a lot of
1659 <ulink
1660 url="http://www.freeswan.ca/docs/freeswan-1.99/doc/index.html">documentation</ulink>
1661 is <ulink url="http://www.freeswan.org/doc.html">available</ulink>.
1662     </para>
1663     <para>
1664       As of Linux 2.5.47, there is a native IPSEC implementation in the kernel. It was written by Alexey Kuznetsov and
1665       Dave Miller, inspired by the work of the USAGI IPv6 group. With its merge, James Morris' CrypoAPI also became 
1666       part of the kernel - it does the actual crypting.
1667     </para>
1668     <para>
1669       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
1670       that its configuration will differ from the native IPSEC. In related
1671 news, there are now <ulink
1672 url="http://gondor.apana.org.au/~herbert/freeswan/">patches</ulink> to make the FreeS/WAN userspace code work with
1673 the native Linux IPSEC.
1674     </para>
1675     <para>
1676         As of 2.5.49, IPSEC works without further patches.
1677         </para>
1678         <para>
1679       <note>
1680         <para>
1681           Userspace tools appear to be available <ulink
1682           url="http://sourceforge.net/projects/ipsec-tools">here</ulink>.
1683 There are multiple programs available, the one linked here is based on
1684 Racoon. 
1685         </para>
1686         <para>
1687         When compiling your kernel, be sure to turn on 'PF_KEY', 'AH', 'ESP' and
1688 everything in the CryptoAPI!
1689         </para>
1690       </note>
1691       <warning>
1692         <para>
1693           The author of this chapter is a complete IPSEC nitwit! If you find the inevitable mistakes, please email
1694           bert hubert <email>ahu@ds9a.nl</email>. 
1695         </para>
1696       </warning>
1697     </Para>
1698     <para>
1699       First, we'll show how to manually setup secure communication between
1700       two hosts. A large part of this process can also be automated, but
1701 here we'll do it by hand so as to acquaint ourselves with what is going on
1702 'under the hood'. 
1703     </para>
1704     <para>
1705         Feel free to skip the following section if you are only interested
1706 in automatic keying but be aware that some understanding of manual keying is
1707 useful. 
1708     </para>
1709     <sect1 id="lartc.ipsec.intro"><title>Intro with Manual Keying</title>
1710       <para>
1711         IPSEC is a complicated subject. A lot of information is available online, this HOWTO will concentrate on getting you
1712         up and running and explaining the basic principles. All examples are
1713 based on Racoon as found on the link above.
1714       </para>
1715       <para>
1716         <note>
1717           <para>
1718             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'
1719           </para>
1720         </note>
1721       </para>
1722       <para>
1723         IPSEC offers a secure version of the Internet Protocol. Security in this context means two different things: encryption and authentication. 
1724         A naive vision of security offers only encryption but it can easily be shown that is insufficient - you may be communicating encyphered,
1725         but no guarantee is offered that the remote party is the one you expect it to be.
1726       </para>
1727       <para>
1728         IPSEC supports 'Encapsulated Security Payload' (ESP) for encryption and 'Authentication Header' (AH) for authenticating the remote partner.
1729         You can configure both of them, or decided to do only either.
1730       </para>
1731       <para>
1732         Both ESP and AH rely on security associations. A security association (SA) consists of a source, a destination and an instruction. A sample 
1733         authentication SA may look like this:
1734         <screen>
1735           add 10.0.0.11 10.0.0.216 ah 15700 -A hmac-md5 "1234567890123456";
1736         </screen>
1737         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
1738         is labelled with SPI ('Security Parameter Index') id '15700', more about that later.
1739         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
1740         other side. Do note however that there is no 'autoreverse' rule - this SA only describes a possible authentication from 10.0.0.11 to 
1741         10.0.0.216. For two-way traffic, two SAs are needed.
1742       </para>
1743       <para>
1744         A sample ESP SA:
1745         <screen>
1746 add 10.0.0.11 10.0.0.216 esp 15701 -E 3des-cbc "123456789012123456789012";
1747         </screen>
1748         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
1749         SPI id is '15701'.
1750       </para>
1751       <para>
1752         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,
1753         there could be an arbitrary number of nearly identical SAs with only differing SPI ids. Incidentally, SPI stands for Security Parameter Index.
1754         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'.
1755       </para>
1756       <para>
1757         A typical simple Security Policy (SP) looks like this:
1758         <screen>
1759 spdadd 10.0.0.216 10.0.0.11 any -P out ipsec
1760    esp/transport//require
1761    ah/transport//require;
1762         </screen>
1763         If entered on host 10.0.0.216, this means that all traffic going out to 10.0.0.11 must be encrypted 
1764         and be wrapped in an AH authenticating header. Note that this does not describe which SA is to be used,
1765         that is left as an exercise for the kernel to determine.
1766       </para>
1767         <para>
1768         In other words, a Security Policy specifies WHAT we want; a Security
1769 Association describes HOW we want it. 
1770 </para>
1771       <para>
1772         Outgoing packets are labelled with the SA SPI ('the how') which the
1773         kernel used for encryption and authentication so the remote can
1774         lookup the corresponding verification and decryption instruction.
1775       </para>
1777       <para>
1778         What follows is a very simple configuration for talking from host 10.0.0.216 to 10.0.0.11 using 
1779         encryption and authentication. Note that the reverse path is plaintext in this first version and that
1780         this configuration should not be deployed.
1781       </para>
1782       <para>
1783         On host 10.0.0.216:
1784         <screen>
1785 #!/sbin/setkey -f
1786 add 10.0.0.216 10.0.0.11 ah 24500 -A hmac-md5 "1234567890123456";          
1787 add 10.0.0.216 10.0.0.11 esp 24501 -E 3des-cbc "123456789012123456789012";
1789 spdadd 10.0.0.216 10.0.0.11 any -P out ipsec
1790    esp/transport//require
1791    ah/transport//require;
1792         </screen>
1793       </para>
1794       <para>
1795         On host 10.0.0.11, the same Security Associations, no Security Policy:
1796         <screen>
1797 #!/sbin/setkey -f
1798 add 10.0.0.216 10.0.0.11 ah 24500 -A hmac-md5 "1234567890123456";
1799 add 10.0.0.216 10.0.0.11 esp 24501 -E 3des-cbc "123456789012123456789012";
1800         </screen>
1801       </para>
1802       <para>
1803         With the above configuration in place (these files can be executed if 'setkey' is installed in /sbin),
1804         'ping 10.0.0.11' from 10.0.0.216 looks like this using tcpdump:
1805         <screen>
1806 22:37:52 10.0.0.216 &gt; 10.0.0.11: AH(spi=0x00005fb4,seq=0xa): ESP(spi=0x00005fb5,seq=0xa) (DF)
1807 22:37:52 10.0.0.11 &gt; 10.0.0.216: icmp: echo reply
1808         </screen>
1809         Note how the ping back from 10.0.0.11 is indeed plainly visible. The forward ping cannot be read by tcpdump
1810         of course, but it does show the Security Parameter Index of AH and ESP, which tells 10.0.0.11 how to 
1811         verify the authenticity of our packet and how to decrypt it.
1812       </para>
1813       <para>
1814         A few things must be mentioned however. The configuration above is shown in a lot of IPSEC examples and it is very dangerous.
1815         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
1816         should treat those packets but it does NOT instruct 10.0.0.11 to discard unauthenticated or unencrypted traffic! 
1817       </para>
1818       <para>
1819         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 
1820         Security Policy on 10.0.0.11, as follows:
1821         <screen>
1822 #!/sbin/setkey -f 
1823 spdadd 10.0.0.216 10.0.0.11 any -P IN ipsec
1824    esp/transport//require
1825    ah/transport//require;
1826         </screen>
1827         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.
1828       </para>
1829       <para>
1830         Now, to complete this configuration, we need return traffic to be encrypted and authenticated as well of course. The full configuration on
1831         10.0.0.216:
1832         <screen>
1833 #!/sbin/setkey -f
1834 flush;
1835 spdflush;
1837 # AH
1838 add 10.0.0.11 10.0.0.216 ah 15700 -A hmac-md5 "1234567890123456";
1839 add 10.0.0.216 10.0.0.11 ah 24500 -A hmac-md5 "1234567890123456";
1841 # ESP
1842 add 10.0.0.11 10.0.0.216 esp 15701 -E 3des-cbc "123456789012123456789012";
1843 add 10.0.0.216 10.0.0.11 esp 24501 -E 3des-cbc "123456789012123456789012";
1845 spdadd 10.0.0.216 10.0.0.11 any -P out ipsec
1846            esp/transport//require
1847            ah/transport//require;
1849 spdadd 10.0.0.11 10.0.0.216 any -P in ipsec
1850            esp/transport//require
1851            ah/transport//require;
1852           
1853         </screen>
1854       </para>
1855       <para>
1856         And on 10.0.0.11:
1857         <screen>
1858 #!/sbin/setkey -f
1859 flush;
1860 spdflush;
1862 # AH
1863 add 10.0.0.11 10.0.0.216 ah 15700 -A hmac-md5 "1234567890123456";
1864 add 10.0.0.216 10.0.0.11 ah 24500 -A hmac-md5 "1234567890123456";
1866 # ESP
1867 add 10.0.0.11 10.0.0.216 esp 15701 -E 3des-cbc "123456789012123456789012";
1868 add 10.0.0.216 10.0.0.11 esp 24501 -E 3des-cbc "123456789012123456789012";
1871 spdadd 10.0.0.11 10.0.0.216 any -P out ipsec
1872            esp/transport//require
1873            ah/transport//require;
1875 spdadd 10.0.0.216 10.0.0.11 any -P in ipsec
1876            esp/transport//require
1877            ah/transport//require;
1879         </screen>
1880       </para>
1881       <para>
1882         Note that in this example we used identical keys for both directions of traffic. This is not in any way required however.
1883       </para>
1884       <para>
1885         To examine the configuration we just created, execute <command>setkey -D</command>, which shows the Security Associations or 
1886         <command>setkey -DP</command> which shows the configured policies.
1887       </para>
1888     </sect1>
1889     <sect1 id="lartc.ipsec.automatic.keying"><title>Automatic keying</title>
1890       <para>
1891         In the previous section, encryption was configured using simple shared secrets. In other words, to remain secure,
1892         we need to transfer our encryption configuration over a trusted channel. If we were to configure the remote host 
1893         over telnet, any third party would know our shared secret and the setup would not be secure.
1894       </para>
1895       <para>
1896         Furthermore, because the secret is shared, it is not a secret. The remote can't do a lot with our secret, but we do 
1897         need to make sure that we use a different secret for communicating with all our partners. This requires a large number of keys,
1898         if there are 10 parties, this needs at least 50 different secrets. 
1899       </para>
1900       <para>
1901         Besides the symmetric key problem, there is also the need for key rollover. If a third party manages to sniff enough traffic,
1902         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
1903         a process that needs to be automated.
1904       </para>
1905       <para>
1906         Another problem is that with manual keying as described above we exactly define the algorithms and key lengths used, something
1907         that requires a lot of coordination with the remote party. It is desirable to be able to have the ability to describe a 
1908         broader key policy such as 'We can do 3DES and Blowfish with at least the following key lengths'.
1909       </para>
1910       <para>
1911         To solve these isses, IPSEC provides Internet Key Exchange to automatically exchange randomly generated keys which are
1912         transmitted using asymmetric encryption technology, according to negotiated algorithm details.
1913       </para>
1914       <para>
1915         The Linux 2.5 IPSEC implementation works with the KAME 'racoon' IKE
1916         daemon. As of 9 November, the racoon version in Alexey's iptools
1917         distribution can be compiled, although you may need to remove 
1918 #include &lt;net/route.h&gt; in two files. Alternatively, I've supplied a
1919 <ulink url="http://ds9a.nl/ipsec/racoon.bz2">precompiled version</ulink>.
1920       </para>
1921         <para>
1922         <note>
1923           <para>
1924                 IKE needs access to UDP port 500, be sure that iptables does
1925 not block it.
1926           </para>
1927         </note>
1928         </para>
1929         <sect2 id="lartc.ipsec.keying.theory"><title>Theory</title>
1930         <para>
1931                 As explained before, automatic keying does a lot of the work
1932 for us. Specifically, it creates Security Associations on the fly. It does
1933 not however set policy for us, which is as it should be.
1934         </para>
1935         <para>
1936         So, to benefit from IKE, setup a policy, but do not supply any
1937 SAs. If the kernel discovers that there is an IPSEC policy, but no Security
1938 Association, it will notify the IKE daemon, which then goes to work on
1939 trying to negotiate one.
1940         </para>
1941         <para>
1942         Reiterating, a Security Policy specifies WHAT we want; a Security
1943 Association describes HOW we want it. Using automatic keying lets us get
1944 away with only specifying what we want.
1945         </para>
1946 </sect2>
1947         <sect2 id="lartc.ipsec.automatic.keying.example"><title>Example</title>
1948         <para>
1949         Kame racoon comes with a grand host of options, most of which have
1950 very fine default values, so we don't need to touch them. As described
1951 above, the operator needs to define a Security Policy, but no Security
1952 Associations. We leave their negotiation to the IKE daemon.
1953         </para>
1954         <para>
1955         In this example, 10.0.0.11 and 10.0.0.216 are once again going to
1956 setup secure communications, but this time with help from racoon. For
1957 simplicity this configuration will be using pre-shared keys, the
1958 dreaded 'shared secrets'. X.509 certificates are discussed in a separate
1959 section, see <xref linkend="lartc.ipsec.x509">.
1960 </para>
1961 <para> We're
1962 going to stick to almost the default configuration, identical on both hosts:
1963         </para> 
1964         <para>
1965 <screen>
1966 path pre_shared_key "/usr/local/etc/racoon/psk.txt";
1968 remote anonymous
1970         exchange_mode aggressive,main;
1971         doi ipsec_doi;
1972         situation identity_only;
1974         my_identifier address;
1976         lifetime time 2 min;   # sec,min,hour
1977         initial_contact on;
1978         proposal_check obey;    # obey, strict or claim
1980         proposal {
1981                 encryption_algorithm 3des;
1982                 hash_algorithm sha1;
1983                 authentication_method pre_shared_key;
1984                 dh_group 2 ;
1985         }
1988 sainfo anonymous
1990         pfs_group 1;
1991         lifetime time 2 min;
1992         encryption_algorithm 3des ;
1993         authentication_algorithm hmac_sha1;
1994                 compression_algorithm deflate ;
1996 </screen>
1997         </para>
1998         <para>
1999         Lots of settings - I think yet more can be removed to get closer to
2000 the default configuration. A few noteworthy things. We've configured two
2001 anonymous settings which hold for all remotes, making further configuration
2002 easy. There is no need for per-host stanzas here, unless we really want
2003 them.
2004 </para>
2005         <para>
2006         Furthermore, we've set it up such that we identify ourselves based
2007 on our IP address ('my_identifier address'), and declare that we can do
2008 3des, sha1, and that we will be using a pre-shared key, located in psk.txt.
2009         </para>
2010         <para>
2011         In psk.txt, we now setup two entries, which do differ on both hosts.
2012 On 10.0.0.11:
2013 <screen>
2014 10.0.0.216      password2
2015 </screen>
2016 On 10.0.0.216:
2017 <screen>
2018 10.0.0.11       password2
2019 </screen>
2020         Make sure these files are owned by root, and set to mode 0600,
2021 racoon will not trust their contents otherwise. Note that these files are
2022 mirrors from eachother.
2023         </para>
2024         <para>
2025         Now we are ready to setup our desired policy, which is simple
2026 enough. On host 10.0.0.216:
2027 <screen>
2028 #!/sbin/setkey -f
2029 flush;
2030 spdflush;
2032 spdadd 10.0.0.216 10.0.0.11 any -P out ipsec
2033         esp/transport//require;
2035 spdadd 10.0.0.11 10.0.0.216 any -P in ipsec
2036         esp/transport//require;
2037 </screen>
2038 And on 10.0.0.11:
2039 <screen>
2040 #!/sbin/setkey -f
2041 flush;
2042 spdflush;
2044 spdadd 10.0.0.11 10.0.0.216 any -P out ipsec
2045         esp/transport//require;
2047 spdadd 10.0.0.216 10.0.0.11 any -P in ipsec
2048         esp/transport//require;
2049 </screen>
2050 Note how again these policies are mirrored.
2051         </para>
2052         <para>
2053         We are now ready to launch racoon! Once launched, the moment we try
2054 to telnet from 10.0.0.11 to 10.0.0.216, or the other way around, racoon
2055 will start negotiating:
2056 <screen>
2057 12:18:44: INFO: isakmp.c:1689:isakmp_post_acquire(): IPsec-SA
2058   request for 10.0.0.11 queued due to no phase1 found.
2059 12:18:44: INFO: isakmp.c:794:isakmp_ph1begin_i(): initiate new
2060   phase 1 negotiation: 10.0.0.216[500]<=>10.0.0.11[500]
2061 12:18:44: INFO: isakmp.c:799:isakmp_ph1begin_i(): begin Aggressive mode.
2062 12:18:44: INFO: vendorid.c:128:check_vendorid(): received Vendor ID: 
2063   KAME/racoon
2064 12:18:44: NOTIFY: oakley.c:2037:oakley_skeyid(): couldn't find
2065   the proper pskey, try to get one by the peer's address.
2066 12:18:44: INFO: isakmp.c:2417:log_ph1established(): ISAKMP-SA
2067   established 10.0.0.216[500]-10.0.0.11[500] spi:044d25dede78a4d1:ff01e5b4804f0680
2068 12:18:45: INFO: isakmp.c:938:isakmp_ph2begin_i(): initiate new phase 2 
2069   negotiation: 10.0.0.216[0]<=>10.0.0.11[0]
2070 12:18:45: INFO: pfkey.c:1106:pk_recvupdate(): IPsec-SA established: 
2071   ESP/Transport 10.0.0.11->10.0.0.216 spi=44556347(0x2a7e03b)
2072 12:18:45: INFO: pfkey.c:1318:pk_recvadd(): IPsec-SA established:
2073   ESP/Transport 10.0.0.216->10.0.0.11 spi=15863890(0xf21052)
2074 </screen>
2075 </para>
2076 <para>
2077         If we now run setkey -D, which shows the Security Associations, they
2078 are indeed there:
2079 <screen>
2080 10.0.0.216 10.0.0.11 
2081         esp mode=transport spi=224162611(0x0d5c7333) reqid=0(0x00000000)
2082         E: 3des-cbc  5d421c1b d33b2a9f 4e9055e3 857db9fc 211d9c95 ebaead04
2083         A: hmac-sha1  c5537d66 f3c5d869 bd736ae2 08d22133 27f7aa99
2084         seq=0x00000000 replay=4 flags=0x00000000 state=mature 
2085         created: Nov 11 12:28:45 2002   current: Nov 11 12:29:16 2002
2086         diff: 31(s)     hard: 600(s)    soft: 480(s)
2087         last: Nov 11 12:29:12 2002      hard: 0(s)      soft: 0(s)
2088         current: 304(bytes)     hard: 0(bytes)  soft: 0(bytes)
2089         allocated: 3    hard: 0 soft: 0
2090         sadb_seq=1 pid=17112 refcnt=0
2091 10.0.0.11 10.0.0.216 
2092         esp mode=transport spi=165123736(0x09d79698) reqid=0(0x00000000)
2093         E: 3des-cbc  d7af8466 acd4f14c 872c5443 ec45a719 d4b3fde1 8d239d6a
2094         A: hmac-sha1  41ccc388 4568ac49 19e4e024 628e240c 141ffe2f
2095         seq=0x00000000 replay=4 flags=0x00000000 state=mature 
2096         created: Nov 11 12:28:45 2002   current: Nov 11 12:29:16 2002
2097         diff: 31(s)     hard: 600(s)    soft: 480(s)
2098         last:                           hard: 0(s)      soft: 0(s)
2099         current: 231(bytes)     hard: 0(bytes)  soft: 0(bytes)
2100         allocated: 2    hard: 0 soft: 0
2101         sadb_seq=0 pid=17112 refcnt=0
2102 </screen>
2103 As are the Security Policies we configured ourselves:
2104 <screen>
2105 10.0.0.11[any] 10.0.0.216[any] tcp
2106         in ipsec
2107         esp/transport//require
2108         created:Nov 11 12:28:28 2002 lastused:Nov 11 12:29:12 2002
2109         lifetime:0(s) validtime:0(s)
2110         spid=3616 seq=5 pid=17134
2111         refcnt=3
2112 10.0.0.216[any] 10.0.0.11[any] tcp
2113         out ipsec
2114         esp/transport//require
2115         created:Nov 11 12:28:28 2002 lastused:Nov 11 12:28:44 2002
2116         lifetime:0(s) validtime:0(s)
2117         spid=3609 seq=4 pid=17134
2118         refcnt=3
2119 </screen>
2120 </para>
2121         <sect3><title>Problems and known defects</title>
2122         <para>
2123                 If this does not work, check that all configuration files
2124 are owned by root, and can only be read by root. To start racoon on the
2125 foreground, use '-F'. To force it to read a certain configuration file,
2126 instead of at the compiled location, use '-f'. For staggering amounts of
2127 detail, add a 'log debug;' statement to racoon.conf.
2128         </para>
2129         </sect3>
2130         </sect2>
2131         <sect2 id="lartc.ipsec.x509"><title>Automatic keying using X.509 certificates</title>
2132         <para>
2133         As mentioned before, the use of shared secrets is hard because they
2134 aren't easily shared and once shared, are no longer secret. Luckily, there
2135 is asymmetric encryption technology to help resolve this.
2136         </para>
2137         <para>
2138         If each IPSEC participant makes a public and a private key, secure
2139 communications can be setup by both parties publishing their public key, and
2140 configuring policy.
2141         </para>
2142         <para>
2143         Building a key is relatively easy, although it requires some work.
2144 The following is based on the 'openssl' tool. 
2145         </para>
2146         <sect3><title>Building an X.509 certificate for your host</title>
2147         <para>
2148         OpenSSL has a lot of infrastructure for keys that may or may not be
2149 signed by certificate authorities. Right now, we need to circumvent all that
2150 infrastructure and practice some good old Snake Oil security, and do without
2151 a certificate authority.
2152         </para>
2153         <para>
2154         First we issue a 'certificate request' for our host, called
2155 'laptop':
2156 <screen>
2157 $ openssl req -new -nodes -newkey rsa:1024 -sha1 -keyform PEM -keyout \
2158   laptop.private -outform PEM -out request.pem
2159 </screen>
2160 This asks us some questions:
2161 <screen>
2162 Country Name (2 letter code) [AU]:NL
2163 State or Province Name (full name) [Some-State]:.
2164 Locality Name (eg, city) []:Delft
2165 Organization Name (eg, company) [Internet Widgits Pty Ltd]:Linux Advanced
2166 Routing & Traffic Control
2167 Organizational Unit Name (eg, section) []:laptop
2168 Common Name (eg, YOUR name) []:bert hubert
2169 Email Address []:ahu@ds9a.nl
2171 Please enter the following 'extra' attributes
2172 to be sent with your certificate request
2173 A challenge password []:
2174 An optional company name []:
2175 </screen>
2176         It is left to your own discretion how completely you want to fill
2177 this out. You may or may not want to put your hostname in there, depending
2178 on your security needs. In this example, we have.
2179 </para>
2180         <para>
2181         We'll now 'self sign' this request:
2182 <screen>
2183 $ openssl x509 -req -in request.pem -signkey laptop.private -out \
2184   laptop.public
2185 Signature ok
2186 subject=/C=NL/L=Delft/O=Linux Advanced Routing &amp; Traffic \
2187   Control/OU=laptop/CN=bert hubert/Email=ahu@ds9a.nl
2188 Getting Private key
2189 </screen>       
2190         The 'request.pem' file can now be discarded. 
2191         </para>
2192         <para>
2193         Repeat this procedure for all hosts you need a key for. You can
2194 distribute the '.public' file with impunity, but keep the '.private' one
2195 private!
2196         </para>
2197         </sect3>
2198         <sect3><title>Setting up and launching</title>
2199         <para>
2200         Once we have a public and a private key for our hosts we can tell
2201         racoon to use them.
2202         </para>
2203         <para>
2204         We return to our previous configuration and the two hosts, 10.0.0.11
2205 ('upstairs') and 10.0.0.216 ('laptop').
2206         </para>
2207         <para>
2208         To the <filename>racoon.conf</filename> file on 10.0.0.11, we add:
2209 <screen>
2210 path certificate "/usr/local/etc/racoon/certs";
2212 remote 10.0.0.216
2214         exchange_mode aggressive,main;
2215         my_identifier asn1dn;
2216         peers_identifier asn1dn;
2218         certificate_type x509 "upstairs.public" "upstairs.private";
2220         peers_certfile "laptop.public";
2221         proposal {
2222                 encryption_algorithm 3des;
2223                 hash_algorithm sha1;
2224                 authentication_method rsasig;
2225                 dh_group 2 ;
2226         }
2228 </screen>
2229         This tells racoon that certificates are to be found in
2230 <filename>/usr/local/etc/racoon/certs/</filename>. Furthermore, it contains
2231 configuration items specific for remote 10.0.0.216.
2232         </para>
2233         <para>
2234         The 'asn1dn' lines tell racoon that the identifier for both the
2235 local and remote ends are to be extracted from the public keys. This is the
2236 'subject=/C=NL/L=Delft/O=Linux Advanced Routing &amp; Traffic 
2237   Control/OU=laptop/CN=bert hubert/Email=ahu@ds9a.nl' output from above.
2238         </para>
2239         <para>
2240         The <command>certificate_type</command> line configures the local
2241 public and private key. The <command>peers_certfile</command> statement
2242 configures racoon to read the public key of the remote peer from the file
2243 <filename>laptop.public</filename>.
2244         </para>
2245         <para>
2246         The <command>proposal</command> stanza is unchanged from what we've
2247 seen earlier, with the exception that the
2248 <command>authentication_method</command> is now <command>rsasig</command>,
2249 indicating the use of RSA public/private keys for authentication.
2250         </para>
2251         <para>
2252         The addition to the configuration of 10.0.0.216 is nearly identical, except for the
2253 usual mirroring:
2254 <screen>
2255 path certificate "/usr/local/etc/racoon/certs";
2257 remote 10.0.0.11
2259         exchange_mode aggressive,main;
2260         my_identifier asn1dn;
2261         peers_identifier asn1dn;
2263         certificate_type x509 "laptop.public" "laptop.private";
2265         peers_certfile "upstairs.public";
2267         proposal {
2268                 encryption_algorithm 3des;
2269                 hash_algorithm sha1;
2270                 authentication_method rsasig;
2271                 dh_group 2 ;
2272         }
2274 </screen>
2275 </para>
2276         <para>
2277         Now that we've added these statements to both hosts, we only need to
2278 move the key files in place. The 'upstairs' machine needs 
2279 <filename>upstairs.private</filename>, <filename>upstairs.public</filename>, 
2280 and <filename>laptop.public</filename> in
2281 <filename>/usr/local/etc/racoon/certs</filename>. Make sure that this
2282 directory is owned by root and has mode 0700 or racoon may refuse to read
2284 </para>
2285 <para>
2286 The 'laptop' machine needs 
2287 <filename>laptop.private</filename>, <filename>laptop.public</filename>, 
2288 and <filename>upstairs.public</filename> in
2289 <filename>/usr/local/etc/racoon/certs</filename>. In other words, each host
2290 needs its own public and private key and additionally, the public key of the
2291 remote.
2292 </para>
2293 <para>
2294         Verify that a Security Policy is in place (execute the 'spdadd' lines in
2295 <xref linkend="lartc.ipsec.automatic.keying.example">). Then launch racoon and everything should
2296 work.
2297 </para>
2298         </sect3>
2299         <sect3><title>How to setup tunnels securely</title>
2300         <para>
2301         To setup secure communications with a remote party, we must exchange
2302 public keys. While the public key does not need to be kept a secret, on the
2303 contrary, it is very important to be sure that it is in fact the unaltered
2304 key. In other words, you need to be certain there is no 'man in the middle'.
2305         </para>
2306         <para>
2307 To make this easy, OpenSSL provides the 'digest' command:
2308 <screen>
2309 $ openssl dgst upstairs.public 
2310 MD5(upstairs.public)= 78a3bddafb4d681c1ca8ed4d23da4ff1
2311 </screen>
2312 </para>
2313         <para>
2314         Now all we need to do is verify if our remote partner sees the same
2315 digest. This might be done by meeting in real life or perhaps over the
2316 phone, making sure the number of the remote party was not in fact sent over
2317 the same email containing the key!
2318         </para>
2319         <para>
2320         Another way of doing this is the use of a Trusted Third Party which
2321 runs a Certificate Authority. This CA would then sign your key, which we've
2322 done ourselves above.
2323         </para>
2324         
2325         </sect3>
2326     </sect2>
2328     </sect1>
2329     <sect1 id="lartc.ipsec.tunnel"><title>IPSEC tunnels</title>
2330       <para>
2331         So far, we've only seen IPSEC in so called 'transport' mode where both endpoints understand IPSEC directly. As this is often not
2332         the case, it may be necessary to have only routers understand IPSEC, and have them do the work for the hosts behind them. 
2333         This is called 'tunnel mode'.
2334       </para>
2335       <para>
2336         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
2337         10.0.0.216:
2338 <screen>
2339 #!/sbin/setkey -f
2340 flush;
2341 spdflush;
2343 add 10.0.0.216 10.0.0.11 esp 34501
2344         -m tunnel
2345         -E 3des-cbc "123456789012123456789012";
2347 spdadd 10.0.0.0/24 130.161.0.0/16 any -P out ipsec
2348            esp/tunnel/10.0.0.216-10.0.0.11/require;
2349 </screen>
2350         Note the '-m tunnel', it is vitally important! This first configures an ESP encryption SA between our tunnel endpoints,
2351         10.0.0.216 and 10.0.0.11. 
2352       </para>
2353       <para>
2354         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
2355         130.161.0.0. Furthermore, this traffic then has to be shipped to 10.0.0.11.
2356       </para>
2357       <para>
2358         10.0.0.11 also needs some configuration:
2359 <screen>
2360 #!/sbin/setkey -f
2361 flush;
2362 spdflush;
2364 add 10.0.0.216 10.0.0.11 esp 34501
2365         -m tunnel
2366         -E 3des-cbc "123456789012123456789012";
2368 spdadd 10.0.0.0/24 130.161.0.0/16 any -P in ipsec
2369            esp/tunnel/10.0.0.216-10.0.0.11/require;
2370 </screen>
2371         Note that this is exactly identical, except for the change from '-P out' to '-P in'. As with earlier examples,
2372         we've now only configured traffic going one way. Completing the other half of the tunnel is left as an
2373         exercise for the reader.
2374       </para>
2375       <para>
2376         Another name for this setup is 'proxy ESP', which is somewhat clearer.
2377       </para>
2378       <para>
2379         <note>
2380           <para>
2381             The IPSEC tunnel needs to have IP Forwarding enabled in the kernel!
2382           </para>
2383         </note>
2384       </para>
2385     </sect1>
2386     <sect1 id="lartc.ipsec.other"><title>Other IPSEC software</title>
2387       <para>
2388         Thomas Walpuski reports that he wrote a patch to make OpenBSD isakpmd work with Linux 2.5 IPSEC.
2389 Furthermore, the main isakpmd CVS repository now contains this code!
2390         Some notes are <ulink
2391 url="http://bender.thinknerd.de/~thomas/IPsec/isakmpd-linux.html">on his page</ulink>.
2392       </para>
2393       <para>
2395         isakpmd is quite different from racoon mentioned above but many
2396         people like it. It can be found <ulink
2397 url="http://www.openbsd.org/cgi-bin/cvsweb/src/sbin/isakmpd/">here</ulink>.
2398 Read more about OpenBSD CVS <ulink
2399 url="http://www.openbsd.org/anoncvs.html">here</ulink>. Thomas also made a
2400 <ulink
2401 url="http://bender.thinknerd.de/~thomas/IPsec/isakmpd.tgz">tarball</ulink>
2402 available for those uncomfortable with CVS or patch.
2404       </para>
2405         <para>
2406         Furthermore, there are patches to make the FreeS/WAN userspace tools
2407 work with the native Linux 2.5 IPSEC, you can find them <ulink
2408 url="http://gondor.apana.org.au/~herbert/freeswan/">here</ulink>.
2409     </sect1>
2410     <sect1 id="lartc.ipsec.interop"><title>IPSEC interoperation with other systems</title>
2411       <para>
2412         FIXME: Write this
2413       </para>
2414       <sect2 id="lartc.ipsec.interop.win32"><title>Windows</title>
2415         <para>
2416         Andreas Jellinghaus &lt;aj@dungeon.inka.de&gt; reports: "win2k: it works. pre_shared key with ip address for authentication (I don't
2417 think windows supports fqdn or userfqdn strings).  Certificates should also work, didn't
2418 try.".
2420         </para>
2421       </sect2>
2422     </sect1>
2424   </chapter>
2426 <chapter id="lartc.multicast">
2427 <Title>Multicast routing</Title>
2429 <Para>
2430 FIXME: Editor Vacancy!
2431 </Para>
2433 <Para>
2434 The Multicast-HOWTO is ancient (relatively-speaking) and may be inaccurate
2435 or misleading in places, for that reason.
2436 </Para>
2438 <Para>
2439 Before you can do any multicast routing, you need to configure the Linux
2440 kernel to support the type of multicast routing you want to do. This, in
2441 turn, requires you to decide what type of multicast routing you expect to
2442 be using. There are essentially four "common" types - DVMRP (the Multicast
2443 version of the RIP unicast protocol), MOSPF (the same, but for OSPF), PIM-SM
2444 ("Protocol Independent Multicasting - Sparse Mode", which assumes that users
2445 of any multicast group are spread out, rather than clumped) and PIM-DM (the
2446 same, but "Dense Mode", which assumes that there will be significant clumps
2447 of users of the same multicast group).
2448 </Para>
2450 <Para>
2451 In the Linux kernel, you will notice that these options don't appear. This is
2452 because the protocol itself is handled by a routing application, such as
2453 Zebra, mrouted, or pimd. However, you still have to have a good idea of which
2454 you're going to use, to select the right options in the kernel.
2455 </Para>
2457 <Para>
2458 For all multicast routing, you will definitely need to enable "multicasting"
2459 and "multicast routing". For DVMRP and MOSPF, this is sufficient. If you are
2460 going to use PIM, you must also enable PIMv1 or PIMv2, depending on whether
2461 the network you are connecting to uses version 1 or 2 of the PIM protocol.
2462 </Para>
2464 <Para>
2465 Once you have all that sorted out, and your new Linux kernel compiled, you
2466 will see that the IP protocols listed, at boot time, now include IGMP. This
2467 is a protocol for managing multicast groups. At the time of writing, Linux
2468 supports IGMP versions 1 and 2 only, although version 3 does exist and has
2469 been documented. This doesn't really affect us that much, as IGMPv3 is still
2470 new enough that the extra capabilities of IGMPv3 aren't going to be that
2471 much use. Because IGMP deals with groups, only the features present in the
2472 simplest version of IGMP over the entire group are going to be used. For the
2473 most part, that will be IGMPv2, although IGMPv1 is sill going to be
2474 encountered.
2475 </Para>
2477 <Para>
2478 So far, so good. We've enabled multicasting. Now, we have to tell the Linux
2479 kernel to actually do something with it, so we can start routing. This means
2480 adding the Multicast virtual network to the router table:
2481 </Para>
2483 <Para>
2484 ip route add 224.0.0.0/4 dev eth0
2485 </Para>
2487 <Para>
2488 (Assuming, of course, that you're multicasting over eth0! Substitute the
2489 device of your choice, for this.)
2490 </Para>
2492 <Para>
2493 Now, tell Linux to forward packets...
2494 </Para>
2496 <Para>
2497 echo 1 &#62; /proc/sys/net/ipv4/ip_forward
2498 </Para>
2500 <Para>
2501 At this point, you may be wondering if this is ever going to do anything. So,
2502 to test our connection, we ping the default group, 224.0.0.1, to see if anyone
2503 is alive. All machines on your LAN with multicasting enabled <Emphasis>should</Emphasis>
2504 respond, but nothing else. You'll notice that none of the machines that
2505 respond have an IP address of 224.0.0.1. What a surprise! :) This is a group
2506 address (a "broadcast" to subscribers), and all members of the group will
2507 respond with their own address, not the group address.
2508 </Para>
2510 <Para>
2511 ping -c 2 224.0.0.1
2512 </Para>
2514 <Para>
2515 At this point, you're ready to do actual multicast routing. Well, assuming
2516 that you have two networks to route between.
2517 </Para>
2519 <Para>
2520 (To Be Continued!)
2521 </Para>
2523 </chapter>
2525 <chapter id="lartc.qdisc">
2526 <Title>Queueing Disciplines for Bandwidth Management</Title>
2528 <Para>
2529 Now, when I discovered this, it <Emphasis>really</Emphasis> blew me away. Linux 2.2/2.4
2530 comes with everything to manage bandwidth in ways comparable to high-end
2531 dedicated bandwidth management systems.
2532 </Para>
2534 <Para>
2535 Linux even goes far beyond what Frame and ATM provide. 
2536 </Para>
2538 <Para>Just to prevent confusion, <command>tc</command> uses the following 
2539 rules for bandwith specification:
2541 <literallayout class='monospaced'>
2542 mbps = 1024 kbps = 1024 * 1024 bps =&#62; byte/s
2543 mbit = 1024 kbit =&#62; kilo bit/s.
2544 mb = 1024 kb = 1024 * 1024 b =&#62; byte
2545 mbit = 1024 kbit =&#62; kilo bit.
2546 </literallayout>
2548 Internally, the number is stored in bps and b.
2549 </Para>
2551 <Para>But when <command>tc</command> prints the rate, it uses following :
2552 </Para>
2554 <literallayout class='monospaced'>
2555 1Mbit = 1024 Kbit = 1024 * 1024 bps =&#62; byte/s
2556 </literallayout>
2558 <Sect1 id="lartc.qdisc.explain">
2559   <Title>Queues and Queueing Disciplines explained</Title>
2561 <Para>
2562 With queueing we determine the way in which data is <Emphasis>SENT</Emphasis>.
2563 It is important to realise that we can only shape data that we transmit.
2564 </Para>
2566 <Para>
2567 With the way the Internet works, we have no direct control of what people
2568 send us. It's a bit like your (physical!) mailbox at home. There is no way
2569 you can influence the world to modify the amount of mail they send you,
2570 short of contacting everybody.
2571 </Para>
2573 <Para>
2574 However, the Internet is mostly based on TCP/IP which has a few features
2575 that help us. TCP/IP has no way of knowing the capacity of the network
2576 between two hosts, so it just starts sending data faster and faster ('slow
2577 start') and when packets start getting lost, because there is no room to
2578 send them, it will slow down. In fact it is a bit smarter than this, but
2579 more about that later.
2580 </Para>
2582 <Para>
2583 This is the equivalent of not reading half of your mail, and hoping that
2584 people will stop sending it to you. With the difference that it works for
2585 the Internet :-)
2586 </Para>
2588 <Para>
2589 If you have a router and wish to prevent certain hosts within your network
2590 from downloading too fast, you need to do your shaping on the *inner* interface
2591 of your router, the one that sends data to your own computers.
2592 </Para>
2594 <Para>
2595 You also have to be sure you are controlling the bottleneck of the link.
2596 If you have a 100Mbit NIC and you have a router that has a 256kbit link,
2597 you have to make sure you are not sending more data than your router can
2598 handle.  Otherwise, it will be the router who is controlling the link and
2599 shaping the available bandwith. We need to 'own the queue' so to speak, and
2600 be the slowest link in the chain. Luckily this is easily possible.
2601 </Para>
2603 </Sect1>
2605 <Sect1 id="lartc.qdisc.classless">
2606   <Title>Simple, classless Queueing Disciplines</Title>
2608 <Para>
2609 As said, with queueing disciplines, we change the way data is sent.
2610 Classless queueing disciplines are those that, by and large accept data and
2611 only reschedule, delay or drop it.
2612 </Para>
2614 <Para>
2615 These can be used to shape traffic for an entire interface, without any
2616 subdivisions. It is vital that you understand this part of queueing before
2617 we go on the classful qdisc-containing-qdiscs!
2618 </Para>
2620 <Para>
2621 By far the most widely used discipline is the pfifo_fast qdisc - this is the
2622 default. This also explains why these advanced features are so robust. They
2623 are nothing more than 'just another queue'.
2624 </Para>
2626 <Para>
2627 Each of these queues has specific strengths and weaknesses. Not all of them
2628 may be as well tested.
2629 </Para>
2631 <Sect2>
2632 <Title>pfifo_fast</Title>
2634 <Para>
2635 This queue is, as the name says, First In, First Out, which means that no
2636 packet receives special treatment. At least, not quite. This queue has 3 so
2637 called 'bands'. Within each band, FIFO rules apply. However, as long as
2638 there are packets waiting in band 0, band 1 won't be processed. Same goes
2639 for band 1 and band 2.
2640 </Para>
2642 <Para>
2643 The kernel honors the so called Type of Service flag of packets, and takes
2644 care to insert 'minimum delay' packets in band 0. 
2645 </Para>
2647 <Para>
2648 Do not confuse this classless simple qdisc with the classful PRIO one!
2649 Although they behave similarly, pfifo_fast is classless and you cannot add
2650 other qdiscs to it with the tc command.
2651 </Para>
2653 <Sect3>
2654 <Title>Parameters &amp; usage</Title>
2656 <Para>
2657 You can't configure the pfifo_fast qdisc as it is the hardwired default.
2658 This is how it is configured by default:
2659 <VariableList>
2661 <VarListEntry>
2662 <Term>priomap</Term>
2663 <ListItem>
2664 <Para>
2665 Determines how packet priorities, as assigned by the kernel, map to bands.
2666 Mapping occurs based on the TOS octet of the packet, which looks like this:
2667 </Para>
2669 <Para>
2671 <Screen>
2672    0     1     2     3     4     5     6     7
2673 +-----+-----+-----+-----+-----+-----+-----+-----+
2674 |                 |                       |     |
2675 |   PRECEDENCE    |          TOS          | MBZ |
2676 |                 |                       |     |
2677 +-----+-----+-----+-----+-----+-----+-----+-----+
2678 </Screen>
2680 </Para>
2682 <Para>
2683 The four TOS bits (the 'TOS field') are defined as:
2685 <Screen>
2686 Binary Decimcal  Meaning
2687 -----------------------------------------
2688 1000   8         Minimize delay (md)
2689 0100   4         Maximize throughput (mt)
2690 0010   2         Maximize reliability (mr)
2691 0001   1         Minimize monetary cost (mmc)
2692 0000   0         Normal Service
2693 </Screen>
2695 </Para>
2697 <Para>
2698 As there is 1 bit to the right of these four bits, the actual value of the
2699 TOS field is double the value of the TOS bits. Tcpdump -v -v shows you the
2700 value of the entire TOS field, not just the four bits. It is the value you
2701 see in the first column of this table:
2702 </Para>
2704 <Para>
2706 <Screen>
2707 TOS     Bits  Means                    Linux Priority    Band
2708 ------------------------------------------------------------
2709 0x0     0     Normal Service           0 Best Effort     1
2710 0x2     1     Minimize Monetary Cost   1 Filler          2
2711 0x4     2     Maximize Reliability     0 Best Effort     1
2712 0x6     3     mmc+mr                   0 Best Effort     1
2713 0x8     4     Maximize Throughput      2 Bulk            2
2714 0xa     5     mmc+mt                   2 Bulk            2
2715 0xc     6     mr+mt                    2 Bulk            2
2716 0xe     7     mmc+mr+mt                2 Bulk            2
2717 0x10    8     Minimize Delay           6 Interactive     0
2718 0x12    9     mmc+md                   6 Interactive     0
2719 0x14    10    mr+md                    6 Interactive     0
2720 0x16    11    mmc+mr+md                6 Interactive     0
2721 0x18    12    mt+md                    4 Int. Bulk       1
2722 0x1a    13    mmc+mt+md                4 Int. Bulk       1
2723 0x1c    14    mr+mt+md                 4 Int. Bulk       1
2724 0x1e    15    mmc+mr+mt+md             4 Int. Bulk       1
2725 </Screen>
2727 </Para>
2729 <Para>
2730 Lots of numbers. The second column contains the value of the relevant four
2731 TOS bits, followed by their translated meaning. For example, 15 stands for a
2732 packet wanting Minimal Monetary Cost, Maximum Reliability, Maximum
2733 Throughput AND Minimum Delay. I would call this a 'Dutch Packet'.
2734 </Para>
2736 <Para>
2737 The fourth column lists the way the Linux kernel interprets the TOS bits, by
2738 showing to which Priority they are mapped. 
2739 </Para>
2741 <Para>
2742 The last column shows the result of the default priomap. On the command line,
2743 the default priomap looks like this:
2745 <Screen>
2746 1, 2, 2, 2, 1, 2, 0, 0 , 1, 1, 1, 1, 1, 1, 1, 1
2747 </Screen>
2749 </Para>
2751 <Para>
2752 This means that priority 4, for example, gets mapped to band number 1. The
2753 priomap also allows you to list higher priorities (&gt; 7) which do not
2754 correspond to TOS mappings, but which are set by other means.
2755 </Para>
2757 <Para>
2758 This table from RFC 1349 (read it for more details) tells you how
2759 applications might very well set their TOS bits:
2761 <Screen>
2762 TELNET                   1000           (minimize delay)
2764         Control          1000           (minimize delay)
2765         Data             0100           (maximize throughput)
2767 TFTP                     1000           (minimize delay)
2769 SMTP 
2770         Command phase    1000           (minimize delay)
2771         DATA phase       0100           (maximize throughput)
2773 Domain Name Service
2774         UDP Query        1000           (minimize delay)
2775         TCP Query        0000
2776         Zone Transfer    0100           (maximize throughput)
2778 NNTP                     0001           (minimize monetary cost)
2780 ICMP
2781         Errors           0000
2782         Requests         0000 (mostly)
2783         Responses        &#60;same as request&#62; (mostly)
2784 </Screen>
2786 </Para></ListItem>
2787 </VarListEntry>
2788 <VarListEntry>
2789 <Term>txqueuelen</Term>
2790 <ListItem>
2791 <Para>
2792 The length of this queue is gleaned from the interface configuration, which
2793 you can see and set with ifconfig and ip. To set the queue length to 10,
2794 execute: ifconfig eth0 txqueuelen 10
2795 </Para>
2797 <Para>
2798 You can't set this parameter with tc!
2799 </Para></ListItem>
2800 </VarListEntry>
2801 </VariableList>
2802 </Para>
2804 </Sect3>
2806 </Sect2>
2808 <Sect2>
2809 <Title>Token Bucket Filter</Title>
2811 <Para>
2812 The Token Bucket Filter (TBF) is a simple qdisc that only passes packets
2813 arriving at a rate which is not exceeding some administratively set rate, but
2814 with the possibility to allow short bursts in excess of this rate.
2815 </Para>
2817 <Para>
2818 TBF is very precise, network- and processor friendly. It should be your
2819 first choice if you simply want to slow an interface down!
2820 </Para>
2822 <Para>
2823 The TBF implementation consists of a buffer (bucket), constantly filled by
2824 some virtual pieces of information called tokens, at a specific rate (token
2825 rate). The most important parameter of the bucket is its size, that is the
2826 number of tokens it can store.
2827 </Para>
2829 <Para>
2830 Each arriving token collects one incoming data packet from the data queue
2831 and is then deleted from the bucket. Associating this algorithm
2832 with the two flows -- token and data, gives us three possible scenarios:
2833 </Para>
2835 <Para>
2837 <ItemizedList>
2838 <ListItem>
2840 <Para>
2841  The data arrives in TBF at a rate that's <Emphasis>equal</Emphasis> to the rate
2842 of incoming tokens. In this case each incoming packet has its matching token
2843 and passes the queue without delay.
2845 </Para>
2846 </ListItem>
2847 <ListItem>
2849 <Para>
2850  The data arrives in TBF at a rate that's <Emphasis>smaller</Emphasis> than the
2851 token rate. Only a part of the tokens are deleted at output of each data packet
2852 that's sent out the queue, so the tokens accumulate, up to the bucket size.
2853 The unused tokens can then be used to send data at a speed that's exceeding the
2854 standard token rate, in case short data bursts occur.
2856 </Para>
2857 </ListItem>
2858 <ListItem>
2860 <Para>
2861  The data arrives in TBF at a rate <Emphasis>bigger</Emphasis> than the token rate.
2862 This means that the bucket will soon be devoid of tokens, which causes the
2863 TBF to throttle itself for a while. This is called an 'overlimit situation'.
2864 If packets keep coming in, packets will start to get dropped.
2865 </Para>
2866 </ListItem>
2868 </ItemizedList>
2870 </Para>
2872 <Para>
2873 The last scenario is very important, because it allows to
2874 administratively shape the bandwidth available to data that's passing
2875 the filter.
2876 </Para>
2878 <Para>
2879 The accumulation of tokens allows a short burst of overlimit data to be
2880 still passed without loss, but any lasting overload will cause packets to be
2881 constantly delayed, and then dropped.
2882 </Para>
2884 <Para>
2885 Please note that in the actual implementation, tokens correspond to bytes,
2886 not packets.
2887 </Para>
2889 <Sect3>
2890 <Title>Parameters &amp; usage</Title>
2892 <Para>
2893 Even though you will probably not need to change them, tbf has some knobs
2894 available. First the parameters that are always available:
2895 <VariableList>
2897 <VarListEntry>
2898 <Term>limit or latency</Term>
2899 <ListItem>
2900 <Para>
2901 Limit is the number of bytes that can be queued waiting for tokens to become
2902 available. You can also specify this the other way around by setting the
2903 latency parameter, which specifies the maximum amount of time a packet can
2904 sit in the TBF. The latter calculation takes into account the size of the
2905 bucket, the rate and possibly the peakrate (if set).
2906 </Para></ListItem>
2907 </VarListEntry>
2908 <VarListEntry>
2909 <Term>burst/buffer/maxburst</Term>
2910 <ListItem>
2911 <Para>
2912 Size of the bucket, in bytes. This is the maximum amount of bytes that
2913 tokens can be available for instantaneously. In general, larger shaping
2914 rates require a larger buffer. For 10mbit/s on Intel, you need at least
2915 10kbyte buffer if you want to reach your configured rate!
2916 </Para>
2918 <Para>
2919 If your buffer is too small, packets may be dropped because more tokens
2920 arrive per timer tick than fit in your bucket.
2921 </Para></ListItem>
2922 </VarListEntry>
2923 <VarListEntry>
2924 <Term>mpu</Term>
2925 <ListItem>
2926 <Para>
2927 A zero-sized packet does not use zero bandwidth. For ethernet, no packet
2928 uses less than 64 bytes. The Minimum Packet Unit determines the minimal
2929 token usage for a packet.
2930 </Para></ListItem>
2931 </VarListEntry>
2932 <VarListEntry>
2933 <Term>rate</Term>
2934 <ListItem>
2935 <Para>
2936 The speedknob. See remarks above about limits!
2937 </Para></ListItem>
2938 </VarListEntry>
2939 </VariableList>
2940 </Para>
2942 <Para>
2943 If the bucket contains tokens and is allowed to empty, by default it does so
2944 at infinite speed. If this is unacceptable, use the following parameters:
2945 </Para>
2947 <Para>
2948 <VariableList>
2950 <VarListEntry>
2951 <Term>peakrate</Term>
2952 <ListItem>
2953 <Para>
2954 If tokens are available, and packets arrive, they are sent out immediately
2955 by default, at 'lightspeed' so to speak. That may not be what you want,
2956 especially if you have a large bucket. 
2957 </Para>
2959 <Para>
2960 The peakrate can be used to specify how quickly the bucket is allowed to be
2961 depleted. If doing everything by the book, this is achieved by releasing a
2962 packet, and then wait just long enough, and release the next. We calculated
2963 our waits so we send just at peakrate.
2964 </Para>
2966 <Para>
2967 However, due to de default 10ms timer resolution of Unix, with 10.000 bits
2968 average packets, we are limited to 1mbit/s of peakrate!
2969 </Para></ListItem>
2970 </VarListEntry>
2971 <VarListEntry>
2972 <Term>mtu/minburst</Term>
2973 <ListItem>
2974 <Para>
2975 The 1mbit/s peakrate is not very useful if your regular rate is more than
2976 that. A higher peakrate is possible by sending out more packets per
2977 timertick, which effectively means that we create a second bucket!
2978 </Para>
2980 <Para>
2981 This second bucket defaults to a single packet, which is not a bucket at
2982 all.
2983 </Para>
2985 <Para>
2986 To calculate the maximum possible peakrate, multiply the configured mtu by
2987 100 (or more correctly, HZ, which is 100 on Intel, 1024 on Alpha).
2988 </Para></ListItem>
2989 </VarListEntry>
2990 </VariableList>
2991 </Para>
2993 </Sect3>
2995 <Sect3>
2996 <Title>Sample configuration</Title>
2998 <Para>
2999 A simple but *very* useful configuration is this:
3001 <Screen>
3002 # tc qdisc add dev ppp0 root tbf rate 220kbit latency 50ms burst 1540
3003 </Screen>
3005 </Para>
3007 <Para>
3008 Ok, why is this useful? If you have a networking device with a large queue,
3009 like a DSL modem or a cable modem, and you talk to it over a fast device,
3010 like over an ethernet interface, you will find that uploading absolutely
3011 destroys interactivity.
3012 </Para>
3014 <Para>
3015 This is because uploading will fill the queue in the modem, which is
3016 probably *huge* because this helps actually achieving good data throughput
3017 uploading. But this is not what you want, you want to have the queue not too
3018 big so interactivity remains and you can still do other stuff while sending
3019 data.
3020 </Para>
3022 <Para>
3023 The line above slows down sending to a rate that does not lead to a queue in
3024 the modem - the queue will be in Linux, where we can control it to a limited
3025 size.
3026 </Para>
3028 <Para>
3029 Change 220kbit to your uplink's *actual* speed, minus a few percent. If you
3030 have a really fast modem, raise 'burst' a bit. 
3031 </Para>
3033 </Sect3>
3035 </Sect2>
3037 <Sect2 id="lartc.sfq">
3038 <Title>Stochastic Fairness Queueing</Title>
3040 <Para>
3041 Stochastic Fairness Queueing (SFQ) is a simple implementation of the fair
3042 queueing algorithms family. It's less accurate than others, but it also
3043 requires less calculations while being almost perfectly fair.
3044 </Para>
3046 <Para>
3047 The key word in SFQ is conversation (or flow), which mostly corresponds to a
3048 TCP session or a UDP stream. Traffic is divided into a pretty large number
3049 of FIFO queues, one for each conversation. Traffic is then sent in a round
3050 robin fashion, giving each session the chance to send data in turn.
3051 </Para>
3053 <Para>
3054 This leads to very fair behaviour and disallows any single conversation from
3055 drowning out the rest. SFQ is called 'Stochastic' because it doesn't really
3056 allocate a queue for each session, it has an algorithm which divides traffic
3057 over a limited number of queues using a hashing algorithm. 
3058 </Para>
3060 <Para>
3061 Because of the hash, multiple sessions might end up in the same bucket, which
3062 would halve each session's chance of sending a packet, thus halving the
3063 effective speed available. To prevent this situation from becoming
3064 noticeable, SFQ changes its hashing algorithm quite often so that any two
3065 colliding sessions will only do so for a small number of seconds.
3066 </Para>
3068 <Para>
3069 It is important to note that SFQ is only useful in case your actual outgoing
3070 interface is really full! If it isn't then there will be no queue on your
3071 linux machine and hence no effect. Later on we will describe how to combine
3072 SFQ with other qdiscs to get a best-of-both worlds situation.
3073 </Para>
3075 <Para>
3076 Specifically, setting SFQ on the ethernet interface heading to your
3077 cable modem or DSL router is pointless without further shaping!
3078 </Para>
3080 <Sect3>
3081 <Title>Parameters &amp; usage</Title>
3083 <Para>
3084 The SFQ is pretty much self tuning:
3085 <VariableList>
3087 <VarListEntry>
3088 <Term>perturb</Term>
3089 <ListItem>
3090 <Para>
3091 Reconfigure hashing once this many seconds. If unset, hash will never be
3092 reconfigured. Not recommended. 10 seconds is probably a good value.
3093 </Para></ListItem>
3094 </VarListEntry>
3095 <VarListEntry>
3096 <Term>quantum</Term>
3097 <ListItem>
3098 <Para>
3099 Amount of bytes a stream is allowed to dequeue before the next queue gets a
3100 turn. Defaults to 1 maximum sized packet (MTU-sized). Do not set below the
3101 MTU!
3102 </Para></ListItem>
3103 </VarListEntry>
3104 <VarListEntry>
3105  <Term>limit</Term>
3106  <ListItem>
3107    <Para>
3108    The total number of packets that will be queued by this SFQ (after that it
3109    starts dropping them).
3110    </Para>
3111  </ListItem>
3112 </VarListEntry>
3113 </VariableList>
3114 </Para>
3116 </Sect3>
3118 <Sect3>
3119 <Title>Sample configuration</Title>
3121 <Para>
3122 If you have a device which has identical link speed and actual available
3123 rate, like a phone modem, this configuration will help promote fairness:
3125 <Screen>
3126 # tc qdisc add dev ppp0 root sfq perturb 10
3127 # tc -s -d qdisc ls
3128 qdisc sfq 800c: dev ppp0 quantum 1514b limit 128p flows 128/1024 perturb 10sec 
3129  Sent 4812 bytes 62 pkts (dropped 0, overlimits 0) 
3130 </Screen>
3132 </Para>
3134 <Para>
3135 The number 800c: is the automatically assigned handle number, limit means
3136 that 128 packets can wait in this queue. There are 1024 hashbuckets
3137 available for accounting, of which 128 can be active at a time (no more
3138 packets fit in the queue!) Once every 10 seconds, the hashes are
3139 reconfigured.
3140 </Para>
3142 </Sect3>
3144 </Sect2>
3146 </Sect1>
3148 <Sect1 id="lartc.qdisc.advice">
3149   <Title>Advice for when to use which queue</Title>
3151 <Para>
3152 Summarizing, these are the simple queues that actually manage traffic by
3153 reordering, slowing or dropping packets.
3154 </Para>
3156 <Para>
3157 The following tips may help in choosing which queue to use. It mentions some
3158 qdiscs described in the
3159 <citetitle><xref linkend="lartc.adv-qdisc"></citetitle> chapter.
3160 </Para>
3162 <ItemizedList>
3163 <ListItem>
3164 <Para>
3165 To purely slow down outgoing traffic, use the Token Bucket Filter. Works up
3166 to huge bandwidths, if you scale the bucket.
3167 </Para>
3168 </ListItem>
3169 <ListItem>
3171 <Para>
3172 If your link is truly full and you want to make sure that no single session
3173 can dominate your outgoing bandwidth, use Stochastical Fairness Queueing.
3174 </Para>
3175 </ListItem>
3176 <ListItem>
3178 <Para>
3179 If you have a big backbone and know what you are doing, consider Random
3180 Early Drop (see Advanced chapter).
3181 </Para>
3182 </ListItem>
3183 <ListItem>
3185 <Para>
3186 To 'shape' incoming traffic which you are not forwarding, use the Ingress
3187 Policer. Incoming shaping is called 'policing', by the way, not 'shaping'.  
3188 </Para>
3189 </ListItem>
3190 <ListItem>
3192 <Para>
3193 If you *are* forwarding it, use a TBF on the interface you are forwarding
3194 the data to. Unless you want to shape traffic that may go out over several
3195 interfaces, in which case the only common factor is the incoming interface.
3196 In that case use the Ingress Policer.
3197 </Para>
3198 </ListItem>
3199 <ListItem>
3201 <Para>
3202 If you don't want to shape, but only want to see if your interface is so
3203 loaded that it has to queue, use the pfifo queue (not pfifo_fast). It lacks
3204 internal bands but does account the size of its backlog.
3205 </Para>
3206 </ListItem>
3207 <ListItem>
3208 <Para>
3209 Finally - you can also do <quote>social shaping</quote>.
3210 You may not always be able to use technology to achieve what you want.
3211 Users experience technical constraints as hostile.
3212 A kind word may also help with getting your bandwidth to be divided right!
3213 </Para>
3214 </ListItem>
3215 </ItemizedList>
3217 </Sect1>
3219 <Sect1 id="lartc.qdisc.terminology">
3220   <Title>Terminology</Title>
3222 <Para>
3223 To properly understand more complicated configurations it is necessary to
3224 explain a few concepts first. Because of the complexity and the relative
3225 youth of the subject, a lot of different words are used when people in fact
3226 mean the same thing.
3227 </Para>
3229 <Para>
3230 The following is loosely based on 
3231 <filename>draft-ietf-diffserv-model-06.txt</filename>,
3232 <citetitle>An Informal Management Model for Diffserv Routers</citetitle>.
3233 It can currently be found at 
3234 <ulink url="http://www.ietf.org/internet-drafts/draft-ietf-diffserv-model-06.txt">
3235   http://www.ietf.org/internet-drafts/draft-ietf-diffserv-model-06.txt
3236 </ulink>.
3237 </Para>
3239 <Para>
3240 Read it for the strict definitions of the terms used.
3241 <VariableList>
3243 <VarListEntry>
3244 <Term>Queueing Discipline (qdisc)</Term>
3245 <ListItem>
3246 <Para>
3247 An algorithm that manages the queue of a device, either incoming (ingress)
3248 or outgoing (egress).
3249 </Para></ListItem>
3250 </VarListEntry>
3251 <VarListEntry>
3252 <Term>root qdisc</Term>
3253 <ListItem>
3254 <Para>
3255 The root qdisc is the qdisc attached to the device.
3256 </Para></ListItem>
3257 </VarListEntry>
3258 <VarListEntry>
3259 <Term>Classless qdisc</Term>
3260 <ListItem>
3261 <Para>
3262 A qdisc with no configurable internal subdivisions. 
3263 </Para></ListItem>
3264 </VarListEntry>
3265 <VarListEntry>
3266 <Term>Classful qdisc</Term>
3267 <ListItem>
3268 <Para>
3269 A classful qdisc contains multiple classes. Some of these classes contains a
3270 further qdisc, which may again be classful, but need not be. According to
3271 the strict definition, pfifo_fast *is* classful, because it contains three
3272 bands which are, in fact, classes. However, from the user's configuration
3273 perspective, it is classless as the classes can't be touched with the tc
3274 tool. 
3275 </Para></ListItem>
3276 </VarListEntry>
3277 <VarListEntry>
3278 <Term>Classes</Term>
3279 <ListItem>
3280 <Para>
3281 A classful qdisc may have many classes, each of which is internal to the
3282 qdisc.  A class, in turn, may have several classes added to it.  So a class
3283 can have a qdisc as parent or an other class.
3285 A leaf class is a class with no child classes.  This class has 1 qdisc attached
3286 to it.  This qdisc is responsible to send the data from that class.  When
3287 you create a class, a fifo qdisc is attached to it.  When you add a child class,
3288 this qdisc is removed.
3289 For a leaf class, this fifo qdisc can be replaced with
3290 an other more suitable qdisc.  You can even replace this fifo qdisc with a
3291 classful qdisc so you can add extra classes.
3292 </Para></ListItem>
3293 </VarListEntry>
3294 <VarListEntry>
3295 <Term>Classifier</Term>
3296 <ListItem>
3297 <Para>
3298 Each classful qdisc needs to determine to which class it needs to send a
3299 packet. This is done using the classifier.
3300 </Para></ListItem>
3301 </VarListEntry>
3302 <VarListEntry>
3303 <Term>Filter</Term>
3304 <ListItem>
3305 <Para>
3306 Classification can be performed using filters. A filter contains a number of
3307 conditions which if matched, make the filter match.
3308 </Para></ListItem>
3309 </VarListEntry>
3310 <VarListEntry>
3311 <Term>Scheduling</Term>
3312 <ListItem>
3313 <Para>
3314 A qdisc may, with the help of a classifier, decide that some packets need to
3315 go out earlier than others. This process is called Scheduling, and is
3316 performed for example by the pfifo_fast qdisc mentioned earlier. Scheduling
3317 is also called 'reordering', but this is confusing.
3318 </Para></ListItem>
3319 </VarListEntry>
3320 <VarListEntry>
3321 <Term>Shaping</Term>
3322 <ListItem>
3323 <Para>
3324 The process of delaying packets before they go out to make traffic confirm
3325 to a configured maximum rate. Shaping is performed on egress. Colloquially, 
3326 dropping packets to slow traffic down is also often called Shaping.
3327 </Para></ListItem>
3328 </VarListEntry>
3329 <VarListEntry>
3330 <Term>Policing</Term>
3331 <ListItem>
3332 <Para>
3333 Delaying or dropping packets in order to make traffic stay below a
3334 configured bandwidth. In Linux, policing can only drop a packet and not
3335 delay it - there is no 'ingress queue'.
3336 </Para></ListItem>
3337 </VarListEntry>
3338 <VarListEntry>
3339 <Term>Work-Conserving</Term>
3340 <ListItem>
3341 <Para>
3342 A work-conserving qdisc always delivers a packet if one is available. In
3343 other words, it never delays a packet if the network adaptor is ready to
3344 send one (in the case of an egress qdisc).
3345 </Para></ListItem>
3346 </VarListEntry>
3347 <VarListEntry>
3348 <Term>non-Work-Conserving</Term>
3349 <ListItem>
3350 <Para>
3351 Some queues, like for example the Token Bucket Filter, may need to hold on
3352 to a packet for a certain time in order to limit the bandwidth. This means
3353 that they sometimes refuse to pass a packet, even though they have one
3354 available.
3355 </Para></ListItem>
3356 </VarListEntry>
3357 </VariableList>
3358 </Para>
3360 <Para>
3361 Now that we have our terminology straight, let's see where all these things
3362 are.
3363 </Para>
3365 <Para>
3367 <Screen width="80">
3368                 Userspace programs
3369                      ^
3370                      |
3371      +---------------+-----------------------------------------+
3372      |               Y                                         |
3373      |    -------&#62; IP Stack                                    |
3374      |   |              |                                      |
3375      |   |              Y                                      |
3376      |   |              Y                                      |
3377      |   ^              |                                      |
3378      |   |  / ----------&#62; Forwarding -&#62;                        |
3379      |   ^ /                           |                       |
3380      |   |/                            Y                       |
3381      |   |                             |                       |
3382      |   ^                             Y          /-qdisc1-\   |
3383      |   |                            Egress     /--qdisc2--\  |
3384   ---&#62;-&#62;Ingress                       Classifier ---qdisc3---- | -&#62;
3385      |   Qdisc                                   \__qdisc4__/  |
3386      |                                            \-qdiscN_/   |
3387      |                                                         |
3388      +----------------------------------------------------------+
3389 </Screen>
3391 Thanks to Jamal Hadi Salim for this ASCII representation.
3392 </Para>
3394 <Para>
3395 The big block represents the kernel. The leftmost arrow represents traffic
3396 entering your machine from the network. It is then fed to the Ingress
3397 Qdisc which may apply Filters to a packet, and decide to drop it. This
3398 is called 'Policing'.
3399 </Para>
3401 <Para>
3402 This happens at a very early stage, before it has seen a lot of the kernel.
3403 It is therefore a very good place to drop traffic very early, without
3404 consuming a lot of CPU power.
3405 </Para>
3407 <Para>
3408 If the packet is allowed to continue, it may be destined for a local
3409 application, in which case it enters the IP stack in order to be processed,
3410 and handed over to a userspace program. The packet may also be forwarded
3411 without entering an application, in which case it is destined for egress.
3412 Userspace programs may also deliver data, which is then examined and
3413 forwarded to the Egress Classifier.
3414 </Para>
3416 <Para>
3417 There it is investigated and enqueued to any of a number of qdiscs. In the
3418 unconfigured default case, there is only one egress qdisc installed, the
3419 pfifo_fast, which always receives the packet. This is called 'enqueueing'.
3420 </Para>
3422 <Para>
3423 The packet now sits in the qdisc, waiting for the kernel to ask for
3424 it for transmission over the network interface. This is called 'dequeueing'.
3425 </Para>
3427 <Para>
3428 This picture also holds in case there is only one network adaptor - the
3429 arrows entering and leaving the kernel should not be taken too literally.
3430 Each network adaptor has both ingress and egress hooks.
3431 </Para>
3433 </Sect1>
3435 <Sect1 id="lartc.qdisc.classful">
3436   <Title>Classful Queueing Disciplines</Title>
3438 <Para>
3439 Classful qdiscs are very useful if you have different kinds of traffic which
3440 should have differing treatment. One of the classful qdiscs is called 'CBQ',
3441 'Class Based Queueing' and it is so widely mentioned that people identify
3442 queueing with classes solely with CBQ, but this is not the case.
3443 </Para>
3445 <Para>
3446 CBQ is merely the oldest kid on the block - and also the most complex one.
3447 It may not always do what you want.  This may come as something of a shock
3448 to many who fell for the 'sendmail effect', which teaches us that any
3449 complex technology which doesn't come with documentation must be the best
3450 available.
3451 </Para>
3453 <Para>
3454 More about CBQ and its alternatives shortly.
3455 </Para>
3457 <Sect2>
3458 <Title>Flow within classful qdiscs &amp; classes</Title>
3460 <Para>
3461 When traffic enters a classful qdisc, it needs to be sent to any of the
3462 classes within - it needs to be 'classified'. To determine what to do with a
3463 packet, the so called 'filters' are consulted. It is important to know that
3464 the filters are called from within a qdisc, and not the other way around!
3465 </Para>
3467 <Para>
3468 The filters attached to that qdisc then return with a decision, and the
3469 qdisc uses this to enqueue the packet into one of the classes. Each subclass
3470 may try other filters to see if further instructions apply. If not, the
3471 class enqueues the packet to the qdisc it contains.
3472 </Para>
3474 <Para>
3475 Besides containing other qdiscs, most classful qdiscs also perform shaping.
3476 This is useful to perform both packet scheduling (with SFQ, for example) and
3477 rate control. You need this in cases where you have a high speed
3478 interface (for example, ethernet) to a slower device (a cable modem).
3479 </Para>
3481 <Para>
3482 If you were only to run SFQ, nothing would happen, as packets enter &amp;
3483 leave your router without delay: the output interface is far faster than
3484 your actual link speed. There is no queue to schedule then.
3485 </Para>
3487 </Sect2>
3489 <Sect2>
3490 <Title>The qdisc family: roots, handles, siblings and parents</Title>
3492 <Para>
3493 Each interface has one egress 'root qdisc'. By default, it is the earlier mentioned
3494 classless pfifo_fast queueing discipline. Each qdisc and class is assigned a
3495 handle, which can be used by later configuration statements to refer to that
3496 qdisc. Besides an egress qdisc, an interface may also have an ingress qdisc ,
3497 which polices traffic coming in.
3498 </Para>
3500 <Para>
3501 The handles of these qdiscs consist of two parts, a major number and a minor
3502 number : &lt;major&gt;:&lt;minor&gt;. It is customary to name the root qdisc '1:', which
3503 is equal to '1:0'.  The minor number of a qdisc is always 0. 
3504 </Para>
3506 <Para>
3507 Classes need to have the same major number as their parent.  This major number
3508 must be unique within a egress or ingress setup.  The minor number must be
3509 unique within a qdisc and his classes.
3510 </Para>
3512 <Sect3>
3513 <Title>How filters are used to classify traffic </Title>
3515 <Para>
3516 Recapping, a typical hierarchy might look like this:
3518 <Screen>
3519                      1:   root qdisc
3520                       |
3521                      1:1    child class
3522                    /  |  \
3523                   /   |   \
3524                  /    |    \
3525                  /    |    \
3526               1:10  1:11  1:12   child classes
3527                |      |     | 
3528                |     11:    |    leaf class
3529                |            | 
3530                10:         12:   qdisc
3531               /   \       /   \
3532            10:1  10:2   12:1  12:2   leaf classes
3533 </Screen>
3535 </Para>
3537 <Para>
3538 But don't let this tree fool you! You should *not* imagine the kernel to be
3539 at the apex of the tree and the network below, that is just not the case.
3540 Packets get enqueued and dequeued at the root qdisc, which is the only thing
3541 the kernel talks to. 
3542 </Para>
3544 <Para>
3545 A packet might get classified in a chain like this:
3546 </Para>
3548 <Para>
3549 1: -&#62; 1:1 -&#62; 1:12 -&#62; 12: -&#62; 12:2
3550 </Para>
3552 <Para>
3553 The packet now resides in a queue in a qdisc attached to class 12:2. In this
3554 example, a filter was attached to each 'node' in the tree, each choosing a
3555 branch to take next. This can make sense. However, this is also possible:
3556 </Para>
3558 <Para>
3559 1: -&#62; 12:2
3560 </Para>
3562 <Para>
3563 In this case, a filter attached to the root decided to send the packet
3564 directly to 12:2.
3565 </Para>
3567 </Sect3>
3569 <Sect3>
3570 <Title>How packets are dequeued to the hardware</Title>
3572 <Para>
3573 When the kernel decides that it needs to extract packets to send to the
3574 interface, the root qdisc 1: gets a dequeue request, which is passed to
3575 1:1, which is in turn passed to 10:, 11: and 12:, each of which queries its
3576 siblings, and tries to dequeue() from them. In this case, the kernel needs to
3577 walk the entire tree, because only 12:2 contains a packet. 
3578 </Para>
3580 <Para>
3581 In short, nested classes ONLY talk to their parent qdiscs, never to an
3582 interface. Only the root qdisc gets dequeued by the kernel!
3583 </Para>
3585 <Para>
3586 The upshot of this is that classes never get dequeued faster than their
3587 parents allow. And this is exactly what we want: this way we can have SFQ in
3588 an inner class, which doesn't do any shaping, only scheduling, and have a
3589 shaping outer qdisc, which does the shaping.
3590 </Para>
3592 </Sect3>
3594 </Sect2>
3596 <Sect2>
3597 <Title>The PRIO qdisc</Title>
3599 <Para>
3600 The PRIO qdisc doesn't actually shape, it only subdivides traffic based on
3601 how you configured your filters. You can consider the PRIO qdisc a kind
3602 of pfifo_fast on steroids, whereby each band is a separate class instead of
3603 a simple FIFO.
3604 </Para>
3606 <Para>
3607 When a packet is enqueued to the PRIO qdisc, a class is chosen based on the
3608 filter commands you gave. By default, three classes are created. These
3609 classes by default contain pure FIFO qdiscs with no internal
3610 structure, but you can replace these by any qdisc you have available.
3611 </Para>
3613 <Para>
3614 Whenever a packet needs to be dequeued, class :1 is tried first. Higher
3615 classes are only used if lower bands all did not give up a packet.
3616 </Para>
3618 <Para>
3619 This qdisc is very useful in case you want to prioritize certain kinds of
3620 traffic without using only TOS-flags but using all the power of the tc
3621 filters. You can also add an other qdisc to the 3 predefined classes,
3622 whereas pfifo_fast is limited to simple fifo qdiscs.
3623 </Para>
3625 <Para>
3626 Because it doesn't actually shape, the same warning as for SFQ holds: either
3627 use it only if your physical link is really full or wrap it inside a
3628 classful qdisc that does shape. The latter holds for almost all cable modems
3629 and DSL devices.
3630 </Para>
3632 <Para>
3633 In formal words, the PRIO qdisc is a Work-Conserving scheduler.
3634 </Para>
3636 <Sect3>
3637 <Title>PRIO parameters &amp; usage</Title>
3639 <Para>
3640 The following parameters are recognized by tc:
3641 <VariableList>
3643 <VarListEntry>
3644 <Term>bands</Term>
3645 <ListItem>
3646 <Para>
3647 Number of bands to create. Each band is in fact a class. If you change this
3648 number, you must also change:
3649 </Para></ListItem>
3650 </VarListEntry>
3651 <VarListEntry>
3652 <Term>priomap</Term>
3653 <ListItem>
3654 <Para>
3655 If you do not provide tc filters to classify traffic, the PRIO qdisc looks
3656 at the TC_PRIO priority to decide how to enqueue traffic. 
3657 </Para>
3659 <Para>
3660 This works just like with the pfifo_fast qdisc mentioned earlier, see there
3661 for lots of detail.
3662 </Para></ListItem>
3663 </VarListEntry>
3664 </VariableList>
3665 The bands are classes, and are called major:1 to major:3 by default, so if
3666 your PRIO qdisc is called 12:, tc filter traffic to 12:1 to grant it more
3667 priority.
3668 </Para>
3670 <Para>
3671 Reiterating, band 0 goes to minor number 1! Band 1 to minor number 2, etc.
3672 </Para>
3674 </Sect3>
3676 <Sect3>
3677 <Title>Sample configuration</Title>
3679 <Para>
3680 We will create this tree:
3682 <Screen>
3683           1:   root qdisc
3684          / | \ 
3685        /   |   \
3686        /   |   \
3687      1:1  1:2  1:3    classes
3688       |    |    |
3689      10:  20:  30:    qdiscs    qdiscs
3690      sfq  tbf  sfq
3691 band  0    1    2
3692 </Screen>
3694 </Para>
3696 <Para>
3697 Bulk traffic will go to 30:, interactive traffic to 20: or 10:.
3698 </Para>
3700 <Para>
3701 Command lines:
3703 <Screen>
3704 # tc qdisc add dev eth0 root handle 1: prio 
3705 ## This *instantly* creates classes 1:1, 1:2, 1:3
3706   
3707 # tc qdisc add dev eth0 parent 1:1 handle 10: sfq
3708 # tc qdisc add dev eth0 parent 1:2 handle 20: tbf rate 20kbit buffer 1600 limit 3000
3709 # tc qdisc add dev eth0 parent 1:3 handle 30: sfq                                
3710 </Screen>
3712 </Para>
3714 <Para>
3715 Now let's see what we created:
3717 <Screen>
3718 # tc -s qdisc ls dev eth0 
3719 qdisc sfq 30: quantum 1514b 
3720  Sent 0 bytes 0 pkts (dropped 0, overlimits 0) 
3722  qdisc tbf 20: rate 20Kbit burst 1599b lat 667.6ms 
3723  Sent 0 bytes 0 pkts (dropped 0, overlimits 0) 
3725  qdisc sfq 10: quantum 1514b 
3726  Sent 132 bytes 2 pkts (dropped 0, overlimits 0) 
3728  qdisc prio 1: bands 3 priomap  1 2 2 2 1 2 0 0 1 1 1 1 1 1 1 1
3729  Sent 174 bytes 3 pkts (dropped 0, overlimits 0) 
3730 </Screen>
3732 As you can see, band 0 has already had some traffic, and one packet was sent
3733 while running this command!
3734 </Para>
3736 <Para>
3737 We now do some bulk data transfer with a tool that properly sets TOS flags,
3738 and take another look:
3740 <Screen>
3741 # scp tc ahu@10.0.0.11:./
3742 ahu@10.0.0.11's password: 
3743 tc                   100% |*****************************|   353 KB    00:00    
3744 # tc -s qdisc ls dev eth0
3745 qdisc sfq 30: quantum 1514b 
3746  Sent 384228 bytes 274 pkts (dropped 0, overlimits 0) 
3748  qdisc tbf 20: rate 20Kbit burst 1599b lat 667.6ms 
3749  Sent 2640 bytes 20 pkts (dropped 0, overlimits 0) 
3751  qdisc sfq 10: quantum 1514b 
3752  Sent 2230 bytes 31 pkts (dropped 0, overlimits 0) 
3754  qdisc prio 1: bands 3 priomap  1 2 2 2 1 2 0 0 1 1 1 1 1 1 1 1
3755  Sent 389140 bytes 326 pkts (dropped 0, overlimits 0) 
3756 </Screen>
3758 As you can see, all traffic went to handle 30:, which is the lowest priority
3759 band, just as intended. Now to verify that interactive traffic goes to
3760 higher bands, we create some interactive traffic:
3761 </Para>
3763 <Para>
3765 <Screen>
3766 # tc -s qdisc ls dev eth0
3767 qdisc sfq 30: quantum 1514b 
3768  Sent 384228 bytes 274 pkts (dropped 0, overlimits 0) 
3770  qdisc tbf 20: rate 20Kbit burst 1599b lat 667.6ms 
3771  Sent 2640 bytes 20 pkts (dropped 0, overlimits 0) 
3773  qdisc sfq 10: quantum 1514b 
3774  Sent 14926 bytes 193 pkts (dropped 0, overlimits 0) 
3776  qdisc prio 1: bands 3 priomap  1 2 2 2 1 2 0 0 1 1 1 1 1 1 1 1
3777  Sent 401836 bytes 488 pkts (dropped 0, overlimits 0) 
3778 </Screen>
3780 </Para>
3782 <Para>
3783 It worked - all additional traffic has gone to 10:, which is our highest
3784 priority qdisc. No traffic was sent to the lowest priority, which previously
3785 received our entire scp.
3786 </Para>
3788 </Sect3>
3790 </Sect2>
3792 <Sect2>
3793 <Title>The famous CBQ qdisc</Title>
3795 <Para>
3796 As said before, CBQ is the most complex qdisc available, the most hyped, the
3797 least understood, and probably the trickiest one to get right. This is not
3798 because the authors are evil or incompetent, far from it, it's just that the
3799 CBQ algorithm isn't all that precise and doesn't really match the way Linux
3800 works.
3801 </Para>
3803 <Para>
3804 Besides being classful, CBQ is also a shaper and it is in that aspect that
3805 it really doesn't work very well. It should work like this. If you try to
3806 shape a 10mbit/s connection to 1mbit/s, the link should be idle 90% of the
3807 time. If it isn't, we need to throttle so that it IS idle 90% of the time.
3808 </Para>
3810 <Para>
3811 This is pretty hard to measure, so CBQ  instead derives the idle time from
3812 the number of microseconds that elapse between requests from the hardware
3813 layer for more data. Combined, this can be used to approximate how full or
3814 empty the link is.<!--which is combined with which?-->
3815 </Para>
3817 <Para>
3818 This is rather tortuous and doesn't always arrive at proper results. For
3819 example, what if the actual link speed of an interface that is not really
3820 able to transmit the full 100mbit/s of data, perhaps because of a badly
3821 implemented driver? A PCMCIA network card will also never achieve 100mbit/s
3822 because of the way the bus is designed - again, how do we calculate the idle
3823 time?
3824 </Para>
3826 <Para>
3827 It gets even worse if we consider not-quite-real network devices like PPP
3828 over Ethernet or PPTP over TCP/IP. The effective bandwidth in that case is
3829 probably determined by the efficiency of pipes to userspace - which is huge.
3830 </Para>
3832 <Para>
3833 People who have done measurements discover that CBQ is not always very
3834 accurate and sometimes completely misses the mark.
3835 </Para>
3837 <Para>
3838 In many circumstances however it works well. With the documentation provided
3839 here, you should be able to configure it to work well in most cases.
3840 </Para>
3842 <Sect3>
3843 <Title>CBQ shaping in detail</Title>
3845 <Para>
3846 As said before, CBQ works by making sure that the link is idle just long
3847 enough to bring down the real bandwidth to the configured rate. To do so, it
3848 calculates the time that should pass between average packets. 
3849 </Para>
3851 <Para>
3852 During operations, the effective idletime is measured using an exponential
3853 weighted moving average (EWMA), which considers recent packets to be
3854 exponentially more important than past ones. The UNIX loadaverage is
3855 calculated in the same way.
3856 </Para>
3858 <Para>
3859 The calculated idle time is subtracted from the EWMA measured one, the
3860 resulting number is called 'avgidle'. A perfectly loaded link has an avgidle
3861 of zero: packets arrive exactly once every calculated interval.  
3862 </Para>
3864 <Para>
3865 An overloaded link has a negative avgidle and if it gets too negative, CBQ
3866 shuts down for a while and is then 'overlimit'.
3867 </Para>
3869 <Para>
3870 Conversely, an idle link might amass a huge avgidle, which would then allow
3871 infinite bandwidths after a few hours of silence. To prevent this, avgidle is
3872 capped at maxidle.
3873 </Para>
3875 <Para>
3876 If overlimit, in theory, the CBQ could throttle itself for exactly the
3877 amount of time that was calculated to pass between packets, and then pass
3878 one packet, and throttle again. But see the 'minburst' parameter below.
3879 </Para>
3881 <Para>
3882 These are parameters you can specify in order to configure shaping:
3883 <VariableList>
3885 <VarListEntry>
3886 <Term>avpkt</Term>
3887 <ListItem>
3888 <Para>
3889 Average size of a packet, measured in bytes. Needed for calculating maxidle,
3890 which is derived from maxburst, which is specified in packets.
3891 </Para></ListItem>
3892 </VarListEntry>
3893 <VarListEntry>
3894 <Term>bandwidth</Term>
3895 <ListItem>
3896 <Para>
3897 The physical bandwidth of your device, needed for idle time
3898 calculations.
3899 </Para></ListItem>
3900 </VarListEntry>
3901 <VarListEntry>
3902 <Term>cell</Term>
3903 <ListItem>
3904 <Para>
3905 The time a packet takes to be transmitted over a device may grow in steps,
3906 based on the packet size. An 800 and an 806 size packet may take just as long
3907 to send, for example - this sets the granularity. Most often set to '8'.
3908 Must be an integral power of two.
3909 </Para></ListItem>
3910 </VarListEntry>
3911 <VarListEntry>
3912 <Term>maxburst</Term>
3913 <ListItem>
3914 <Para>
3915 This number of packets is used to calculate maxidle so that when avgidle is
3916 at maxidle, this number of average packets can be burst before avgidle drops
3917 to 0. Set it higher to be more tolerant of bursts. You can't set maxidle
3918 directly, only via this parameter.
3919 </Para></ListItem>
3920 </VarListEntry>
3921 <VarListEntry>
3922 <Term>minburst</Term>
3923 <ListItem>
3924 <Para>
3925 As mentioned before, CBQ needs to throttle in case of overlimit. The ideal
3926 solution is to do so for exactly the calculated idle time, and pass 1
3927 packet. For Unix kernels, however, it is generally hard to schedule events
3928 shorter than 10ms, so it is better to throttle for a longer period, and then
3929 pass minburst packets in one go, and then sleep minburst times longer.
3930 </Para>
3932 <Para>
3933 The time to wait is called the offtime. Higher values of minburst lead to
3934 more accurate shaping in the long term, but to bigger bursts at millisecond
3935 timescales.
3936 </Para></ListItem>
3937 </VarListEntry>
3938 <VarListEntry>
3939 <Term>minidle</Term>
3940 <ListItem>
3941 <Para>
3942 If avgidle is below 0, we are overlimits and need to wait until avgidle will
3943 be big enough to send one packet. To prevent a sudden burst from shutting
3944 down the link for a prolonged period of time, avgidle is reset to minidle if
3945 it gets too low.
3946 </Para>
3948 <Para>
3949 Minidle is specified in negative microseconds, so 10 means that avgidle is
3950 capped at -10us.
3951 </Para></ListItem>
3952 </VarListEntry>
3953 <VarListEntry>
3954 <Term>mpu</Term>
3955 <ListItem>
3956 <Para>
3957 Minimum packet size - needed because even a zero size packet is padded
3958 to 64 bytes on ethernet, and so takes a certain time to transmit. CBQ needs
3959 to know this to accurately calculate the idle time.
3960 </Para></ListItem>
3961 </VarListEntry>
3962 <VarListEntry>
3963 <Term>rate</Term>
3964 <ListItem>
3965 <Para>
3966 Desired rate of traffic leaving this qdisc - this is the 'speed knob'!
3967 </Para></ListItem>
3968 </VarListEntry>
3969 </VariableList>
3970 </Para>
3972 <Para>
3973 Internally, CBQ has a lot of fine tuning. For example, classes which are
3974 known not to have data enqueued to them aren't queried. Overlimit classes
3975 are penalized by lowering their effective priority. All very smart &amp;
3976 complicated.
3977 </Para>
3979 </Sect3>
3981 <Sect3>
3982 <Title>CBQ classful behaviour</Title>
3984 <Para>
3985 Besides shaping, using the aforementioned idletime approximations, CBQ also
3986 acts like the PRIO queue in the sense that classes can have differing
3987 priorities and that lower priority numbers will be polled before the higher
3988 priority ones.
3989 </Para>
3991 <Para>
3992 Each time a packet is requested by the hardware layer to be sent out to the
3993 network, a weighted round robin process ('WRR') starts, beginning with the
3994 lower-numbered priority classes.
3995 </Para>
3997 <Para>
3998 These are then grouped and queried if they have data available. If so, it is
3999 returned. After a class has been allowed to dequeue a number of bytes, the
4000 next class within that priority is tried.
4001 </Para>
4003 <Para>
4004 The following parameters control the WRR process:
4005 <VariableList>
4007 <VarListEntry>
4008 <Term>allot</Term>
4009 <ListItem>
4010 <Para>
4011 When the outer CBQ is asked for a packet to send out on the interface, it
4012 will try all inner qdiscs (in the classes) in turn, in order of 
4013 the 'priority' parameter. Each time a class gets its turn, it can only send out
4014 a limited amount of data. 'Allot' is the base unit of this amount. See 
4015 the 'weight' parameter for more information.
4016 </Para></ListItem>
4017 </VarListEntry>
4018 <VarListEntry>
4019 <Term>prio</Term>
4020 <ListItem>
4021 <Para>
4022 The CBQ can also act like the PRIO device. Inner classes with higher priority
4023 are tried first and as long as they have traffic, other classes are not
4024 polled for traffic.
4025 </Para></ListItem>
4026 </VarListEntry>
4027 <!--It is rather confusing between high/low "priority" and
4028     "priorigy number" around here.
4029     How about using large/small for the latter?-->
4030 <VarListEntry>
4031 <Term>weight</Term>
4032 <ListItem>
4033 <Para>
4034 Weight helps in the Weighted Round Robin process. Each class gets a chance
4035 to send in turn. If you have classes with significantly more bandwidth than
4036 other classes, it makes sense to allow them to send more data in one round
4037 than the others.
4038 </Para>
4040 <Para>
4041 A CBQ adds up all weights under a class, and normalizes them, so you can use
4042 arbitrary numbers: only the ratios are important. People have been 
4043 using 'rate/10' as a rule of thumb and it appears to work well. The renormalized
4044 weight is multiplied by the 'allot' parameter to determine how much data can
4045 be sent in one round. 
4046 </Para></ListItem>
4047 </VarListEntry>
4048 </VariableList>
4049 </Para>
4051 <Para>
4052 Please note that all classes within an CBQ hierarchy need to share the same
4053 major number!
4054 </Para>
4056 </Sect3>
4058 <Sect3>
4059 <Title>CBQ parameters that determine link sharing &amp; borrowing</Title>
4061 <Para>
4062 Besides purely limiting certain kinds of traffic, it is also possible to
4063 specify which classes can borrow capacity from other classes or, conversely,
4064 lend out bandwidth.
4065 </Para>
4067 <Para>
4068 <VariableList>
4070 <VarListEntry>
4071 <Term>Isolated/sharing</Term>
4072 <ListItem>
4073 <Para>
4074 A class that is configured with 'isolated' will not lend out bandwidth to
4075 sibling classes. Use this if you have competing or mutually-unfriendly
4076 agencies on your link who do not want to give each other freebies.
4077 </Para>
4079 <Para>
4080 The control program tc also knows about 'sharing', which is the reverse 
4081 of 'isolated'.
4082 </Para></ListItem>
4083 </VarListEntry>
4084 <VarListEntry>
4085 <Term>bounded/borrow</Term>
4086 <ListItem>
4087 <Para>
4088 A class can also be 'bounded', which means that it will not try to borrow
4089 bandwidth from sibling classes. tc also knows about 'borrow', which is the
4090 reverse of 'bounded'.
4091 </Para></ListItem>
4092 </VarListEntry>
4093 </VariableList>
4094 A typical situation might be where you have two agencies on your link which
4095 are both 'isolated' and 'bounded', which means that they are really limited
4096 to their assigned rate, and also won't allow each other to borrow.
4097 </Para>
4099 <Para>
4100 Within such an agency class, there might be other classes which are allowed
4101 to swap bandwidth.
4102 </Para>
4104 </Sect3>
4106 <Sect3>
4107 <Title>Sample configuration</Title>
4108 <Screen>
4110                1:           root qdisc
4111                |
4112               1:1           child class
4113              /   \
4114             /     \
4115           1:3     1:4       leaf classes
4116            |       |
4117           30:     40:       qdiscs
4118          (sfq)   (sfq)
4119 </Screen>
4121 <Para>
4122 This configuration limits webserver traffic to 5mbit and SMTP traffic to 3
4123 mbit. Together, they may not get more than 6mbit. We have a 100mbit NIC and
4124 the classes may borrow bandwidth from each other.
4126 <Screen>
4127 # tc qdisc add dev eth0 root handle 1:0 cbq bandwidth 100Mbit         \
4128   avpkt 1000 cell 8
4129 # tc class add dev eth0 parent 1:0 classid 1:1 cbq bandwidth 100Mbit  \
4130   rate 6Mbit weight 0.6Mbit prio 8 allot 1514 cell 8 maxburst 20      \
4131   avpkt 1000 bounded
4132 </Screen>
4134 This part installs the root and the customary 1:1 class. The 1:1 class is
4135 bounded, so the total bandwidth can't exceed 6mbit.
4136 </Para>
4138 <Para>
4139 As said before, CBQ requires a *lot* of knobs. All parameters are explained
4140 above, however. The corresponding HTB configuration is lots simpler.
4141 </Para>
4143 <Para>
4145 <Screen>
4146 # tc class add dev eth0 parent 1:1 classid 1:3 cbq bandwidth 100Mbit  \
4147   rate 5Mbit weight 0.5Mbit prio 5 allot 1514 cell 8 maxburst 20      \
4148   avpkt 1000                       
4149 # tc class add dev eth0 parent 1:1 classid 1:4 cbq bandwidth 100Mbit  \
4150   rate 3Mbit weight 0.3Mbit prio 5 allot 1514 cell 8 maxburst 20      \
4151   avpkt 1000
4152 </Screen>
4154 </Para>
4156 <Para>
4157 These are our two leaf classes. Note how we scale the weight with the configured
4158 rate. Both classes are not bounded, but they are connected to class 1:1
4159 which is bounded.  So the sum of bandwith of the 2 classes will never be
4160 more than 6mbit. The classids need to be within the same major number as
4161 the parent qdisc, by the way!
4162 </Para>
4164 <Para>
4166 <Screen>
4167 # tc qdisc add dev eth0 parent 1:3 handle 30: sfq
4168 # tc qdisc add dev eth0 parent 1:4 handle 40: sfq
4169 </Screen>
4171 </Para>
4173 <Para>
4174 Both classes have a FIFO qdisc by default.  But we replaced these with an SFQ
4175 queue so each flow of data is treated equally.
4177 <Screen>
4178 # tc filter add dev eth0 parent 1:0 protocol ip prio 1 u32 match ip \
4179   sport 80 0xffff flowid 1:3
4180 # tc filter add dev eth0 parent 1:0 protocol ip prio 1 u32 match ip \
4181   sport 25 0xffff flowid 1:4
4182 </Screen>
4184 </Para>
4186 <Para>
4187 These commands, attached directly to the root, send traffic to the right
4188 qdiscs.
4189 </Para>
4191 <Para>
4192 Note that we use 'tc class add' to CREATE classes within a qdisc, but that
4193 we use 'tc qdisc add' to actually add qdiscs to these classes.
4194 </Para>
4196 <Para>
4197 You may wonder what happens to traffic that is not classified by any of the
4198 two rules. It appears that in this case, data will then be processed within
4199 1:0, and be unlimited. 
4200 </Para>
4202 <Para>
4203 If SMTP+web together try to exceed the set limit of 6mbit/s, bandwidth will
4204 be divided according to the weight parameter, giving 5/8 of traffic to  the
4205 webserver and 3/8 to the mail server.
4206 </Para>
4208 <Para>
4209 With this configuration you can also say that webserver traffic will always
4210 get at minimum 5/8 * 6 mbit = 3.75 mbit.
4211 </Para>
4213 </Sect3>
4215 <Sect3>
4216 <Title>Other CBQ parameters: split &amp; defmap</Title>
4218 <Para>
4219 As said before, a classful qdisc needs to call filters to determine
4220 which class a packet will be enqueued to. 
4221 </Para>
4223 <Para>
4224 Besides calling the filter, CBQ offers other options, defmap &amp; split.
4225 This is pretty complicated to understand, and it is not vital. But as this
4226 is the only known place where defmap &amp; split are properly explained, I'm
4227 doing my best. 
4228 </Para>
4230 <Para>
4231 As you will often want to filter on the Type of Service field only, a special
4232 syntax is provided. Whenever the CBQ needs to figure out where a packet
4233 needs to be enqueued, it checks if this node is a 'split node'. If so, one
4234 of the sub-qdiscs has indicated that it wishes to receive all packets with
4235 a certain configured priority, as might be derived from the TOS field, or
4236 socket options set by applications.
4237 </Para>
4239 <Para>
4240 The packets' priority bits are and-ed with the defmap field to see if a match
4241 exists. In other words, this is a short-hand way of creating a very fast
4242 filter, which only matches certain priorities. A defmap of ff (hex) will
4243 match everything, a map of 0 nothing. A sample configuration may help make
4244 things clearer:
4245 </Para>
4247 <Para>
4249 <Screen>
4250 # tc qdisc add dev eth1 root handle 1: cbq bandwidth 10Mbit allot 1514 \
4251   cell 8 avpkt 1000 mpu 64
4253 # tc class add dev eth1 parent 1:0 classid 1:1 cbq bandwidth 10Mbit    \
4254   rate 10Mbit allot 1514 cell 8 weight 1Mbit prio 8 maxburst 20        \
4255   avpkt 1000
4256 </Screen>
4258 Standard CBQ preamble. I never get used to the sheer amount of numbers
4259 required!
4260 </Para>
4262 <Para>
4263 Defmap refers to TC_PRIO bits, which are defined as follows:
4264 </Para>
4266 <Para>
4268 <Screen>
4269 TC_PRIO..          Num  Corresponds to TOS
4270 -------------------------------------------------
4271 BESTEFFORT         0    Maximize Reliablity        
4272 FILLER             1    Minimize Cost              
4273 BULK               2    Maximize Throughput (0x8)  
4274 INTERACTIVE_BULK   4                               
4275 INTERACTIVE        6    Minimize Delay (0x10)      
4276 CONTROL            7                               
4277 </Screen>
4279 </Para>
4281 <Para>
4282 The TC_PRIO.. number corresponds to bits, counted from the right. See the
4283 pfifo_fast section for more details how TOS bits are converted to
4284 priorities.
4285 </Para>
4287 <Para>
4288 Now the interactive and the bulk classes:
4289 </Para>
4291 <Para>
4293 <Screen>
4294 # tc class add dev eth1 parent 1:1 classid 1:2 cbq bandwidth 10Mbit     \
4295   rate 1Mbit allot 1514 cell 8 weight 100Kbit prio 3 maxburst 20        \
4296   avpkt 1000 split 1:0 defmap c0
4298 # tc class add dev eth1 parent 1:1 classid 1:3 cbq bandwidth 10Mbit     \
4299   rate 8Mbit allot 1514 cell 8 weight 800Kbit prio 7 maxburst 20        \
4300   avpkt 1000 split 1:0 defmap 3f
4301 </Screen>
4303 </Para>
4305 <Para>
4306 The 'split qdisc' is 1:0, which is where the choice will be made. C0 is
4307 binary for 11000000, 3F for 00111111, so these two together will match
4308 everything. The first class matches bits 7 &#38; 6, and thus corresponds 
4309 to 'interactive' and 'control' traffic. The second class matches the rest.
4310 </Para>
4312 <Para>
4313 Node 1:0 now has a table like this:
4315 <Screen>
4316 priority        send to
4317 0               1:3
4318 1               1:3
4319 2               1:3
4320 3               1:3
4321 4               1:3
4322 5               1:3
4323 6               1:2
4324 7               1:2
4325 </Screen>
4327 </Para>
4329 <Para>
4330 For additional fun, you can also pass a 'change mask', which indicates
4331 exactly which priorities you wish to change. You only need to use this if you
4332 are running 'tc class change'. For example, to add best effort traffic to
4333 1:2, we could run this:
4334 </Para>
4336 <Para>
4338 <Screen>
4339 # tc class change dev eth1 classid 1:2 cbq defmap 01/01
4340 </Screen>
4342 </Para>
4344 <Para>
4345 The priority map at 1:0 now looks like this:
4346 </Para>
4348 <Para>
4350 <Screen>
4351 priority        send to
4352 0               1:2
4353 1               1:3
4354 2               1:3
4355 3               1:3
4356 4               1:3
4357 5               1:3
4358 6               1:2
4359 7               1:2
4360 </Screen>
4362 </Para>
4364 <Para>
4365 FIXME: did not test 'tc class change', only looked at the source.
4366 </Para>
4368 </Sect3>
4370 </Sect2>
4372 <Sect2>
4373 <Title>Hierarchical Token Bucket </Title>
4375 <Para>
4376 Martin Devera (&lt;devik&gt;) rightly realised that CBQ is complex and does
4377 not seem optimized for many typical situations. His Hierarchical approach is
4378 well suited for setups where you have a fixed amount of bandwidth which you
4379 want to divide for different purposes, giving each purpose a guaranteed
4380 bandwidth, with the possibility of specifying how much bandwidth can be
4381 borrowed.
4382 </Para>
4384 <Para>
4385 HTB works just like CBQ but does not resort to idle time calculations to
4386 shape. Instead, it is a classful Token Bucket Filter - hence the name. It
4387 has only a few parameters, which are well documented on his 
4388 <ULink
4389 URL="http://luxik.cdi.cz/~devik/qos/htb/"
4390 >site</ULink
4392 </Para>
4394 <Para>
4395 As your HTB configuration gets more complex, your configuration scales
4396 well. With CBQ it is already complex even in simple cases! HTB3 (check
4397 <ulink url="http://luxik.cdi.cz/~devik/qos/htb/">its homepage</ulink> for
4398 details on HTB versions) is now part of the official kernel sources 
4399 (from 2.4.20-pre1 and 2.5.31 onwards). However, maybe you still need to
4400 get a HTB3 patched version of 'tc': HTB kernel and userspace parts must
4401 be the same major version, or 'tc' will not work with HTB.
4403 </Para>
4405 <Para>
4406 If you already have a modern kernel, or are in a position to patch your 
4407 kernel, by all means consider HTB.
4408 </para>
4411 <Sect3>
4412 <Title>Sample configuration</Title>
4414 <Para>
4415 Functionally almost identical to the CBQ sample configuration above:
4416 </Para>
4418 <Para>
4420 <Screen>
4421 # tc qdisc add dev eth0 root handle 1: htb default 30
4423 # tc class add dev eth0 parent 1: classid 1:1 htb rate 6mbit burst 15k
4425 # tc class add dev eth0 parent 1:1 classid 1:10 htb rate 5mbit burst 15k
4426 # tc class add dev eth0 parent 1:1 classid 1:20 htb rate 3mbit ceil 6mbit burst 15k
4427 # tc class add dev eth0 parent 1:1 classid 1:30 htb rate 1kbit ceil 6mbit burst 15k
4428 </Screen>
4430 </Para>
4432 <Para>
4433 The author then recommends SFQ for beneath these classes:
4435 <Screen>
4436 # tc qdisc add dev eth0 parent 1:10 handle 10: sfq perturb 10
4437 # tc qdisc add dev eth0 parent 1:20 handle 20: sfq perturb 10
4438 # tc qdisc add dev eth0 parent 1:30 handle 30: sfq perturb 10
4439 </Screen>
4441 </Para>
4443 <Para>
4444 Add the filters which direct traffic to the right classes:
4446 <Screen>
4447 # U32="tc filter add dev eth0 protocol ip parent 1:0 prio 1 u32"
4448 # $U32 match ip dport 80 0xffff flowid 1:10
4449 # $U32 match ip sport 25 0xffff flowid 1:20
4450 </Screen>
4452 And that's it - no unsightly unexplained numbers, no undocumented
4453 parameters. 
4454 </Para>
4456 <Para>
4457 HTB certainly looks wonderful - if 10: and 20: both have their guaranteed
4458 bandwidth, and more is left to divide, they borrow in a 5:3 ratio, just as
4459 you would expect.
4460 </Para>
4462 <Para>
4463 Unclassified traffic gets routed to 30:, which has little bandwidth of its
4464 own but can borrow everything that is left over. Because we chose SFQ
4465 internally, we get fairness thrown in for free!
4466 </Para>
4468 </Sect3>
4470 </Sect2>
4472 </Sect1>
4474 <Sect1 id="lartc.qdisc.filters">
4475   <Title>Classifying packets with filters</Title>
4477 <Para>
4478 To determine which class shall process a packet, the so-called 'classifier
4479 chain' is called each time a choice needs to be made. This chain consists of
4480 all filters attached to the classful qdisc that needs to decide.
4481 </Para>
4483 <Para>To reiterate the tree, which is not a tree:
4484 </Para>
4486 <Screen width="80">
4487                     root 1:
4488                       |
4489                     _1:1_
4490                    /  |  \
4491                   /   |   \
4492                  /    |    \
4493                10:   11:   12:
4494               /   \       /   \
4495            10:1  10:2   12:1  12:2
4496 </Screen>
4498 <Para>
4499 When enqueueing a packet, at each branch the filter chain is consulted for a
4500 relevant instruction. A typical setup might be to have a filter in 1:1 that
4501 directs a packet to 12: and a filter on 12: that sends the packet to 12:2.
4502 </Para>
4504 <Para>
4505 You might also attach this latter rule to 1:1, but you can make efficiency
4506 gains by having more specific tests lower in the chain.
4507 </Para>
4509 <Para>
4510 You can't filter a packet 'upwards', by the way. Also, with HTB, you should
4511 attach all filters to the root!
4512 </Para>
4514 <Para>
4515 And again - packets are only enqueued downwards! When they are dequeued,
4516 they go up again, where the interface lives. They do NOT fall off the end of
4517 the tree to the network adaptor!
4518 </Para>
4520 <Sect2>
4521 <Title>Some simple filtering examples</Title>
4523 <Para>
4524 As explained in the Classifier chapter, you can match on literally anything,
4525 using a very complicated syntax. To start, we will show how to do the
4526 obvious things, which luckily are quite easy.
4527 </Para>
4529 <Para>
4530 Let's say we have a PRIO qdisc called '10:' which contains three classes, and
4531 we want to assign all traffic from and to port 22 to the highest priority
4532 band, the filters would be:
4533 </Para>
4535 <Para>
4537 <Screen>
4538 # tc filter add dev eth0 protocol ip parent 10: prio 1 u32 match \ 
4539   ip dport 22 0xffff flowid 10:1
4540 # tc filter add dev eth0 protocol ip parent 10: prio 1 u32 match \
4541   ip sport 80 0xffff flowid 10:1
4542 # tc filter add dev eth0 protocol ip parent 10: prio 2 flowid 10:2
4543 </Screen>
4545 </Para>
4547 <Para>
4548 What does this say? It says: attach to eth0, node 10: a  priority 1 u32
4549 filter that matches on IP destination port 22 *exactly* and send it to band
4550 10:1. And it then repeats the same for source port 80. The last command says
4551 that anything unmatched so far should go to band 10:2, the next-highest
4552 priority.
4553 </Para>
4555 <Para>
4556 You need to add 'eth0', or whatever your interface is called, because each
4557 interface has a unique namespace of handles.
4558 </Para>
4560 <Para>
4561 To select on an IP address, use this:
4563 <Screen>
4564 # tc filter add dev eth0 parent 10:0 protocol ip prio 1 u32 \ 
4565   match ip dst 4.3.2.1/32 flowid 10:1
4566 # tc filter add dev eth0 parent 10:0 protocol ip prio 1 u32 \
4567   match ip src 1.2.3.4/32 flowid 10:1
4568 # tc filter add dev eth0 protocol ip parent 10: prio 2      \
4569   flowid 10:2
4570 </Screen>
4572 </Para>
4574 <Para>
4575 This assigns traffic to 4.3.2.1 and traffic from 1.2.3.4 to the highest
4576 priority queue, and the rest to the next-highest one.
4577 </Para>
4579 <Para>
4580 You can concatenate matches, to match on traffic from 1.2.3.4 and from port
4581 80, do this:
4583 <Screen>
4584 # tc filter add dev eth0 parent 10:0 protocol ip prio 1 u32 match ip src 4.3.2.1/32 \
4585   match ip sport 80 0xffff flowid 10:1
4586 </Screen>
4588 </Para>
4590 </Sect2>
4592 <Sect2 id="lartc.filtering.simple">
4593 <Title>All the filtering commands you will normally need</Title>
4595 <Para>
4596 Most shaping commands presented here start with this preamble:
4598 <Screen>
4599 # tc filter add dev eth0 parent 1:0 protocol ip prio 1 u32 ..
4600 </Screen>
4602 These are the so called 'u32' matches, which can match on ANY part of a
4603 packet.
4604 <VariableList>
4606 <VarListEntry>
4607 <Term>On source/destination address</Term>
4608 <ListItem>
4609 <Para>
4610 Source mask 'match ip src 1.2.3.0/24', destination mask 'match ip dst
4611 4.3.2.0/24'. To match a single host, use /32, or omit the mask.
4612 </Para></ListItem>
4613 </VarListEntry>
4614 <VarListEntry>
4615 <Term>On source/destination port, all IP protocols</Term>
4616 <ListItem>
4617 <Para>
4618 Source: 'match ip sport 80 0xffff', destination: 'match ip dport 80 0xffff'
4619 </Para></ListItem>
4620 </VarListEntry>
4621 <VarListEntry>
4622 <Term>On ip protocol (tcp, udp, icmp, gre, ipsec)</Term>
4623 <ListItem>
4624 <Para>
4625 Use the numbers from /etc/protocols, for example, icmp is 1: 'match ip
4626 protocol 1 0xff'. 
4627 </Para></ListItem>
4628 </VarListEntry>
4629 <VarListEntry>
4630 <Term>On fwmark</Term>
4631 <ListItem>
4632 <Para>
4633 You can mark packets with either ipchains or iptables and have that mark
4634 survive routing across interfaces. This is really useful to for example only
4635 shape traffic on eth1 that came in on eth0. Syntax:
4636 <screen>
4637 # tc filter add dev eth1 protocol ip parent 1:0 prio 1 handle 6 fw flowid 1:1
4638 </screen>
4639 Note that this is not a u32 match!
4640 </Para>
4642 <Para>
4643 You can place a mark like this:
4645 <Screen>
4646 # iptables -A PREROUTING -t mangle -i eth0 -j MARK --set-mark 6
4647 </Screen>
4649 The number 6 is arbitrary.
4650 </Para>
4652 <Para>
4653 If you don't want to understand the full tc filter syntax, just use
4654 iptables, and only learn to select on fwmark.
4655 </Para></ListItem>
4656 </VarListEntry>
4657 <VarListEntry>
4658 <Term>On the TOS field</Term>
4659 <ListItem>
4660 <Para>
4661 To select interactive, minimum delay traffic:
4663 <Screen>
4664 # tc filter add dev ppp0 parent 1:0 protocol ip prio 10 u32 \
4665       match ip tos 0x10 0xff \
4666      flowid 1:4
4667 </Screen>
4669 Use 0x08 0xff for bulk traffic.
4670 </Para></ListItem>
4671 </VarListEntry>
4672 </VariableList>
4673 </Para>
4675 <Para>
4676 For more filtering commands, see the Advanced Filters chapter.
4677 </Para>
4679 </Sect2>
4681 </Sect1>
4682 <Sect1 id="lartc.imq">
4683 <Title>The Intermediate queueing device (IMQ)</Title>
4685 <Para>
4686 The Intermediate queueing device is not a qdisc but its usage is tightly bound
4687 to qdiscs. Within linux, qdiscs are attached to network devices and everything
4688 that is queued to the device is first queued to the qdisc. From this concept,
4689 two limitations arise:
4690 </Para>
4692 <Orderedlist>
4693 <Listitem>
4694 <Para>
4695 Only egress shaping is possible (an ingress qdisc exists, but its
4696 possibilities are very limited compared to classful qdiscs).
4697 </Para>
4698 </Listitem>
4699 <Listitem>
4700 <Para>
4701 A qdisc can only see traffic of one interface, global limitations can't be
4702 placed.
4703 </Para>
4704 </Listitem>
4705 </Orderedlist>
4707 <Para>
4708 IMQ is there to help solve those two limitations. In short, you can put 
4709 everything you choose in a qdisc. Specially marked packets get intercepted
4710 in netfilter NF_IP_PRE_ROUTING and NF_IP_POST_ROUTING hooks and pass through
4711 the qdisc attached to an imq device. An iptables target is used for marking
4712 the packets.
4713 </Para>
4715 <Para>
4716 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.
4717 You can also do lots of other stuff like just putting your http traffic in a
4718 qdisc, put new connection requests in a qdisc, ...
4719 </Para>
4721 <Sect2>
4722 <Title>Sample configuration</Title>
4724 <Para>
4725 The first thing that might come to mind is use ingress shaping to give yourself
4726 a high guaranteed bandwidth. ;)
4727 Configuration is just like with any other interface:
4729 <Screen>
4730 tc qdisc add dev imq0 root handle 1: htb default 20
4732 tc class add dev imq0 parent 1: classid 1:1 htb rate 2mbit burst 15k
4734 tc class add dev imq0 parent 1:1 classid 1:10 htb rate 1mbit
4735 tc class add dev imq0 parent 1:1 classid 1:20 htb rate 1mbit
4737 tc qdisc add dev imq0 parent 1:10 handle 10: pfifo
4738 tc qdisc add dev imq0 parent 1:20 handle 20: sfq
4740 tc filter add dev imq0 parent 10:0 protocol ip prio 1 u32 match \
4741                 ip dst 10.0.0.230/32 flowid 1:10
4742 </Screen>
4744 In this example u32 is used for classification. Other classifiers should work as
4745 expected.
4746 Next traffic has to be selected and marked to be enqueued to imq0.
4748 <Screen>
4749 iptables -t mangle -A PREROUTING -i eth0 -j IMQ --todev 0
4751 ip link set imq0 up
4752 </Screen>
4754 </Para>
4756 <Para>
4757 The IMQ iptables targets is valid in the PREROUTING and POSTROUTING chains of
4758 the mangle table. It's syntax is 
4760 <Screen>
4761 IMQ [ --todev n ]       n : number of imq device
4762 </Screen>
4764 An ip6tables target is also provided.
4765 </Para>
4767 <Para>
4768 Please note traffic is not enqueued when the target is hit but afterwards.
4769 The exact location where traffic enters the imq device depends on the
4770 direction of the traffic (in/out).
4771 These are the predefined netfilter hooks used by iptables:
4773 <Screen>
4774 enum nf_ip_hook_priorities {
4775         NF_IP_PRI_FIRST = INT_MIN,
4776         NF_IP_PRI_CONNTRACK = -200,
4777         NF_IP_PRI_MANGLE = -150,
4778         NF_IP_PRI_NAT_DST = -100,
4779         NF_IP_PRI_FILTER = 0,
4780         NF_IP_PRI_NAT_SRC = 100,
4781         NF_IP_PRI_LAST = INT_MAX,
4783 </Screen>
4785 </Para>
4787 <Para>
4788 For ingress traffic, imq registers itself with NF_IP_PRI_MANGLE + 1 priority
4789 which means packets enter the imq device directly after the mangle PREROUTING
4790 chain has been passed.
4791 </Para>
4793 <Para>
4794 For egress imq uses NF_IP_PRI_LAST which honours the fact that packets dropped
4795 by the filter table won't occupy bandwidth.
4796 </Para>
4798 <Para>
4799 The patches and some more information can be found at the
4800 <ULink
4801 URL="http://luxik.cdi.cz/~patrick/imq/"
4802 >imq site</ULink>.
4803 </Para>
4805 </Sect2>
4807 </Sect1>
4809 </chapter>
4811 <chapter id="lartc.loadshare">
4812 <Title>Load sharing over multiple interfaces</Title>
4814 <Para>
4815 There are several ways of doing this. One of the easiest and straightforward
4816 ways is 'TEQL' - "True" (or "trivial") link equalizer. Like most things
4817 having to do with queueing, load sharing goes both ways. Both ends of a link
4818 may need to participate for full effect.
4819 </Para>
4821 <Para>
4822 Imagine this situation:
4823 </Para>
4825 <Para>
4827 <Screen>
4828                  +-------+   eth1   +-------+
4829                  |       |==========|       |
4830  'network 1' ----|   A   |          |   B   |---- 'network 2'
4831                  |       |==========|       |
4832                  +-------+   eth2   +-------+
4833 </Screen>
4835 </Para>
4837 <Para>
4838 A and B are routers, and for the moment we'll assume both run Linux. If
4839 traffic is going from network 1 to network 2, router A needs to distribute
4840 the packets over both links to B. Router B needs to be configured to accept
4841 this. Same goes the other way around, when packets go from network 2 to
4842 network 1, router B needs to send the packets over both eth1 and eth2.
4843 </Para>
4845 <Para>
4846 The distributing part is done by a 'TEQL' device, like this (it couldn't be
4847 easier):
4848 </Para>
4850 <Para>
4852 <Screen>
4853 # tc qdisc add dev eth1 root teql0
4854 # tc qdisc add dev eth2 root teql0
4855 # ip link set dev teql0 up
4856 </Screen>
4858 </Para>
4860 <Para>
4861 Don't forget the 'ip link set up' command!
4862 </Para>
4864 <Para>
4865 This needs to be done on both hosts. The device teql0 is basically a
4866 roundrobbin distributor over eth1 and eth2, for sending packets. No data
4867 ever comes in over an teql device, that just appears on the 'raw' eth1 and
4868 eth2.
4869 </Para>
4871 <Para>
4872 But now we just have devices, we also need proper routing. One way to do
4873 this is to assign a /31 network to both links, and a /31 to the teql0 device
4874 as well:
4875 </Para>
4877 <Para>
4878 On router A:
4880 <Screen>
4881 # ip addr add dev eth1 10.0.0.0/31
4882 # ip addr add dev eth2 10.0.0.2/31
4883 # ip addr add dev teql0 10.0.0.4/31
4884 </Screen>
4886 </Para>
4888 <Para>
4889 On router B:
4891 <Screen>
4892 # ip addr add dev eth1 10.0.0.1/31
4893 # ip addr add dev eth2 10.0.0.3/31
4894 # ip addr add dev teql0 10.0.0.5/31
4895 </Screen>
4897 </Para>
4899 <Para>
4900 Router A should now be able to ping 10.0.0.1, 10.0.0.3 and 10.0.0.5 over the
4901 2 real links and the 1 equalized device. Router B should be able to ping
4902 10.0.0.0, 10.0.0.2 and 10.0.0.4 over the links.
4903 </Para>
4905 <Para>
4906 If this works, Router A should make 10.0.0.5 its route for reaching network
4907 2, and Router B should make 10.0.0.4 its route for reaching network 1. For
4908 the special case where network 1 is your network at home, and network 2 is
4909 the Internet, Router A should make 10.0.0.5 its default gateway.
4910 </Para>
4912 <Sect1 id="lartc.loadshare.caveats">
4913   <Title>Caveats</Title>
4915 <Para>
4916 Nothing is as easy as it seems. eth1 and eth2 on both router A and B need to
4917 have return path filtering turned off, because they will otherwise drop
4918 packets destined for ip addresses other than their own:
4919 </Para>
4921 <Para>
4923 <Screen>
4924 # echo 0 &#62; /proc/sys/net/ipv4/conf/eth1/rp_filter
4925 # echo 0 &#62; /proc/sys/net/ipv4/conf/eth2/rp_filter
4926 </Screen>
4928 </Para>
4930 <Para>
4931 Then there is the nasty problem of packet reordering. Let's say 6 packets
4932 need to be sent from A to B - eth1 might get 1, 3 and 5. eth2 would then do
4933 2, 4 and 6. In an ideal world, router B would receive this in order, 1, 2,
4934 3, 4, 5, 6. But the possibility is very real that the kernel gets it like
4935 this: 2, 1, 4, 3, 6, 5. The problem is that this confuses TCP/IP. While not
4936 a problem for links carrying many different TCP/IP sessions, you won't be
4937 able to bundle multiple links and get to ftp a single file lots faster,
4938 except when your receiving or sending OS is Linux, which is not easily
4939 shaken by some simple reordering.
4940 </Para>
4942 <Para>
4943 However, for lots of applications, link load balancing is a great idea.
4944 </Para>
4946 </Sect1>
4947 <Sect1 id="lartc.loadshare.other">
4948   <Title>Other possibilities</Title>
4949 <para>
4950 William Stearns has used an advanced tunneling setup to achieve good use of
4951 multiple, unrelated, internet connections together. It can be found on
4952 <ULink
4953 URL="http://www.stearns.org/tunnel/">his tunneling page</ULink>.
4954 </para>
4955 <para>
4956 The HOWTO may feature more about this in the future.
4957 </para>
4958 </Sect1>
4959 </chapter>
4961 <chapter id="lartc.netfilter">
4962 <Title>Netfilter &amp; iproute - marking packets</Title>
4964 <Para>
4965 So far we've seen how iproute works, and netfilter was mentioned a few
4966 times. This would be a good time to browse through <ULink
4967 URL="http://netfilter.samba.org/unreliable-guides/"
4968 >Rusty's Remarkably Unreliable Guides</ULink
4969 >. Netfilter itself
4970 can be found <ULink
4971 URL="http://netfilter.filewatcher.org/"
4972 >here</ULink
4974 </Para>
4976 <Para>
4977 Netfilter allows us to filter packets, or mangle their headers. One special
4978 feature is that we can mark a packet with a number. This is done with the
4979 --set-mark facility. 
4980 </Para>
4982 <Para>
4983 As an example, this command marks all packets destined for port 25, outgoing
4984 mail:
4985 </Para>
4987 <Para>
4989 <Screen>
4990 # iptables -A PREROUTING -i eth0 -t mangle -p tcp --dport 25 \
4991  -j MARK --set-mark 1
4992 </Screen>
4994 </Para>
4996 <Para>
4997 Let's say that we have multiple connections, one that is fast (and
4998 expensive, per megabyte) and one that is slower, but flat fee. We would most
4999 certainly like outgoing mail to go via the cheap route.
5000 </Para>
5002 <Para>
5003 We've already marked the packets with a '1', we now instruct the routing
5004 policy database to act on this:
5005 </Para>
5007 <Para>
5009 <Screen>
5010 # echo 201 mail.out &#62;&#62; /etc/iproute2/rt_tables
5011 # ip rule add fwmark 1 table mail.out
5012 # ip rule ls
5013 0:      from all lookup local 
5014 32764:  from all fwmark        1 lookup mail.out 
5015 32766:  from all lookup main 
5016 32767:  from all lookup default 
5017 </Screen>
5019 </Para>
5021 <Para>
5022 Now we generate a route to the slow but cheap link in the mail.out table:
5024 <Screen>
5025 # /sbin/ip route add default via 195.96.98.253 dev ppp0 table mail.out
5026 </Screen>
5028 </Para>
5030 <Para>
5031 And we are done. Should we want to make exceptions, there are lots of ways
5032 to achieve this. We can modify the netfilter statement to exclude certain
5033 hosts, or we can insert a rule with a lower priority that points to the main
5034 table for our excepted hosts.
5035 </Para>
5037 <Para>
5038 We can also use this feature to honour TOS bits by marking packets with a
5039 different type of service with different numbers, and creating rules to act
5040 on that. This way you can even dedicate, say, an ISDN line to interactive
5041 sessions.
5042 </Para>
5044 <Para>
5045 Needless to say, this also works fine on a host that's doing NAT
5046 ('masquerading').
5047 </Para>
5049 <Para>
5050 IMPORTANT: We received a report that MASQ and SNAT at least collide
5051 with marking packets. Rusty Russell explains it in
5052 <ULink
5053 URL="http://lists.samba.org/pipermail/netfilter/2000-November/006089.html"
5054 >this posting</ULink
5055 >. Turn off the reverse path filter to make it work
5056 properly.
5057 </Para>
5059 <Para>
5060 Note: to mark packets, you need to have some options enabled in your
5061 kernel:
5062 </Para>
5064 <Para>
5066 <Screen>
5067 IP: advanced router (CONFIG_IP_ADVANCED_ROUTER) [Y/n/?]
5068 IP: policy routing (CONFIG_IP_MULTIPLE_TABLES) [Y/n/?]
5069 IP: use netfilter MARK value as routing key (CONFIG_IP_ROUTE_FWMARK) [Y/n/?]
5070 </Screen>
5072 </Para>
5074 <Para>
5075 See also the <xref linkend="lartc.cookbook.squid"> in the
5076 <citetitle><xref linkend="lartc.cookbook"></citetitle>.
5077 </Para>
5079 </chapter>
5081 <chapter id="lartc.adv-filter"
5082   xreflabel="Advanced filters for (re-)classifying packets">
5083   <Title>Advanced filters for (re-)classifying packets</Title>
5085 <Para>
5086 As explained in the section on classful queueing disciplines, filters are
5087 needed to classify packets into any of the sub-queues. These filters are