Advice
======

Try CBQ first. I mean it. If you don't like it/whatever, try this. But, 
remember: if you already did try CBQ, this might be your last chance to run 
away :)

Intro
=====

Shaperd is a user-mode program (a.k.a. daemon) that can shape traffic passing 
through a linux box. I began to write it because I was tired of waiting for the
echoes when I telnet other machines over my slow ppp link to the internet. I 
did try cbq and shaper, but none satisfied me. Cbq is very powerful and 
generic (try it!), but has a rather steep learning curve. Besides, I was 
looking for something cool to play with :-).

Prerequisite
============

So it's the kernel who forwards the incoming packets to the shaper; this can 
be done with the BSD divert sockets patch for 2.2 kernels or with netfilter's
ipq library on 2.4 kernels.

Please note that support for divert sockets is somewhat limited, because
there's no way to stop a forwarded packet. The application can only reinject
it (inbound or outbound), so the packet will:
- re-enter the network stack as any other new, incoming packet (inbound) ;
- go to the wire (outbound).
This makes firewall rules somewhat tricky to write, specially for 
forwarded/masq'd packets.

Linux 2.2
~~~~~~~~~
Applying a patch is easy, just cd to the kernel source directory (for example, 
/usr/src/linux) and execute:

shell> cat linux-2.2.x-div-1.x.x.patch | patch -p1 --verbose

When you're done with the patch, proceed with kernel building as usual, but
remember to enable the divert-sockets feature!. You'll also need a patched
ipchains, check out the divert sockets' site at http://www.anr.mcnc.org/~divert.
Once the kernel has been built and installed, try running the test program from
the divert sockets mini-HOWTO.

Linux 2.4
~~~~~~~~~
1) Enable the following compile-time options and recompile yer kernel if
necessary:

- code maturity ->
  - prompt for development and/or incomplete code/drivers
- networking options ->
  - kernel/user netlink socket
  - netnetwork packet filtering
  - netfilter configuration ->
    - userspace queueing via netlink
    - ip tables support
    - packet filtering

2) Install iptables' headers and shared libraries (make && make install-devel,
get them here -> http://netfilter.samba.org)

Bulding-Installing
==================

Did you get the divert sockets stuff done and/or installed libipq? Good. Now we
can build shaperd: log in as root, unpack the tarball, chdir into the 'src' 
subdirectory and type one of these lines (*):

shell> gmake with_divert=yes # <- for 2.2 kernels
shell> gmake with_ipq=yes    # <- for 2.4 kernels (**)
shell> gmake with_divert=yes with_ipq=yes # <- for a multi-boot system (**)

