Fair NAT for Linux Routers

last updated: 2009-07-21

What's this?

This is the home of my linux router shaper script which allows something like fair bandwidth sharing among clients in the local network. The script is not great or anything - please don't expect the holy grail here - I just thought I'd publish it because many people helped me write it and maybe someone has some use for it. I bet there are still lots of things that can be improved. Sorry about the crappy design of this page, I don't have time to put more effort in better looks.

Network

Here's a very basic ASCII-art which shows my network situation:

                 +-----+
    +--------+   |  S  |
    | User A |---+  W  |
    +--------+   |  I  |
    +--------+   |  T  |     +--------+        +----------+
    | User B |---+  C  +-----| Router |--------| Internet |
    +--------+   |  H  |     +--------+        +----------+
       ....     ... / ...
    +--------+   |  H  |
    | User N |---+  U  |
    +--------+   |  B  |
                 +-----+

In words, it's a common setup. You have one internet connection, one router and several people in your LAN (family, roommates, neighbours, ...) who all want to use the internet.

Problem

You have a certain number of Clients (User A - User N) in your LAN which are connected by a Switch (or a Hub or BNC) to the Linux Router which is supposed to act as a gateway to the internet. The trouble now is, User B has a lot of downloads running and User C uploads stuff day and night, which leaves User A who only wants to use an interactive SSH shell in the rain, since B and C already use up all bandwidth the internet connection offers.

Solution

What we need to do is to share available bandwidth fairly among clients. In order to achieve this, I first tried several searches at Google and Freshmeat. This turned up quite a lot of results, like the Linux Advanced Routing & Traffic Control HOWTO which is a must-read and also contains great scripts, like the Wondershaper for single users. Another great general purpose script I found was HTB.init, which doesn't do anything by default, but gives you an easy way to setup HTB queues. In case you prefer CBQ, there's a CBQ.init too. If you don't know what I'm talking about, read the HOWTO above or continue reading here.

Script

Since I never found a script that did exactly what I wanted, I decided to write my own. It's designed to be an all-I-need script, therefore it does not just setup Traffic Shaping, but Masquerading and Port Forwarding too. In short, it does everything that has to do with IPTables and Traffic Control. I use HTB (Hierarchical Token Bucket) to share bandwidth among clients (one class per client). On top of that I added a PRIO queue to prioritize interactive traffic on a per-user basis. On top of PRIO I set SFQ to treat connections fairly. In version 0.72, experimental support for IPP2P to recognize peer-to-peer traffic was added.

This is the simplified class setup for per user Fair NAT uses per default:

    HTB class (for bandwidth sharing)
    |
    \-- PRIO (for prioritizing interactive traffic)
        |
        \--- Interactive:  SFQ (to treat concurrent connections fairly)
        \--- Normal:       SFQ
        \--- High-Traffic: SFQ
      [ \--- P2P:          SFQ (if IPP2P support is enabled only) ]

I bet this can still be improved and I'm always interested in ways to do so. In case you want another class structure, this can be done by replacing the parent_class and user_class functions in the script. See CLASS_MODE in Configuration section and the function documentation in the script for details. Feel free to send me your own functions with a short explanation, if you want me to make them available for everybody.

Here's a "real" graphic, which shows the complete qdisc/class structure on $DEV_LAN if you use the unmodified example configuration file. This graphic was created using a hacked version of Stef Coene's show.pl script and GraphViz. Click here to see it, but I warn you: it's quite big. Here's a similar picture, which includes IPP2P support. Note that there are more filter rules (the blue arrows) now which put the filesharing traffic into the user's prio band 4.

What you can and what you can't expect

Without traffic shaping, users with low-traffic, interactive connections experience ping times between 2-5 seconds, when other users have up- and downloads running. This is of course deadly for SSH connections. You can't work on remote machines like that. With my script, I get much lower pings, at about 100-200ms. Compared to the 2000-5000ms before, this is a huge improvement. However, considering that the ping on a free line would be at around 50ms, the connection still feels laggy. It's nearly impossible to make perfect interactive connections if the line is maxed out in both directions.

Requirements

For this script, you need iptables, tc and a QoS-enabled kernel. All these binaries must support HTB (usually the case unless you got a really old installation, in which case you ought to update anyway). I also use several kernel patches, none of which are actually required (unless if you want P2P shaping and some other Hacks). See README.patches in the tarball.

Configuration

