3.4.1. ip shows us our links

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

Your mileage may vary, but this is what it shows on my NAT router athome. I'll only explain part of the output as not everything is directlyrelevant.

We first see the loopback interface. While your computer may functionsomewhat without one, I'd advise against it. The MTU size (Maximum TransferUnit) is 3924 octets, and it is not supposed to queue. Which makes sensebecause the loopback interface is a figment of your kernel's imagination.

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

Note the absence of IP addresses. iproute disconnects the concept of 'links'and 'IP addresses'. With IP aliasing, the concept of 'the' IP address hadbecome quite irrelevant anyhow.

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

3.4.2. ip shows us our IP addresses

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

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

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

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

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

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

You may also note 'qdisc', which stands for Queueing Discipline. This willbecome vital later on.

3.4.3. ip shows us our routes

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

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

This is pretty much self explanatory. The first 3 lines of output explicitlystate what was already implied by ip address show, the last linetells us that the rest of the world can be found via 212.64.94.1, ourdefault gateway. We can see that it is a gateway because of the wordvia, which tells us that we need to send packets to 212.64.94.1, and that itwill take care of things.

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

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

4.2.1. Split access

The first is how to route answers to packets coming in over a particular provider, say Provider 1, back out again over that same provider.

Let us first set some symbolical names. Let $IF1 be the name of the first interface (if1 in the picture above) and $IF2 the name of the second interface. Then let $IP1 be the IP address associated with $IF1 and $IP2 the IP address associated with $IF2. Next, let $P1 be the IP address of the gateway at Provider 1, and $P2 the IP address of the gateway at provider 2. Finally, let $P1_NET be the IP network $P1 is in, and $P2_NET the IP network $P2 is in.

One creates two additional routing tables, say T1 and T2. These are added in /etc/iproute2/rt_tables. Then you set up routing in these tables as follows:

	  ip route add $P1_NET dev $IF1 src $IP1 table T1
	  ip route add default via $P1 table T1
	  ip route add $P2_NET dev $IF2 src $IP2 table T2
	  ip route add default via $P2 table T2
	

