SFQ and ESFQ for Linux 2.6

ESFQ is the Enhanced Stochastic Fairness Queueing discipline. ESFQ is a modified version of the original SFQ which allows the user control over several originally hardcoded values. The most useful modification, for me, is the ability to change "hash type" so that ESFQ allocates bandwidth fairly per source IP rather than per connection.

ESFQ was originally created by Alexander Atanasov, and ported to Linux 2.6 by Alexander Clouter (and an anonymous flatmate). I have maintained the patch since then.

Recently, I have rewritten the ESFQ modifications on top of the original SFQ and prepared a new set of patches. The SFQ patches are cleaner and should have fewer bugs; please use them instead and report any problems (especially regressions) to me. See the download section below.

Current Status

I am currently in the process of trying to get ESFQ's functionality merged into SFQ in the main Linux kernel. I have created a patchset that adds all the new features except for the separate hash types and submitted the patches to the netdev mailing list. ...and resubmitted several times after fixing issues noticed in review.
Try 1
Try 2
Try 3
Try 4
Try 5

So far, I have not received any feedback about my latest round of patches, despite my prodding on netdev. I'm getting discouraged. By now, my patches are no longer up to date with the current net-2.6.25 git tree anyway, so I have to forward port them. Once I do, I'll re-send and try to get more input.

Meanwhile, I think it would be very good for my latest SFQ patches to get wider usage and testing. If you're currently using ESFQ, please download my SFQ patches (in the download section) and use them instead.

Patrick McHardy has submitted an alternate method of handling separate hash types; expect to see it in Linux 2.6.26, if I'm not mistaken.

Beware

I'm not really a kernel hacker and I don't know enough about the Linux kernel to actually understand all of how this patch works. So, if your packets don't come home tonight I might not be able to tell you why. On the other hand, SFQ still seems to be working all right, and a few other people have included my version in their own custom patchsets.

Instructions

Please see the current README file for instructions.

Downloads

You can view the individual files of the latest release here. Release packages are listed below.

--- current version ---
2008-02-09: sfq-2.6.24.1.tar.bz2 SFQ patches for Linux 2.6.24.1
This fixes an obvious typo that prevented usage of the conntrack hash types; somehow the fix didn't make it into my git tree after I tested it. If you don't use the conntrack hashes, you can ignore this release. If you're too lazy to re-patch, you can also fix this directly; within the kernel source, do:

$ sed -i s/ESFQ/SFQ/ net/sched/sch_sfq.c

--- old versions ---
2008-01-28: sfq-2.6.24.tar.bz2 SFQ patches for Linux 2.6.24
These patches apply on top of the original SFQ rather than creating a separate qdisc. They should be cleaner and bug-free. Please use them instead of ESFQ, which has known bugs. If you really want ESFQ, you can find ESFQ patches within the SFQ tarball. Futher infomation is at the top of the README.

2007-06-24: esfq-2.6.21.5.tar.gz ESFQ for Linux 2.6.21.5
This release fulfills a request that ESFQ not depend on netfilter connection tracking. The conntrack hash types are now configurable separately, so, if you use them, be sure to run 'make oldconfig' and choose Y for "Connection Tracking Hash Types". I've also added some better information to the README with respect to perturb, limit, depth, and divisor, including some equations for calculating the effects of those parameters.

2007-06-17: esfq-kernel-2.6.22-rc5.diff Incremental patch for Linux 2.6.22-rc5 (still works as of 2.6.23.1)
The 2.6.21.5 patch doesn't compile when applied to 2.6.22-rc5. This is an incremental patch, so apply it after the 2.6.21.5 patch. Once 2.6.22 is released and I make an "official" patch for it, this file will disappear.

2007-06-09: esfq-2.6.21.4.tar.gz ESFQ for Linux 2.6.21.4
I've cleaned up the patch to remove some duplicate code and make it, hopefully, adhere to kernel coding style. Meanwhile, I fixed a couple small bugs and added a new conntrack hash type. See the ChangeLog and the section in the README describing ctnatchg.

2007-05-20: esfq-2.6.21.1.tar.gz ESFQ for Linux 2.6.21.1
This release contains the final change I had wanted to make before trying to get ESFQ included in the kernel: rewriting esfq_change(). This means that you can now use tc to alter ESFQ's parameters without removing and reloading the qdisc. If I don't encounter any problems after this patch has been out for a while, then I'll start working toward submitting it upstream. See the TODO for a few details.

