This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
IEEE/ACM TRANSACTIONS ON NETWORKING

1

QFQ: Efficient Packet SchedulingWith Tight Guarantees
Fabio Checconi, Luigi Rizzo, and Paolo Valente

Abstract—Packet scheduling, together with classification, is oneof the most expensive processing steps in systems providing tightbandwidth and delay guarantees at high packet rates. Schedulers
time complexity
with near-optimal service guarantees andhave been proposed in the past, using techniques such as timestamp
rounding and flow grouping to keep their execution time small.
However, even the two best proposals in this family have a perpacket cost component that is linear either in the number of groups
or in the length of the packet being transmitted. Furthermore, nostudies are available on the actual execution time of these algorithms. In this paper we make two contributions. First, we present
Quick Fair Queueing (QFQ), a newscheduler that provides
near-optimal guarantees and is the first to achieve that goal with atruly constant cost also with respect to the number of groups andthe packet length. The QFQ algorithm has no loops and uses very
simple instructions and data structures that contribute to its speedof operation. Second, we have developed production-quality implementations of QFQ and of its closest competitors, which we use topresent a detailed comparative performance analysis of the various
algorithms. Experiments show that QFQ fulfills our expectations,outperforming the other algorithms in the same class. In absoluteterms, even on a low-end workstation, QFQ takes about 110 ns foran enqueue()/dequeue() pair (only twice the time of DRR, but withmuch better service guarantees).
Index Terms—Algorithms, communication systems, computer
network performance, data structures, packet scheduling.

I. INTRODUCTIONIF AN outgoing link on a network node is fully utilized,
the only option to provide bandwidth or delay guarantees
on that link is enforcing a suitable packet scheduling policy.
Fine-grained per-flow guarantees can be provided with an
IntServ [12] approach, but this requires a reservation protocol(with well-known scalability problems) and imposes a nonnegligible load on packet classifiers and schedulers, who have todeal with a potentially large number of flows in progress (up to
10 according to [10]). Besides memory costs to keep per-flowstate, the time complexity and service guarantees of the scheduling algorithm can be a concern. DiffServ [12] “solves” thespace and time complexity problem by aggregating flows into
Manuscript received November 25, 2010; revised August 26, 2011 and March
10, 2012; accepted July 20, 2012; approved by IEEE/ACM TRANSACTIONS ON
NETWORKING Editor I. Keslassy.
F. Checconi was with Scuola Superiore Sant’Anna, Pisa 56127, Italy. He is
now with the IBM T. J. Watson Research Center, Yorktown Heights, NY 10598
USA (e-mail: fchecco@us.ibm.com).
L. Rizzo is with the Università di Pisa, Pisa 56122, Italy.
P. Valente is with the Università di Modena, Modena 41100, Italy.
Color versions of one or more of the figures in this paper are available online
at http://ieeexplore.ieee.org.
Digital Object Identifier 10.1109/TNET.2012.2215881

a few classes with predefined service levels and schedules theaggregate classes. Per-flow scheduling within each class may
still be needed to provide guarantees to individual flows.
The above considerations motivate the interest for packet
schedulers that, even in presence of a large number of flows,
can offer low complexity and tight guarantees.
Round Robin schedulers havetime complexity, butworst-case de(with the exception of FRR [24]) haveviation with respect to the ideal service that the flow should
receive over any given time interval.
More accurate schedulers have been proposed, implementing
schedapproximate versions of the worst-case optimaluler [2]. Thanks to flow grouping and timestamp rounding, firsttime complexity in the
introduced in [17], they feature
number of flows, and near-optimal deviation from the ideal service (WFI; see Section II). However, even the two most efficient proposals in this class, namely Group Fair Queueing(GFQ) [17] and Simple KPS (S-KPS) [9], as well as FRR [24],have some nonconstant components in their time complexity,
as discussed in Section II, and are significantly slower thanRound Robin schedulers. Section VII-C shows some performance comparison.
Our Contributions: In this paper, we first present Quick Fairtime comQueueing (QFQ), a new scheduler with truewithplexity, implementing an approximate version ofnear-optimal service guarantees. We then provide an extensive
comparison of the actual performance of production-quality implementations of QFQ and of several competing algorithms.
The key contribution of QFQ is the introduction of a novel
mechanism (Group Sets, Section IV-3), which removes thelinear component (in the number of groups or packet size)
schedulers. In QFQ, the flow groups
from previous quasiare partitioned into four sets, each represented by a machine
word and constructed so that all the bookkeeping required to
implement scheduling decisions can be done using simple andconstant-time CPU instructions such as AND, OR, XOR, andFind First bit Set1 (which we use to implement constant-timesearching).
The major improvement of QFQ over the previous proposals
is on performance: The algorithm has no loops, and the simplicity of the data structures and instructions involved makes itwell suited to hardware implementations. The execution time iswithin two times that of DRR, and consistently about three times
faster than S-KPS, across a wide variety of configurations andCPUs. Speed does not sacrifice service guarantees: The WFI of
1The Find First bit Set instruction (called ffs() or BSR) can locate in conclock cycles on
stant time the leftmost bit set in a machine word. It uses
modern CPUs such as Intel Core 2, Core i7, or Athlon K10.

1063-6692/$31.00 © 2012 IEEE

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
2