Next you set up the main routing table. It is a good idea to route things to the direct neighbour through the interface connected to that neighbour. Note the `src' arguments, they make sure the right outgoing IP address is chosen.

	    ip route add $P1_NET dev $IF1 src $IP1
	    ip route add $P2_NET dev $IF2 src $IP2
	  

	    ip route add default via $P1
	  

	    ip rule add from $IP1 table T1
	    ip rule add from $IP2 table T2
	  

Reader Rod Roark notes: 'If $P0_NET is the local network and $IF0 is its interface,the following additional entries are desirable: ip route add $P0_NET dev $IF0 table T1 ip route add $P2_NET dev $IF2 table T1 ip route add 127.0.0.0/8 dev lo table T1 ip route add $P0_NET dev $IF0 table T2 ip route add $P1_NET dev $IF1 table T2 ip route add 127.0.0.0/8 dev lo table T2 '

Now, this is just the very basic setup. It will work for all processes running on the router itself, and for the local network, if it is masqueraded. If it is not, then you either have IP space from both providers or you are going to want to masquerade to one of the two providers. In both cases you will want to add rules selecting which provider to route out from based on the IP address of the machine in the local network.

4.2.2. Load balancing

The second question is how to balance traffic going out over the two providers. This is actually not hard if you already have set up split access as above.

Instead of choosing one of the two providers as your default route, you now set up the default route to be a multipath route. In the default kernel this will balance routes over the two providers. It is done as follows (once more building on the example in the section on split-access):

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

Note that balancing will not be perfect, as it is route based, and routes are cached. This means that routes to often-used sites will always be over the same provider.

Furthermore, if you really want to do this, you probably also want to look at Julian Anastasov's patches at http://www.ssi.bg/~ja/#routes , Julian's route patch page. They will make things nicer to work with.

5.3.1. IPv4 Tunneling

Let's do IPv4 tunneling first:

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

So we have network A:

network 10.0.1.0
netmask 255.255.255.0
router  10.0.1.1

and network B:

network 10.0.2.0
netmask 255.255.255.0
router  10.0.2.1

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

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

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

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

The second line enables the device.

In the third line we gave the newly born interface netb the address10.0.1.1. This is OK for smaller networks, but when you're starting up amining expedition (LOTS of tunnels), you might want to consider usinganother IP range for tunneling interfaces (in this example, you could use10.0.3.0).

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

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

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

ip link set netb down
ip tunnel del netb

5.3.2. IPv6 Tunneling

See Section 6 for a short bit about IPv6 Addresses.

On with the tunnels.

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

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

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

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

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

7.2.1. Theory

As explained before, automatic keying does a lot of the workfor us. Specifically, it creates Security Associations on the fly. It doesnot however set policy for us, which is as it should be.

So, to benefit from IKE, setup a policy, but do not supply anySAs. If the kernel discovers that there is an IPSEC policy, but no SecurityAssociation, it will notify the IKE daemon, which then goes to work ontrying to negotiate one.

Reiterating, a Security Policy specifies WHAT we want; a SecurityAssociation describes HOW we want it. Using automatic keying lets us getaway with only specifying what we want.

7.2.2. Example

Kame racoon comes with a grand host of options, most of which havevery fine default values, so we don't need to touch them. As describedabove, the operator needs to define a Security Policy, but no SecurityAssociations. We leave their negotiation to the IKE daemon.

In this example, 10.0.0.11 and 10.0.0.216 are once again going tosetup secure communications, but this time with help from racoon. Forsimplicity this configuration will be using pre-shared keys, thedreaded 'shared secrets'. X.509 certificates are discussed in a separatesection, see Section 7.2.3.

We'regoing to stick to almost the default configuration, identical on both hosts:

path pre_shared_key "/usr/local/etc/racoon/psk.txt";

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

	my_identifier address;

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

	proposal {
	        encryption_algorithm 3des;
	        hash_algorithm sha1;
	        authentication_method pre_shared_key;
	        dh_group 2 ;
	}
}
 
sainfo anonymous
{
 	pfs_group 1;
 	lifetime time 2 min;
 	encryption_algorithm 3des ;
 	authentication_algorithm hmac_sha1;
		compression_algorithm deflate ;
}

Lots of settings - I think yet more can be removed to get closer tothe default configuration. A few noteworthy things. We've configured twoanonymous settings which hold for all remotes, making further configurationeasy. There is no need for per-host stanzas here, unless we really wantthem.

Furthermore, we've set it up such that we identify ourselves basedon our IP address ('my_identifier address'), and declare that we can do3des, sha1, and that we will be using a pre-shared key, located in psk.txt.

In psk.txt, we now setup two entries, which do differ on both hosts.On 10.0.0.11:

10.0.0.216	password2

10.0.0.11	password2

Now we are ready to setup our desired policy, which is simpleenough. On host 10.0.0.216:

#!/sbin/setkey -f
flush;
spdflush;

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

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

#!/sbin/setkey -f
flush;
spdflush;

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

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

We are now ready to launch racoon! Once launched, the moment we tryto telnet from 10.0.0.11 to 10.0.0.216, or the other way around, racoonwill start negotiating:

12:18:44: INFO: isakmp.c:1689:isakmp_post_acquire(): IPsec-SA
  request for 10.0.0.11 queued due to no phase1 found.
12:18:44: INFO: isakmp.c:794:isakmp_ph1begin_i(): initiate new
  phase 1 negotiation: 10.0.0.216[500]<=>10.0.0.11[500]
12:18:44: INFO: isakmp.c:799:isakmp_ph1begin_i(): begin Aggressive mode.
12:18:44: INFO: vendorid.c:128:check_vendorid(): received Vendor ID: 
  KAME/racoon
12:18:44: NOTIFY: oakley.c:2037:oakley_skeyid(): couldn't find
  the proper pskey, try to get one by the peer's address.
12:18:44: INFO: isakmp.c:2417:log_ph1established(): ISAKMP-SA
  established 10.0.0.216[500]-10.0.0.11[500] spi:044d25dede78a4d1:ff01e5b4804f0680
12:18:45: INFO: isakmp.c:938:isakmp_ph2begin_i(): initiate new phase 2 
  negotiation: 10.0.0.216[0]<=>10.0.0.11[0]
12:18:45: INFO: pfkey.c:1106:pk_recvupdate(): IPsec-SA established: 
  ESP/Transport 10.0.0.11->10.0.0.216 spi=44556347(0x2a7e03b)
12:18:45: INFO: pfkey.c:1318:pk_recvadd(): IPsec-SA established:
  ESP/Transport 10.0.0.216->10.0.0.11 spi=15863890(0xf21052)

If we now run setkey -D, which shows the Security Associations, theyare indeed there:

10.0.0.216 10.0.0.11 
	esp mode=transport spi=224162611(0x0d5c7333) reqid=0(0x00000000)
	E: 3des-cbc  5d421c1b d33b2a9f 4e9055e3 857db9fc 211d9c95 ebaead04
	A: hmac-sha1  c5537d66 f3c5d869 bd736ae2 08d22133 27f7aa99
	seq=0x00000000 replay=4 flags=0x00000000 state=mature 
	created: Nov 11 12:28:45 2002	current: Nov 11 12:29:16 2002
	diff: 31(s)	hard: 600(s)	soft: 480(s)
	last: Nov 11 12:29:12 2002	hard: 0(s)	soft: 0(s)
	current: 304(bytes)	hard: 0(bytes)	soft: 0(bytes)
	allocated: 3	hard: 0	soft: 0
	sadb_seq=1 pid=17112 refcnt=0
10.0.0.11 10.0.0.216 
	esp mode=transport spi=165123736(0x09d79698) reqid=0(0x00000000)
	E: 3des-cbc  d7af8466 acd4f14c 872c5443 ec45a719 d4b3fde1 8d239d6a
	A: hmac-sha1  41ccc388 4568ac49 19e4e024 628e240c 141ffe2f
	seq=0x00000000 replay=4 flags=0x00000000 state=mature 
	created: Nov 11 12:28:45 2002	current: Nov 11 12:29:16 2002
	diff: 31(s)	hard: 600(s)	soft: 480(s)
	last:                     	hard: 0(s)	soft: 0(s)
	current: 231(bytes)	hard: 0(bytes)	soft: 0(bytes)
	allocated: 2	hard: 0	soft: 0
	sadb_seq=0 pid=17112 refcnt=0

10.0.0.11[any] 10.0.0.216[any] tcp
	in ipsec
	esp/transport//require
	created:Nov 11 12:28:28 2002 lastused:Nov 11 12:29:12 2002
	lifetime:0(s) validtime:0(s)
	spid=3616 seq=5 pid=17134
	refcnt=3
10.0.0.216[any] 10.0.0.11[any] tcp
	out ipsec
	esp/transport//require
	created:Nov 11 12:28:28 2002 lastused:Nov 11 12:28:44 2002
	lifetime:0(s) validtime:0(s)
	spid=3609 seq=4 pid=17134
	refcnt=3

7.2.3. Automatic keying using X.509 certificates

As mentioned before, the use of shared secrets is hard because theyaren't easily shared and once shared, are no longer secret. Luckily, thereis asymmetric encryption technology to help resolve this.

If each IPSEC participant makes a public and a private key, securecommunications can be setup by both parties publishing their public key, andconfiguring policy.

Building a key is relatively easy, although it requires some work.The following is based on the 'openssl' tool.

$ openssl req -new -nodes -newkey rsa:1024 -sha1 -keyform PEM -keyout \
  laptop.private -outform PEM -out request.pem

Country Name (2 letter code) [AU]:NL
State or Province Name (full name) [Some-State]:.
Locality Name (eg, city) []:Delft
Organization Name (eg, company) [Internet Widgits Pty Ltd]:Linux Advanced
Routing & Traffic Control
Organizational Unit Name (eg, section) []:laptop
Common Name (eg, YOUR name) []:bert hubert
Email Address []:ahu@ds9a.nl

Please enter the following 'extra' attributes
to be sent with your certificate request
A challenge password []:
An optional company name []:

$ openssl x509 -req -in request.pem -signkey laptop.private -out \
  laptop.public
Signature ok
subject=/C=NL/L=Delft/O=Linux Advanced Routing & Traffic \
  Control/OU=laptop/CN=bert hubert/Email=ahu@ds9a.nl
Getting Private key

path certificate "/usr/local/etc/racoon/certs";

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

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

	peers_certfile "laptop.public";
	proposal {
                encryption_algorithm 3des;
		hash_algorithm sha1;
		authentication_method rsasig;
		dh_group 2 ;
	}
}

path certificate "/usr/local/etc/racoon/certs";

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

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

	proposal {
                encryption_algorithm 3des;
	        hash_algorithm sha1;
		authentication_method rsasig;
	        dh_group 2 ;
	}
}

$ openssl dgst upstairs.public 
MD5(upstairs.public)= 78a3bddafb4d681c1ca8ed4d23da4ff1

7.5.1. Windows

Andreas Jellinghaus <aj@dungeon.inka.de> reports: "win2k: it works. pre_shared key with ip address for authentication (I don'tthink windows supports fqdn or userfqdn strings). Certificates should also work, didn'ttry.".

7.5.2. Check Point VPN-1NG

Peter Bieringer reports:

Here are some results (tunnel mode only tested, auth=SHA1):

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

Tested version: FP4 aka R54 aka w/AI

More information here.

9.2.1. pfifo_fast

This queue is, as the name says, First In, First Out, which means that nopacket receives special treatment. At least, not quite. This queue has 3 socalled 'bands'. Within each band, FIFO rules apply. However, as long asthere are packets waiting in band 0, band 1 won't be processed. Same goesfor band 1 and band 2.

The kernel honors the so called Type of Service flag of packets, and takescare to insert 'minimum delay' packets in band 0.

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

9.2.2. Token Bucket Filter

The Token Bucket Filter (TBF) is a simple qdisc that only passes packetsarriving at a rate which is not exceeding some administratively set rate, butwith the possibility to allow short bursts in excess of this rate.

TBF is very precise, network- and processor friendly. It should be yourfirst choice if you simply want to slow an interface down!

The TBF implementation consists of a buffer (bucket), constantly filled bysome virtual pieces of information called tokens, at a specific rate (tokenrate). The most important parameter of the bucket is its size, that is thenumber of tokens it can store.

Each arriving token collects one incoming data packet from the data queueand is then deleted from the bucket. Associating this algorithmwith the two flows -- token and data, gives us three possible scenarios:

• The data arrives in TBF at a rate that's equal to the rateof incoming tokens. In this case each incoming packet has its matching tokenand passes the queue without delay.

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

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

The last scenario is very important, because it allows toadministratively shape the bandwidth available to data that's passingthe filter.

The accumulation of tokens allows a short burst of overlimit data to bestill passed without loss, but any lasting overload will cause packets to beconstantly delayed, and then dropped.

Please note that in the actual implementation, tokens correspond to bytes,not packets.

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

9.2.3. Stochastic Fairness Queueing

Stochastic Fairness Queueing (SFQ) is a simple implementation of the fairqueueing algorithms family. It's less accurate than others, but it alsorequires less calculations while being almost perfectly fair.

The key word in SFQ is conversation (or flow), which mostly corresponds to aTCP session or a UDP stream. Traffic is divided into a pretty large numberof FIFO queues, one for each conversation. Traffic is then sent in a roundrobin fashion, giving each session the chance to send data in turn.

This leads to very fair behaviour and disallows any single conversation fromdrowning out the rest. SFQ is called 'Stochastic' because it doesn't reallyallocate a queue for each session, it has an algorithm which divides trafficover a limited number of queues using a hashing algorithm.

Because of the hash, multiple sessions might end up in the same bucket, whichwould halve each session's chance of sending a packet, thus halving theeffective speed available. To prevent this situation from becomingnoticeable, SFQ changes its hashing algorithm quite often so that any twocolliding sessions will only do so for a small number of seconds.

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

Specifically, setting SFQ on the ethernet interface heading to yourcable modem or DSL router is pointless without further shaping!

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

9.5.1. Flow within classful qdiscs & classes

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

The filters attached to that qdisc then return with a decision, and theqdisc uses this to enqueue the packet into one of the classes. Each subclassmay try other filters to see if further instructions apply. If not, theclass enqueues the packet to the qdisc it contains.

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

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

9.5.2. The qdisc family: roots, handles, siblings and parents

Each interface has one egress 'root qdisc'. By default, it is the earlier mentionedclassless pfifo_fast queueing discipline. Each qdisc and class is assigned ahandle, which can be used by later configuration statements to refer to thatqdisc. Besides an egress qdisc, an interface may also have an ingress qdisc ,which polices traffic coming in.

The handles of these qdiscs consist of two parts, a major number and a minornumber : <major>:<minor>. It is customary to name the root qdisc '1:', whichis equal to '1:0'. The minor number of a qdisc is always 0.

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

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

9.5.3. The PRIO qdisc

The PRIO qdisc doesn't actually shape, it only subdivides traffic based onhow you configured your filters. You can consider the PRIO qdisc a kindof pfifo_fast on steroids, whereby each band is a separate class instead ofa simple FIFO.

When a packet is enqueued to the PRIO qdisc, a class is chosen based on thefilter commands you gave. By default, three classes are created. Theseclasses by default contain pure FIFO qdiscs with no internalstructure, but you can replace these by any qdisc you have available.

Whenever a packet needs to be dequeued, class :1 is tried first. Higherclasses are only used if lower bands all did not give up a packet.

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

Because it doesn't actually shape, the same warning as for SFQ holds: eitheruse it only if your physical link is really full or wrap it inside aclassful qdisc that does shape. The latter holds for almost all cable modemsand DSL devices.

In formal words, the PRIO qdisc is a Work-Conserving scheduler.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

9.5.4. The famous CBQ qdisc

As said before, CBQ is the most complex qdisc available, the most hyped, theleast understood, and probably the trickiest one to get right. This is notbecause the authors are evil or incompetent, far from it, it's just that theCBQ algorithm isn't all that precise and doesn't really match the way Linuxworks.

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

This is pretty hard to measure, so CBQ instead derives the idle time fromthe number of microseconds that elapse between requests from the hardwarelayer for more data. Combined, this can be used to approximate how full orempty the link is.

This is rather tortuous and doesn't always arrive at proper results. Forexample, what if the actual link speed of an interface that is not reallyable to transmit the full 100mbit/s of data, perhaps because of a badlyimplemented driver? A PCMCIA network card will also never achieve 100mbit/sbecause of the way the bus is designed - again, how do we calculate the idletime?

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

People who have done measurements discover that CBQ is not always veryaccurate and sometimes completely misses the mark.

In many circumstances however it works well. With the documentation providedhere, you should be able to configure it to work well in most cases.

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

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

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

# tc qdisc add dev eth0 parent 1:3 handle 30: sfq
# tc qdisc add dev eth0 parent 1:4 handle 40: sfq

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

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

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

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

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

priority	send to
0		1:3
1		1:3
2		1:3
3		1:3
4		1:3
5		1:3
6		1:2
7		1:2

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

priority	send to
0		1:2
1		1:3
2		1:3
3		1:3
4		1:3
5		1:3
6		1:2
7		1:2

9.5.5. Hierarchical Token Bucket

Martin Devera (<devik>) rightly realised that CBQ is complex and doesnot seem optimized for many typical situations. His Hierarchical approach iswell suited for setups where you have a fixed amount of bandwidth which youwant to divide for different purposes, giving each purpose a guaranteedbandwidth, with the possibility of specifying how much bandwidth can beborrowed.

HTB works just like CBQ but does not resort to idle time calculations toshape. Instead, it is a classful Token Bucket Filter - hence the name. Ithas only a few parameters, which are well documented on his site.

As your HTB configuration gets more complex, your configuration scaleswell. With CBQ it is already complex even in simple cases! HTB3 (checkits homepage fordetails on HTB versions) is now part of the official kernel sources (from 2.4.20-pre1 and 2.5.31 onwards). However, maybe you still need toget a HTB3 patched version of 'tc': HTB kernel and userspace parts mustbe the same major version, or 'tc' will not work with HTB.

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

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

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

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

# tc qdisc add dev eth0 parent 1:10 handle 10: sfq perturb 10
# tc qdisc add dev eth0 parent 1:20 handle 20: sfq perturb 10
# tc qdisc add dev eth0 parent 1:30 handle 30: sfq perturb 10

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

9.6.1. Some simple filtering examples

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

Let's say we have a PRIO qdisc called '10:' which contains three classes, andwe want to assign all traffic from and to port 22 to the highest priorityband, the filters would be:

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

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

You need to add 'eth0', or whatever your interface is called, because eachinterface has a unique namespace of handles.

To select on an IP address, use this:

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

This assigns traffic to 4.3.2.1 and traffic from 1.2.3.4 to the highestpriority queue, and the rest to the next-highest one.

You can concatenate matches, to match on traffic from 1.2.3.4 and from port80, do this:

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

9.6.2. All the filtering commands you will normally need

Most shaping commands presented here start with this preamble:

# tc filter add dev eth0 parent 1:0 protocol ip prio 1 u32 ..

For more filtering commands, see the Advanced Filters chapter.

9.7.1. Sample configuration

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

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

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

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

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

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

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

ip link set imq0 up

The IMQ iptables targets is valid in the PREROUTING and POSTROUTING chains ofthe mangle table. It's syntax is

IMQ [ --todev n ]	n : number of imq device

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

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

For ingress traffic, imq registers itself with NF_IP_PRI_MANGLE + 1 prioritywhich means packets enter the imq device directly after the mangle PREROUTINGchain has been passed.

For egress imq uses NF_IP_PRI_LAST which honours the fact that packets droppedby the filter table won't occupy bandwidth.

The patches and some more information can be found at theimq site.

12.1.1. U32 selector

The U32 selector contains definition of the pattern, that will be matchedto the currently processed packet. Precisely, it defines which bits areto be matched in the packet header and nothing more, but this simplemethod is very powerful. Let's take a look at the following examples,taken directly from a pretty complex, real-world filter:

# tc filter add dev eth0 protocol ip parent 1:0 pref 10 u32 \
  match u32 00100000 00ff0000 at 0 flowid 1:10

For now, leave the first line alone - all these parameters describethe filter's hash tables. Focus on the selector line, containingmatch keyword. This selector will match to IP headers, whosesecond byte will be 0x10 (0010). As you can guess, the 00ff number isthe match mask, telling the filter exactly which bits to match. Hereit's 0xff, so the byte will match if it's exactly 0x10. The atkeyword means that the match is to be started at specified offset (inbytes) -- in this case it's beginning of the packet. Translating allthat to human language, the packet will match if its Type of Servicefield will have `low delay' bits set. Let's analyze another rule:

# tc filter add dev eth0 protocol ip parent 1:0 pref 10 u32 \
  match u32 00000016 0000ffff at nexthdr+0 flowid 1:10

The nexthdr option means next header encapsulated in the IP packet,i.e. header of upper-layer protocol. The match will also start hereat the beginning of the next header. The match should occur in thesecond, 32-bit word of the header. In TCP and UDP protocols this fieldcontains packet's destination port. The number is given in big-endianformat, i.e. older bits first, so we simply read 0x0016 as 22 decimal,which stands for SSH service if this was TCP. As you guess, this matchis ambiguous without a context, and we will discuss this later.

Having understood all the above, we will find the following selectorquite easy to read: match c0a80100 ffffff00 at 16. What wegot here is a three byte match at 17-th byte, counting from the IPheader start. This will match for packets with destination addressanywhere in 192.168.1/24 network. After analyzing the examples, wecan summarize what we have learned.

12.1.2. General selectors

General selectors define the pattern, mask and offset the patternwill be matched to the packet contents. Using the general selectorsyou can match virtually any single bit in the IP (or upper layer)header. They are more difficult to write and read, though, thanspecific selectors that described below. The general selector syntaxis:

match [ u32 | u16 | u8 ] PATTERN MASK at [OFFSET | nexthdr+OFFSET]

One of the keywords u32, u16 or u8 specifieslength of the pattern in bits. PATTERN and MASK should follow, of lengthdefined by the previous keyword. The OFFSET parameter is the offset,in bytes, to start matching. If nexthdr+ keyword is given,the offset is relative to start of the upper layer header.

Some examples:

Packet will match to this rule, if its time to live (TTL) is 64.TTL is the field starting just after 8-th byte of the IP header.

# tc filter add dev ppp14 parent 1:0 prio 10 u32 \
     match u8 64 0xff at 8 \
     flowid 1:4

The following matches all TCP packets which have the ACK bit set:

# tc filter add dev ppp14 parent 1:0 prio 10 u32 \
     match ip protocol 6 0xff \
     match u8 0x10 0xff at nexthdr+13 \
     flowid 1:3 

Use this to match ACKs on packets smaller than 64 bytes:

## match acks the hard way,
## IP protocol 6,
## IP header length 0x5(32 bit words),
## IP Total length 0x34 (ACK + 12 bytes of TCP options)
## TCP ack set (bit 5, offset 33)
# tc filter add dev ppp14 parent 1:0 protocol ip prio 10 u32 \
            match ip protocol 6 0xff \
            match u8 0x05 0x0f at 0 \
            match u16 0x0000 0xffc0 at 2 \
            match u8 0x10 0xff at 33 \
            flowid 1:3