Wheee, configuration. At first, my script didn't even have a configuration file. Now that it has one, a whole load of options were added to it. An example configuration file with lots of comments is included in the package. The stuff you most likely will have to change is the devices, the rates and the user settings. Otherwise the script won't work. The other stuff is mainly for people who know what they're doing.

• FEATURES

  • This is a variable with a space-separated list of features that should be enabled. Default is all enabled if you dont set this variable.
  • PROC:
    Allow Fair NAT to change some system variables in /proc, like setting /proc/sys/net/ipv4/ip_forward to 1.
  • MODULES:
    Try to load kernel modules for QoS first.
  • RESET:
    Fair NAT will replace all existing iptables rules with a very basic (empty) configuration. Not healthy for firewalls. You can disable this feature to keep the original rules in place. See Firewall Support below.
  • NAT:
    Allow Fair NAT to configure NAT. You could disable this if you prefer to set this up yourself / let your firewall do it.
  • FORWARD:
    Allow Fair NAT to configure Port Forwarding. Same as NAT, you can disable this if you don't need it.
  • QOS_DOWN:
    Shape download traffic. If you know a little bit about traffic shaping and believe that download shaping is completely useless, feel free to disable this.
  • QOS_UP:
    Shaping upload traffic can be disabled also. If you disable this and QOS_DOWN also, you could use Fair NAT for setting up NAT and Port Forwarding only, although that's not really the purpose of the script ;-)
  • TOS:
    Allow Fair NAT to modify the TOS (type-of-service) field of packets. Right now, Fair NAT relies on this TOS field for shaping, so using this feature is highly recommended.

• LAN

  • DEV_LAN:
    The network device your local clients are connected to. For example eth1.
  • RATE_LAN:
    The transfer rate in kbit/s of your LAN. This should be faster than your internet connection speed. Use a realistic value here. Don't blindly use 10/100Mbit on a 10/100Mbit network - you usually don't get those speeds because of overhead, collisions and such.

• Internet

  • DEV_NET:
    The network device of your internet connection. For example ppp0.
  • RATE_UP:

    Your internet upload connection speed in kbit/s. Since ISPs tend to overestimate their rates, you should use a realistic value here (measure it on a completely free line).

    You can also specify a unit for a rate. Supported units are kbps, mbps, mbit, kbit, and bps (same as 'tc'). If no unit is specified, kbit will be used per default.

  • RATE_DOWN:

    Your internet download connection speed in kbit/s. Just like RATE_UP, you should use a realistic value here.

    You can also specify a unit for a rate. Supported units are kbps, mbps, mbit, kbit, and bps (same as 'tc'). If no unit is specified, kbit will be used per default.

  • RATE_SUB_PERCENT:
    If your modem or your ISP has queues, you should make your router the bottleneck to avoid packet queueing which is bad for latency. Per default, 5% of bandwidth are subbed to achieve this. Read more about the bottleneck problem in the LARTC Howto mentioned above.
  • RATE_LOCAL_PERCENT:
    How much of your internet bandwidth should the router get? Usually, the machine requires some bandwidth for DNS requests (if it does act as an DNS cacher), for SSH access from the outside and similar. Per default, 5% of bandwidth are used here, which should be fine for most setups, where the router does not actively produce traffic (unlike webservers and such). It's not a hard limit, therefore this setting mainly ensures low latency for low traffic caused by the router.