IEEE/ACM TRANSACTIONS ON NETWORKINGQFQ is slightly better than S-KPS and close to the theoreticalminimum.
Paper Structure: Section II complements this introduction by
discussing related work. In Section III, we define the systemmodel and other terms used in the rest of the paper. Section IV
presents the QFQ algorithm in detail and illustrates its implementation. The correctness of the properties used in QFQ isthen proved in Section V. Section VI gives an analytical evaluation of the (worst-case) service guarantees. In Section VII-A, we
present the results of some ns2 simulations to compare the delay
experienced by various traffic patterns under different scheduling policies. Finally, Section VII-B measures the actual performance of the algorithm on a real machine, comparing production-quality implementations of QFQ, S-KPS, and of otherschedulers (FIFO, DRR, and WF2Q ).
II. BACKGROUND AND RELATED WORK
Packet schedulers can be classified based on their service
properties and time/space complexity. Relevant problem dimensions are the number of flows, , and the maximum size of
packets in the system. The service metrics defined in the literature try to measure, in various dimensions, the differences
between the scheduler under analysis and an ideal fluid systemthat implements perfect bandwidth distribution over any timeinterval.
Two important service metrics are the Bit- and Time-Worstcase Fair Index (B-WFI and T-WFI [2], [3]). B-WFI (definedin Section VI-A) represents the worst-case deviation, in terms ofservice, that a flow may experience over any time interval withrespect to a perfect weighted bandwidth sharing server during
the same interval. T-WFI , defined in Section VI-B, expresses
similar deviations in terms of time. From the WFIs, it is easy
to compute the minimum bandwidth and the worst-case packet
completion times guaranteed for a flow. However, the WFIs indicate more than just worst-case packet delays or per-flow lag(the difference between the service received in an ideal, perfectly fair system and the one received in the actual system).
The WFIs capture the fact that an actual scheduler may serve
some packets much earlier than the ideal system, and this may
result in long intervals during which a flow receives no service
to compensate for that received in advance. This may not affectthe lag, but causes extreme burstiness in service, which has bad
effects on protocols and applications (e.g., TCP’s rate adaptation) as well as on per-flow lag and delay guarantees in a hierarchical setting [2].
In contrast, the WFIs do not measure another important
service property: how fairly a scheduler distributes the excess
bandwidth when not all the flows are backlogged. This property
can be measured with an early metric, called relative fairness
in [8] and proportional fairness in [24], which is equal to theworst-case difference between the normalized service (service
divided by the flow’s weight) given to any two backlogged
flows over any time interval [16].
Round Robin Schedulers: Round Robin (RR) schedulers
and variants (Deficit Round Robin [15]) are the usual choice
when fast schedulers are needed. They lend naturally to
implementations with small constants. Several variants havebeen proposed (Smoothed Round Robin [6] and G-3 [7],Aliquem [11], and Stratified Round Robin [13]) to mitigate
some of their shortcomings (burstiness, etc.). Nevertheless, forall but one of the schedulers in this family, and irrespective of
the weightof any flow , both the flow’s packet delay andthe B-WFI have an
component.2
FRR [24] differs from other RR proposals in that, similarly
to QFQ, it divides flows into groups and schedules packets in
two phases: First, an extended version of[3] schedulesgroups; following that, an extended version of DRR [15] schedules flows within groups. In FRR, a flow belongs to groupsuch that, whereis the flow’s weight.3 isan integer constant that can be freely chosen to set the desired
tradeoff between runtime complexity and service guarantees. As
shown by its authors in [24, Theorem 4], FRR has , whereis the number of groups,isthe minimum bandwidth guaranteed to flow , and is the linkrate. The time complexity is. T-WFI grows with ,and in the best case, with weights ranging between
10 and 1, we would haveand hence, much higher than the of
QFQ.
Exact Timestamp-Based Schedulers: To achieve a lower WFIthan what is possible with RR schedulers, other, modern scheduler families try to serve flows as close as possible (i.e., not
too late and not too early) to the service provided by an internally tracked ideal system, using a concept called eligibility. We
call them timestamp-based schedulers as they typically timestamp packets with some kind of Virtual Time function and try toserve them in ascending timestamp order, which has an inherent
complexity [23]. This bound is matched by some actual algorithms [21].
With this approach, schedulers such as[3] and[2] offer optimal lag, packet delay, and WFI, i.e.,they achieve the lowest possible values for a nonpreemptive
system. In particular, their lag and B-WFI are bothwithvery small constants (see Section VI-A), much better than theof most RR schedulers.
Fast Timestamp-Based Schedulers: Breaking the theoreticalbound requires the use of approximate timestamps
to reduce the complexity of the sorting steps. Some schedulers(such as GFQ, S-KPS, and LFVC) use this approach to achievecomplexity with respect to the number of flows, while
preserving
B-WFI.
GFQ [17] uses variable timestamp rounding, splits flows into
groups, and relies on a calendar queue to sort flows within
the same group. Its complexity is. S-KPS [9] uses a data
structure called Interleaved Stratified Timer Wheels (ISTW) to
execute packet enqueue and dequeue operations at a worst-casecost independent of even the number of groups, though it requires
bookkeeping steps during packet transmissions.
Finally, LFVC [20] rounds timestamps to multiples of a fixed
constant, relying on van Emde Boas priority queues for sorting(hencecomplexity). Unfortunately, LFVC has a
2Such worst case behavior is easy to achieve in practice (e.g., with a few highweight flows and a large number of low-weight flows). In these circumstances,the high-weight flows will experience a very bursty service, with unpleasanteffects for downstream devices and applications.
3QFQ also defines groups of flows, but using a different formula, (4).

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
CHECCONI et al.: QFQ: EFFICIENT PACKET SCHEDULING WITH TIGHT GUARANTEESTABLE I
DEFINITIONS OF THE SYMBOLS USED IN THE PAPER

3

between the flows and the link: Arriving packets are immediately enqueued, and the next packet to serve is chosen and dequeued by the scheduler when the link is ready. The interfaceof the scheduler to the rest of the system is made of one packet
enqueue() and one packet dequeue() function.
In our model, each flow is assigned a fixed weight.
Without losing generality, we assume that.4
A flow is defined as backlogged/idle if it owns/does not own
packets not yet completely transmitted. We callthe set offlows backlogged at time . Inside the system, each flow uses a
first-in–first-out (FIFO) queue to hold the flow’s own backlog.
We call head packet of a flow the packet at the head of thequeue, andits length;
when a flow is idle. We saythat a flow is receiving service if one of its packets is beingtransmitted. Both the amount of service
received bya flow and the total amount of service
delivered by
the system in the time interval
are measured in numberof bits transmitted during the interval.
A.

worst-case complexity of
because the algorithm maintains separate queues for eligible and ineligible flows, and individual events may require to move up toflows from one
queue to the other.
The use of approximate timestamps has an implication,
proved in [23]: Any scheduler based on approximate timestamps has a packet delay with respect to an ideal GPS serverlarger than
. Fortunately, the B-WFI bounds are notaffected: GFQ, S-KPS, and our QFQ guarantee the sameas the optimal schedulers, differing only in the multiplying constant, which is 1 with exact timestamps and slightly
larger otherwise (e.g., 3 in the case of QFQ; see Section VI-B).
Thus, approximate timestamps still give much better guarantees
than RR schedulers.
We should note that the data structures used in the various
schedulers differ largely, so that low asymptotic complexity
does not necessarily reflect in faster execution times, especiallywith a small number of flows. Also, there may be dependencies on other parameters, (e.g., GFQ or S-KPS) or worst-casebehaviors significantly larger than average (e.g., LFVC).
III. SYSTEM MODEL AND DEFINITIONSIn this section, we give some definitions commonly used in
the scheduling literature, and then present the exact
algorithm, which is used as a reference to describe QFQ. For
convenience, all symbols used in the paper are listed in Table I.
Most quantities are a function of time, but we omit the timeargument
when not ambiguous and clear from the context.
We consider a system in whichpacket flows (defined inwhatever meaningful way) share a common transmission link
serving one packet at a time. The link has a time-varying rate.
A system is called work-conserving if the link is used at full
capacity whenever there are packets queued. A scheduler sits

Here, we outline the originalalgorithm for avariable-rate system (see [2] and [18] for a complete description).
is a packet scheduler that approximates, on apacket-by-packet basis, the service provided by a work-conserving ideal fluid system that delivers the following, almost
perfect bandwidth distribution over any time interval:(1)
The packet and the fluid system serve the same flows and de(systems with theseliver the same total amount of workfeatures are called corresponding in the literature). They differ
in that the fluid system may serve multiple packets in parallel,
whereas the packet system has to serve one packet at a timeand is nonpreemptive. Because of these constraints, the allocation of work to the individual flows may differ in the twosystems.
has optimal B-/T-WFI andcomplexity, which makes it of practical interest.
operates as follows. Each time the link is ready,the scheduler starts to serve, among the packets that have already started5 in the ideal fluid system, the next one that would
be completed in the fluid system; ties are arbitrarily broken.
is a work-conserving online algorithm, hence it succeeds in finishing packets in the same order as the ideal fluid
system, except when the next packet to serve arrives after one
or more out-of-order packets have already started.
Virtual Times: The
policy is efficiently implemented by considering, for each flow, a special flow virtual timefunctionthat grows as the normalized amount of service
received by the flow (i.e., actual service received, divided by
the flow’s weight). In addition, when the flow turns from idle tobacklogged,is set to the maximum between its current
value and the value of a further function, the system virtualtime, defined below. For each flow , the value of
4The implementation of QFQ does not rely on this assumption, and it tracks
the actual sum of weights as flows come and go, thus providing tighter guarantees to the backlogged flows.
5This property, called “eligibility, ” is fundamental in providing small WFI.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
4

IEEE/ACM TRANSACTIONS ON NETWORKING

needs to be known (hence computed) only on the following
events: 1) when the flow becomes backlogged, or 2) when its
head packet completes transmission in the ideal fluid system.
The resulting values of, called flow’s virtual start andfinish time,and, are used to timestamp the flow itself
and are computed as
on newly backlogged flowon packet dequeue
(2)
where
is the time when a packet enqueue/dequeue occurs.
is the system virtual time function defined as follows (assuming):(3)
Note thatis only computed at discrete times, so the instantaneous link rate does not need to be known, and just(the amount of data transferred in) suffices. At systemstartup,, and.
Eligibility: Flow is said to be eligible at time if.
This inequality guarantees that the head packet of the flow has
already started to be served in the ideal fluid system. Using thisdefinition,
can be implemented as follows:
Each time the link is ready, the scheduler selects fortransmission the head packet of the eligible flow withthe smallest virtual finish time.
Note that the second argument of theoperator in (3) guarantees that the system is work-conserving.
The time complexity incomes from three tasks:
1) computing
from (3), which requires to track the minimum
and hascost; 2) selecting the next flow toserve among the eligible ones, which requires tracking the minimum
among eligible flows, and also hascost ateach step; 3) updating eligible flows as
grows. Any change
incan render
flows eligible, and it takes some cleverdata structure [19] to avoid an
cost.