This rule will only match TCP packets with ACK bit set, and no furtherpayload. Here we can see an example of using two selectors, the final resultwill be logical AND of their results. If we take a look at TCP headerdiagram, we can see that the ACK bit is second older bit (0x10) in the 14-thbyte of the TCP header (at nexthdr+13). As for the secondselector, if we'd like to make our life harder, we could write match u80x06 0xff at 9 instead of using the specific selector protocoltcp, because 6 is the number of TCP protocol, present in 10-th byte ofthe IP header. On the other hand, in this example we couldn't use anyspecific selector for the first match - simply because there's no specificselector to match TCP ACK bits.

The filter below is a modified version of the filter above. The difference is, that itdoesn't check the ip header length. Why? Because the filter above does only work on 32bit systems.

tc filter add dev ppp14 parent 1:0 protocol ip prio 10 u32 \
     match ip protocol 6 0xff \
     match u8 0x10 0xff at nexthdr+13 \
     match u16 0x0000 0xffc0 at 2 \
     flowid 1:3

12.1.3. Specific selectors

The following table contains a list of all specific selectors the author of this section has found in the tc programsource code. They simply make your life easier and increase readabilityof your filter's configuration.

FIXME: table placeholder - the table is in separate file ,,selector.html''

FIXME: it's also still in Polish :-(

FIXME: must be sgml'ized

Some examples:

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

FIXME: tcp dport match does not work as described below:

The above rule will match packets which have the TOS field set to 0x10.The TOS field starts at second byte of the packet and is one byte big,so we could write an equivalent general selector: match u8 0x10 0xffat 1. This gives us hint to the internals of U32 filter -- thespecific rules are always translated to general ones, and in thisform they are stored in the kernel memory. This leads to another conclusion-- the tcp and udp selectors are exactly the sameand this is why you can't use single match tcp dport 53 0xffffselector to match TCP packets sent to given port -- they will alsomatch UDP packets sent to this port. You must remember to also specifythe protocol and end up with the following rule:

# tc filter add dev ppp0 parent 1:0 prio 10 u32 \
        match tcp dport 53 0xffff \
        match ip protocol 0x6 0xff \
        flowid 1:2

12.3.1. Ways to police

There are basically two ways to police. If you compiled the kernel with 'Estimators', the kernel can measure for each filter how much trafficit is passing, more or less. These estimators are very easy on the CPU, asthey simply count 25 times per second how many data has been passed, andcalculate the bitrate from that.

The other way works again via a Token Bucket Filter, this time living withinyour filter. The TBF only matches traffic UP TO your configured bandwidth,if more is offered, only the excess is subject to the configured overlimitaction.

12.3.2. Overlimit actions

If your filter decides that it is overlimit, it can take 'actions'.Currently, four actions are available:

12.3.3. Examples

The only real example known is mentioned in the 'Protecting your host from SYN floods' section.

Limit incoming icmp traffic to 2kbit, drop packetsover the limit:

tc filter add dev $DEV parent ffff: \
    protocol ip prio 20 \
    u32 match ip protocol 1 0xff \
    police rate 2kbit buffer 10k drop \
    flowid :1

Limit packets to a certain size (i.e. all packetswith a length greater than 84 bytes will get dropped):

tc filter add dev $DEV parent ffff: \
   protocol ip prio 20 \
   u32 match tos 0 0 \
   police mtu 84 drop \
   flowid :1

This method can be used to drop all packets:

tc filter add dev $DEV parent ffff: \
   protocol ip prio 20 \
   u32 match ip protocol 1 0xff \
   police mtu 1 drop \
   flowid :1

It actually drops icmp packets greater-than 1 byte. While packets witha size of 1 byte are possible in theory, you will not find these in a real network.

12.5.1. How come that IPv6 tc filters do not work?

The Routing Policy Database (RPDB) replaced the IPv4 routing andaddressing structure within the Linux Kernel which lead to all thewonderful features this HOWTO describes. Unfortunately, the IPv6structure within Linux was implemented outside of this core structure.Although they do share some facilities, the essential RPDB structuredoes not particpate in or with the IPv6 addressing and routingstructures.

This will change for sure, we just have to wait a little longer.

FIXME: Any ideas if someone is working on this? Plans?

12.5.2. Marking IPv6 packets using ip6tables

ip6tables is able to mark a packet and assign a number to it:

# ip6tables -A PREROUTING -i eth0 -t mangle -p tcp -j MARK --mark 1

But still, this will not help because the packet will not pass through theRPDB structure.

12.5.3. Using the u32 selector to match IPv6 packet

IPv6 is normally encapsulated in a SIT tunnel and transportedover IPv4 networks. See section IPv6 Tunneling for information onhowto setup such a tunnel. This allows us to filter on the IPv4 packetsholding the IPv6 packets as payload.

The following filter matches all IPv6 encapsulated in IPv4 packets:

# tc filter add dev $DEV parent 10:0 protocol ip prio 10 u32 \
            match ip protocol 41 0xff flowid 42:42

Let's carry on with that. Assume your IPv6 packets get sent outover IPv4 and these packets have no options set. One could usethe following filter to match ICMPv6 in IPv6 in IPv4 with no options.0x3a (58) is the Next-Header type for ICMPv6.

# tc filter add dev $DEV parent 10:0 protocol ip prio 10 u32 \
           match ip protocol 41 0xff \
           match u8 0x05 0x0f at 0 \
           match u8 0x3a 0xff at 26 \
           flowid 42:42

Matching the destination IPv6 address is a bit more work. The followingfilter matches on the destination address3ffe:202c:ffff:32:230:4fff:fe08:358d:

# tc filter add dev $DEV parent 10:0 protocol ip prio 10 u32 \
            match ip protocol 41 0xff \
            match u8 0x05 0x0f at 0 \
            match u8 0x3f 0xff at 44 \
            match u8 0xfe 0xff at 45 \
            match u8 0x20 0xff at 46 \
            match u8 0x2c 0xff at 47 \
            match u8 0xff 0xff at 48 \
            match u8 0xff 0xff at 49 \
            match u8 0x00 0xff at 50 \
            match u8 0x32 0xff at 51 \
            match u8 0x02 0xff at 52 \
            match u8 0x30 0xff at 53 \
            match u8 0x4f 0xff at 54 \
            match u8 0xff 0xff at 55 \
            match u8 0xfe 0xff at 56 \
            match u8 0x08 0xff at 57 \
            match u8 0x35 0xff at 58 \
            match u8 0x8d 0xff at 59 \
            flowid 10:13

The same technique can be used to match subnets. For example 2001::

# tc filter add dev $DEV parent 10:0 protocol ip prio 10 u32 \
            match ip protocol 41 0xff \
            match u8 0x05 0x0f at 0 \
            match u8 0x20 0xff at 28 \
            match u8 0x01 0xff at 29 \
            flowid 10:13

13.2.1. Generic ipv4

As a generic note, most rate limiting features don't work on loopback, sodon't test them locally. The limits are supplied in 'jiffies', and areenforced using the earlier mentioned token bucket filter.

The kernel has an internal clock which runs at 'HZ' ticks (or 'jiffies') persecond. On Intel, 'HZ' is mostly 100. So setting a *_rate file to, say 50,would allow for 2 packets per second. The token bucket filter is alsoconfigured to allow for a burst of at most 6 packets, if enough tokens havebeen earned.

Several entries in the following list have been copied from/usr/src/linux/Documentation/networking/ip-sysctl.txt, written by AlexeyKuznetsov <kuznet@ms2.inr.ac.ru> and Andi Kleen <ak@muc.de>

13.2.2. Per device settings

DEV can either stand for a real interface, or for 'all' or 'default'.Default also changes settings for interfaces yet to be created.

13.2.3. Neighbor policy

Dev can either stand for a real interface, or for 'all' or 'default'.Default also changes settings for interfaces yet to be created.

13.2.4. Routing settings

14.1.1. Parameters & usage

14.3.1. Introduction

First of all, it would be a great idea for you to read RFCswritten about this (RFC2474, RFC2475, RFC2597 and RFC2598) at IETF DiffServ working Group web site and Werner Almesberger web site(he wrote the code to support Differentiated Services on Linux).

14.3.2. What is Dsmark related to?

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

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

14.3.3. Differentiated Services guidelines

Differentiated Services is group-oriented. I mean, we don't know anythingabout flows (this will be the Integrated Services purpose); we know aboutflow aggregations and we will apply different behaviours depending on whichaggregation a packet belongs to.

