FairQ ALTQ for PF - Patch #1

[Max Laier]

On Friday 04 April 2008 06:28:22 Matthew Dillon wrote:
>     Ok, This is my first attempt at adding a fairq feature to ALTQ/PF.
>     It isn't perfect yet, but it appears to work reasonably well.
>
> 	fetch http://apollo.backplane.com/DFlyMisc/fairq01.patch

There is a WFQ discipline for ALTQ: 
http://www.kame.net/dev/cvsweb2.cgi/kame/kame/sys/altq/ altq_wfq.{h,c}

It has never been integrated with pf, but I think using your approach of 
passing a hash in the pkthdr this should be rather straight forward.

>     It isn't hierarchical (at least not yet), but you can specify
> multiple queues for each interface as long as you give them different
> priorities.
>
>     Here is an example configuration:
>
> altq on vke0 fairq bandwidth 500Kb queue { normal, fair }
> queue fair priority 1 bandwidth 100Kb fairq(buckets 64) qlimit 50
> queue normal priority 2 bandwidth 400Kb fairq(buckets 64, default)
> qlimit 50
>
> pass out on vke0 inet proto tcp from any to any keep state queue normal
> pass out on vke0 inet proto tcp from any to 216.240.41.28 keep state
> queue fair
>
>     Here is how it works:
>
>     * The queues are scanned from highest priority to lowest priority.
>
>     * If the packet bandwidth on the queue does not exceed the
> bandwidth parameter and a packet is available, a packet will be chosen
> from that queue.
>
>     * If a packet is available but the queue has exceeded the specified
>       bandwidth, the next lower priority queue is scanned (and so
> forth).
>
>     * If NO lower priority queues either have packets or are all over
> the bandwidth limit, then a packet will be taken from the highest
> priority queue with a packet ready.
>
>     * Packet rate can exceed the queue bandwidth specification (but
>       will not exceed the interface bandwidth specification, of
> course), but under full saturation the average bandwidth for any given
> queue will be limited to the specified value.
>
>     Here is how the fair queueing works:
>
>     * You MUST specify 'keep state' in the related rules.
>
>     * keep state 'connections' will be given a fingerprint hash code
> which will be used to enqueue the mbuf in one of the N buckets (64 in
> our example) for each fair queue.
>
>     * When PF request's a packet from the fairq, a packet will be
> selected from each of the 64 buckets in a round-robin fashion.
>
>       Thus if you have a very hungy connection, it will not be able to
>       steal all the bandwidth (or queue up tons of packets to the
> actual interface) from other connections within the queue.
>
>     Caveats and issues:
>
>     (1) The qlimit is per-bucket.  So 64 buckets x 50 packets is, worst
> case, 3200 packets.  It's unlikely this would ever occur, but it's an
> issue that I haven't dealt with yet.
>
>     (2) Due to limitations on the number of buckets, multiple
> connections can end up in the same bucket.  If one of those connections
> is a heavy hitter, the others will suffer.
>
> 	This could probably be fixed with further sorting or perhaps a
> 	different topology (e.g. like a tree instead of a fixed array).
>
>     Please Test!  I have this running on my router box right now and
>     it appears to work very well.
>
> 						-Matt



-- 
/"\  Best regards,                      | mlaier at freebsd.org
\ /  Max Laier                          | ICQ #67774661
 X   http://pf4freebsd.love2party.net/  | mlaier at EFnet
/ \  ASCII Ribbon Campaign              | Against HTML Mail and News