Packet Scheduling and QoS for Wireless Networks


Update! 21/09/04 - ipkg for OpenWRT based Linksys WRT54G Wireless routers now available on the downloads page.

Frottle (Freenet throttle) is an open source GNU GPL project to control traffic on wireless networks. Such control eliminates the common hidden-node effect even on large scale wireless networks. Frottle is currently only available for Linux wireless gateways using iptables firewalls, with plans to develop a windows client in the future.

Frottle works by scheduling the traffic of each client, using a master node to co-ordinate actions. This eliminates collisions, and prevents clients with stronger signals from receiving bandwidth bias.

Frottle has been developed and tested on the large community wireless network of WaFreeNet. We have found running frottle has given us a significant improvment in the network usability. Testing results will be documented here as time permits.


Operation

Frottle currently operates as a userspace application, receiveing outbound packets via the iptables QUEUE functionality. Access to the network is controlled by the frottle master, sending each client a control packet (token) which contains information about how much data can be sent at this time.

Each client receives its token and sends any required data, one at a time. This eliminates collisions, and with a reasonable signal packetloss is virtually zero. Also, since each client gets a limited slice of the bandwidth, everyone can get fair access regardless of their signal strength. Whilst this mechanism does result in increased latency, overall network performance and utilisation can significantly increase.

Additional Features

Traffic queues built in to frottle assign different, dynamic priorities to different traffic. Most traffic has a default priority. Traffic to/from specified ports (and ICMP packets) are made high priority. Traffic for connections that have done more than 2 MB of data and have a rate of more than 5 KB/s are made low priority. When a client is polled, high priority traffic is sent first, then default, then low until the poll quota is used.

Realtime info on each clients performance is available from the master in a html file and optionally at each client in a similar html file. (The names and locations of these files is set in /etc/frottle.conf.)

Independent user testemonial by SteveH:

"I have a poor connection to the access point. I have a low snr (varies from 7 to 11 dB) and rarely achieve better than a 2 Mb/s connection. When we were running without any form of QOS I was often struggling to achieve transfer rates of 3 kB/s. During testing of the current frottle I am able to get my share of bandwidth. My transfer rates now average 80 kB/s download and 35 kB/s upload. Peaks for these are about double this. The end result is a network which is usable and reliable."


WiCCP

WiCCP is another free traffic management package has similar goals to Frottle. We have also run WiCCP on our for a test period of several weeks on our network, with a developer participating in testing and providing updates. WiCCP is the only other project we could find that has similar goals to frottle. We wanted to compare WiCCP to Frottle so that we could use the better performing technology on our network.

Here is an extract from an email from Marcus that is a summary of the sort of results we saw:

"Now - in terms of performance comparison, Ive been monitoring my latency and packetloss to Hills Hub. Over the past few weeks (testing both WiCCP and frottle), my SNR has been terrible - between 4 to 6. This is a pretty extreme circumstance, but it has highlighted some differences:

WiCCP: avg packetloss ~ 15%, avg latency ~ 300ms frottle: avg packetloss ~ 6%, avg latency ~ 150ms

I have not tested throughput with frottle in these poor conditions, though throughput with WiCCP was reasonable. I can however see that total Hills Hub bandwidth usage was much higher with frottle:

WiCCP: peak (2 hour avg) downloads ~ 100kB/sec, uploads ~ 50kB/sec frottle: peak (2 hour avg) downloads ~ 250kB/sec, uploads ~ 180kB/sec
...
My 6% packetloss with frottle is due to VERY poor SNR ... it's an RF error. Without frottle/WiCCP, the packetloss in my poor conditions would be more like 90%.

Based on our observations, we will continue developing and using frottle on HillsHub, however keeping an eye on WiCCP and continuing to support their development/testing in any way we can. The above comments only relate to our environment, WiCCP may well be a better solution than frottle in other environments.


Downloads

Version 0.2.1 (30 July 2003)

OpenWRT Installation Instructions

An "itsy" package for OpenWRT based WRT54G routers has been kindly provided by Zombie, and can be downloaded from his webserver or the project download page. Installation instructions have been provided here.

With the help of OpenWRT, Quagga and Frottle, a cheap, versatile and highly functional freenet AP/Client/router can be built. This is especially usefull for people with Windows servers who are currently unable to run frottle.

Standard Installation Instructions

