Saturday, March 26, 2011

Fair traffic shaping an ADSL line for a local network using Linux

I am currently writing this up! In the meantime, full details are located here
Traffic shaping a standard ADSL link in order to share it with a couple of hundred users is a common problem. There are dozens of bits of software and firewall scripts out there already to do this. This particular script is one that I have written. It aims to be as simple as possible, is easily customised, and uses connlimit to identify P2P users. Although the latter is not 100% reliable, it seems to work pretty well and does not fall foul of any new/changed P2P software that happens to some of the other scripts.


Contents

[hide]

[edit] Software required

Any recent Linux distribution should be able to be used for these scripts. The example shown here uses Debian.
The following packages are required:
  • Kernel 2.6.26
  • IPset
IPset is not yet in the stable kernel, so the easiest way to install it (in Debian) is:
apt-get install ipset
apt-get install module-assistant xtables-addons-source
module-assistant prepare
module-assistant auto-install xtables-addons-source
(Note: at the time of writing, the above packages are not in stable, so will have to be installed from testing repositories. See here for an example).
A better way is possibly:
apt-get install ipset
apt-get install module-assistant
apt-get install netfilter-extensions-source
module-assistant build netfilter-extensions-source
module-assistant install netfilter-extensions-source
or from recent feedback:
aptitude install ipset ipset-source module-assistant
module-assistant auto-install ipset-source
But I need to check this on a clean install.

[edit] Principle of operation

  • All traffic is given an iptables MARK depending on its type:
    • 10 for low latency traffic such as SSH shells
    • 30 for normal web browsing
    • 40 for any normal traffic including large web downloads
    • 60 for P2P traffic
  • HTB is used to create classes for all this traffic
  • All traffic shaping is hashed by client, not by connection. This means that one user with several large download connections will get the same amount of total bandwidth as one user with one connection. The default within Linux and routers is normally to do it per connection.
  • ipset is used to generate a list of client IP addresses that are using P2P software.
  • connlimit is used to detect P2P software. The firewall rules below look for multiple connections to high port numbers from a client.


[edit] Assumptions

  • ppp0 is the internet connection
  • eth0 is the local network connection


[edit] Firewall rules required

I will first describe some of the rules that form the basis of the traffic shaping. Later in this page the full script is shown.
The first task is to create an ipset for storing the IP addresses of all our naughty users slurping up the bandwidth with constantly downloading P2P software. A timeout of 60 seconds is used, so that as soon as they turn off their software their IP address is removed. The current IP addresses in the IPset can be monitored with the 'ipset -L' comand from the bash prompt
# Create a set called p2p with 60 second timeout
ipset -N p2p iptree --timeout 60
Next we need to mark traffic as required, using the principles set out earlier. The following code contains some examples.
# First mark all traffic coming in on the ppp link with the default of 40
$IPTABLES -t mangle -A PREROUTING -i ppp0 -j MARK --set-mark 40

# Mark http and https traffic as 30, both in and out
$IPTABLES -t mangle -A FORWARD -p tcp --sport 80 -i ppp0 -j MARK --set-mark 30
$IPTABLES -t mangle -A FORWARD -p tcp --dport 80 -o ppp0 -j MARK --set-mark 30
$IPTABLES -t mangle -A FORWARD -p tcp --sport 443 -i ppp0 -j MARK --set-mark 30
$IPTABLES -t mangle -A FORWARD -p tcp --dport 443 -i eth0 -j MARK --set-mark 30

# Mark in and out SSH traffic as high priority
$IPTABLES -t mangle -A FORWARD -p tcp --sport 22 -i ppp0 -j MARK --set-mark 10
$IPTABLES -t mangle -A FORWARD -p tcp --dport 22 -o ppp0 -j MARK --set-mark 10

# Mark any traffic destined for the local machine with 1
# This traffic does not need shaping and we will ignore it later
$IPTABLES -t mangle -A POSTROUTING --source 10.0.0.1 -j MARK --set-mark 1
$IPTABLES -t mangle -A POSTROUTING --destination 10.0.0.1 -j MARK --set-mark 1