Fig. 1. QFQ at a glance. The figure represents all main data structures used by
the algorithm. The four groups sets on the top (see Section IV-3) are stored ina bitmap by index number. The groups (rectangles on the bottom; see SectionIV-1) contain the bucket lists and individual flow queues.

In practice, the number of distinct groups is less than 64(32 groups suffice in many cases),6 so a set of groups can be
represented by a bitmap in a single machine word.
We define(bits) as the slot size of the group. Since, from (2) we havefor any
flow in group .
2) Timestamp Rounding: Same as other timestamp-basedschedulers, QFQ labels flow with both exact and approximate
virtual times. The exact values [and, (2)] are used toprovide guarantees.7 The approximate values are defined as(5)(where is the group index) and are used to compute eligibility
and scheduling order. Note that, whichhas useful implications on the runtime and service guaranteesof the algorithm.
For each group, QFQ defines(6)

IV. QUICK FAIR QUEUEINGIn this section, we describe QFQ. For ease of exposition, theproperties requiring long proofs are demonstrated separately in
Section V. The scheduler uses the data structure represented inFig. 1 and relies on three techniques (Flow Grouping, Timestamp Rounding, Group Sets) to perform all computations intime.
1) Flow Grouping: Each flow (one of the squares at thebottom of Fig. 1) is statically mapped into one of a finite numberof groups (the regions at the bottom of the figure). The groupis chosen as(4)
is the maximum size of the packets for flow .
whereis related to the service guarantees given to a flow, so flows withsimilar guarantees are grouped together.

called the group’s virtual start and finish times.
within the definition of the virtual time
QFQ replaces
function(7)
It is easy to show that thein the equation can be calculated as the minimum
among the backlogged groups in thesystem. Same as in (3), at system startup,
and.
6This is trivially proven by substituting values in (4); as an example,
between 1 and 10 yield values between
tween 64 and 16 kB,
and, or 29 groups.

be-7There is one case where thefor certain newly backlogged groups can be; this exception is describedshifted backwards to preserve the ordering ofand its correctness is proved in Lemma 4.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
CHECCONI et al.: QFQ: EFFICIENT PACKET SCHEDULING WITH TIGHT GUARANTEES

5

1)

Fig. 2. Representation of bucket lists. The number of buckets (gray, each corresponding to a possible value of) is fixed and independent of the numberof flows in the group.

Finally, note that network interfaces operate on apacket-by-packet basis and do not export a real-time indication of the amount of service provided. To deal with thisissue, QFQ computes
based on a simple approximation of
the exact amount of service: It assumes that
immediately
increments each time a packet is dequeued and updates
accordingly (Section IV–A2).
Timestamp Properties:
andcan only assume a limited
range of values around( andhave a similar property called Globally Bounded Timestamp or GBT [17]). We canprove (see Theorems 1 and 2 in Section V) that at all times,.
Furthermore,is quantized and can only assume
distinct values (remember that, so the second term
is bounded by the ratio between the min and max packet sizein the system). The small number of possible values permits
sorting within a group using a constant-time bucket sort algorithm, implemented using a bucket list (Fig. 2), a short arraywith as many buckets as the number of distinct values for .
Each bucket contains a FIFO list of all the flows with the sameand
. For practical purposes, 64 buckets are largely sufficient, so once again each bucket can be mapped to a bit in amachine word, and a constant-time Find First bit Set instruction
can be used to locate the first nonempty bucket, which contains
the next flow to serve.
The use ofin (7) also saves another sorting step because,
as we will see, the group sets defined in the next section let us
compute (7) in constant time.
3) Group Sets and Their Properties: QFQ partitions backlogged groups into four distinct sets (the top rows in Fig. 1).
As will be shown in Section IV-A, this reduces scheduling andbookkeeping operations to simple set manipulations, in turn performed with basic CPU instructions such as AND, OR, and FFS
on single machine words.
The sets are called
and(from the initials of
Eligible, Ineligible, Ready, and Blocked), and the partitioning isdone using two properties.
• Eligible: Group is Eligible at time iff. Thegroup is Ineligible otherwise.
• Blocked: iIndependent of its own eligibility, a group is
Blocked if there is some eligible group with higher index
and lower finish time. Otherwise, the group is Ready.
The “blocked” property is used to partition groups so that withineach set the group index reflects the ordering by finish time:. In particular, the following
properties hold.

is sorted by as a result of the GBT property. In
fact, if a group is ineligible, any flow in the group has. Due to the rounding, we can only
have
, and if
, we have
,
hence
.
2)
is also sorted bybecause of the sorting by
and the fact that ’s are increasing with .
3)
is sorted by , as proven in Theorem 4 (Section V).
4)
is sorted by , as proven in Theorem 5 (Section V).
Hence, the group with the smallest timestamp in a set can belocated with an FFS instruction.
Managing Sets: A group can enter any of the four sets when it
becomes backlogged or after it is served. After serving a group,
QFQ may need to move one or more other groups from one set
to another, but only on the paths

because the transitions of a group from ineligible to eligible(driven by the increase of) and from blocked to ready(driven by the increase of theof the group that was blocking
group ) are not reversible until group itself is served.
Moving multiple groups from one set to another requires
comparing groups’ timestamps with a threshold and affects allgroups above or below the threshold. Again, this is done withbasic CPU instructions (AND, OR, NOT) without iteratingover the sets because the ordering by finish time holds for
all the four sets, andis sorted by bothand .
Thus, once the index of the first matching group is known (seeSection IV-A.3), all other matching groups are on the same sideof the set.
A. Quick Fair Queueing: The Algorithm
We are now ready to describe the details of the QFQ
algorithm.
1) Packet Enqueue: Function enqueue(), shown in Fig. 3, iscalled on the arrival of a packet.
As a first step, the packet is appended to the flow’s queue,
and nothing else needs to be done if the flow is already backlogged. Otherwise, the flow’s timestamps are updated (lines 7
and 8), and line 10 checks whether the group’s state needs tobe updated. This happens if the group was idle, or if the newflow causes the group’s timestamp to decrease (in this case, thegroup was ineligible: line 7 implies, the second test
in line 10 succeeds if, hence). The update is done by lines 11–17, which possibly remove the groupfrom the ineligible sets (lines 13 and 14) and update the group’s
timestamps (being the slot size , the start time calculation only
needs to clear the last bits of , line 15).
Once the group’s timestamps are set, a constant-timebucket insert (line 18) sorts the flow with respect to the otherflows in the group. At this point, if needed,
is updated
according to (2). Finally, function compute_group_state()(Section IV-A.3/Fig. 5) computes the new state of the group(which may have changed because of the new values of,and), and line 27 puts the group in its new set.
Note that an enqueue does not move other groups across sets:
Their eligibility remains the same (changes only if all other

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
6

IEEE/ACM TRANSACTIONS ON NETWORKING

Fig. 3. enqueue() function, called on packet arrivals, andcompute_group_state() that implements the tests for eligibility andreadiness.

groups are idle); blocked/ready states also remain unchanged,
though for less intuitive reasons.8
2) Packet Dequeue: Function dequeue() in Fig. 4 is called toreturn the next packet to send.
The packet selection (lines 2–8) is straightforward. If there
are queued flows, at least one flow is eligible, so
is notempty: A first FFS instruction (line 6) picks the group with thelowest index in, then another FFS is used to locate the firstflow in the bucket list (line 7), and the head packet from thatflow is the next packet to serve.
Before returning, the function updates the scheduler’s data
structures in preparation for further work. The flow’s timestamps are updated, and the flow is possibly reinserted in thebucket list (lines 10–16). Virtual time is increased in line 19
to reflect the service of the packet selected for transmission.
Next (lines 21–28), the group’s timestamps and state are updated. If the group has increased its finish time or it has become
8If the new packet belongs to an already backlogged flow, its group does notchange its finish time, so the readiness of others cannot be affected. Otherwise,
the group containing flow just became backlogged, or its finish time de, hence. Any Readycreased. However,will have(one comes from the uppergroup). Hence,bound on , the other two come from the definition of. By definition,, soand thenewly backlogged group cannot block a previously Ready group, even in theworst case (largest possible , smallest possible ).

