Fair NAT for Linux Routers

                                      last updated: 2005-08-21 01:10 CEST

  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
   [1]Google and [2]Freshmeat. This turned up quite a lot of results,
   like the [3]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
   [4]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 [5]here to see it, but I warn you:
   it's quite big. Here's a [6]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).
            NEW: Now 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.
            NEW: Now 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.
            NEW: In Fair NAT 0.79, 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. [7]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 [8]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 [9]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 [10]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.

   This way, P2P traffic is not limited at all, but gets an even lower
   priority than HTTP traffic or FTP transfers. If you don't know what
   all this marking stuff is, don't bother. It's just the identifier that
   tells the Traffic Shaping mechanism which packet belongs to which
   user.

  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.

   The script can be found here: (use 0.79 if you have issues with 0.80)
     * [11]fairnat-0.80 (Firewall "support", selectable Features)
     * [12]fairnat-0.79 (Custom download / upload ceil per user, support
       rate units other than kbit.)
     * [13]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.)
     * [14]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.)
     * [15]fairnat-0.76 (Mini-Update: Forgot to remove some debug rules
       in 0.75.)
     * [16]fairnat-0.75 (Added HTB hacks: HTB_MPU and HTB_OVERHEAD. These
       require a special tc patch available from the [17]HTB homepage. I
       included an already patched tc-htb binary into the package.)
     * [18]fairnat-0.74 (New config options BORROW, IPP2P_DROP_MARKED,
       CLASS_MODE, CLAMP_MSS)
     * [19]fairnat-0.73 (Bugfix: user upload rates were totally boggled
       which caused traffic to be dropped instead of being shaped
       correctly.)
     * [20]fairnat-0.72 (minor bugfixes, experimental IPP2P support)
     * [21]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.)
     * [22]fairnat-0.70 (User grouping allows multiple IPs per user.
       Thanks to Tomasz for the suggestion. Added command line arguments
       stop, info, <config-file>)
     * [23]fairnat-0.69
     * [24]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.

  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: [25]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

   Sorry about the inactivity lately. I'm experimenting with some new
   features I was asked for, including, but not limited to:
     * 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)

   It's still an experiment, so I can't guarantee yet that Fair NAT will
   ever support all this stuff. If I succeed, this script will be quite
   powerful :-) and if I don't, well, it's still fun to try.

   In short: As long as there are no critical bug reports for the current
   version of the script, there won't be any updates for a while because
   I'm working on these experimental features.
     _________________________________________________________________

  Other projects

     * [26]tc-graph.pl : Inspired by Stef Coene's [27]show.pl , I wrote
       this script. It generates GraphViz .dot files (see
       [28]http://www.graphviz.org for details on GraphViz) from
       tc-output. You can use it to create qdisc/class/filter structure
       visualizations like [29]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.
     * [30]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.
     * [31]genkouyoushi.ps: A generator for Japanese calligraphy paper
       written in PostScript. It prints squares, circles, centerlines,
       and characters. Here's an [32]example (big). Customizable by
       changing variables at the beginning of the file.

References

   1. http://www.google.com/
   2. http://www.freshmeat.net/
   3. http://www.lartc.org/
   4. http://freshmeat.net/redir/htb.init/21951/url_homepage/htbinit
   5. http://www.metamorpher.de/files/fairnat.png
   6. http://www.metamorpher.de/files/fairnat_ipp2p.png
   7. http://iptables-tutorial.frozentux.net/iptables-tutorial.html#TTLTARGET
   8. http://luxik.cdi.cz/~devik/qos/htb/
   9. http://www.ipp2p.org/
  10. http://www.netfilter.org/
  11. http://www.metamorpher.de/files/fairnat-0.80.tar.gz
  12. http://www.metamorpher.de/files/fairnat-0.79.tar.gz
  13. http://www.metamorpher.de/files/fairnat-0.78.tar.gz
  14. http://www.metamorpher.de/files/fairnat-0.77.tar.gz
  15. http://www.metamorpher.de/files/fairnat-0.76.tar.gz
  16. http://www.metamorpher.de/files/fairnat-0.75.tar.gz
  17. http://luxik.cdi.cz/~devik/qos/htb/
  18. http://www.metamorpher.de/files/fairnat-0.74.tar.gz
  19. http://www.metamorpher.de/files/fairnat-0.73.tar.gz
  20. http://www.metamorpher.de/files/fairnat-0.72.tar.gz
  21. http://www.metamorpher.de/files/fairnat-0.71.tar.gz
  22. http://www.metamorpher.de/files/fairnat-0.70.tar.gz
  23. http://www.metamorpher.de/files/fairnat-0.69.tar.gz
  24. http://www.metamorpher.de/files/fairnat-0.68.tar.gz
  25. mailto:Andreas.Klauer@metamorpher.de
  26. http://www.metamorpher.de/files/tc-graph.pl.txt
  27. http://www.docum.org/stef.coene/qos/show_qos/index.html
  28. http://www.graphviz.org/
  29. http://www.metamorpher.de/files/fairnat.png
  30. http://www.metamorpher.de/files/burn-dvd-image.sh
  31. http://www.metamorpher.de/files/genkouyoushi.ps
  32. http://www.metamorpher.de/files/genkouyoushi.gif