# Mark any large downloads as 40 (they may have been marked 30 or 10 earlier)
$IPTABLES -t mangle -A FORWARD -m connbytes --connbytes 504857: --connbytes-dir both \
  --connbytes-mode bytes -j MARK --set-mark 40

Now we need to look out for all those P2P connections. We're going to find these out by looking for a client on the network making lots of connections to high port numbers, which is generally what P2P software does. This isn't foolproof of course: I have seen P2P software start to use port 80, and there could be false negatives, but on the whole it seems to work better than any other solutions out there that I have tried.
# TCP traffic from clients going to high port numbers
# Add the client IP address to the ipset
$IPTABLES -t mangle -A FORWARD -o ppp0 -p tcp --dport 1024: \
 -m connlimit --connlimit-above 8 -j SET --add-set p2p src 

# UDP traffic from clients going to high port numbers
$IPTABLES -t mangle -A FORWARD -o ppp0 -p udp --dport 1024: \
 -m connlimit --connlimit-above 4 -j SET --add-set p2p src 

# TCP traffic in to clients from high port numbers
$IPTABLES -t mangle -A FORWARD -i ppp0 -p tcp --sport 1024: \
 -m connlimit --connlimit-above 8 -j SET --add-set p2p dst

# UDP traffic in to clients from high port numbers
$IPTABLES -t mangle -A FORWARD -i ppp0 -p udp --sport 1024: \
 -m connlimit --connlimit-above 4 -j SET --add-set p2p dst
The above rules just add the client IP address to the ipset. We now need to mark the traffic, which the following rules do. On one network, traffic became so slow that I marked ALL traffic to and from those clients as '60'. This certainly sped the network up, but of course the entire internet connection for that client became really slow. If you want to do that just remove the destination port parameters.
# Once a user is in the p2p IPSET, these rules mark their traffic
# that is above 1024 to the lowest priority

# TCP traffic from the client
$IPTABLES -t mangle -A FORWARD -o ppp0 -p tcp --dport 1024: \
 -m set --set p2p src -j MARK --set-mark 60

# TCP traffic to the client
$IPTABLES -t mangle -A FORWARD -i ppp0 -p tcp --sport 1024: \
 -m set --set p2p dst -j MARK --set-mark 60

# UDP traffic from the client
$IPTABLES -t mangle -A FORWARD -o ppp0 -p udp --dport 1024: \
 -m set --set p2p src -j MARK --set-mark 60

# UDP traffic to the client
$IPTABLES -t mangle -A FORWARD -i ppp0 -p udp --sport 1024: \
 -m set --set p2p dst -j MARK --set-mark 60

Finally enable internet connection sharing:
$IPTABLES -A FORWARD -i ppp0 -o eth0 -m state --state ESTABLISHED,RELATED -j ACCEPT
$IPTABLES -A FORWARD -i eth0 -o ppp0 -j ACCEPT
$IPTABLES -t nat -A POSTROUTING -o ppp0 -j MASQUERADE

[edit] Shaping the traffic using HTB

Now that we have got to this stage, we have all our traffic nicely marked. All we need to do now is shape it. Unfortunately ingress shaping on Linux is somewhat limited, so instead we only do egress shaping. To limit traffic coming in from the internet, we shape the traffic as it leaves the server. Not ideal, but it seems to work okay.
In these scripts I limit the downlink at 2200 kbps and the uplink at 330 kpbs. These figures *must* be less that your connection is capable of, otherwise no shaping will take place as the connection will do the shaping instead. The generally accepted approach is to set the values to 90% the theoretical maximum, but I advise you to experiment.
First, the downlink. Shaping is done on eth0 as the traffic leaves for the network.
We use HTB to do the shaping. It can be difficult to understand HTB and tc in general, but if you look hard enough there is some good documentation out there, it's just hard to find. I will place some links at the end of this document.
First, some basics. A qdisc is a whole set of shaping rules that we apply, normally to a whole interface. Here we add a HTB qdisc to the interface eth0. This is known as the root for the interface.
We don't set a default class; this is so that local eth0 traffic is not shaped. As already stated, we have to shape at eth0 and not ppp0 as we can only do egress shaping decently.
# Create the root qdisc on the interface
tc qdisc add dev eth0 root handle 1: htb