Fig. 4. dequeue() function, described in Section IV-A.2.

idle (lines 32–36), it is moved to the new set, and function unblock_groups() described in Section IV-A.3 possibly unblocks
other groups.
Finally, lines 38–45 make sure that at least one backloggedgroup is eligible by bumping up
if necessary and moving
groups between sets using function make_eligible(), which will
be discussed next.
3) Support Functions: Fig. 5 documents the remaining support functions, mostly used in the dequeue() code.
Function move_groups() uses simple bit operations to movegroups with indexes in mask from set src to set dest.
Function make_eligible() determines which groups become
eligible as
grows after serving a flow. The properties ofrounded timestamps are used to implement the check in constant time. The algorithm is explained with the help of Fig. 6,
which gives a graphical representation of the possible values of’s and, and the binary representations of(the vertical strings of binary digits). Since slot sizes are powers of two, the binary representation of the timestamps of theth group’s ends withzeros; in any given slot belonging togroup , the value of the th bit is constant during the whole slot.
Whenever the th bit ofchanges, the virtual time enters aThis article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
CHECCONI et al.: QFQ: EFFICIENT PACKET SCHEDULING WITH TIGHT GUARANTEES

Fig. 5. Functions to manage group sets after a flow has been served (seeSection IV-A.2).

7

and finding the minimum timestamps, require constant time. Allarithmetic operations can be done using fixed-point computations, including the division by the flow weight (for efficiency,
divisions are implemented as multiplications by the inverse of
the weight).
Note that while the algorithm has been described assuming, the actual implementation supports arbitraryvalues for , replacing line 19 of the dequeue function with. Changes in are tracked in real time
as flows come and go: New flows increase immediately (thisdoes not violate guarantees), while dead flows are expired lazily,
using the technique shown in [22].
In terms of space, the per-flow overhead is approximately 24
B (two timestamps, weight, group index, and one pointer). Eachgroup contains a variable number of buckets (32 in the worst
case, requiring one pointer each), plus two timestamps and abitmap. Finally, the main data structure contains five bitmaps,
the sum of weights, and a timestamp. Overall, even a large configuration will require 4 kB of memory to hold the entire stateof the scheduler.
QFQ has very good memory locality. On each enqueue()or dequeue() request, the algorithm only touches the internal
memory (the 4 kB mentioned above) and the descriptor of thesingle flow involved in the operation. This is very beneficial
both for software and hardware implementations.
V. PROOFS OF THE PROPERTIES USED IN QFQFig. 6. Tracking group eligibility. On the transition of V from old_V to new_V;
the highest bit that flips across the transition is the second one, so groups zeroand one are the candidates to become eligible (see Section IV-A.3).

new slot of size 2 . As a consequence, on each
update, thehighest bit that changes inindicates that all backloggedgroupsare now eligible.
This is exactly the algorithm implemented by function
make_eligible(): It computes the index using a XOR followed
by a Find Last Set (FLS) operation, then computes the binary
mask of all indexes
and calls function move_groups tomove groups whose index is in the mask from
to
and
from
to
.
Function unblock_groups() updates the set of blocked groups.
When the group under service increases its finish time or becomes idle, some groups
blocked by might become
ready, i.e., do not violate anymore the ordering of.
Theorem 6 in Section V proves which groups can be unblocked;
line 21 verifies the preconditions, and lines 25–26 move groupstoandas needed.
B. Time and Space Complexity
time comFrom the listings, it is clear that QFQ has
plexity on packet arrivals and departures: The algorithm has noloops, and all operations, including insertion in the bucket list

In this section, we prove the properties used in Section IV.
The proofs are complete, but slightly condensed due to spaceconstraints. All symbols are defined in Table I, and quantities
are computed as described in the QFQ algorithm.
Hereafter, we explicitly indicate the time at which any timestamp is computed to avoid ambiguity. Given a generic function of time
, we define. For notational convenience, we avoid writing
ifis continuous at time . To further simplify the notation, if the function
is discontinuous at a time instant , we assume, without losing
generality, that
, i.e., that the function isleft-continuous.
We define the following two notations for convenience:

For any positive quantity, we have(8), withIn fact, can be written as, thenthe thesis holds; if, then, and the thesis holds as well.

. If
, and

A. Group GBT Under QFQ
We start by proving per-group upper bounds for(Theorem 1) and for(Theorem 2, supported by
the two long Lemmas 1 and 2). The two bounds represent agroup-based variant of the GBT property, normally defined forThis article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
8

IEEE/ACM TRANSACTIONS ON NETWORKING

the flow timestamps in an exact virtual-time-based scheduler.
We will use these bounds to prove both the properties of the data
structure and the B/T-WFI of QFQ. Lemmas 1 and 2 are adapted
versions of the ones in [9], repeated here for convenience andwith permission from the author.
Theorem 1: Upper bound for. For any backlogged group and(9)
Proof: By definition (5), at any time and for any groupis an integer multiple of and, for any backlogged flowof the group,. It follows that, if, then (9) trivially holds. Hence, to prove (9),we actually prove the latter inequality, i.e., that, and to prove it we consider only a generic time instantat which a generic packet for flow is enqueued/dequeued, as
this is the only event upon which
may increase.
According to (2), either, in which case thepacket is enqueued and the thesis trivially holds, or. In this case, flow must have had a packet previously
dequeued at time.
When the packet was dequeued atflow was certainly
eligible, andis immediately incremented after the dequeueat , so we have
, whichproves the thesis.
Lemma 1: Let
be asubset of flows. Given a constant
we have(10)is the size of the first packet in the queue for flowwhere
at time .
Proof: By definition,. Thus, forflows in set, we have. Therefore,

the positive component
is removed from thesum. In both subcases, the lemma holds. The remaining caseis if
. Since, this implies. In this case,is incremented by , but
is incremented by, so the left-hand side of (11)remains unchanged and the lemma holds.
Virtual Time Jump: After a virtual time jump, all backlogged
flows have
. With regard to theidle flows, we assume that their virtual start and finish times arepushed to. By doing so, we do not lose generality, as thevirtual start times of these flows will be lower-bounded bywhen they become backlogged (again). Besides, it is easy to seethat pushing up their virtual finish times may only let the left sideof (11) decrease. In the end,
for all flows, andif, then Lemma 1 applies and the lemma holds.
For otherin, the additional term in(11) absorbs any decrement on the right-hand side. Therefore,
the lemma holds.
Packet Dequeue: Flow receives service at time
for its
head packet of size
. We have to distinguish two cases,
depending on
and.
Case 1).
is incremented, and hence theright side of (11) decreases, exactly by. Withregard to the left side, the variation of
canbe seen as the result of first decreasing by,which balances the above decrement of, andthen increasing by, which is in turn balanced
by incrementingby. Hence, the lemma
holds for this case.
Case 2). In this case all flows
have, so they must have been ineligible according to their rounded start time, otherwise the current flow would have not been chosen.
Therefore,
for all flowsin. Lemma 1 applies then for all, i.e.,. This implies, wherethe last passage uses
Lemma 2: Let
flows. Given a constant(12).
be a set of, we have that