This should build a binary called 'shaperd'. Copy the binary to your favourite 
directory  (I'll use /usr/local/shaperd) along with the *.conf example config 
files located in etc. Finally, drop the shaperd man page in your favoutire man 
directory (and run makewhatis and friends).

(*) if you're rebuilding shaperd with a diffrent configuration, it's better to
execute "gmake clean" first.

(**) don't forget to install ipq's libs and headers first! (gmake install-devel)

Testing
=======

Now that shaperd has been built and installed, let's try a few examples to see
if it is working fine. As i said before, some examples (notably those related 
to packet forwarding/masquerading) will be only available for 2.4 kernels 
because of the much cleaner packet manipulation mechanism (divert sockets 
reinject forwarded packets, whereas ipq can just stop them and let the 
user-mode app decide whether to let it continue traversing the stack or not).

First Example
~~~~~~~~~~~~~
In the first example we will enable the local echo server and send some bits 
to it, in order to benchmark the data transfer rate. We will shape the server's
output, so the quotient of the amount of bytes received vs the elapsed time 
should be close to the bandwidth specified in the configuration file 
(example.1.conf), which should be something like:

-- (example.1.conf) (I removed some stuff for simplicity)
#packet forwarding = ipq    # <- (uncomment if using ipq & kernel 2.4)
#packet forwarding = divert # <- (uncomment if using divert sockets)
#divert port = 1111         # <- (uncomment only with divert sockets)
class local_echo {
	# shape every tcp packet from 127.0.0.1, port 7 (echo)
	ipv4 classifier proto=tcp saddr=127.0.0.1 sport=7
	bandwidth = 100 kbyte/s
}
-- (example.1.conf) --

This is simple, notice the 'divert port' entry: it tells the shaper where to
receive packets from (if you are forwarding with divert sockets). We'll use 
that value in the ipchains rules (later). A 'classifier' is a c++ entity that
can pick up data packets and store them on a queue (each class has its own 
queue) (*). After it has been queued, another c++ entity (a packet scheduler)
would reinject it.

(*) if a packet that hasn't been picked up by any classifier, it will be 
dropped.

Now, enable the echo server on the same box as shaperd will run (in my redhat 6
and debian 2.2r2 boxes I have to edit /etc/inetd.conf, uncomment the echo/tcp 
line and send a SIGHUP to inetd, then try 'telnet 127.0.0.1 7' to check this 
step).

These are the commands we will use for the test, i'll explain them bellow:

1  shell> ./shaperd -c ./example.1.conf
2a shell> ipchains -A output -p tcp -s 127.0.0.1 7 -j DIVERT 1111   # linux 2.2
2b shell> iptables -A OUTPUT -p tcp -s 127.0.0.1 --sport 7 -j QUEUE # linux 2.4
3  shell> dd if=/dev/zero bs=1k | nc 127.0.0.1 7 | time dd of=/dev/null bs=1k \
   count=1024

1- launch shaperd and tell it to load config file example.1.conf
2- tells the kernel that we want the bits coming from the echo server to be 
   forwarded to the shaper daemon. You'll have to pick one of the two (2a, 2b) 
   possibilities depending of the kernel version you're running.
   This is an important step, always do check that you are sending the correct 
   stuff to shaperd! It will drop every packet that isn't picked up by any 
   classifier.
3- finally, send some data to the echo server and measure how much time it took 
   for the packets to come back ("nc" is the name of the netcat utility, a 
   *killer* tool! install it if you haven't already (or replace it with
   telnet)

Here's the output of the commands in my box:

shell> dd if=/dev/zero bs=1k | nc 127.0.0.1 7 | time dd of=/dev/null bs=1k \
> count=1024
993+31 records in
993+31 records out
0.01user 0.20system 0:10.45elapsed 1%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (93major+12minor)pagefaults 0swaps
1133+0 records in
1132+0 records out
Broken pipe

We received 1 megabyte in 10.5 seconds, so the throughput is roughly 98 kb/s
(not bad!).

To disable traffic shaping, just tell the kerneal not to forward packets to 
shaperd anymore (pick up one of the following two lines :)

shell> ipchains -D output -p tcp -s 127.0.0.1 7 -j DIVERT 1111   # linux 2.2
shell> iptables -D OUTPUT -p tcp -s 127.0.0.1 --sport 7 -j QUEUE # linux 2.4

finally,

shell> killall shaperd

(it's better not to send a -9 because this will not give shaperd a chance to 
clean up). In case you didn't make it:

- Is the tcp echo server running? (launch a telnet 127.0.0.1 7 and verify it!)
- Is shaperd running? ('ps axuw | grep shaperd').
- If you got the following error:
  "error: not compiled with xxx support
   parse of [./example.1.conf] stopped at line yy"
  Edit ./example.1.conf and check the "packet forwarding" variable.
- Did you build ip_queue as a module? (you'll get and ipq_set_mode() error if 
  you're using IPQ (linux 2.4) and the module isn't loaded before shaperd)
- Check out the logs just after launching shaperd. The actual location of the 
  logfiles depends on your syslog configuration (in my stock redhat 6 they are 
  routed to /var/log/messages).
- If you're using divert sockets, make sure you're DIVERTing to the same port
  specified in shaperd's configuration file. Remember that the firewall rules 
  must forward the packets that shaperd is expecting, not more, nor less (*). 
  Check the logs if you are unsure about this (you may also have to increase 
  shaperd's verbosity).
- Check the values of the firewall rules' counters, they should change for
  every packet that is being shaped (ipchains -L -v -x -n for linux 2.2/divert,
  iptables -L -v -x -n for linux 2.4). If they don't, you'll haver to review
  steps 2a/2b.
- You can increase shaperd's verbosity level by editing its configuration file
  and sending it a SIGHUP with 'killall -HUP shaperd'.
- Ah, one more thing:
  did you configure the kernel (2.2, 2.4) properly?
  for 2.2 kernels: did you patch ipchains for divert sockets support?
  for 2.4 kernels: did you install libipq?
  it won't work if you didn't!.

(*) Automatic firewall-rule generation is possible but I prefer not to mess with
this for the moment.

Second Example
~~~~~~~~~~~~~~
      +--------+                   +--------+                   +--------+
      |        |  192.168.1.x  eth1|        |eth0  192.168.0.x  |        |
      | A  box +-------------------+ B  box +-------------------+ C  box |
      |        |.250             .2|(shaper)|.2               .1|        |
      +--------+                   +--------+                   +--------+
                                       -->
                                       <--
                                    (bits :-)

We will shape every bit coming from/going to A, but we will give higher 
priority to telnet/ssh/icmp packets. Check out the file example.2.conf.xxx for 
the details (xxx is "ipq" for 2.4 and "divert" for 2.2), i'll strip the 
irrelevant stuf here:

-- (example.2.conf.ipq)
class from_A {
	bandwidth = 100 kbyte/s

	# shape every telnet/ssh packet coming from A's net (client)
	# note: you can also use real (dns) host names instead of ip addresses
	ipv4 classifier prio=1 proto=tcp                    \
		inp_if=eth1 saddr=192.168.1.0/255.255.255.0 \
		out_if=eth0 daddr=192.168.0.0/255.255.255.0 dport=telnet,ssh

	# we'll also give high priority to icmp packets (to measure rtt)
	ipv4 classifier prio=1 proto=icmp                   \
		inp_if=eth1 saddr=192.168.1.0/255.255.255.0 \
		out_if=eth0 daddr=192.168.0.0/255.255.255.0

	# finally, shape the rest of the bits
	ipv4 classifier prio=0                              \
		inp_if=eth1 saddr=192.168.1.0/255.255.255.0 \
		out_if=eth0 daddr=192.168.0.0/255.255.255.0

	# netfilter has the ability for forward just the pckts' headers, so
	# only the packet limit makes sense under 2.4
	queue limits = 0 kb 100 packets
}

class from_C {
	bandwidth = 100 kbyte/s

	# shape every telnet/ssh packet coming from C's net (server)
	ipv4 classifier prio=1 proto=tcp                                     \
		inp_if=eth0 saddr=192.168.0.0/255.255.255.0 sport=telnet,ssh \
		out_if=eth1 daddr=192.168.1.0/255.255.255.0

	# we'll also give high priority to icmp packets (to measure rtt)
	ipv4 classifier prio=1 proto=icmp                   \
		inp_if=eth0 saddr=192.168.0.0/255.255.255.0 \
		out_if=eth1 daddr=192.168.1.0/255.255.255.0

	# shape the rest of the bits :-)
	ipv4 classifier prio=0                              \
		inp_if=eth0 saddr=192.168.0.0/255.255.255.0 \
		out_if=eth1 daddr=192.168.1.0/255.255.255.0

	# netfilter has the ability for forward just the pckts' headers, so
	# only the packet limit makes sense under 2.4
	queue limits = 0 kb 100 packets
}
-- (example.2.conf.ipq) --

Enable traffic shaping (as usual, select the a/b series depending on your
kernel version) -->

1a- ./shaperd -c ./example.2.conf.ipq
2a- iptables -A FORWARD -i eth0 -o eth1 -s 192.168.0.0/24 -d 192.168.1.0/24 \
            -j QUEUE
3a- iptables -A FORWARD -i eth1 -o eth0 -s 192.168.1.0/24 -d 192.168.0.0/24 \
            -j QUEUE

1b- ./shaperd -c ./example.2.conf.divert
2b- ipchains -I input -s 192.168.0.0/24 -j DIVERT 1111
3b- ipchains -I input -s 192.168.1.0/24 -j DIVERT 1111

I) Telnet from A to C. It should work fine (i.e. low round trip time). Now, 
we'll simulate heavy network congestion using the tcp echo server on both (A,
C) boxes. As usual, edit /etc/inetd.conf, uncomment the tcp echo server line 
and restart inetd (note: RedHat 7.x boxes come with a fancier inetd -xinetd-; 
luckily, I don't use RedHat 7.x, so you're on your own under RH-7.x :-).

