QFQ: Efficient Packet Scheduling with Tight Bandwidth Distribution Guarantees

Over time, there has been a significant amount of research on fast packet scheduling algorithms providing some form of delay or bandwidth distribution guarantees. A typical measure of the tightness of the guarantees provided by these schedulers is the maximum deviation between the service provided to each flow, and the service that the same flow would receive in an ideal, perfectly fair fluid system.

Current low complexity algorithms belong to three main families:

We have recently designed and developed an O(1) scheduler of the third family, called Quick Fair Queueing (QFQ). It provides tight service guarantees at an extremely low per-packet cost. A prototype running on a commodity PC takes about 110ns per packet, only twice the time consumed by a Deficit Round Robin scheduler, and about 2.5 to 4 times faster than the fastest competitor providing comparable guarantees.

A complete QFQ description, including proofs of the service guarantees and actual performance data, is presented in the following paper:

http://info.iet.unipi.it/~luigi/papers/20120309-qfq.pdf QFQ: Efficient Packet Scheduling with Tight Bandwidth Distribution Guarantees,
by F.Checconi, P. Valente, and L.Rizzo, March 2012 draft, to appear on IEEE/ACM Transactions on Networking
The experiments in the paper have been run using the following code:
Source code for a C implementation of QFQ, KPS and other schedulers measured in the paper.
QFQ is available in the new version of dummynet

Slides, talks and other resources

Luigi Rizzo (rizzo@iet.unipi.it)