My solution for fair traffic shaping in my girlfriend's dorm using tc's stochastic fairness queueing (sfq).

The Problem

In my girlfriend's dorm they used to have some sort of traffic shaping to keep P2P and streaming traffic from making the internet unusable for normal users. This used to work very well, until someone accidentally deleted the config files. Of course the original creator was long gone by then ;-)

Since after that, some days bandwidth would drop to several 10s of kB/s, I decided to re-setup traffic shaping (not knowing how painful that would turn out to be...)

The Solution

The whole topic of QoS under Linux is quite complex and you can do lots of more or less magical things to prefer some traffic over others etc. -- but I decided in the end to go for the simplest method: SFQ.

SFQ stands for stochastic fairness queueing and simply means that each packet is put in a hash bucket by hashing some of it's parameters (source, ports, destination, ...) and each bucket may empty one package at a time in round robin fashion.

If we can now use the source address (i.e. the originator of the packet) as the input for the hashing algorithm, we get a very fair queueing method that makes it impossible for one person to dominate the bandwidth while also allowing heavy users to occupy unused bandwidth. In other words: perfect for a dorm.

The following is a simple script that sets this up for two network interfaces: * eth0 is outward facing to the internet * eth1 is inward facing to the dorm network

#!/bin/sh
# Sets up traffic shaping
# Requires at least kernel version 2.6.26 and module cls_flow to be loaded.
#
# We use SFQ (stochastic fairness queueing):
# *     Each outgoing connection is hashed into one of several hash buckets by its source IP address.
# *     From each bucket, one packet is read and sent out in a round-robin fashion.
# *     This means that statistically, everyone has the same chance to send a packet, making it
#       theoretically impossible for one user to dominate the bandwidth.
# *     We do the same for incoming packets by hashing them by their destination IP.
#
# For more information see:
# *     http://www.wlug.org.nz/TrafficControl
# *     http://lartc.org/manpages/tc.txt
# *     http://www.shorewall.net/traffic_shaping.htm
# 

# Drop all existing qdiscs to be able to set new ones
tc qdisc del root dev eth0
tc qdisc del root dev eth1

# First, set the queueing discipline to SFQ
# *     "handle 1:" is the name of the qdisc, which is required and is used further down
# *     "perturb 10" means change the hashing algorithm every 10 seconds (to avoid hashing two people
#       into the same bucket for a long time).
tc qdisc add dev eth0 handle 1: root sfq perturb 10
tc qdisc add dev eth1 handle 1: root sfq perturb 10

# Next, set a filter that attaches a hash key to each packet according to its source IP
# *     "handle 1010" is the name of the filter, which must be set, even though it's not used
# *     "parent 1:" means use this for the root qdisc
# *     "flow hash keys X" means create the hash keys from X
#       we create hash keys from the netfilter connection tracking source IP (i.e. the IP before NAT) for the
#       outbound traffic (i.e. from the local network to the internet)
#       we create hash keys from the destination IP for the inbound traffic (i.e. from the internet to the
#       local network)
# *     "protocol all" means classify all packets
# *     "divisor 1024" is the modulus of the hash table (this is a compile-time constant of the kernel module,
#       do not change it!)
tc filter add dev eth0 handle 1010 parent 1: prio 1 protocol all flow hash keys nfct-src divisor 1024
tc filter add dev eth1 handle 1010 parent 1: prio 1 protocol all flow hash keys dst divisor 1024

# done :-)

Errors along the Way

I used to get some nice errors, most of which were related to the fact that the firewall server was running Debian Lenny with a 2.6.18 kernel that didn't support cls_flow.ko.

One in particular was very annoying:

RTNETLINK answers: Invalid argument
We have an error talking to the kernel

As one can easily see, kernel developers have a thing for descriptive error messages...

Turns out I hadn't given handles to the qdisc and the filter, both of which are required.