When a packet arrives to an edge node (entry node to a DiffServ domain)entering to a DiffServ Domain we'll have to policy, shape and/or mark thosepackets (marking refers to assigning a value to the DS field. It's just like thecows :-) ). This will be the mark/value that the internal/core nodes on ourDiffServ Domain will look at to determine which behaviour or QoS levelapply.

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

In fact, you can apply your own policies into your local domains, but someService Level Agreements should be considered when connecting toother DS domains.

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

14.3.4. Working with Dsmark

As the DiffServ bibliography specifies, we differentiate boundary nodes andinterior nodes. These are two important points in the traffic path. Bothtypes perform a classification when the packets arrive. Its result may beused in different places along the DS process before the packet is releasedto the network. It's just because of this that the diffserv code supplies anstructure called sk_buff, including a new field called skb->tc_indexwhere we'll store the result of initial classification that may be used inseveral points in DS treatment.

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

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

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

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

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

• Set_tc_index: instructs dsmark discipline to retrieve the DS field and store it onto skb->tc_index.

14.3.5. How SCH_DSMARK works.

This qdisc will apply the next steps:

• If we have declared set_tc_index option in qdisc command, DS field is retrieved and stored ontoskb->tc_index variable.

• Classifier is invoked. The classifier will be executed and it will return a class ID that will be stored inskb->tc_index variable. If no filter matches are found, we consider the default_index option to determine theclassId to store. If neither set_tc_index nor default_index has been declared results may beunpredictable.

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

  New_Ds_field = ( Old_DS_field & mask ) | value

• Thus, new value will result from "anding" ds_field and mask values and next, this result "ORed" withvalue parameter. See next diagram to understand all this process:

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

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

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

Now, we'll explain how TC_INDEX filter works and how fits into this. Besides, TCINDEX filter can beused in other configurations rather than those including DS services.

14.3.6. TC_INDEX Filter

This is the basic command to declare a TC_INDEX filter:

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

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

tc qdisc add dev eth0 handle 1:0 root dsmark indices 64 set_tc_index

tc filter add dev eth0 parent 1:0 protocol ip prio 1 tcindex mask 0xfc  shift 2

tc qdisc add dev eth0 parent 1:0 handle 2:0 cbq bandwidth 10Mbit cell 8 avpkt 1000 mpu 64

# EF traffic class

tc class add dev eth0 parent 2:0 classid 2:1 cbq bandwidth 10Mbit rate 1500Kbit avpkt 1000 prio 1 bounded isolated allot 1514 weight 1 maxburst 10

# Packet fifo qdisc for EF traffic

tc qdisc add dev eth0 parent 2:1 pfifo limit 5

tc filter add dev eth0 parent 2:0 protocol ip prio 1 handle 0x2e tcindex classid 2:1 pass_on

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

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

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

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

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

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

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

But if any filter with that identifier is not found, the result will depend on fall_through flag declaration. If so,value key is returned as classid. If not, an error is returned and process continues with the rest filters. Becareful if you use fall_through flag; this can be done if a simple relation exists between valuesof skb->tc_index variable and class id's.

The latest parameters to comment on are hash and pass_on. The first onerelates to hash table size. Pass_on will be used to indicate that if no classidequal to the result of this filter is found, try next filter.The default action is fall_through (look at next table).

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

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

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

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

14.4.1. Parameters & usage

The ingress qdisc itself does not require any parameters. It differs fromother qdiscs in that it does not occupy the root of a device. Attach it likethis:

# tc qdisc add dev eth0 ingress

For a contrived example how the ingress qdisc could be used, see theCookbook.

15.5.1. Traffic flow diagram after implementation

|-----------------------------------------|
|Traffic flow diagram after implementation|
|-----------------------------------------|

INTERNET
/\
||
\/
-----------------donmuang router---------------------
/\                                      /\         ||
||                                      ||         ||
||                                      \/         ||
naret                                  silom       ||
*destination port 80 traffic=========>(cache)      ||
/\                                      ||         ||
||                                      \/         \/
\\===================================kaosarn, RAS, etc.

Note that the network is asymmetric as there is one extra hop on general outgoing path.

Here is run down for packet traversing the network from kaosarnto and from the Internet.

15.6.1. Solution

When you encounter sites that suffer from this problem, you can disable PathMTU discovery by setting it manually. Koos van den Hout, slightly edited,writes:

The following problem: I set the mtu/mru of my leased line running ppp to296 because it's only 33k6 and I cannot influence the queueing on theother side. At 296, the response to a key press is within a reasonabletime frame.

And, on my side I have a masqrouter running (of course) Linux.

Recently I split 'server' and 'router' so most applications are run on adifferent machine than the routing happens on.

I then had trouble logging into irc. Big panic! Some digging did findout that I got connected to irc, even showed up as 'connected' on ircbut I did not receive the motd from irc. I checked what could be wrongand noted that I already had some previous trouble reaching certainwebsites related to the MTU, since I had no trouble reaching them whenthe MTU was 1500, the problem just showed when the MTU was set to 296.Since irc servers block about every kind of traffic not needed for theirimmediate operation, they also block icmp.

I managed to convince the operators of a webserver that this was the causeof a problem, but the irc server operators were not going to fix this.

So, I had to make sure outgoing masqueraded traffic started with the lowermtu of the outside link. But I want local ethernet traffic to have thenormal mtu (for things like nfs traffic).

Solution:

ip route add default via 10.0.0.1 mtu 296

(10.0.0.1 being the default gateway, the inside address of themasquerading router)

In general, it is possible to override PMTU Discovery by setting specificroutes. For example, if only a certain subnet is giving problems, thisshould help:

ip route add 195.96.96.0/24 via 10.0.0.1 mtu 1000

15.8.1. Why it doesn't work well by default

ISPs know that they are benchmarked solely on how fast people can download.Besides available bandwidth, download speed is influenced heavily by packetloss, which seriously hampers TCP/IP performance. Large queues can helpprevent packet loss, and speed up downloads. So ISPs configure large queues.

These large queues however damage interactivity. A keystroke must firsttravel the upstream queue, which may be seconds (!) long and go to yourremote host. It is then displayed, which leads to a packet coming back, whichmust then traverse the downstream queue, located at your ISP, before itappears on your screen.

This HOWTO teaches you how to mangle and process the queue in many ways, butsadly, not all queues are accessible to us. The queue over at the ISP iscompletely off-limits, whereas the upstream queue probably lives inside yourcable modem or DSL device. You may or may not be able to configure it. Mostprobably not.

So, what next? As we can't control either of those queues, they must beeliminated, and moved to your Linux router. Luckily this is possible.

Now, once we have done this, we have eliminated the downstream queue totally(except for short bursts), and gain the ability to manage the upstream queuewith all the power Linux offers.

What remains to be done is to make sure interactive traffic jumps to thefront of the upstream queue. To make sure that uploads don't hurt downloads,we also move ACK packets to the front of the queue. This is what normallycauses the huge slowdown observed when generating bulk traffic both ways.The ACKnowledgements for downstream traffic must compete with upstreamtraffic, and get delayed in the process.

If we do all this we get the following measurements using an excellent ADSLconnection from xs4all in the Netherlands:

Baseline latency:
round-trip min/avg/max = 14.4/17.1/21.7 ms

Without traffic conditioner, while downloading:
round-trip min/avg/max = 560.9/573.6/586.4 ms

Without traffic conditioner, while uploading:
round-trip min/avg/max = 2041.4/2332.1/2427.6 ms

With conditioner, during 220kbit/s upload:
round-trip min/avg/max = 15.7/51.8/79.9 ms

With conditioner, during 850kbit/s download:
round-trip min/avg/max = 20.4/46.9/74.0 ms

When uploading, downloads proceed at ~80% of the available speed. Uploads
at around 90%. Latency then jumps to 850 ms, still figuring out why.

What you can expect from this script depends a lot on your actual uplinkspeed. When uploading at full speed, there will always be a single packetahead of your keystroke. That is the lower limit to the latency you canachieve - divide your MTU by your upstream speed to calculate. Typicalvalues will be somewhat higher than that. Lower your MTU for better effects!

Next, two versions of this script, one with Devik's excellent HTB, the otherwith CBQ which is in each Linux kernel, unlike HTB. Both are tested and workwell.

15.8.2. The actual script (CBQ)

Works on all kernels. Within the CBQqdisc we place two Stochastic Fairness Queues that make sure that multiplebulk streams don't drown each other out.

Downstream traffic is policed using a tc filter containing a Token BucketFilter.

You might improve on this script by adding 'bounded' to the line that startswith 'tc class add .. classid 1:20'. If you lowered your MTU, also lower theallot & avpkt numbers!

