ESFQ for Linux 2.6 NOTE: I do not intend to develop ESFQ any further. The SFQ patches I have made provide the same functionality and are (hopefully) cleaner and bug-free. ESFQ has a few bugs I know about (and a few I've forgotten). In fact, I just crashed my user-mode Linux while stress-testing the ESFQ patches. Please use the SFQ patches instead. You should have received them in the same tarball; look in the parent directory. Migration is easy: just change your scripts to use 'sfq' instead of 'esfq'--the syntax is the same. Also, if you want to compile SFQ and ESFQ at the same time, that's no problem. * the kernel ESFQ patch applies on top of the SFQ patch (with fuzz=2) * the iproute2 ESFQ patch applies on top of the SFQ patch ESFQ is the Enhanced Stochastic Fairness Queueing discipline. For current information on ESFQ, go to http://fatooh.org/esfq-2.6/ The ESFQ packages are named according to the current version of the Linux kernel. They may or may not work with earlier versions; I only test using the latest. If you find that the most recent ESFQ package available does not work with the newest kernel release, please send me an email. My address is bugfood-c [at] fatooh [dot] org. Note: If you use tcng instead of tc, there is a patch available at: http://devel.dob.sk/tcng+esfq/ The tcng patch is developed separately; if you have any tcng-specific feedback, direct it to the patch's author. =============INSTALLATION============= 1. Download the SFQ tar file from http://fatooh.org/esfq-2.6/ current: http://fatooh.org/esfq-2.6/sfq-2.6.24.tar.gz ESFQ is included in the SFQ tar. You should use SFQ instead! 2. Download iproute2 from http://linux-net.osdl.org/index.php/Iproute2 current: http://developer.osdl.org/dev/iproute2/download/iproute2-2.6.24-rc7.tar.gz 3. Download Linux 2.6 from http://www.kernel.org/ current: http://www.kernel.org/pub/linux/kernel/v2.6/linux-2.6.24.tar.bz2 4. Untar the files you downloaded, somewhere. Commands in the following instructions are examples; you'll have to modify them depending on where you untarred the files. 5. Patch the kernel with ESFQ. $ cd /usr/src/linux $ patch -p1 --dry-run < ~/esfq-2.6.24/esfq-kernel.patch (and, if it works...) $ patch -p1 < ~/esfq-2.6.24/esfq-kernel.patch 6. Prepare the kernel before including ESFQ. The conntrack hash types in ESFQ depend on Netfilter connection tracking. If you want to use them, you can use 'make menuconfig' to enable connection tracking in: Networking ---> Networking options ---> [ ] Network packet filtering framework (Netfilter) ---> Core Netfilter Configuration ---> < > Netfilter connection tracking support Layer 3 Independent Connection tracking 7. Configure the kernel to include ESFQ. a. The easiest way to enable ESFQ is use an old config file, if you have it. The config you use doesn't have to be from the same kernel version, but if it isn't you'll probably be asked other questions besides ESFQ. $ cd /usr/src/linux $ cp /boot/config-2.6.24 .config $ make oldconfig When you get to ESFQ, choose y, or m to use it as a module. If you don't get asked about ESFQ, see the "Note" above and/or follow step "b" below. b. If you want to use 'make menuconfig' instead, ESFQ is buried in: Networking ---> Networking options ---> QoS and/or fair queueing ---> < > ESFQ queue c. If you followed step 6 above, you will be able to select "Connection Tracking Hash Types" immediately below "ESFQ queue". 8. Compile and install the kernel as usual. You can reboot to the new kernel now if you want to. ESFQ will not work, though, until you compile a patched version of tc (in iproute2). 9. Patch the iproute2 package so tc can use ESFQ. cd /usr/local/src/iproute-2.6.24-rc7 patch -p1 --dry-run < ~/esfq-2.6.24/esfq-iproute2.patch (and, if it works...) patch -p1 < ~/esfq-2.6.24/esfq-iproute2.patch 10. Compile iproute2. $ make a. You don't necessarily have to install the entire patched version of iproute2 if you don't want to (perhaps you would rather keep your distribution's package). All you need is the tc binary. # cp -p tc/tc /sbin/tc-esfq # chown root:root /sbin/tc-esfq Just modify your scripts to use /sbin/tc-esfq instead of /sbin/tc. b. Otherwise, go ahead and install iproute2. $ make install 11. Reboot to your new kernel if you haven't already, and have fun! =============USAGE============== ... esfq [ perturb SECS ] [ quantum BYTES ] [ limit PKTS ] [ depth SLOTS ] [ divisor HASHBITS ] [ hash HASHTYPE] Where: HASHTYPE := { classic | src | dst | fwmark | ctorigdst | ctorigsrc | ctreplsrc | ctnatchg } Options: perturb SECS Default: 0 (no perturbation) SFQ and ESFQ don't actually allocate traffic to queues in a one-to-one manner; instead, they divide traffic among a large (but limited) number of hash slots. Sometimes the hashing algorithm results in a collision between two flows of traffic, resulting in them sharing a slot. Both flows have to fight over the bandwidth that slot is allocated. Setting perturb to some nonzero value causes the flows to be redistributed at an interval of that many seconds. There is no set method for choosing a perturb interval, though it is good to use one (see the description of hash collisions under 'divisor', below). A good perturb interval will redistribute flows frequently, but not so frequently that ESFQ spends a large proportion of the total time redistributing--during that time, ESFQ will not necessarily be fair. The worst case scenario for redistributing time is: time = limit * mtu / rate time: the length of time, in seconds, ESFQ will spend redistributing limit: the limit parameter given to ESFQ (default 128 packets) mtu: the interface's maximum transmission unit (probably 1500 bytes) rate: the interface's (or parent class') rate in bytes/sec quantum BYTES Default: 1 MTU-sized packet Recommended: default Amount of bytes a slot is allowed to dequeue before the next slot gets a turn. Do not set this to a value lower than the MTU! limit PKTS Default: equal to depth (default 128) Recommended: default The total number of packets that will be queued before packets start getting dropped. When ESFQ is saturated, a larger limit will result in slightly fewer packets being dropped, but packets will be queued for a longer time. In other words, you will get slightly better bandwidth at the expense of worse latency. Unless you have a reason to maximize bandwidth and don't care about latency, you should leave limit alone. For a flow that is sending packets as quickly as it can, the worst-case latency can be calculated as: time = rate / (limit * mtu) For a flow that sends a single packet when no other packets of that flow are queued, the worst-case latency is: time = rate / (flows * mtu) time: the latency in seconds rate: the interface's (or parent class') rate in bytes/sec limit: the limit parameter given to ESFQ (default 128 packets) flows: the number of concurrently active flows mtu: the interface's maximum transmission unit (probably 1500 bytes) Limit must be greater than or equal to depth; if the specified limit is lower than the specified depth, ESFQ will automatically set limit equal to depth. depth SLOTS Default: 128 Depth sets the number of slots. If the number of active flows is greater than the number of slots, flows will end up sharing slots and ESFQ will no longer be fair. If you anticipate more than 128 concurrently active flows, you should use a larger depth and probably a larger divisor (see below). If you expect there to be far fewer than 128 concurrent flows, you may want to use a lower depth in order to benefit from slightly better latency (because limit can then be lower as well). divisor HASHBITS Default: 10 Maximum: 14 Divisor sets the number of bits to use for the hash table. A larger hash table decreases the likelihood of collisions. When a collision occurs, two or more flows will end up sharing a slot, which isn't fair for either of those flows. The expected number of collisions can be calculated: flows - size + size * (1 - 1/size)^flows flows: the number of concurrent flows as determined by the chosen hash type size: the hash tables size, or 2^divisor There is very little disadvantage to using a large hash table--only slightly higher memory usage (tens of kilobytes). Unless your expected number of collisions is extremely small, you might as well use the maximum divisor. Regardless, setting a perturbation period will ensure that any collisions that do occur will not affect any flows for long. Note also that if the number of concurrent flows ever exceeds the specified depth (see above), flows will end up sharing slots regardless of the hash table size. hash HASHTYPE Default: classic The hash option determines the basis upon which ESFQ separates traffic into flows, and hence, on what basis bandwidth is fairly allocated. See below for descriptions of the available hash types. =============HASH TYPES============== classic This is original SFQ hash. Traffic is separated by connection according to source and destination IP and port (or protocol, for protocols that do not use ports). dst, src, fwmark Hash by the packet's destination IP, source IP, or iptables mark, respectively. Historically, these hash types were prone to collisions when hashing similar values. As of 2.6.19.2, the jhash algorithm is used, so collisions should be rare. See the "perturb" parameter. ctorigdst, ctorigsrc, ctrepldst, ctreplsrc These hash types use the original and reply address from IP conntrack, so they are useful when the router running ESFQ is also handling NAT/masquerade. Non-IPV4 packets, which don't have connection tracking information, are hashed based on "regular" source or destination. Note: netfilter connection tracking must be enabled in the kernel. Consider several workstations behind a router that uses SNAT or masquerade to change the source address of outgoing packets; on the router, the inside (LAN) interface is eth0 and the outside (WAN) interface is eth1. All packets leaving eth1 will have eth1's IP address, so hashing by source IP is useless. Instead, use ctorigsrc, which will correspond to the workstations' IPs. ctnatchg "Conntrack NAT change," for lack of a better name. This is a combination of ctorigsrc and ctreplsrc that is useful when a local host is configured to accept incoming connections (via DNAT "port forwarding"), but outgoing traffic must be shaped regardless of which host initiated the connection. In this situation, ctorigsrc and ctreplsrc could refer to either host, and, because the local host is NATted, src will always refer to the NAT router. Consider this example: local host = 10.0.0.2 NAT router = 1.2.3.4 remote host = 87.65.43.21 ctorigsrc = 10.0.0.2 ctorigdst = 87.65.43.21 ctreplsrc = 87.65.43.21 ctrepldst = 1.2.3.4 ctorigsrc = 87.65.43.21 ctorigdst = 1.2.3.4 ctreplsrc = 10.0.0.2 ctrepldst = 87.65.43.21 The logic for ctnatchg is simple. If ctorigdst == ctreplsrc, then the connection is outgoing, so hash by ctorigsrc. Otherwise, the connection is incoming, so hash by ctreplsrc. ==============EXAMPLES============= # Example 1: Set up ESFQ just like SFQ, as root for eth0. Note that "hash # classic" is the default. tc qdisc add dev eth0 root esfq perturb 10 # Example 2: Attach ESFQ to a parent class (such as HTB) and hash by destination # IP. Very useful if eth0 is on a LAN with bandwidth-consuming clients. # This example assumes you already have a classful qdisc set up. tc qdisc add dev eth0 parent 1:12 handle 12: esfq perturb 10 hash dst # Example 3: Like the example above, but for the WAN interface (eth1 instead of # eth0). This example is intended for usage on a NAT router, so it uses # ctnatchg instead of src). tc qdisc add dev eth1 parent 1:12 handle 12: esfq perturb 10 hash ctnatchg # Example 4: Hash by netfilter mark. Note that this won't do anything unless you # actually use iptables to add different marks to packets. tc qdisc add dev eth0 root esfq perturb 10 hash fwmark ========PROBLEMS/SOLUTIONS========= Problem: ESFQ doesn't seem to have an effect. Possible reason: SFQ and ESFQ work properly only when they can control which packets are dropped. If the bottleneck of a link is elsewhere, such as in a DSL modem, ESFQ will not drop any packets because the DSL modem is dropping enough packets that the link does not appear saturated. Diagnostic: Check the statistics for the orresponding qdisc with, for example, 'tc -s qdisc show dev eth1'. If the stats say "dropped 0", then that means ESFQ is not actually shaping any traffic. Solution: In order for ESFQ to control fairness, it must be attached either to a direct link (such as Ethernet) or to a classful, shaping qdisc (such as HTB). When a shaping qdisc is used, ESFQ's parent class must have a maximum rate less than or equal to the actual available bandwidth. See the HTB documentation for examples; ESFQ can be substituted for SFQ in HTB's examples. Problem: ESFQ isn't being very fair. Possible reason: ESFQ divides traffic into a number of smaller queues ("slots"), one for each flow. Flows are distinguished based on whatever aspect of the packets is hashed, such as source or destination. The maximum number of slots is set by the 'depth' parameter, which defaults to 128. If there are more active flows than slots, some flows will actually start sharing slots. Obviously, this is not good, and fairness will suffer. Diagnostic: Do you have more flows than slots? For example, if you have ESFQ set to hash by destination IP, is your number of concurrent downloaders higher than 128 (the default number of slots)? Solution: Set ESFQ to use a larger number of slots with the 'depth' parameter. Problem: I have ESFQ set to 'hash src', but it isn't doing anything. Possible reason: If ESFQ is on the WAN (Internet-side) interface of a router that uses NAT or masquerade, the source IP of outgoing packets will always be the IP of the router. Diagnostic: Are you using NAT or masquerade? Solution: Use 'hash ctorigsrc' or 'hash ctnatchg' instead of 'hash src'. Problem: RTNETLINK answers: No buffer space available Possible reason: You're using a depth value that is too high. ESFQ can't set a hard limit for depth because the maximum value depends on the size of an external structure. The only way is to try to allocate memory and see if it fails. Diagnostic: Does using a smaller depth value (such as the default) work? Solution: Use a smaller depth value. If you actually have a need for a larger depth than ESFQ can currently provide, send me a feature request. ================BUGS=============== Some known and some forgotten. Use my SFQ patches instead; see the top of this README. If you have any to report, send them to bugfood-c [at] fatooh [dot] org.