Becausewith
Therefore

and we assume
after service, we only need to consider
before service.

(11)
Proof: The proof is by induction over those events thatchange the terms in (11): packet enqueues for idle flows, packet
dequeues, and virtual time jumps. The base case whereisempty is true by assumption. For the inductive proof, we assume (11) to hold at some time .
Packet Enqueue for an Idle Flow: Say a packet of sizeof the idle flow arrives at time .
does not change on
packet arrivals except for virtual time jumps, which are dealt
with later. If after the enqueue of the new packet,i.e.,, we must consider two subcases. First, if, nothing changes. Second, if,(13)
and the lemma holds after service also in this case,thus completing the proof.
Theorem 2: Upper bound for
For any backlogged group(14)
Proof: To prove the thesis, we will actually prove, by contradiction, the more general inequalityfora generic flow of group . The only event that could lead to aThis article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
CHECCONI et al.: QFQ: EFFICIENT PACKET SCHEDULING WITH TIGHT GUARANTEES

violation of the assumption is serving a packet. Assume that at
the lemma holds. A packet with roundedfinish timeand length is served, and afterwards at time
, there is a packet with finish time , suchthat
. Denote withandthe corresponding
start times. We need to distinguish three cases.
Case 1) Packet is eligible at time according to its roundedstart time. Then,(both packets were eligible atand was chosen). Applying Lemma 2
withandresults in

9time of the group decreases. We have thatfor
any backlogged group with.
to decrease,must decrease as well.
Proof: For
According to the enqueue() and dequeue(), this can happen onlyin consequence of the enqueueing of a packet of an empty flowof the group. As this is exactly the same event that may cause agroup to become backlogged, then, from (2), we haveboth if the group becomes backlogged and if
decreases. Substituting this inequality, which finally holds also
if the group becomes eligible at time , and (9) in the following
difference we get:(15)
Because, the second term on the left
side of the inequality is nonnegative, and therefore.
Case 2) Packet is not eligible at according to its roundedstart time, but becomes eligible between
and .
Then,
. Virtual time advances by at most ,and therefore.
Case 3) Packet is not eligible according to its rounded start
time after service to , therefore
is reached bya virtual time jump before can be served. In thiscase,
. This concludes theproof.
B. Proofs of the Data Structure Properties
We can now prove the ordering properties of group sets, considering the two events that can change the set membership:packet enqueue and packet dequeue. We start by proving thefollowing theorem, which bounds the number of possible timestamps within a group.
Theorem 3: At all times, only the first
consecutive
slots beginning from the head slot of a group may be non empty.
Proof: Consider a generic flow belonging to a group .
A new virtual start time may be assigned to the flow (only) as
a consequence of the enqueueing/dequeueing of a new packet
at a time instant . As in the proof of Theorem 1, from (2)may be equal to either: 1), or 2), whereifis the first packet of the flow to
we assume
be enqueued/dequeued.
In the first case, according to (14),. In the,second case, neglecting the trivial subcase
we can consider that flow had to be a head flow when
was served. Hence, according to (5),.
From (2), this implies.
Considering both cases, it follows that,, which proves the thesis.
Using the following lemma, we want now to prove thatis ordered by virtual finish times.
Lemma 3: Let be the time instant at which a previously idle
group becomes backlogged, or at which the group, previously
ineligible, becomes eligible, or finally at which the virtual finish(16)
and the last inequality follows
where.
from that, as
The following theorem guarantees thatis always orderedby virtual finish times.
Theorem 4: Set
is ordered by group virtual finish time.
Proof: We will prove the thesis by induction. In the basecase
, the thesis trivially holds. The ordering of
may change only when one or more groups enter the set. Thiscan happen as a consequence of: 1) a group entering
as it
becomes backlogged; 2) one or more groups moving fromto; 3) one or more groups moving fromto. Let
be a group entering
at time for one of the above threereasons, and let the thesis hold before time .
is not lower thanIn the first case, thanks to Lemma 3;
the virtual finish times of the groups inwith lower index.
By definition ofis also not higher than the virtualwith higher index.
finish times of the groups in
In the second case, given a groupwithbecause either group was already in
before time , or group belonged to, which is orderedby virtual start times according to Section IV-3, item 2. Thisimplies
because. By definition ofis also not higher than the virtual finish times of thegroups inwith higher index.
In the third case, since group is not blocked anymore,is not higher than the virtual finish times of the groups inwith higher index. With regard to the groups with lower index
than , for group to be blocked before time , there had to bewithand. Since wea groupassume thatis ordered by virtual finish time before time ,then, and hence
is not lower than the virtual finish.
times of all the lower index groups in
To prove thatenjoys the same order property as, weneed first a further lemma. The validity of the lemma depends on
the timestamp back-shifting performed by QFQ when insertinga newly backlogged group into
. Hence, this is the right place
to explain in detail this operation.
When an idle group becomes blocked after enqueueing apacket of a flow at time , the timestamps of flow are not
updated using the following variant of (2):(17)

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
10

IEEE/ACM TRANSACTIONS ON NETWORKING

where is the lowest-order group insuch that. Basically, with respect to the exact formula,is used insteadif. This is done because otherwise theofordering by virtual finish time in
may be broken. It would beeasy to show that this would happen if an idle group becomesblocked whenis too much higher than the virtual finish
time of some other blocked group.
With regard to worst-case service guarantees, in casein (17), group just benefits from the
back-shifting, whereas the guarantees of the other flows areunaffected. To prove it, consider that the guarantees provided
to any flow do not depend on the actual arrival time of thepackets of the other flows. Hence, one can still “move” a pairof timestamps backwards, provided that this does not leadto an inconsistent schedule, i.e., provided that the resulting
worst-case schedule for all the flows is the same as if the packet
had actually arrived at a time instant such that the would have
got exactly those timestamps without using any back-shifting.
This is what happens using (17), for the following reason.
Should the packet that lets group become backlogged havearrived at a time instantat which,group would have however got a virtual finish time higher
than. Hence, group should not have been served before
group , exactly as it happens in the schedule resulting fromtimestamping group with (17) at time .
We can now introduce the intermediate lemma we need to
finally prove the ordering in.
Lemma 4: If a pair of groups and withare blocked.
at a generic time instant , then
Proof: We consider two alternative cases. The first is thathas been last updated at a time instantusing(17). The second is that, according to (2) and (5), there are atleast one head flow of group and a time instant
such
that
.
, where is the
In the first case, we havelowest-order group insuch that. We can consider
two subcases. First, group is already backlogged and eligible, then. Otherat time . It follows that, if
wise, from the definition of , group is necessarily blocked,
andmust hold again for group not to be
blocked. In the end, regardless of whether group is ready or
blocked,, and the thesis
holds. In the other subcase, i.e., group is not ready and eligible
at time , thanks to Lemma 3, group cannot happen to havea virtual finish time lower thanduring. Hence,.
, we prove theIn the other case, i.e.,thesis by contradiction. Suppose that
. Flow
must have necessarily been served withat
to hold,some time. In addition, for, and hence
should hold aswell. As flow had to be a head flow at time , it would follow
that
(18)
We consider two cases.
,
First, group is backlogged at time . If
thenbecause. Hence, both group and would be eligible,and group could not be served at time . It follows thatshould hold. This inequality and (18) would. Should
not decrease during, the absurd
would follow. However,from enqueue() and dequeue(), it follows that the only eventthat can let
decrease is the enqueueing of a packet of an
to decrease (lines 12–18
idle flow of group that causesof enqueue). Let
be the minimum value thatmay
assume in consequence of this event.
Since, according to (2), (5), and(18),, which again would.
imply the absurd
The second case is that group is not backlogged at time .
As the event that would let the group become backlogged aftertimeis the same that might have letdecrease in theother case, then, using the same arguments as above, we would
get the same absurd.
In the end,
must hold.
The following theorem guarantees thatis always ordered, thisby virtual finish time (hence, as previously proven fororder is never broken during QFQ operations).
Theorem 5: Set
is ordered by group virtual finish time.
Proof: We will prove the thesis by induction. In the basecase
, the thesis trivially holds. The only event uponwhich the ordering of
may change is when one or moregroups enter the set. The three events that may cause a group to
become blocked are:1) the enqueueing/dequeueing of a packet
of a flow of an idle group, which lets group get a lower
virtual finish time than group (groups with lower order thancan never block group ); 2) the enqueueing/dequeueing of apacket of a flow of group itself, which lets the virtual finish
time of group become higher than the virtual finish of somehigher-order group; 3) the growth of, which causes one ormore groups to move fromto.
With regard to the first event, it is worth noting that group
can cause group to become blocked only if group becomesbacklogged or if
decreases. Let be the time instant at
is orwhich one of these two events occurs and such thatdered up to time . Thanks to Lemma 3,, andhence the event cannot let group become blocked.
as a conSuppose now that, at time , group enterssequence of either a packet of a flow of the group being enqueued/dequeued or the growth of. We will prove that,andgiven any two blocked groups
andhold (whereincase group entersfrom).
, if group enters
With regard to a blocked groupas a consequence of a packet enqueue/dequeue, then from
Lemma 4 and the fact that, as
is an integer multiple of, we have
imply