Now, flood the net by sending some -bogus- bits towards both echo servers:

A's shell>> cat /dev/zero | nc 192.168.0.1 7 >/dev/null 
C's shell>> cat /dev/zero | nc 192.168.1.250 7 >/dev/null 

You shouldn't notice much difference once the transfer has started, because, as 
ssh/telnet packets have higher priority than the rest of the packets, they'll 
go as soon as possible to the wire (*). To measure this, send some pings and
see how much lag we have:

A's shell>> ping -n -c 60 192.168.0.1
... (bits erased for brevity :-)
--- 192.168.0.1 ping statistics ---
60 packets transmitted, 60 packets received, 0% packet loss
round-trip min/avg/max = 2.1/42.2/140.5 ms

(*) note that this is a very simple scheduling criteria, I mean: there's no 
"anti-starvation" policy for the lower-priority packets. They could be even 
dropped if a higher priority packet arrives and there's no more available space
on the queue).

II) Edit the example.2.conf.xxx file again, but this time give all the packets 
the same priority (prio=0). Reload it (killall -HUP shaperd) and repeat step I.
This time, telnet's responsiveness should be *much* worse -->

A's shell>> ping -n -c 60 192.168.0.1
... (more bits erased :-)
--- 192.168.0.1 ping statistics ---
60 packets transmitted, 60 packets received, 0% packet loss
round-trip min/avg/max = 670.4/845.3/1038.5 ms