• Clients

  • USERS:

    Specify who to do NAT for (who is allowed to use this machine as a gateway to the internet). Users are specified per IP and must be in the same subnet as your LAN device. Therefore only the last number of the client's machine is needed. For example, if your gateway is 192.168.100.42, the number 183 would expand to 192.168.100.183. It is also possible to group IPs (for users with more than one machine on the LAN) using ':'. So for example "3 4 7:9:12 42 128" stands for 5 users, one of which has 3 IPs.

    You can also specify a custom ceil download / upload rate per user. For example 17@300 limits IP 192.168.100.17 to 300kbit/s download rate. 17@300|50 adds a 50kbit/s upload limit, and 17@|50 limits upload only.

  • PORTS:
    Specify which ports are to be forwarded to which user (DNAT). The syntax is "user port user port ...", whereas user is the last number of the user's IP (e.g. 42) and port is either a port number (e.g. 3333) or a port range (e.g. 3000:4000). For multiple port ranges, the same IP can be specified multiple times. So for example "3 5000 9 6000:6100 9 6300:6400 42 7000" means that port 5000 is forwarded to IP 3, ports 6000-6100 and 6300-6400 are forwarded to IP 9, and port 7000 is forwarded to IP 42. Please note that ports can't be forwarded to multiple machines, therefore defining overlapping port ranges won't work. Of course you can also disable port forwarding in general by setting PORTS to "".
  • CLASS_MODE:
    There are some other class structures available, in case you don't like the one described above. Usually, this is set to "default". If you set it to "wonder" instead, every user will get a class structure that is pretty similar to what the Wondershaper script does. There may be others, check the example configuration file for a detailed list. Of course, if you have the know-how, you could also add your own by adding a new parent_class and user_class function to the script. Send your function to me and I'll include it here.
  • BORROW:
    Usually, users are allowed to borrow other users' bandwidth, as long as they don't use it themselves. This way, all available bandwidth is distributed among currently active users. If you don't want that for any reason, you can turn it off by setting this variable to 0. Then every user can only use the bandwidth that was reserved for him, even if the line is free.
  • USER_CEIL_UP:
    With this variable, you can set a lower maximum upload rate for all users. Default value is $RATE_UP. Useful if you don't want anyone to have more than, say, 300kbit at all times, on a 500kbit line.
  • USER_CEIL_DOWN:
    Allows lowering the maximum download rate for all users. Explanation see USER_CEIL_UP.

• IPP2P

  • IPP2P_ENABLE:
    Set to 0 (default), if IPP2P should be disabled. Otherwise set to 1. The following IPP2P settings only have an effect if IPP2P_ENABLE is set to 1.
  • IPP2P_OPTIONS:
    Set IPP2P options. See IPP2P documentation for details. Basically, you can specify here which P2P protocols should be detected. Default is "--ipp2p --apple --bit" (detect all protocols).
  • IPP2P_UDP:
    Newer versions of IPP2P also support UDP packet matching. Set this variable to 1 if you want to support it.
  • IPP2P_DROP_ALL:
    Set to 1, if P2P traffic should be dropped in general. Otherwise set to 0 (default). Please note that this applies only to new connections. Already established connections probably won't be affected.
  • IPP2P_DROP_MARKED:
    This option has only an effect when you change IPP2P_DROP_ALL from 0 to 1 while being connected to the internet. If you enable this, packages of already marked connections will be dropped, too.

• Hacks

  • MSS_CLAMP:
    With this, you can enable the MSS Clamping as described in the LARTC Howto. Please read the appropriate section of the Howto for further information.
  • TTL_SET:
    Set the maximum TTL (Time-To-Live) for outgoing packets to a specific value. This option requires a kernel patch. Click here for a more detailed description.
  • HTB_MPU:
    Use MPU for HTB. From the LARTC Howto on MPU: "A zero-sized packet does not use zero bandwidth. For ethernet, no packet uses less than 64 bytes. The Minimum Packet Unit determines the minimal token usage for a packet." This feature requires a patched tc binary. This binary is included in the package. Go to the official HTB homepage if you want to patch it yourself (can be troublesome). Download both HTB and MPU patches there.
  • HTB_OVERHEAD:
    Per-packet size overhead used in HTB's rate computations. According to the HTB page, "overhead implementation is a bit hack", but I guess that's why this is in the Hacks section of my script. ;-)
  • FAIRNAT_PREFIX:
    The prefix is used for Fair NAT's iptables chains. The default value "FAIRNAT" causes created chains to be called FAIRNAT_PREROUTING, FAIRNAT_FORWARD, and so on. This is in the hacks section because changing this could allow running multiple instances of Fair NAT on a single server (whatever you'd want that for).

• Binaries

  • BIN_TC:
    tc binary which supports HTB. Fair NAT will no longer check for 'tc-htb', since the times when we had to patch the kernel to obtain HTB support are long gone.
  • BIN_IPT:
    iptables
  • BIN_IFC:
    ifconfig
  • BIN_GREP:
    grep
  • BIN_SED:
    sed
  • BIN_ECHO:
    echo
  • BIN_MODPROBE:
    modprobe

Command line arguments

Currently, the following arguments are understood:

• help:
  Gives a short overview over the available command line options.
• version:
  Prints the version of your script.
• stop:
  Resets IPTables and Traffic Shaping to zero.
• info:
  Shows information about your current configuration.
