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:
- Priority based schedulers. These algorithms are very simple, with
O(1) time complexity with respect to the number of competing flows,
but offer service guarantees only to the flows with the highest
priority. All other flows may suffer from starvation.
- Round Robin schedulers (of which several variants have been
defined). These schedulers also feature O(1) time complexity, and do
not suffer from starvation, but their deviation with respect to the
ideal service grows linearly with the number of flows.
- Approximated Fair Queueing schedulers. These schedulers have a
tight per-flow deviation with respect to the ideal service: the
heaviest component in this deviation is inversely proportional to
the flow's rate.
Though enjoying an O(1) time complexity, existing
schedulers of this family are expectedly several times more
expensive than Round Robin schedulers.
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)
ipfw3 and qfq; the qfq part starts near minute 36. This was
recorded at Google in Mountain View on March 29, 2010.