(ie, telnet's responsiveness is about 20x times worse, in fact :-)

And ... in case you didn't make it ... well ... look behind you!!! a 3-headed 
monkey!!! :-)

Third Exapmle
~~~~~~~~~~~~~
This is the one i'm using at home:

      +--------+
      |        |
      | A  box +-------+
      |        |.254   |
      +--------+       |
                       |
      +--------+       |
      |        |       |
      | B  box +-------+
      |        |.253   |      +--------+ 
      +--------+       |  eth0| R  box |ppp0
                       +------+ (masq  +------> ppp link
      +--------+       |    .1| shaper)|        128 kbit/s upstream
      |        |       |      +--------+        512 kbit/s downstream
      | C  box +-------+
      |        |.252   |      
      +--------+       |
                       |
      +--------+       |
      |        |       |
      | D  box +-------+ 192.168.0.0/24 (10 mbit lan)
      |        |.251
      +--------+

A-D are a mixture of windows and linux boxes, and R is my trusty masq-router,
running shaperd. Link's bandwidth is 128 kbit/s upstream, 512 kbit/s 
downstream.

I put all the shaperd-related iptables' stuff in the file firewall.init:

#!/bin/sh

IPT="/usr/local/sbin/iptables"

/sbin/depmod -a

# clean up previous stuff
$IPT -t nat -F
$IPT -t mangle -F
$IPT -t filter -F
$IPT -X SHAPE

# create the "shape" chain
$IPT -N SHAPE
$IPT -I SHAPE -j QUEUE

# system policies & security stuff
$IPT -P FORWARD DROP
$IPT -P INPUT DROP

$IPT -A INPUT -i lo -j ACCEPT
$IPT -A INPUT -i eth0 -j ACCEPT
$IPT -A INPUT -m state --state ESTABLISHED,RELATED -j ACCEPT
$IPT -A INPUT -p tcp -i ppp0 --dport 22 -j ACCEPT
$IPT -A INPUT -p tcp -i ppp0 --dport 23 -j ACCEPT
$IPT -A INPUT -p tcp -i ppp0 --dport 80 -j ACCEPT
$IPT -A INPUT -p icmp -i ppp0 -j ACCEPT