#!/bin/bash 

# The Ultimate Setup For Your Internet Connection At Home
# 
#
# Set the following values to somewhat less than your actual download
# and uplink speed. In kilobits
DOWNLINK=800
UPLINK=220
DEV=ppp0

# clean existing down- and uplink qdiscs, hide errors
tc qdisc del dev $DEV root    2> /dev/null > /dev/null
tc qdisc del dev $DEV ingress 2> /dev/null > /dev/null

###### uplink

# install root CBQ

tc qdisc add dev $DEV root handle 1: cbq avpkt 1000 bandwidth 10mbit 

# shape everything at $UPLINK speed - this prevents huge queues in your
# DSL modem which destroy latency:
# main class

tc class add dev $DEV parent 1: classid 1:1 cbq rate ${UPLINK}kbit \
allot 1500 prio 5 bounded isolated 

# high prio class 1:10:

tc class add dev $DEV parent 1:1 classid 1:10 cbq rate ${UPLINK}kbit \
   allot 1600 prio 1 avpkt 1000

# bulk and default class 1:20 - gets slightly less traffic, 
#  and a lower priority:

tc class add dev $DEV parent 1:1 classid 1:20 cbq rate $[9*$UPLINK/10]kbit \
   allot 1600 prio 2 avpkt 1000

# both get Stochastic Fairness:
tc qdisc add dev $DEV parent 1:10 handle 10: sfq perturb 10
tc qdisc add dev $DEV parent 1:20 handle 20: sfq perturb 10

# start filters
# TOS Minimum Delay (ssh, NOT scp) in 1:10:
tc filter add dev $DEV parent 1:0 protocol ip prio 10 u32 \
      match ip tos 0x10 0xff  flowid 1:10

# ICMP (ip protocol 1) in the interactive class 1:10 so we 
# can do measurements & impress our friends:
tc filter add dev $DEV parent 1:0 protocol ip prio 11 u32 \
	match ip protocol 1 0xff flowid 1:10

# To speed up downloads while an upload is going on, put ACK packets in
# the interactive class:

tc filter add dev $DEV parent 1: protocol ip prio 12 u32 \
   match ip protocol 6 0xff \
   match u8 0x05 0x0f at 0 \
   match u16 0x0000 0xffc0 at 2 \
   match u8 0x10 0xff at 33 \
   flowid 1:10

# rest is 'non-interactive' ie 'bulk' and ends up in 1:20

tc filter add dev $DEV parent 1: protocol ip prio 13 u32 \
   match ip dst 0.0.0.0/0 flowid 1:20

########## downlink #############
# slow downloads down to somewhat less than the real speed  to prevent 
# queuing at our ISP. Tune to see how high you can set it.
# ISPs tend to have *huge* queues to make sure big downloads are fast
#
# attach ingress policer:

tc qdisc add dev $DEV handle ffff: ingress

# filter *everything* to it (0.0.0.0/0), drop everything that's
# coming in too fast:

tc filter add dev $DEV parent ffff: protocol ip prio 50 u32 match ip src \
   0.0.0.0/0 police rate ${DOWNLINK}kbit burst 10k drop flowid :1

If the last two lines give an error, update your tc tool to a newer version!

15.8.3. The actual script (HTB)

The following script achieves all goals using the wonderful HTB queue, seethe relevant chapter. Well worth patching your kernel for!

#!/bin/bash

# The Ultimate Setup For Your Internet Connection At Home
# 
#
# Set the following values to somewhat less than your actual download
# and uplink speed. In kilobits
DOWNLINK=800
UPLINK=220
DEV=ppp0

# clean existing down- and uplink qdiscs, hide errors
tc qdisc del dev $DEV root    2> /dev/null > /dev/null
tc qdisc del dev $DEV ingress 2> /dev/null > /dev/null

###### uplink

# install root HTB, point default traffic to 1:20:

tc qdisc add dev $DEV root handle 1: htb default 20

# shape everything at $UPLINK speed - this prevents huge queues in your
# DSL modem which destroy latency:

tc class add dev $DEV parent 1: classid 1:1 htb rate ${UPLINK}kbit burst 6k

# high prio class 1:10:

tc class add dev $DEV parent 1:1 classid 1:10 htb rate ${UPLINK}kbit \
   burst 6k prio 1

# bulk & default class 1:20 - gets slightly less traffic, 
# and a lower priority:

tc class add dev $DEV parent 1:1 classid 1:20 htb rate $[9*$UPLINK/10]kbit \
   burst 6k prio 2

# both get Stochastic Fairness:
tc qdisc add dev $DEV parent 1:10 handle 10: sfq perturb 10
tc qdisc add dev $DEV parent 1:20 handle 20: sfq perturb 10

# TOS Minimum Delay (ssh, NOT scp) in 1:10:
tc filter add dev $DEV parent 1:0 protocol ip prio 10 u32 \
      match ip tos 0x10 0xff  flowid 1:10

# ICMP (ip protocol 1) in the interactive class 1:10 so we 
# can do measurements & impress our friends:
tc filter add dev $DEV parent 1:0 protocol ip prio 10 u32 \
	match ip protocol 1 0xff flowid 1:10

# To speed up downloads while an upload is going on, put ACK packets in
# the interactive class:

tc filter add dev $DEV parent 1: protocol ip prio 10 u32 \
   match ip protocol 6 0xff \
   match u8 0x05 0x0f at 0 \
   match u16 0x0000 0xffc0 at 2 \
   match u8 0x10 0xff at 33 \
   flowid 1:10

# rest is 'non-interactive' ie 'bulk' and ends up in 1:20


########## downlink #############
# slow downloads down to somewhat less than the real speed  to prevent 
# queuing at our ISP. Tune to see how high you can set it.
# ISPs tend to have *huge* queues to make sure big downloads are fast
#
# attach ingress policer:

tc qdisc add dev $DEV handle ffff: ingress

# filter *everything* to it (0.0.0.0/0), drop everything that's
# coming in too fast:

tc filter add dev $DEV parent ffff: protocol ip prio 50 u32 match ip src \
   0.0.0.0/0 police rate ${DOWNLINK}kbit burst 10k drop flowid :1

If you want this script to be run by ppp on connect, copy it to/etc/ppp/ip-up.d.

If the last two lines give an error, update your tc tool to a newer version!

15.10.1. Let's begin optimizing that scarce bandwidth

First we set up some qdiscs in which we will classify the traffic. We create a htb qdisc with 6 classes with ascending priority. Then we have classes that will always get allocated rate, but can use the unused bandwidth that other classes don't need. Recall that classes with higher priority ( i.e with a lower prio number ) will get excess of bandwith allocated first. Our connection is 2Mb down 300kbits/s up Adsl. I use 240kbit/s as ceil rate just because it's the higher I can set it before latency starts to grow, due to buffer filling in whatever place between us and remote hosts. This parameter should be timed experimentally, raising and lowering it while observing latency between some near hosts.

Adjust CEIL to 75% of your upstream bandwith limit by now, and where I use eth0, you should use the interface which has a public Internet address. To begin our example execute the following in a root shell:

CEIL=240
tc qdisc add dev eth0 root handle 1: htb default 15
tc class add dev eth0 parent 1: classid 1:1 htb rate ${CEIL}kbit ceil ${CEIL}kbit
tc class add dev eth0 parent 1:1 classid 1:10 htb rate 80kbit ceil 80kbit prio 0
tc class add dev eth0 parent 1:1 classid 1:11 htb rate 80kbit ceil ${CEIL}kbit prio 1
tc class add dev eth0 parent 1:1 classid 1:12 htb rate 20kbit ceil ${CEIL}kbit prio 2
tc class add dev eth0 parent 1:1 classid 1:13 htb rate 20kbit ceil ${CEIL}kbit prio 2
tc class add dev eth0 parent 1:1 classid 1:14 htb rate 10kbit ceil ${CEIL}kbit prio 3
tc class add dev eth0 parent 1:1 classid 1:15 htb rate 30kbit ceil ${CEIL}kbit prio 3
tc qdisc add dev eth0 parent 1:12 handle 120: sfq perturb 10
tc qdisc add dev eth0 parent 1:13 handle 130: sfq perturb 10
tc qdisc add dev eth0 parent 1:14 handle 140: sfq perturb 10
tc qdisc add dev eth0 parent 1:15 handle 150: sfq perturb 10
			

+---------+
| root 1: |
+---------+
     |
+---------------------------------------+
| class 1:1                             |
+---------------------------------------+
  |      |      |      |      |      |      