To compile frottle you will need iptables installed. You will also need the development IPQ library (part of iptables) installed. To do this download the correct iptables source tarball to match your installed iptables (if you didn't install from a tarball). Do the usual "make" ("make install" if starting from scratch) and then "make install-devel".

Once you have iptables and IPQ installed you can compile frottle using the standard "./configure", "make" and "make install" commands.

There is a 'feature' in iptables which may cause make to fail. If you get errors like:
/usr/include/net/if.h:45: parse error before `0x1'
/usr/include/net/if.h:111: redefinition of `struct ifmap'
etc

Then you need to edit /usr/include/linux/netfilter_ipv4/ip_queue.h and change "#include <net/if.h>" to "#include <linux/if.h>".


Client configuration

You will need to add some rules to your firewall (iptables) script. Assuming the wireless interface is eth1:

modprobe iptable_filter # load module
modprobe ip_queue # load module
iptables -A INPUT -p UDP --sport 999 -j ACCEPT # Allow control packets in
iptables -A OUTPUT -p UDP --dport 999 -j ACCEPT # Allow control packets out
iptables -A OUTPUT -p ALL -o eth1 -j QUEUE # where eth1 is the wireless interface
iptables -A FORWARD -p ALL -o eth1 -j QUEUE # where eth1 is the wireless interface

It is important that all outbound traffic (on the wireless interface) other than control packets are given the QUEUE target. Failure to do so will bypass frottle and contribute to collisions/performance problems. You may however add other rules to block unwanted outbound traffic.

To configure Frottle edit the file /etc/frottle.conf. There are comments in that file to help you. Then just run frottle from the command line, after first starting your firewall (see above).

A typical client frottle.conf will have entries something like this:

# Run in client mode
clientmode 1
# Daemonise, ie run in the background (optional)
# (Quit frottle with 'killall -TERM frottle' if you use this)

daemon 1
# The IP of the master
# (use the other end of your /30 to HH)

masterip 10.60.0.2
# Specify any ports you want to be high priority
# (This only effects your outgoing traffic)

hiports 22,53,7001,5223
# Set your wireless interface
winterface eth1
# If an http server is available,
# set a filename for a stats file output (optional)

statsfile /var/www/html/frottle.html

Master configuration

For the best performance, all wireless traffic must be controlled by the frottle master. This is achieved within WAFreeNet by running a server PC attached to the access point and having a /30 (255.255.255.252) route to each client. Any client traffic therefore passes from the client -> AP -> server, and back out if required to other clients.

(Note: do not forget to disable ICMP redirects, i.e. "/bin/echo "0" > /proc/sys/net/ipv4/conf/all/accept_redirects".)

The server PC is setup as a frottle master, and is able to regulate the flow of inbound packets (which cause the most collisions). The master also operates in a 'selfclient' mode where data being transmitted by the server (and effectivly all data being transmitted by the access point) is also regulated by frottle.

You will need to add the following to your firewall (iptables) script. These are similar to the client, except the UDP direction is reversed.

modprobe iptable_filter # load module
modprobe ip_queue # load module
iptables -A INPUT -p UDP --dport 999 -j ACCEPT # Allow control packets in
iptables -A OUTPUT -p UDP --sport 999 -j ACCEPT # Allow control packets out
iptables -A OUTPUT -p ALL -o eth1 -j QUEUE # where eth1 is the wireless interface
iptables -A FORWARD -p ALL -o eth1 -j QUEUE # where eth1 is the wireless interface

A typical master frottle.conf will have entries something like this:

# Run in master mode
mastermode 1
# Run as a self client as well
selfclient 1
# Daemonise, ie run in the background (optional)
# (Quit frottle with 'killall -TERM frottle' if you use this)

daemon 1
# Sepcify any ports you want to be high priority
# (This only effects your outgoing traffic)

hiports 22,53,7001,5223
# If a http server is available,
# set a filename for an info file output (optional)

infofile /var/www/html/frottle-master.html
# If a http server is available,
# set a filename for a stats file output (optional)

statsfile /var/www/html/frottle-stats.html

Polling parameters in the masters frottle.conf can be specified to fine tune the usage of bandwidth.

# Polling parameters
pollparams 60000,10,6000,7,5000,5,4000
# Time to wait for client response
timeout 100

The performance of the network can be seen from these parameters and the 'poll/sec' as displayed on the client stats page.

The polling cycle is basically the alternation of 'master sends data', 'master receives data' (from the next client) ad infinitum. The point is the master sends data to any client between each poll.

Based on the queuing priorities and high ports, pings (as is all ICMP) are always high priority. Therefore, when a client sends an echo request to the master, the echo reply will come back pretty quickly. The main delay is in the client waiting to be polled so that it can send the echo request. So therefore, if you are getting 8 polls/sec, your ping time can be anything up to (and just over) 125 mS depending when in the poll loop the echo request was queued.

The default polling parameters are currently "60000,10,6000,7,5000,5,4000". This breaks down as follows:
60000 the number of bytes the master (self-client) can send per poll loop. This number is divided by the number of clients and that much data can be sent between each poll
10,6000 the max number of packets, bytes that a client with a data rate of 5.5 Mb/s or over can send per poll
7,5000 the max number of packets, bytes that a client with a data rate of 2 Mb/s can send per poll
5,4000 the max number of packets, bytes that a client with a data rate of less than 1 Mb/s can send per poll

Therefore, if you have a 5.5 Mb/s connection and you are getting 6 polls/sec you are able to send at a raw data speed of (6 x 6000) 36,000 B/s (35.2 KB/s) in this scenario.

4 polls per second at the client is (near enough) 4 poll loops per sec, therefore the master will be able to send at a raw data speed of (4 x 60000) 240,000 B/s (234 KB/s) in this scenario.

One exception to this rule, is if a client still has packets queued after the completion of its poll sequence. In this case it will get an extra poll, resulting in twice the polls/sec than other clients and twice the data rate.

The polling parameters can be changed dynamically, and we have experimented with different settings. Reducing the byte limit per poll does increase the polls/sec and therefore reduce latency. However a larger percentage of the time is spent on frottle overheads and less actual data throughput is achieved. It would be simple to come up with different polling parameters for different usages (uploading vs downloading vs gaming, etc) and have a cron job make the changes at set times.


Feedback, questions, praise and gifts can be sent to the developer.

Credit is due to:
Marcus for the concept and proof of concept Perl program
ChrisK for developing the current C version of frottle
HillsHub connectees for their support in testing during development.
Zombie for the investigation, creation and documentation of the OpenWRT itsy package.
jas for coming up with such a catchy name.



SourceForge.net Logo