(19)
. On the otherwhere the last inequality follows fromfrom, thenhand, if group entersbecause either group was already eligible before time , orgroup belonged to, which is ordered by virtual start time
according to Section IV-3, item 2. This implies
because.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
CHECCONI et al.: QFQ: EFFICIENT PACKET SCHEDULING WITH TIGHT GUARANTEESWith regard to a blocked group, let
be thehighest-order group that is blocking group at time . Indepen, from Lemma 4 we
dently of the reason why group enters
have
(20)
where the last inequality follows fromfact that bothandare integer multiples of(20), we haveand the. Using, i.e.,(21)

because, since.
Finally, we can prove the theorem that allows QFQ to quickly
choose the groups to move from
to.
Theorem 6: Group unblocking. Let be the group that would
be served on the next packet dequeue at time , and assume that
there is no group; in this case, if groupis actually served and, or if group becomesidle at time , then all and only the groups in/
and withorder lower than must be moved into
/ .
Proof: To prove the thesis, we first prove that group is
the only group that can block a group. The proof is bycontradiction. Suppose for a moment that a group
blocksmust hold for group not togroup . Since
be blocked, and bothandare integer multiples of, then. Combining this inequality with, and hence, considering
Lemma 4, we getthat. This contradicts the fact that group blocks group .
increases, then, thanks to (19) andAs a consequence, if(21), all and only the blocked groups
become ready. The
same happens if group becomes idle as a consequence of apacket dequeue.

11

IMPORTANT NOTE: Flow belongs to group , sovaries between
andand the is always bounded
by a small multiple of the packet size, same as for other near-optimal schedulers. In addition, Theorem 1, as well as the theorems
and lemmas on which it depends, are proven without ever using
the link rate. Hence, this theorem holds also for time-varying
link rates.
Proof: In this proof, we express timestamps (,etc.) as functions of time to avoid ambiguities. We consider twocases. The first one is when flow is eligible at time . In thiscase, as for the virtual timeof flow in the real system,
consider that, andtrivially
hold. In addition,
as proven in Theorem 2,then. Hence, we have(24)
The last inequality follows from the fact that, because of theimmediate increment of
as a packet is dequeued (seeupdateV()),. To complete theproof for this case, consider that, forto comply with
the immediate increment of, alsomust increment
immediately each time a packet of flow is dequeued. Should
andhave been computed exactly, then, by definitionofwould have held. In contrast, the fact that
immediately increments also implies
that
holds. Substituting (24)in the latter inequality, we get(25)

VI. SERVICE GUARANTEES
Service guarantees are an important parameter of any scheduling algorithm. In this section, we compute various service
metrics for QFQ: in particular, we will derive two bit guarantees—the B-WFI and relative fairness—and one time guarantee—the T-WFI.

The other case is when flow is not eligible at time . Thisimplies thatis exactly equal to. Hence, considering thatand exploiting the same properties used in the derivations for the other case, we have

A. Bit Guarantees
The –guaranteed to a flow-

is defined as9
(22)

where
is any time interval during which the flow is continuously backlogged;is the minimum amount ofservice the flow should have received according to its share of
the link bandwidth; andis the actual amount of service provided by the scheduler to the flow.
Theorem 7: B-WFI for QFQ. For a flow belonging togroup , QFQ guarantees-(23)

9This definition is slightly more general than the original one in [2], where
was constrained to the completion time of a packet.

(26)

Comparison to Other Schedulers: In a perfectly fair ideal
fluid system such as the GPS server, (see [2]),whereas repeating the same passages of the proof in case ofexact timestamps (i.e., exact
with stepwise), theresulting would be.
The B-WFIs for S-KPS and GFQ have not been computedby their authors. However, both these algorithms and QFQ implement the same policy, differing only in how they
approximate the timestamps. Generalizing the previous proof,
we can show that GFQ has a slightly lower -This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
12

IEEE/ACM TRANSACTIONS ON NETWORKING, whereas S-KPS has .
Relative Fairness: The relative fairness bound, RFB, is defined as the maximum difference, over any time interval
and pair of flows and , between the normalized service given
to two continuosly backlogged flows(27)
Consider two flows,
and , belonging, respectively, togroups and , and continuously backlogged during a timeinterval. Equation (6), Theorem 2, and the fact that agroup is served only if eligible, give an upper bound to thenormalized service received by a flow in the interval, resultingin. The proof of Theorem 7
establishes a lower bound for the normalized service. Substituting these two extremes in (27) and taking the maximum overall possible flow/group pairs, we have(28)
As for GFQ and S-KPS, we haveand. To put the bound for FRR in a form that allows it to becompared more easily against the bound for QFQ, we assume
that all packets have the same length (otherwise
may
be higher), and get(in the best case for FRR, i.e., for).
B. Time Guarantees
Expressing the service guarantees in terms of time is only
guaranteed to apossible if the link rate is known. The flow on a link with constant rate is defined as-(29)

where and are, respectively, the arrival and completion timeof a packet, andis the backlog of flow just after thearrival of the packet.
Theorem 8: T-WFI for QFQ. For a flow belonging togroup , QFQ guarantees-(30)

The proof, omitted for brevity, is conceptually similar to theone for the B-WFI. Here again, note that the factor(orequivalent) is present in the T-WFI of any near-optimal scheduler. For comparison, a perfectly fair ideal fluid system would
have , whereas for, which uses exact
timestamps, repeating the same passages of the proof yields.
Same as for the B-WFI, the T-WFI of S-KPS happens to beequal to that of QFQ, whereas the T-WFI of GFQ is lower thanthat of QFQ by. Finally, about FRR, as already shown in
Section II, the T-WFI of FRR in a realistic scenario is not lower
than.

Fig. 7. Simulated scenario. Flowsandare originated by nodes
and, whereas
generates 50 CBR flows to perturbate the traffic. All routers run
the same scheduling algorithm.