2007-02-16: esfq-2.6.20.tar.gz ESFQ for Linux 2.6.20
The ChangeLog is kind of long, but the highlight of this release is the ability to use source/destination addresses from Netfilter connection tracking as hash types, which lets ESFQ be fair to upstream traffic from users behind NAT (as long as the NAT router is the router running ESFQ, of course). See the README for instructions. Speaking of which, several parts of the README file are rewritten and/or extended.

2007-01-22: esfq-2.6.19.2.tar.gz ESFQ for Linux 2.6.19.2
ESFQ now uses jhash for classic, src, dst, and fwmark hash types. This means that hash collisions are no longer a problem for similar numbers (small network ranges, close fwmarks, etc). The src_direct, dst_direct, and fwmark_direct hash type hacks are no longer useful, and I intend to deprecate them in the next release. Send me an email if you have a reason I should leave the *_direct hash types alone.

2006-01-30: esfq-2.6.15.1.tar.gz ESFQ for Linux 2.6.15.1
This release has a couple bugfixes and a small update from SFQ. See the ChangeLog for details.

2005-11-02: esfq-2.6.14.tar.gz ESFQ for Linux 2.6.14
I proofread and updated the README a bit, but mostly this release is just to fix the iproute2 diff I messed up in the last one.

2005-10-23: esfq-2.6.13.tar.gz ESFQ for Linux 2.6.13
This release has a few new features. In brief, there is now hashing by fwmark and a new "direct" hashing method that eliminates collisions when the range of input values is smaller than the size of the hash table. See the expanded, updated README file; for information on the new features, scroll down to the "HASH TYPES" and "EXAMPLES" sections.

2005-03-31: esfq-2.6.12-rc1.tar.gz ESFQ for Linux 2.6.12-rc1
This version no longer interferes with the original SFQ; unlike previous versions, you can still use an unpatched tc with SFQ. Patching tc is still needed for ESFQ, though. I've tested this patch with Linux 2.6.11 as well.

2004-11-06: esfq-2.6.10-rc1.tar.gz ESFQ for Linux 2.6.10-rc1
Piotr Neuman (of the qnet patchset) send me a patch to support iproute2-2.6.9-041019. I also updated the kernel patch to 2.6.10-rc1, including synching with recent changes to sch_sfq.c.

2004-09-30: esfq-2.6.9-rc2.tar.gz ESFQ for Linux 2.6.9-rc2
No functional changes whatsoever this time. The README file referred to esfq-2.6.8.1_2.tar.gz, which never actually existed (it turned into esfq-2.6.9-rc1.tar.gz). Apparently somebody wouldn't take 404 for an answer and wanted the nonexistent ESFQ so badly that they ran a once-per-minute looping download script for six hours, quit, started again the next evening, and continued for over three hours until I fed them a bogus file. So, here's a new package with updated URLs in the README.

2004-09-08: esfq-2.6.9-rc1.tar.gz ESFQ for Linux 2.6.9-rc1
Although the kernel patch is functionally unchaged, this release is a big update in all other respects. See the ChangeLog for details. In short, I've included lots of help information, updated the iproute2 patch, and bundled the files together in a tar file.

2004-08-25: esfq-2.6.8.1_fixed.patch ESFQ for Linux 2.6.8.1
This doesn't have any functional changes from esfq-2.6.8-rc4.patch. I merely give credit to Alexander Clouter for the original 2.6 port (he certainly deserves it) and to myself (I might deserve it). Update: I goofed up when I made the first esfq-2.6.8.1.patch, so use this instead.

2004-08-12: esfq-2.6.8-rc4.patch ESFQ for Linux 2.6.8-rc4
With older ESFQ patches, 2.6.8-rc4 doesn't compile.

2004-08-02: esfq-2.6.8-rc2.patch ESFQ for Linux 2.6.8-rc2
This patch is actually no different from the previous patch (esfq-2.6.patch), except that the offset numbers are altered so it applies cleanly.

Old files

These are the original three files I released:
2004-03-10: esfq-2.6.patch.old ESFQ for 2.6 by Alexander Clouter, which I separated from the IMQ content.
2004-03-11: esfq-2.6.patch The same as above, but with updates based on sch_sfq.c
2004-03-12: esfq-2.6.patch.incr An incremental patch between esfq-2.6.patch.old and esfq-2.6.patch

Bugs

I don't know of any.

Bugreports

Please send bugreports (and patches) directly to me; I don't always have time to keep up with any related mailing lists. My address is bugfood-c [at] fatooh [dot] org, and I'll do what I can to help you out.

Links

Patchsets that use ESFQ

I culled these from my Apache logs. If you have a project I ought to list, tell me.

SFQ papers

These papers are listed near the top of sch_sfq.c.


2008-02-11
Corey Hickey, bugfood-c [at] fatooh [dot] org
other stuff