+----+ +----+ +----+ +----+ +----+ +----+
|1:10| |1:11| |1:12| |1:13| |1:14| |1:15| 
+----+ +----+ +----+ +----+ +----+ +----+ 
			

15.10.2. Classifying packets

We have created the qdisc setup but no packet classification has been made, so now all outgoing packets are going out in class 1:15 ( because we used: tc qdisc add dev eth0 root handle 1: htb default 15 ). Now we need to tell which packets go where. This is the most important part.

Now we set the filters so we can classify the packets with iptables. I really prefer to do it with iptables, because they are very flexible and you have packet count for each rule. Also with the RETURN target packets don't need to traverse all rules. We execute the following commands:

tc filter add dev eth0 parent 1:0 protocol ip prio 1 handle 1 fw classid 1:10
tc filter add dev eth0 parent 1:0 protocol ip prio 2 handle 2 fw classid 1:11
tc filter add dev eth0 parent 1:0 protocol ip prio 3 handle 3 fw classid 1:12
tc filter add dev eth0 parent 1:0 protocol ip prio 4 handle 4 fw classid 1:13
tc filter add dev eth0 parent 1:0 protocol ip prio 5 handle 5 fw classid 1:14
tc filter add dev eth0 parent 1:0 protocol ip prio 6 handle 6 fw classid 1:15
			

First you have to understand how packet traverse the filters with iptables:

        +------------+                +---------+               +-------------+
Packet -| PREROUTING |--- routing-----| FORWARD |-------+-------| POSTROUTING |- Packets
input   +------------+    decision    +---------+       |       +-------------+    out
                             |                          |
                        +-------+                    +--------+   
                        | INPUT |---- Local process -| OUTPUT |
                        +-------+                    +--------+

			

Next we instruct the kernel to actually do NAT, so clients in the private network can start talking to the outside.

echo 1 > /proc/sys/net/ipv4/ip_forward
iptables -t nat -A POSTROUTING -s 172.17.0.0/255.255.0.0 -o eth0 -j SNAT --to-source 212.170.21.172
			

tc -s class show dev eth0
			

You can start marking packets adding rules to the PREROUTING chain in the mangle table.

iptables -t mangle -A PREROUTING -p icmp -j MARK --set-mark 0x1
iptables -t mangle -A PREROUTING -p icmp -j RETURN
			

tc -s class show dev eth0
			

iptables -t mangle -A PREROUTING -m tos --tos Minimize-Delay -j MARK --set-mark 0x1
iptables -t mangle -A PREROUTING -m tos --tos Minimize-Delay -j RETURN
iptables -t mangle -A PREROUTING -m tos --tos Minimize-Cost -j MARK --set-mark 0x5
iptables -t mangle -A PREROUTING -m tos --tos Minimize-Cost -j RETURN
iptables -t mangle -A PREROUTING -m tos --tos Maximize-Throughput -j MARK --set-mark 0x6
iptables -t mangle -A PREROUTING -m tos --tos Maximize-Throughput -j RETURN
			

iptables -t mangle -A PREROUTING -p tcp -m tcp --sport 22 -j MARK --set-mark 0x1
iptables -t mangle -A PREROUTING -p tcp -m tcp --sport 22 -j RETURN
			

iptables -t mangle -I PREROUTING -p tcp -m tcp --tcp-flags SYN,RST,ACK SYN -j MARK --set-mark 0x1
iptables -t mangle -I PREROUTING -p tcp -m tcp --tcp-flags SYN,RST,ACK SYN -j RETURN
			

iptables -t mangle -A PREROUTING -j MARK --set-mark 0x6
			

It will be a good idea to do the same in the OUTPUT rule, so repeat those commands with -A OUTPUT instead of PREROUTING. ( s/PREROUTING/OUTPUT/ ). Then traffic generated locally (on the Linux router) will also be classified. I finish OUTPUT chain with -j MARK --set-mark 0x3 so local traffic has higher priority.

15.10.3. Improving our setup

Now we have all our setup working. Take time looking at the graphs, and watching where your bandwith is spent and how do you want it. Doing that for lots of hours, I finally got the Internet connection working really well. Otherwise continuous timeouts and nearly zero allotment of bandwith to newly created tcp connections will occur.

If you find that some classes are full most of the time it would be a good idea to attach another queueing discipline to them so bandwith sharing is more fair:

tc qdisc add dev eth0 parent 1:13 handle 130: sfq perturb 10
tc qdisc add dev eth0 parent 1:14 handle 140: sfq perturb 10
tc qdisc add dev eth0 parent 1:15 handle 150: sfq perturb 10
			

15.10.4. Making all of the above start at boot

It sure can be done in many ways. In mine, I have a shell script in /etc/init.d/packetfilter that accepts [start | stop | stop-tables | start-tables | reload-tables] it configures qdiscs and loads needed kernel modules, so it behaves much like a daemon. The same script loads iptables rules from /etc/network/iptables-rules which can be saved with iptables-save and restored with iptables-restore.

16.3.1. ARP & Proxy-ARP

When a host wants to talk to another host on the same physical networksegment, it sends out an Address Resolution Protocol packet, which, somewhatsimplified, reads like this 'who has 10.0.0.1, tell 10.0.0.7'. In responseto this, 10.0.0.1 replies with a short 'here' packet.

10.0.0.7 then sends packets to the hardware address mentioned in the 'here' packet. It caches this hardware address for a relatively long time, andafter the cache expires, it re-asks the question.

When building a Pseudo-bridge, we instruct the bridge to reply to these ARPpackets, which causes the hosts in the network to send its packets to thebridge. The bridge then processes these packets, and sends them to therelevant interface.

So, in short, whenever a host on one side of the bridge asks for thehardware address of a host on the other, the bridge replies with a packetthat says 'hand it to me'.

This way, all data traffic gets transmitted to the right place, and alwayspasses through the bridge.

16.3.2. Implementing it

In the bad old days, it used to be possible to instruct the Linux Kernel toperform 'proxy-ARP' for just any subnet. So, to configure a pseudo-bridge,you would have to specify both the proper routes to both sides of the bridgeAND create matching proxy-ARP rules. This is bad in that it requires a lotof typing, but also because it easily allows you to make mistakes which makeyour bridge respond to ARP queries for networks it does not know how toroute.

With Linux 2.4/2.5 (and possibly 2.2), this possibility has been withdrawn andhas been replaced by a flag in the /proc directory, called 'proxy_arp'. Theprocedure for building a pseudo-bridge is then:

1. Assign an IP address to both interfaces, the 'left' and the 'right'one

2. Create routes so your machine knows which hosts reside on the left,and which on the right

3. Turn on proxy-ARP on both interfaces, echo 1 >/proc/sys/net/ipv4/conf/ethL/proxy_arp, echo 1 >/proc/sys/net/ipv4/conf/ethR/proxy_arp, where L and R stand for the numbersof your interfaces on the left and on the right side

Also, do not forget to turn on the ip_forwarding flag! When converting froma true bridge, you may find that this flag was turned off as it is notneeded when bridging.

Another thing you might note when converting is that you need to clear thearp cache of computers in the network - the arp cache might contain oldpre-bridge hardware addresses which are no longer correct.

On a Cisco, this is done using the command 'clear arp-cache', underLinux, use 'arp -d ip.address'. You can also wait for the cache to expiremanually, which can take rather long.

You can speed this up using the wonderful 'arping' tool, which on manydistributions is part of the 'iputils' package. Using 'arping' you can sendout unsolicited ARP messages so as to update remote arp caches.

This is a very powerful technique that is also used by 'black hats' tosubvert your routing!

On Linux 2.4, you may need to execute 'echo 1 > /proc/sys/net/ipv4/ip_nonlocal_bind' before being able to sendout unsolicited ARP messages!

You may also discover that your network was misconfigured if you are/were ofthe habit of specifying routes without netmasks. To explain, some versionsof route may have guessed your netmask right in the past, or guessed wrongwithout you noticing. When doing surgical routing like described above, itis *vital* that you check your netmasks!

17.1.1. Prerequisites

17.1.2. Configuring Zebra

Let's take this network as an example:

----------------------------------------------------
| 192.168.0.0/24                                   |
|                                                  |
|      Area 0    100BaseTX Switched                |
|     Backbone     Ethernet                        |
----------------------------------------------------
  |           |                |              |
  |           |                |              |
  |eth1       |eth1            |eth0          |
  |100BaseTX  |100BaseTX       |100BaseTX     |100BaseTX
  |.1         |.2              |.253          |
 ---------   ------------   -----------      ----------------
 |R Omega|   |R Atlantis|   |R Legolas|      |R Frodo       |
 ---------   ------------   -----------      ----------------
  |eth0         |eth0             |             |          |
  |             |                 |             |          |
  |2MbDSL/ATM   |100BaseTX        |10BaseT      |10BaseT   |10BaseT