VII. EXPERIMENTAL RESULTS
We evaluate the performance of QFQ by comparing its service properties and actual run times to those of other schedulingalgorithms. Due to space limitations, we only report a subset
of our experimental results. The algorithms selected for the experiments presented here are DRR, to represent the class ofhigh-performance round-robin schedulers;, as a reference point for its optimal service properties; and S-KPS, asan example of high-efficiency timestamp-based scheduler.
The experiments cover two aspects: service properties areevaluated by running experiments with NS on a simulated
topology and measuring end-to-end delays and their variations;absolute performance is evaluated by measuring actual run
times of production-quality code, i.e., code that includes allfeatures needed in an actual deployment, such as support for
dynamic flow creation and destruction, and exception handling.
These features are normally neglected in prototype implementations, but are necessary in a realistic test as their support may
impose significant overhead to the run times.
A. Evaluation of Service Properties
To prove the effectiveness of the service properties guaranteed by QFQ, we implemented it in the ns2 simulator [1], andwe compared it to DRR, S-KPS, and.
The network topology used in the simulations is inspired by
the one used in [7] and is depicted in Fig. 7. Links
andhave 10 Mb/s bandwidth and 10 ms propagation delay;
all the other links have 100 Mb/s and 1 ms. The observed flows
are (a 32-kb/s CBR fromto), and (a 512-kb/s CBRfromto). Interfering flows are a 512-kb/s CBR fromto(same as ), 50 160-kb/s CBR flows fromto, andtwo best-effort flows, one fromtoand one fromto, each generated from its own Pareto source with mean on
and off times of 100 ms,, and mean rate of 2 Mb/s(larger than the unallocated bandwidth of the links between therouters, in order to saturate their queues).
Table II shows the end-to-end delays (average, stddev andmaximum) experienced by and during the last 15 s of simulation (the total simulation time was 20 s; the first five were notconsidered to let the values settle). QFQ performs as expected,
with delays similar to the ones measured for S-KPS, given thecommon nature that the two schedulers share. DRR shows muchlarger delays and deviations, which is also expected because of
the inherent
WFI of this family of schedulers.
The “max” value for the low bandwidth flows is in good accordance with the WFI values computed in Section VI: The

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
CHECCONI et al.: QFQ: EFFICIENT PACKET SCHEDULING WITH TIGHT GUARANTEES

Fig. 8. Our testing environment: A controller drives the scheduler module with
programmable sequences of requests.

TABLE IISIMULATION RESULTS FOR THE TOPOLOGY OF FIG. 7. END-TO-END DELAYS(AVERAGE/STDDEV, MAX) IN MILLISECONDS FOR THE OBSERVED FLOWS

delay component inversely proportional to the flow’s rate isbest forand grows as we move to QFQ, S-KPS, andDRR. The larger standard deviation of the delays in QFQ and
S-KPS, compared tocomes from the use of approximate timestamps, which gives QFQ and S-KPS a WFI larger
than that of. Also note how the effect of approximations is higher for(a low rate flow) than for , which is ahigh rate flow.
B. Run-Time Performance
Together with the good service guarantees, the most interesting feature of QFQ is the constant (independent of thenumber of flows) and small per-packet execution time, whichmakes the algorithm extremely practical.
To study the actual performance of our algorithm, and compare it to other alternatives, we have measured the C versions of
QFQ and various other schedulers, including S-KPS, which we
implemented as part of the Dummynet [4] traffic shaper, running on FreeBSD, Linux, and Windows.
We have performed a thorough performance analysis by running the schedulers in the environment shown in Fig. 8, where
we could precisely control the sequence of enqueue/dequeue requests presented to the schedulers. The controller lets us decide
the number and distribution of flow weights and packet sizes,
as well as keep track of the number of backlogged flows andthe total amount of traffic queued in the scheduler. These parameters may impact the behavior of the schedulers, by influencing the code paths taken by the algorithms, and the memory
usage and access patterns. The latter are extremely important on
modern CPUs, where cached and noncached access times differ
by one order of magnitude or more.
In the next section, we report experimental results for the
average enqueue() dequeue() times (including generation anddisposal by the controller) in different operating conditions(number and distribution of flows, queue size occupation). Oneof the configurations (the “NONE” case) only measures thecontroller’s costs, so we can determine, by difference, the time
consumed by the scheduler.
This test setup does not allow us to separate the cost of enqueue() and dequeue() operations, but the problem is not relevant. First, in the steady state, there is approximately the same

13

number of calls for the two functions. Only when a link is severely overloaded, the number of enqueue() will be much larger
than its counterpart, but in this case dropping a packet (in theenqueue()) is very inexpensive. Second, in most algorithms it ispossible to move some operations between enqueue() and dequeue(), so it is really the sum of the two costs that counts tojudge the overall performance of an algorithm.
Test Cases: Our tests include the following algorithms.
NONE

The baseline case, measures the cost of
packet generation and disposal, including
memory-touching operations. Packets generated
by the controller are stored in a FIFO queue andextracted when the controller calls dequeue().
FIFO
The simplest possible scheduler, an unbounded
FIFO queue. Compared to the baseline case, here
we exercise the scheduler’s API, which causes one
extra function calls and counter updates on eachrequest.
DRR
The Deficit Round Robin scheduler, where eachflow has a configurable quantum size.
QFQ
QFQ, as described in this paper. We use 19 groups,
packet sizes up to 2 kB, and weights between 1
and 2 .
S-KPS
Our implementation from the description in [9],with some minor optimizations, and revised by
the original authors. Internal parameters (e.g.,) have been set to values similar to thoseused for QFQ.
WF2Q
The
algorithm taken from the FreeBSD’s
dummynet code. It has
scaling
properties, but it is of interest to determine thebreakeven point between schedulers with different
asymptotical behavior.
Flow Distributions: We ran extensive tests with different combinations and numbers of flows (from 1 to 128 K), with various weight and packet size distributions. These configurations
show how the schedulers depend on the number of flows, trafficclasses, and also their sensitivity to memory access times.
Load Conditions: To emulate different load conditions for thelink, we generate requests for the scheduler with three patterns:
SMALL and LARGE generate bursts of
andpackets,
respectively (where is the number of active flows), and thencompletely drain the scheduler; FULL keeps the scheduler
constantly busy, with a total backlog between
andpackets. The bursty patterns try to reproduce operation on anormally unloaded link, whereas the FULL pattern mimics the
behavior of a fully loaded link driven by TCP or otherwise
adaptive flows, which modify their offered load depending on
available bandwidth.
C. Results
Table III and Fig. 9 report some of the most significant test results, measured on a low-end desktop machine (2.1 GHz CPU,
32-bit OS, 667 MHz memory bandwidth), with code compiled
with gcc -O3. Different platforms perform proportionally to theplatform’s performance (e.g., a 3-GHz Nehalem CPU is almost
twice as fast; a 200-MHz MIPS CPU on a low-cost Access Point

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
14

Fig. 9. Scaling properties of the various algorithms.
, reaching 2000 ns for 32 K flows (see Table III).

IEEE/ACM TRANSACTIONS ON NETWORKING

grows asTABLE IIISUBSET OF EXPERIMENTAL RESULTS, FOR DIFFERENT FLOW DISTRIBUTIONS
AND LOAD CONDITIONS

misses start to matter. S-KPS also has reasonably good performance, taking approximately 500 ns (times the cost of
QFQ).
Finally, we would like to note that while
has obvious scalability issues, it can still be a viable alternative for
configurations with a small number of flows.
The final block of the table reports the result of experimentswith a large mix of flows using different weights. This case does
not show significant differences with the case where all flows
have the same parameters.
Table III, Fig. 9, and other experiments not reported here
show that algorithms can have peculiar behaviors in certain
conditions. As an example, QFQ takes a modest performance
hit when there is only one flow backlogged. This happens because, in the dequeue code, the removal of the flow from thegroup leaves the group empty and triggers unnecessary calls
to unblock_groups() and make_eligible(). S-KPS seems to haveslightly better performance in the presence of small bursts, presumably due to similar reasons (certain code paths becoming
more frequent). DRR takes a performance hit when the packet
size is not matched with the quantum size, as certain packets
require two rounds instead of one to be processed. These variations tend to be small in absolute and relative terms, but aremeasurable as we are dealing with extremely fast algorithms
where even small changes in the instruction counts affect theperformance.
QFQ is a significant step toward the feasibility of software
packet processing on 10-Gb/s links. At these speeds, the perpacket budget varies between 67.2 and 1230 ns per packet (for64- and 1518-B frames). QFQ’s speed (100–150 ns/pkt) fits
well in the budget, together with recent results on fast packet
I/O [14].
VIII. CONCLUSION

is 30–40 times slower in running the same experiments). Similarly, the point where cache effects become visible varies depending on available cache sizes.
Fig. 9 shows clearly that the performance of allalgorithms does not depend on the number of flows (except for the
impact of cache misses), whereas WF2Q shows the expectedbehavior. We see that DRR and FIFO are extremely
fast, with most of the time in the test consumed by the packet
generator (the curve labeled NONE in the figure), which accounts for approximately 60 ns per enqueue/dequeue pair. Allschedulers, and the generator itself, show a modest increase of
the execution time as the number of flows goes (on this particular platform) above 4 K. This is likely due to the working setof the algorithm overflowing the available cache, which causes
cache misses that impact on the total execution time. In absoluteterms, QFQ behaves really well, consuming about 100–110 ns(excluding the traffic generation) up to the point where cache