• <config-file>:
  This file will be used instead of the default configuration file. Please note that if you use this feature, you have to specify the file when using the stop and info parameters too. (It's probably easier to change the FAIRNAT_CONFIG variable directly in the script)

IPP2P support

Let me add some notes about the IPP2P support introduced in Fair NAT v0.72. IPP2P provides a (more or less) reliable means to detect traffic of peer-to-peer (filesharing) applications. To use it, you first have to patch the kernel and the iptables program. You can get the patches at the Official IPP2P Homepage along with plenty documentation. When that's done, you have to enable IPP2P in the Fair NAT configuration file, too. See the example configuration file for details.

Please note that IPP2P also requires the CONNMARK patch, unless you intend to drop all P2P packets in general. Applying this patch can be a pain in the ..., it took me several days to do it properly. If you use the newest version of the CONNMARK patch, you also need a new version of iptables - at least version 1.2.10 (at the moment, you need iptables-cvs). Otherwise CONNMARK won't work - you'll get an 'Invalid Argument' error. Another solution would be using an OLD version of the CONNMARK patch, but I haven't found any that worked together with kernel 2.4.26 so far. The patch is part of patch-o-matic-ng which you can get on the Official Netfilter Homepage .

If IPP2P is enabled, Fair NAT uses it like this. If P2P traffic is forbidden in general, all packets recognized by IPP2P are dropped. End of story. Bye bye. However, if P2P traffic is allowed, Fair NAT does the following:

• Mark and remember all P2P connections using CONNMARK.
• Mark all packets of P2P-marked connections
• Use 4 instead of 3 prio bands per user.
• If a packet is marked as P2P, use $USER_MARK+1 as new package mark instead of $USER_MARK
• Put all $USER_MARK+1 packages into prio band 4. Bands 1-3 still depend on TOS.

Firewall Support (Experimental)

With Fair NAT 0.80, I've started taking the first steps towards Firewall support (which is one of the most requested features). In order not to collide with Firewall iptables rules, Fair NAT now creates it's very own private iptables chains. These can be flushed without risking to lose something the Firewall might have set up.

However, there are at least three things about Firewall Support I need to point out:

• For backward compatibility, Fair NAT will still reset all iptables rules unless you remove the RESET feature from the FEATURES list in fairnat.config.
• You will have to modify your Firewall to make it put packets into the Fair NAT chains - otherwise Fair NAT will not be able to do anything. See below for the rules you have to add.
• I still don't use a firewall myself, so this implementation is just an untested theory and might not work at all.

For Firewall Support, it has to put packets into the Fair NAT chains at some point. Ideally this is after the Firewall dropped unwanted packets, but that's just a guess. The best spot to put the rules in depends on the Firewall. Here's the rules:

iptables -t nat -A PREROUTING -j FAIRNAT_PREROUTING
iptables -t mangle -A PREROUTING -j FAIRNAT_PREROUTING
iptables -A FORWARD -j FAIRNAT_FORWARD
iptables -t mangle -A FORWARD -j FAIRNAT_FORWARD
iptables -t nat -A POSTROUTING -j FAIRNAT_POSTROUTING
iptables -t mangle -A POSTROUTING -j FAIRNAT_POSTROUTING

Of course, that's just a suggestion. You can modify these rules any way you like. However, don't forget that packets that don't go into the Fair NAT chains, will not be seen by Fair NAT rules, which could have side effects like packets not being shaped properly and so on.

Please send me some feedback if this solution works for you.

Download

WARNING: Use this script at your own risk only. It may remove all existing firewall rules, it may have critical bugs that are lethal to your system, it will set your duck on fire and many more bad things may happen to you. I'm not responsible for any damage caused by this script. Handle with care. Thanks.

Due to lack of free time and a proper Linux box, this script will no longer be updated. Hopefully the script can still be useful as an example that helps you creating your own shaping setup. Other / contributed versions of the script available down below.

The script can be found here: (use 0.79 if you have issues with 0.80)

• fairnat-0.80 (Firewall "support", selectable Features)
• fairnat-0.79 (Custom download / upload ceil per user, support rate units other than kbit.)
• fairnat-0.78 (Replaced hardcoded TTL setting with the configuration option TTL_SET. Workaround for localized (i18ned) ifconfigs where the IP address wasn't detected. Thanks to Simon for pointing these out.)
• fairnat-0.77 (Just a small feature I was asked for. If you want all your users to have a lower ceil than total available bandwidth, set CEIL_USER_UP and CEIL_USER_DOWN. See above for documentation.)
• fairnat-0.76 (Mini-Update: Forgot to remove some debug rules in 0.75.)
• fairnat-0.75 (Added HTB hacks: HTB_MPU and HTB_OVERHEAD. These require a special tc patch available from the HTB homepage. I included an already patched tc-htb binary into the package.)
• fairnat-0.74 (New config options BORROW, IPP2P_DROP_MARKED, CLASS_MODE, CLAMP_MSS)
• fairnat-0.73 (Bugfix: user upload rates were totally boggled which caused traffic to be dropped instead of being shaped correctly.)
• fairnat-0.72 (minor bugfixes, experimental IPP2P support)
• fairnat-0.71 (Class numbers are now derived from user IP instead of array index. This makes it much easier to read class-based statistics. Thanks to Udo for the suggestion.)
• fairnat-0.70 (User grouping allows multiple IPs per user. Thanks to Tomasz for the suggestion. Added command line arguments stop, info, <config-file>)
• fairnat-0.69
• fairnat-0.68

Please take the time to read the comments directly in the script, especially in the sample configuration file, too. I tried to add loads of comments in case you want to modify some parts of the script.

OpenWRT version

I have an OpenWRT router now. Since some different rules apply to this box than the stand alone Linux PC I had as a router at my old place, I wrote a simplified version of the FairNAT script for this router. It still uses subroutines to do its work, but it does not have a config file. So every user has to write his own shaping rules in his own subroutine. Other than that, the concept is still the same. Since the OpenWRT box has only one ethernet device, downstream shaping is done using a virtual IMQ interface. It uses HTB and one class per user, and it works great. It does not use HSFC because I can not make this scheduler behave like I want it to.

Albeit simplified, this is the latest version of Fair NAT (2008-01-10), and by the looks of it also the last for now. This OpenWRT router is serving a 16Mbit DSL line now, and I'm stuck with that solution for at least two years. I won't add any features to it because I don't need them, and I don't have time for adding them.

• fairnat_wrt.sh (updated 2009-07-21)

Unofficial / Contributed Versions

As some of you may already have noticed, I don't have much time to work on this project, as I'm very busy with my studies and such. I also moved, and my new home does not have a Linux router and no people to share a line with, so I'm not even using Fair NAT myself for the time being. So instead of letting all the contributions go to waste, I'll put user modified versions of Fair NAT here. These are all untested, so use at your own risk only.

• fairnat-0.80-dhcp.sh by Mike Hughes (Fair NAT as a daemon with DHCP support)
• fairnat-0.80-dhcp-iptables.sh by Nenad Markovic (adds iptables save/restore)

Contact

If you find bugs, please report them. If you have ideas for improvements, please tell me. If you need more features, ask me to implement them. If you decide to (not) use the script, drop me a note. If the script works particularly well (or bad) for you, I want to hear about it. If you can't get it to work, I'll see what I can do to help you. No, really. Give me some feedback. I'm tired of having nothing but spam in my mailbox. Thanks.

My mail address is: Andreas.Klauer@metamorpher.de

Credits

Thanks to all those people who helped me write this script. Special thanks to the authors of the LARTC Howto and the people on the LARTC mailing list. And of course to Stef Coene for his great Docum page. Thanks to everyone who sent me bug reports, suggestions, feature requests and so on.

TODO

This is more like a will-never-be-done list than a TODO list really.

• Support for multiple subnets, not only one
• Compatibility with alien iptables-rules (Firewalls)
• Custom rates per user
• Fair Sharing among multiple IPs per user
• Dynamic addition/removal of users (e.g. DHCP support)
• Support for more than one internet link (load balancing)

Other projects

• tc-graph.pl : Inspired by Stef Coene's show.pl , I wrote this script. It generates GraphViz .dot files (see http://www.graphviz.org for details on GraphViz) from tc-output. You can use it to create qdisc/class/filter structure visualizations like this one. It should be able to show any qdisc/class properly, but it's still bad with filters; it's really hard to parse output for matches etc, so only mark filters are supported so far.
• burn-dvd-image.sh : Simple script that uses a combination of growisofs, pipebuf and nice to make high speed DVD image burning under heavy load conditions possible. If you use growisofs, and experience speed breakdowns (reported writing speed is not constant), this is probably the right script for you.
• burn-dvd-fly.sh : Essentially the same as above, but instead of using an already existing DVD / image, mkisofs is used to burn files or directory contents on the fly.
• genkouyoushi.ps: A generator for Japanese calligraphy paper written in PostScript. It prints squares, circles, centerlines, and characters, customizable by changing variables at the beginning of the file. Example PDF output 20x20 10x10 Kana Table, utilizing the Kanji Stroke Order font.