------------   ------------------------------------       -------------------------------
| Internet |   | 172.17.0.0/16        Area 1      |       |  192.168.1.0/24 wlan  Area 2|
------------   |         Student network (dorm)   |       |       barcelonawireless     |
               ------------------------------------       -------------------------------
			

hostname omega
password xxx 
enable password xxx
!
! Interface's description.
!
!interface lo
! description test of desc.
!
interface eth1
multicast
!
! Static default route
!
ip route 0.0.0.0/0 212.170.21.129
!
log file /var/log/zebra/zebra.log
			

zebra=yes
ospfd=yes
			

hostname omega
password xxx
enable password xxx
!
router ospf
  network 192.168.0.0/24 area 0
  network 172.17.0.0/16 area 1
!
! log stdout
log file /var/log/zebra/ospfd.log
			

17.1.3. Running Zebra

Now, we have to start Zebra; either by hand by typing "zebra -d" or with some script like "/etc/init.d/zebra start". Then carefully watching the ospdfd logs we should see something like:

2002/12/13 22:46:24 OSPF: interface 192.168.0.1 join AllSPFRouters Multicast group.
2002/12/13 22:46:34 OSPF: SMUX_CLOSE with reason: 5   
2002/12/13 22:46:44 OSPF: SMUX_CLOSE with reason: 5
2002/12/13 22:46:54 OSPF: SMUX_CLOSE with reason: 5   
2002/12/13 22:47:04 OSPF: SMUX_CLOSE with reason: 5   
2002/12/13 22:47:04 OSPF: DR-Election[1st]: Backup 192.168.0.1
2002/12/13 22:47:04 OSPF: DR-Election[1st]: DR     192.168.0.1
2002/12/13 22:47:04 OSPF: DR-Election[2nd]: Backup 0.0.0.0
2002/12/13 22:47:04 OSPF: DR-Election[2nd]: DR     192.168.0.1
2002/12/13 22:47:04 OSPF: interface 192.168.0.1 join AllDRouters Multicast group.
2002/12/13 22:47:06 OSPF: DR-Election[1st]: Backup 192.168.0.2
2002/12/13 22:47:06 OSPF: DR-Election[1st]: DR     192.168.0.1
2002/12/13 22:47:06 OSPF: Packet[DD]: Negotiation done (Slave).
2002/12/13 22:47:06 OSPF: nsm_change_status(): scheduling new router-LSA origination
2002/12/13 22:47:11 OSPF: ospf_intra_add_router: Start
			

We can also interact with the zebra or the ospfd interface by executing:

$ telnet localhost zebra
$ telnet localhost ospfd
			

root@atlantis:~# telnet localhost zebra
Trying 127.0.0.1...
Connected to atlantis.
Escape character is '^]'.

Hello, this is zebra (version 0.92a).
Copyright 1996-2001 Kunihiro Ishiguro.

User Access Verification

Password: 
atlantis> show ip route
Codes: K - kernel route, C - connected, S - static, R - RIP, O - OSPF,
       B - BGP, > - selected route, * - FIB route

K>* 0.0.0.0/0 via 192.168.0.1, eth1
C>* 127.0.0.0/8 is directly connected, lo
O   172.17.0.0/16 [110/10] is directly connected, eth0, 06:21:53
C>* 172.17.0.0/16 is directly connected, eth0
O   192.168.0.0/24 [110/10] is directly connected, eth1, 06:21:53
C>* 192.168.0.0/24 is directly connected, eth1
atlantis> show ip ospf border-routers
============ OSPF router routing table =============
R    192.168.0.253         [10] area: (0.0.0.0), ABR
			   via 192.168.0.253, eth1
				 [10] area: (0.0.0.1), ABR
			   via 172.17.0.2, eth0
			

root@omega:~# ip route
212.170.21.128/26 dev eth0  proto kernel  scope link  src 212.170.21.172 
192.168.0.0/24 dev eth1  proto kernel  scope link  src 192.168.0.1 
172.17.0.0/16 via 192.168.0.2 dev eth1  proto zebra  metric 20 
default via 212.170.21.129 dev eth0  proto zebra 
root@omega:~# 
			

Hint: You can use:

tcpdump -i eth1 ip[9] == 89
			

OSPF has a lot of tunable parameters, specially for large networks. In further ampliations of the howto we will show some methodologies for fine tunning OSPF.

17.2.1. Network Map (Example)

The following network map is used for further examples. AS 1 and 50have more neighbors but we only need to configure 1 and 50 as ourneighbor. The nodes itself communicate over tunnels in this examplebut that is not a must.

Note: The AS numbers used in this example are reserved, pleaseget your own AS from RIPE if you set up official peerings.

          --------------------
          | 192.168.23.12/24 |
          |    AS: 23        |
          --------------------
            /             \
           /               \
          /                 \
------------------       ------------------
| 192.168.1.1/24 |-------| 10.10.1.1/16   |
|    AS: 1       |       |    AS: 50      |
------------------       ------------------

17.2.2. Configuration (Example)

The following configuration is written for node 192.168.23.12/24,it is easy to adapt it for the other nodes.

It starts with some general stuff like hostname, passwords anddebug switches:

! hostname
hostname anakin

! login password
password xxx

! enable password (super user mode)
enable password xxx

! path to logfile
log file /var/log/zebra/bgpd.log

! debugging: be verbose (can be removed afterwards)
debug bgp events
debug bgp filters
debug bgp fsm
debug bgp keepalives
debug bgp updates

Access list, used to limit the redistribution to private networks (RFC 1918).

! RFC 1918 networks
access-list local_nets permit 192.168.0.0/16
access-list local_nets permit 172.16.0.0/12
access-list local_nets permit 10.0.0.0/8
access-list local_nets deny any

Next step is to do the per AS configuration:

! Own AS number
router bgp 23

    ! IP address of the router
    bgp router-id 192.168.23.12

    ! announce our own network to other neighbors
    network 192.168.23.0/24

    ! advertise all connected routes (= directly attached interfaces)
    redistribute connected

    ! advertise kernel routes (= manually inserted routes)
    redistribute kernel

Every 'router bgp' block contains a list of neighbors to whichthe router is connected to:

    neighbor 192.168.1.1 remote-as 1
    neighbor 192.168.1.1 distribute-list local_nets in
    neighbor 10.10.1.1   remote-as 50
    neighbor 10.10.1.1   distribute-list local_nets in

17.2.3. Checking Configuration

Note: vtysh is a multiplexer and connects all the Zebra interfacestogether.

anakin# sh ip bgp summary 
BGP router identifier 192.168.23.12, local AS number 23
2 BGP AS-PATH entries
0 BGP community entries

Neighbor        V    AS MsgRcvd MsgSent   TblVer  InQ OutQ Up/Down  State/PfxRcd
10.10.0.1       4    50      35      40        0    0    0 00:28:40        1
192.168.1.1     4     1   27574   27644        0    0    0 03:26:04       14

Total number of neighbors 2
anakin#
anakin# sh ip bgp neighbors 10.10.0.1
BGP neighbor is 10.10.0.1, remote AS 50, local AS 23, external link
  BGP version 4, remote router ID 10.10.0.1
  BGP state = Established, up for 00:29:01
  ....
anakin#

Let's see which routes we got from our neighbors:

anakin# sh ip ro bgp 
Codes: K - kernel route, C - connected, S - static, R - RIP, O - OSPF,
       B - BGP, > - selected route, * - FIB route

B>* 172.16.0.0/14 [20/0] via 192.168.1.1, tun0, 2d10h19m
B>* 172.30.0.0/16 [20/0] via 192.168.1.1, tun0, 10:09:24
B>* 192.168.5.10/32 [20/0] via 192.168.1.1, tun0, 2d10h27m
B>* 192.168.5.26/32 [20/0] via 192.168.1.1, tun0, 10:09:24
B>* 192.168.5.36/32 [20/0] via 192.168.1.1, tun0, 2d10h19m
B>* 192.168.17.0/24 [20/0] via 192.168.1.1, tun0, 3d05h07m
B>* 192.168.17.1/32 [20/0] via 192.168.1.1, tun0, 3d05h07m
B>* 192.168.32.0/24 [20/0] via 192.168.1.1, tun0, 2d10h27m
anakin#