# Add some overall rate limits as defined above. Parent number 1:
# says to apply it to the root above. Call this child 1:1
tc class add dev eth0 parent 1: classid 1:1 htb rate 2200kbit
We now have one root HTB qdisc with a rate limit of 2200kbps. To this we add 4 further children. Note the numbers. 1: (or 1:0) is the root. 1:1 is the first child with the overall rate limit. Each child of this is 1:10, 1:20 and so on. To make things simpler, I have numbered the children below to align with the MARK numbers. Note that all the rates of the children should add up to the single rate limit of the parent.
# Add a number of classes to the root qdisc.
# With some qdiscs the classes are automatically
# created. With HTB they are not so we add 4 in total
# with different rate limits for each

# interactive traffic
tc class add dev eth0 parent 1:1  classid 1:10 htb \
 rate 100kbit ceil 100kbit prio 0

# web browsing
tc class add dev eth0 parent 1:1  classid 1:30 htb \
 rate 1000kbit ceil 1000kbit prio 1

# default traffic
tc class add dev eth0 parent 1:1  classid 1:40 htb \
 rate 1000kbit ceil 1000kbit prio 2

# bad boys
tc class add dev eth0 parent 1:1  classid 1:60 htb \
 rate 100kbit ceil 100kbit prio 3

We now have the HTB qdisc fully set up. However, no traffic will be sent to it yet, and the traffic will not be shaped within each class.
The next set of rules shape traffic in each class. If we don't do this, then all the traffic for a particular class (such as all the webbrowsing traffic - 30) will be piled into the class on a fifo basis. We want to be more intelligent than this. SFQ does some nice fair shaping.
tc qdisc add dev eth0 parent 1:10 handle 10: sfq perturb 10
tc qdisc add dev eth0 parent 1:30 handle 30: sfq perturb 10
tc qdisc add dev eth0 parent 1:40 handle 40: sfq perturb 10
tc qdisc add dev eth0 parent 1:60 handle 60: sfq perturb 10
So, everything is set up and ready to go. We just need to divert some traffic into each of the classes. We do this by attaching a filter to the class. A filter looks for traffic of a particular type and sucks it into the class. In this example, we use the MARK of the traffic (called flowid here).
tc filter add dev eth0 parent 1:0 protocol ip handle 10 fw flowid 1:10
tc filter add dev eth0 parent 1:0 protocol ip handle 30 fw flowid 1:30
tc filter add dev eth0 parent 1:0 protocol ip handle 40 fw flowid 1:40
tc filter add dev eth0 parent 1:0 protocol ip handle 60 fw flowid 1:60
Everything will be working nicely at this point. However, we have one more tweak to do. We want to share traffic between clients (by IP address) not by connection. This means that if one client has 4 downloads on the go, and another has only one, that traffic will be split 50/50, as opposed to the first client getting 80%. We do this by applying more filters to the existing ones.
tc filter add dev eth0 parent 10: protocol ip handle 10 flow hash keys nfct-dst divisor 1024
tc filter add dev eth0 parent 30: protocol ip handle 30 flow hash keys nfct-dst divisor 1024
tc filter add dev eth0 parent 40: protocol ip handle 40 flow hash keys nfct-dst divisor 1024
tc filter add dev eth0 parent 60: protocol ip handle 60 flow hash keys nfct-dst divisor 1024
That completes the downlink. The uplink (out on ppp0) is exactly the same. I have not repeated it here, but it is shown in the full example later.

[edit] The full script

The full script is the same script as used for the complete web portal / traffic shaping solution (detailed here). It can be downloaded from here.

[edit] References

A really well written overview of traffic shaping (chapter 2)
http://www.opalsoft.net/qos/DS.htm

HTB info and manual:
http://www.mikrotik.com/testdocs/ros/2.9/root/queue.php
http://luxik.cdi.cz/~devik/qos/htb/manual/userg.htm

Kernel traffic routing diagram - really handy
http://www.docum.org/docum.org/kptd/

Courtesy : http://www.andybev.com/index.php/Fair_traffic_shaping_an_ADSL_line_for_a_local_network_using_Linux