# this is a workaround for some broken routers out there
$IPT -A FORWARD -p tcp --tcp-flags SYN,RST SYN -j TCPMSS --clamp-mss-to-pmtu

# masq'd hosts: A (.254), B (.253), C (.252), D (.251)
$IPT -t nat -A POSTROUTING -s 192.168.0.254/32 -o ppp0 -j MASQUERADE
$IPT -t nat -A POSTROUTING -s 192.168.0.253/32 -o ppp0 -j MASQUERADE
$IPT -t nat -A POSTROUTING -s 192.168.0.252/32 -o ppp0 -j MASQUERADE
$IPT -t nat -A POSTROUTING -s 192.168.0.251/32 -o ppp0 -j MASQUERADE

# shape (upstream) the masqueraded hosts (.251 ... .254)
$IPT -A FORWARD -s 192.168.0.254/32 -i eth0 -o ppp0 -j SHAPE
$IPT -A FORWARD -s 192.168.0.253/32 -i eth0 -o ppp0 -j SHAPE
$IPT -A FORWARD -s 192.168.0.252/32 -i eth0 -o ppp0 -j SHAPE
$IPT -A FORWARD -s 192.168.0.251/32 -i eth0 -o ppp0 -j SHAPE

# shape (downstream) the masqueraded hosts (.251 ... .254, tcp only)
$IPT -A FORWARD -p tcp -d 192.168.0.254/32 -o eth0 -i ppp0 -m state \
        --state ESTABLISHED,RELATED -j SHAPE
$IPT -A FORWARD -p tcp -d 192.168.0.253/32 -o eth0 -i ppp0 -m state \
        --state ESTABLISHED,RELATED -j SHAPE
$IPT -A FORWARD -p tcp -d 192.168.0.252/32 -o eth0 -i ppp0 -m state \
        --state ESTABLISHED,RELATED -j SHAPE
$IPT -A FORWARD -p tcp -d 192.168.0.251/32 -o eth0 -i ppp0 -m state \
        --state ESTABLISHED,RELATED -j SHAPE

# don't shape the rest of the (downstream) traffic (it makes no sense)
$IPT -A FORWARD -d 192.168.0.254/32 -o eth0 -i ppp0 -m state \
        --state ESTABLISHED,RELATED -j ACCEPT
$IPT -A FORWARD -d 192.168.0.253/32 -o eth0 -i ppp0 -m state \
        --state ESTABLISHED,RELATED -j ACCEPT
$IPT -A FORWARD -d 192.168.0.252/32 -o eth0 -i ppp0 -m state \
        --state ESTABLISHED,RELATED -j ACCEPT
$IPT -A FORWARD -d 192.168.0.251/32 -o eth0 -i ppp0 -m state \
        --state ESTABLISHED,RELATED -j ACCEPT

# warez server: leechers can suck every bit out of your pipe so it's better 
# to keep 'em shaped :-)
$IPT -A OUTPUT -p tcp -o ppp+ --sport 80 -j QUEUE

# enable ipv4 packet forwarding
echo "1" >/proc/sys/net/ipv4/ip_forward

And shaper configuration (/usr/local/shaperd/shaperd.conf) is:

# /usr/local/shaperd/shaperd.conf
log level = warning
packet forwarding = ipq
daemon = yes
pidfile = /var/run/shaperd.pid

class A_up {
        bandwidth = 32 kbit/s
        ipv4 classifier out_if=ppp+ saddr=192.168.0.254
        borrow from B_up, C_up, D_up
        queue limits = 0 kb 150 packets
}

class A_down {
        bandwidth = 128 kbit/s
        ipv4 classifier inp_if=ppp+ daddr=192.168.0.254
        borrow from B_down, C_down, D_down
        queue limits = 0 kb 150 packets
}

class B_up {
        bandwidth = 32 kbit/s
        ipv4 classifier out_if=ppp+ saddr=192.168.0.253
        borrow from A_up, C_up, D_up
        queue limits = 0 kb 150 packets
}

class B_down {
        bandwidth = 128 kbit/s
        ipv4 classifier inp_if=ppp+ daddr=192.168.0.253
        borrow from A_down, C_down, D_down
        queue limits = 0 kb 150 packets
}