In this paper, we presented QFQ, an approximate implementation ofthat can run in true constant time, with very
low constants and using extremely simple data structures. The
algorithm is based on very simple instructions and uses verysmall and localized data structures, which make it amenable to a
hardware implementation. Together with a detailed descriptionof the algorithm, we provide a theoretical analysis of its service properties and present an accurate performance analysis,comparing QFQ to a variety of other schedulers. The experimental results show that QFQ lives up to its promises: It is fasterthan other schedulers with optimal service guarantees, only twotimes slower than DRR, and operates, even in software, at a ratecompatible with 10-Gb/s interfaces.
QFQ and the other algorithms analyzed here are available
at [5] as well as part of standard distributions of FreeBSD andLinux and are included in the Dummynet [4] traffic shaper/network emulator for FreeBSD, Linux, and Windows.
REFERENCES[1] “The network simulator—ns-2,” 2012 [Online]. Available:
http://www.isi.edu/nsnam/ns/[2] J. C. R. Bennet and H. Zhang, “Hierarchical packet fair queueing algorithms,” IEEE/ACM Trans. Netw., vol. 5, no. 5, pp. 675–689, Oct.
1997.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
CHECCONI et al.: QFQ: EFFICIENT PACKET SCHEDULING WITH TIGHT GUARANTEES[3] J. C. R. Bennett and H. Zhang, “WF Q: Worst-case fair weighted fairqueueing,” in Proc. IEEE INFOCOM, Mar. 1996, pp. 120–128.
[4] M. Carbone and L. Rizzo, “Dummynet revisited,” Comput. Commun.
Rev., vol. 40, no. 2, pp. 12–20, 2010.
[5] F. Checconi, P. Valente, and L. Rizzo, “QFQ: Efficient packet scheduling with tight bandwidth distribution guarantees (full paper andexperimental code),” 2012 [Online]. Available: http://info.iet.unipi.it/~luigi/qfq/[6] C. Guo, “SRR: An O(1) time complexity packet scheduler for flows in
multi-service packet networks,” in Proc. ACM SIGCOMM, Aug. 2001,
pp. 211–222.
time complexity packet scheduler that provides[7] C. Guo, “G-3: Anbounded end-to-end delay,” in Proc. IEEE INFOCOMM, May 2007,
pp. 1109–1117.
approximation with small constant[8] M. Karsten, “SI-WF Q:
execution overhead,” in Proc. IEEE INFOCOM, Apr. 2006, pp. 1–12.
[9] M. Karsten, “Approximation of generalized processor sharing withstratified interleaved timer wheels,” IEEE/ACM Trans. Netw., vol. 18,
no. 3, pp. 708–721, Jun. 2010.
[10] A. Kortebi, L. Muscariello, S. Oueslati, and J. Roberts, “Evaluating
the number of active flows in a scheduler realizing fair statistical bandwidth sharing,” Perform. Eval. Rev., vol. 33, no. 1, pp. 217–228, 2005.
[11] L. Lenzini, E. Mingozzi, and G. Stea, “Tradeoffs between low complexity, low latency, and fairness with deficit round-robin schedulers,”
IEEE/ACM Trans. Netw., vol. 12, no. 4, pp. 681–693, Aug. 2004.
[12] L. L. Peterson and B. S. Davie, Computer Networks—A Systems Approach. San Mateo, CA: Morgan Kaufmann, 2010.
[13] S. Ramabhadran and J. Pasquale, “The stratified round robin scheduler:
Design, analysis and implementation,” IEEE/ACM Trans. Netw., vol.
14, no. 6, pp. 1362–1373, Dec. 2006.
[14] L. Rizzo, “Revisiting network I/O APIs: The netmap framework,”
Commun. ACM, vol. 55, no. 3, pp. 45–51, Mar. 2012.
[15] M. Shreedhar and G. Varghese, “Efficient fair queuing using deficit
round robin,” IEEE/ACM Trans. Netw., vol. 4, no. 3, pp. 375–385, Jun.
1996.
[16] S. J. Golestani, “A self-clocked fair queueing scheme for broadband
applications,” in Proc. IEEE INFOCOM, Jun. 1994, pp. 636–646.
[17] D. C. Stephens, J. C. R. Bennett, and H. Zhang, “Implementing
scheduling algorithms in high-speed networks,” IEEE J. Sel. Areas
Commun., vol. 17, no. 6, pp. 1145–1158, Jun. 1999.
[18] D. Stiliadis and A. Varma, “A general methodology for designing efficient traffic scheduling and shaping algorithms,” in Proc. IEEE INFOCOM, Apr. 1997, pp. 326–335.
[19] I. Stoica and H. Abdel-Wahab, “Earliest eligible virtual deadline first:
A flexible and accurate mechanism for proportional share resource allocation,” Department of Computer Science, Old Dominion University,
Norfolk, VA, Tech. Rep. 95-22, Nov. 1995.
[20] S. Suri, G. Varghese, and G. Chandranmenon, “Leap forward virtual clock: A new fair queuing scheme with guaranteed delays andthroughput fairness,” in Proc. IEEE INFOCOM, Apr. 1997, pp.
557–565.

15[21] P. Valente, “Exact GPS simulation and optimal fair scheduling withlogarithmic complexity,” IEEE/ACM Trans. Netw., vol. 15, no. 6, pp.
1454–1466, Dec. 2007.
to support a dynamic traffic mix,” in[22] P. Valente, “Extending
Proc. AAA-IDEA, Jun. 2005, pp. 26–33.
[23] J. Xu and R. J. Lipton, “On fundamental tradeoffs between delay
bounds and computational complexity in packet scheduling algorithms,” IEEE/ACM Trans. Netw., vol. 13, no. 1, pp. 15–28, Feb. 2005.
[24] X. Yuan and Z. Duan, “Fair round-robin: A low complexity packet
scheduler with proportional and worst-case fairness,” IEEE Trans.
Comput., vol. 58, no. 3, pp. 365–379, Mar. 2009.
Fabio Checconi received the Ph.D. degree in computer engineering, with a focus on real-time operating
systems, from the Scuola Superiore Sant’Anna, Pisa,
Italy, in 2010.
He currently is a Postdoctoral Researcher with
the IBM T. J. Watson Research Center, Yorktown
Heights, NY, where he works in the Multicore
Systems Group.

Luigi Rizzo received the Laurea degree from the
Università di Pisa, Pisa, Italy, in 1987, and the Ph.D.
degree from the Scuola Superiore Sant’Anna, Pisa,
Italy, in 1993, both in electronic engineering.
He is an Associate Professor in computer networks
with the Università di Pisa. He Rizzo has done extensive work in the areas of computer networks, network
emulation, and operating systems.

Paolo Valente received the Laurea and Ph.D. degrees
in computer systems engineering from the Universityof Pisa, Pisa, Italy, in 2000 and 2004, respectively.
Since 2006, he has been an Assistant Professor(Ricercatore) with the Department of Computer
Science, University of Modena, Modena, Italy. His
current research focus is the design and analysis ofCPU, network, and disk scheduling algorithms.