class C_up {
        bandwidth = 32 kbit/s
        borrow from A_up, B_up, D_up
        ipv4 classifier out_if=ppp+ saddr=192.168.0.252
        queue limits = 0 kb 150 packets
}

class C_down {
        bandwidth = 128 kbit/s
        borrow from A_down, B_down, D_down
        ipv4 classifier inp_if=ppp+ daddr=192.168.0.252
        queue limits = 0 kb 150 packets
}

class D_up {
        bandwidth = 32 kbit/s
        borrow from A_up, B_up, C_up
        ipv4 classifier out_if=ppp+ saddr=192.168.0.251
        queue limits = 0 kb 150 packets
}

class D_down {
        bandwidth = 128 kbit/s
        borrow from A_down, B_down, C_down
        ipv4 classifier inp_if=ppp+ daddr=192.168.0.251
        queue limits = 0 kb 150 packets
}

class wrz_up {
	bandwidth = 4.0 kbyte/s
	ipv4 classifier out_if=ppp+ proto=tcp sport=80
	queue limits = 0 kb 20 packets
}

A class can steal some bandwidth from other classes with the "borrow from" 
directive, if the stolen class has been inactive for some time. This feature
is experimental, bandwidth assignment should be fair but it isn't, actually 
(try it!).

Note that, although it makes no sense to shape downstream traffic, it does
for protocols like tcp, because it'll shrink its congestion window in presence 
of network congestion (i.e. it will slow down the bit rate).

The order in which the classifiers are declared *does* matter. For example,

class bad_cfg {
        ipv4 classifier saddr=x.x.x.x # <- this one will pick every packet
                                      #    coming from x.x.x.x
        ipv4 classifier proto=udp saddr=x.x.x.x dport=domain # starving
        ipv4 classifier proto=tcp saddr=x.x.x.x dport=domain # same
        ipv4 classifier proto=tcp saddr=x.x.x.x dport=telnet # same
        # ...
}

Misc stuff
==========
- I've succesfully built and tested this thing using redhat 6.0, redhat 6.2,
debian 2.2r2, VA-6.2.4 (x86 only), debian 2.2r3 (x86, ppc). Kernels: 2.2.16, 
2.4.2, 2.4.3, 2.4.4, 2.4.5-pre1, 2.4.5, 2.4.8-powerpc-smp, 2.4.10-pre9. It 
has been reported to work on slack 7.1, 7.2.0-pre8.0 w/linux 2.2.19 (many 
thanks to Ben Bauer and Martin Nenov for the feedback).

- As of this first alpha-quality release, code isn't optimized at all, be it in
terms of speed of size. I've been using the STL, It has too many features that
I don't need, and code-size is a bit big because of it. I'll replace it with a 
custom library someday, but there are other priorities for the moment. I did 
all my testing so far on a 32 megs, 120-mhz pentium machine with 10 mbit (ne2k)
nics, and cpu load hasn't been an issue at all (but, the more complex config, 
the more cpu power you'll need). Anyway, this thing is *slow*, a quick measure
on my 120-mhz box revealed an average processing time of 300 us (cpu time) per 
packet.

- As i mentioned before, packet-selection/dispatching/shared-bandwidth 
allocation/congestion algorithms are *very* simple, this makes the shaper not 
as "fair" as I would like.

- If you change the system clock while shaperd is running, strange things 
may happen (shaperd it might also auto shutdown). There are a couple of 
workarounds for this (e.g. use the tsc for time tracking) ; maybe i fix 
this someday, but right now i have more "philosophical" stuff to solve (i.e.,
whether this project is a crap, a bloat, or both :-).

- This code is distributed under the GNU GPL license, it is free software, I 
wrote it on my spare time and I'm in no way responsible if it blows away some
very-maliciously-chosen machines in yer net. You have been warned!

Contact
=======

- homepage: http://www.wireless-open.com.ar/shaperd
- mirror: http://webs.sinectis.com.ar/lesanti/shaperd
- email: lsanti@fi.uba.ar

chao ...