1

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

Abstract—Packet scheduling, together with classification, is
one of the most expensive processing steps in systems providing
tight bandwidth and delay guarantees at high packet rates.
Schedulers with near-optimal service guarantees and O(1) timecomplexity have been proposed in the past, using techniques suchas timestamp rounding and flow grouping to keep their execution
time small. However, even the two best proposals in this family
have a per-packet cost component which is linear either in
the number of groups, or in the length of the packet beingtransmitted. Furthermore, no studies are available on the actual
execution time of these algorithms.
In this paper we make two contributions. Firstly, we present
QFQ, a new O(1) scheduler that provides near-optimal guarantees, and is the first to achieve that goal with a truly constantcost also with respect to the number of groups and the packet
length. The QFQ algorithm has no loops, and uses very simple
instructions and data structures which contribute to its speed ofoperation.
Secondly, we have developed production-quality implementations of QFQ and of its closest competitors, which we use
to present a detailed comparative performance analysis of thevarious algorithms. Experiments show that QFQ fulfils our
expectations, outperforming the other algorithms of the sameclass. In absolute terms, even on a low end workstation, QFQ
takes about 110 ns for an enqueue()/dequeue() pair (only twice
the time of DRR, but with much better service guarantees).

I. I NTRODUCTION
If an outgoing link on a network node is fully utilized, the only
option to provide bandwidth or delay guarantees on that linkis 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 wellknown scalability problems), and imposes a non-negligible
load on packet classifiers and schedulers, who have to deal
with a potentially large number of flows in progress (up to
105 according to [10]). Besides memory costs to keep perflow state, the time complexity and service guarantees of thescheduling algorithm can be a concern. DiffServ [12] “solves”
the space and time complexity problem by aggregating flows
into a few classes with predefined service levels, and schedules
the aggregate 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.
Fabio Checconi is with IBM Research, Multicore Computing Department,
Yorktown Heights, NY (this work was completed while he was with the Scuola
Superiore S. Anna, Pisa, Italy).
Luigi Rizzo is with the Università di Pisa, Pisa, Italy
Paolo Valente is with the Università di Modena, Modena, Italy

Round Robin schedulers have O(1) time complexity, but(with the exception of FRR [24]) have O(N ) worst-casedeviation with respect to the ideal service that the flow should
receive over any given time interval.
More accurate schedulers have been proposed, implementing approximate versions of the worst-case optimal WF2 Q+
scheduler [2]. Thanks to flow grouping and timestamp rounding, first introduced in [17], they feature O(1) time complexity
in the number of flows, and near-optimal deviation from theideal service (WFI, see Section II). However, even the twomost efficient proposals in this class, namely Group Fair
Queueing (GFQ) [17] and Simple KPS (S-KPS) [9], as well
as FRR [24], have some non-constant components in theirtime complexity, as discussed in Sec. II, and are significantly
slower than Round Robin schedulers. Section VII-C showssome performance comparison.
Our contributions: In this paper we first present Quick
Fair Queueing (QFQ), a new scheduler with true O(1) timecomplexity, implementing an approximate version of WF2 Q+
with near-optimal service guarantees. Secondly we provide anextensive comparison of the actual performance of productionquality versions of QFQ and 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)
from previous quasi-O(1) schedulers. In QFQ, groups of flows
are partitioned into four sets, each represented by a machine
word and constructed so that all bookkeeping to implement
scheduling decisions can be done using simple and constanttime CPU instructions such as AND, OR, XOR and Find Firstbit Set1 (which we use to implement constant-time searching).
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
it well suited to hardware implementations. The execution
time is within two times that of DRR, and consistently
about three times faster than S-KPS, across a wide varietyof configurations and CPUs. Speed does not sacrifice service
guarantees: the WFI of QFQ is slightly better than S-KPS, andclose to the theoretical minimum.
Paper Structure: Section II complements this introduction
by discussing related work. In Section III we define thesystem model 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
1 The Find First bit Set instruction (called ffs() or BSR) can locate inconstant time the leftmost bit set in a machine word. It uses 1..3 clock cycles
on modern CPUs such as Intel Core 2, Core i7, or Athlon K10.

2

in QFQ is then proved in Section V. Section VI gives ananalytical 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 realmachine, comparing production-quality implementations of
QFQ, S-KPS, and other schedulers (FIFO, DRR and WF2Q+).

II. BACKGROUND AND R ELATED W ORK
Packet schedulers can be classified based on their service
properties and time/space complexity. Relevant problem dimensions are the number of flows, N , and the maximum
size L of packets in the system. The service metrics definedin the literature try to measure, in various dimensions, thedifferences between the scheduler under analysis and an ideal
fluid system which implements perfect bandwidth distribution
over any time interval.
Two important service metrics are the Bit- and Time- Worstcase Fair Index (B-WFI and T-WFI [2], [3]). B-WFIk (definedin Sec. VI-A) represents the worst-case deviation, in termsof service, that a flow k may experience over any timeinterval with respect to a perfect weighted bandwidth sharing
server during the same interval. T-WFIk , defined in Sec. VI-B,
expresses similar deviations in terms of time. From the WFIs
it is easy to compute the minimum bandwidth and the worstcase packet completion times guaranteed for a flow. But the
WFIs indicate more than just worst-case packet delays or perflow 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 affect the lag, but causes extreme burstiness inservice, which has bad effects on protocols and applications(e.g., TCP’s rate adaptation) as well as on per-flow lag anddelay 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], and equal
to the worst-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 O(1)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 irrespectiveof the weight φk of any flow k, both the flow’s packet delay

and the B-WFIk have an O(N L) 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 WF2 Q [3] schedulesgroups; following that, an extended version of DRR [15]schedules flows within groups.
In FRR, a flow k belongs togroup i such that i = logC φk , where φk is the flow’s
weight.3 C is an integer constant that can be freely chosen
to set the desired tradeoff between runtime complexity andservice guarantees. As shown by its authors in [24, Theorem
L4], FRR has T-WFIk = 12 CL
r k + (G − 1) R , where G is theknumber of groups, r is the minimum bandwidth guaranteed
to flow k and R is the link rate. The time complexity isO(G log G). T-WFI grows with C, and in the best case−6
(C = 2), withwould
 weights
 ranging between 10 kand 1, weL
6have G = logC 10 = 20 and hence T-WFI = 24 rLk + 19 R,
LLkmuch higher than the T-WFI of QFQ (3 rk + 2 R ).
Exact Timestamp-based Schedulers: To achieve a lower
WFI than 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 Timefunction, and try to serve them in ascending timestamp order,
which has an inherent Ω(log N ) complexity [23]. This boundis matched by some actual algorithms [21].
With this approach, schedulers such as WF2 Q [3] andWF2 Q+ [2] offer optimal lag, packet delay and WFI, i.e.,they achieve the lowest possible values for a non-preemptive
system. In particular, their lag and B-WFI are both O(L) withvery small constants (see Sec. VI-A), much better than theO(N L) of most RR schedulers.
Fast Timestamp-based Schedulers: Breaking the theoreticalΩ(log N ) bound 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 achieve
O(1) complexity with respect to the number of flows, while
preserving O(L) B-WFI.
GFQ [17] uses variable timestamp rounding, splits flows
into G groups, and relies on a calendar queue to sort flows
within the same group. Its complexity is O(G). S-KPS [9]uses a data structure called Interleaved Stratified Timer Wheels(ISTW) to execute packet enqueue and dequeue operations
at a worst-case cost independent of even the number ofgroups, though it requires O(L) bookkeeping steps during
packet transmissions. Finally, LFVC [20] rounds timestamps
to multiples of a fixed constant, relying on van Emde Boaspriority queues for sorting (hence O(log log N ) complexity).
Unfortunately LFVC has a worst-case complexity of O(N ),because the algorithm maintains separate queues for eligible
and ineligible flows, and individual events may require to move
up to O(N ) flows from one queue to the other.
2 Such worst case behaviour is easy to achieve in practice (e.g., with afew high-weight flows, and a large number of low-weight flows). In thesecircumstances, the high-weight flows will experience a very bursty service,with unpleasant effects for downstream devices and applications.
3 QFQ also defines groups of flows, but using a different formula, Eq. (4).

3The 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
server larger than O(L). Fortunately the B-WFI bounds are
not affected: GFQ, S-KPS and our QFQ guarantee the same
O(L) B-WFIk as the optimal schedulers, differing only inthe multiplying constant, which is 1 with exact timestamps
and slightly larger otherwise (e.g., 3 in the case of QFQ,
see Sec. VI-B). Thus, approximate timestamps still give muchbetter 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 small number of flows. Also, there may be dependencies
on other parameters, (e.g., GFQ or S-KPS) or worst-casebehaviours significantly larger than average (e.g., LFVC).

The interface of the scheduler to the rest of the system is madeof one packet enqueue() and one packet dequeue() function.
In our model, each flow k is assigned a fixed
φk > 0.
PNweightkWithout losing generality, we assume that k=1 φ ≤ 14 .
A flow is defined backlogged/idle if it owns/does not own
packets not yet completely transmitted. We call B(t) the setof flows backlogged at time t. Inside the system each flowuses a FIFO queue to hold the flow’s own backlog.
We call head packet of a flow the packet at the head of thequeue, and lk its length; lk = 0 when a flow is idle. We saythat a flow is receiving service if one of its packets is beingtransmitted. Both the amount of service W k (t1 , t2 ) received
by a flow and the total amount of service W (t1 , t2 ) deliveredby the system in the time interval [t1 , t2 ] are measured in
number of bits transmitted during the interval.
A. WF2 Q+

III. S YSTEM M ODEL AND D EFINITIONSIn this section we give some definitions commonly used in
the scheduling literature, and then present the exact WF2 Q+
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 (t) when not ambiguous and clear from the context.
SymbolN
L
B(t)W (t1 , t2 )
k
Lk
φk
lk
Qk (t)W k (t1 , t2 )V (t)V k (t)Sk, F kŜ k , F̂ ki, j
Si , Fi
σi
ER, EB,IR, IB

Meaning
Total number of flows
Maximum length of any packet in the system
The set of backlogged flows at time t
Total service delivered by the system in [t1 , t2 ]Flow index
Maximum length of packets in flow k
Weight of flow k
Length of the head packet in flow k; lk = 0 when
the flow is idle
Backlog of flow k at time t
Service received by flow k in [t1 , t2 ]System virtual time, see Eq. (3)Virtual time of flow k, see Sec. III-A
Virtual start and finish times of flow k, see Eq. (2)Approximated S k and F k for flow k, see Section IV-2
Group index (groups are defined in Sec. IV-1)
Virtual start and finish times of group i, see Eq. (6)Slot size of group i (defined in Sec. IV-1, σi = 2i )The four sets in which groups are partitioned

TABLE ID EFINITIONS OF THE SYMBOLS USED IN THE PAPER .

We consider a system in which N packet 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 isused at full capacity whenever there are packets queued. A
scheduler sits between the flows and the link: arriving packets
are immediately enqueued, and the next packet to serve ischosen and dequeued by the scheduler when the link is ready.

Here we outline the original WF2 Q+ algorithm for avariable-rate system (see [2], [18] for a complete description).
WF2 Q+ is a packet scheduler that approximates, on a packetby-packet basis, the service provided by a work-conserving
ideal fluid system that delivers the following, almost perfect
bandwidth distribution over any time interval:
W k (t1 , t2 ) ≥ φk W (t1 , t2 ) − (1 − φk )L(1)

The packet and the fluid system serve the same flows anddeliver the same total amount of work W (t) (systems withthese features are called corresponding in the literature). They
differ in that the fluid system may serve multiple packets inparallel, whereas the packet system has to serve one packet at atime, and is non preemptive. Because of these constraints, theallocation of work to the individual flows may differ in thetwo systems. WF2 Q+ has optimal B-/T-WFI and O(log N )complexity, which makes it of practical interest.
WF2 Q+ operates as follows. Each time the link is ready,the scheduler starts to serve, among the packets that havealready started5 in the ideal fluid system, the next one thatwould be completed in the fluid system; ties are arbitrarily
broken. WF2 Q+ is a work-conserving on-line 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 WF2 Q+ policy is efficiently implemented
by considering, for each flow, a special flow virtual timefunction V k (t) that grows as the normalized amount of service(i.e., actual service received, divided by the flow’s weight)
received by the flow. In addition, when the flow turns from
idle to backlogged, V k (t) is set to the maximum between
its current value and the value of a further function, thesystem virtual time V (t), defined below. For each flow k, thevalue of V k (t) needs to be known (hence computed) only on
the following events: when the flow becomes backlogged, orwhen its head packet completes transmission in the ideal fluid
4 The 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.
5 This property, called “eligibility” is fundamental in providing small WFI.

4system. The resulting values of V k (t), called flow’s virtual
start and finish time, S k and F k , are used to timestamp theflow itself, and are computed as:max(V (tp ), F k ) on newly backlogged flowkS ←Fk
on packet dequeuekkkkF ← S + l /φ(2)where tp is the time when a packet enqueue/dequeue occurs.
V (t) is thePsystem virtual time function defined as follows(assumingφk ≤ 1):(3)
V (t2 ) ≡ max V (t1 ) + W (t1 , t2 ), min S kk∈B(t2 )Note that V (t) is only computed at discrete times, so theinstantaneous link rate need not be known, and just W (t1 , t2 )(the amount of data transferred in [t1 , t2 ]) suffices. At systemstart-up V (0) = 0, S k ← 0 and F k ← 0.
Eligibility: Flow k is said to be eligible at time t if V (t) ≥ S k .
This inequality guarantees that the head packet of the flow has
already started to be served in the ideal fluid system. Using
this definition, WF2 Q+ can be implemented as follows: eachtime the link is ready, the scheduler selects for transmission
the head packet of the eligible flow with the smallest virtualfinish time. Note that the second argument of the max operator
in Eq. (3) guarantees that the system is work-conserving.
The time complexity in WF2 Q+ comes from three tasks:i) computing V (t) from Eq. (3), which requires to track theminimum S k and has O(log N ) cost; ii) selecting the next flow
to serve among the eligible ones, which requires tracking theminimum F k among eligible flows and also has O(log N ) costat each step; iii) updating eligible flows as V (t) grows. Anychange in V (t) can render O(N ) flows eligible, and it takessome clever data structure [19] to avoid an O(N ) cost.

Fig. 1, and relies on three techniques (Flow Grouping, Timestamp Rounding, Group Sets) to perform all computations inO(1) time.
1) Flow Grouping: Each flow k (one of the squares at thebottom of Figure 1) is statically mapped into one of a finite
number of groups (the regions at the bottom of the figure).
The group i is chosen as


Lk
(4)
i = log2 k
φwhere Lk is the maximum size of the packets for flow k.
Lk /φk is related to the service guarantees given to a flow, so
flows with similar guarantees are grouped together.
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 σi ≡ 2i (bits) as the slot size of the group. Since
σi−1 < Lk /φk ≤ σi , from Eq. (2) we have F k − S k ≤ σi forany flow k in group i.
2) Timestamp Rounding: Same as other timestamp-basedschedulers, QFQ labels flows with both exact and approximate
virtual times. The exact values (S k and F k , Eq. (2)) are used
to provide guarantees7. The approximate values are defined as
j kk
Ŝ k ← Sσi σi , F̂ k ← Ŝ k + 2σi(5)(where i is the group index) and are used to compute eligibility
and scheduling order. Note that Ŝ k ≤ S k < F k < F̂ k which
has useful implications on the runtime and service guaranteesof the algorithm.
For each group QFQ defines
Si =

min

k∈groupiŜ k,

Fi = Si + 2σi(6)called the group’s virtual start and finish times.
Finally, QFQ replaces S k with Ŝ k in the definition of thevirtual time function:


k
(7)
V (t2 ) ≡ max V (t1 ) + W (t1 , t2 ), min Ŝ
k∈B(t2 )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) arestored in a bitmap by index number. The groups (rectangles on the bottom,
see Section IV-1) contain the bucket lists and individual flow queues.

IV. Q UICK FAIR Q UEUEINGIn 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 in

It is easy to show that the min Ŝ k in the equation can becalculated as the minimum Si among the backlogged groups
in the system. Same as in Eq. (3), at system start-up V (0) = 0,
Si ← 0 and Fi ← 0.
Timestamp properties: Ŝ k and F̂ k can only assume a limited
range of values around V (t) (S k and F k have a similar
property called Globally Bounded Timestamp or GBT [17]).
We can prove (see Theorems 1 and 2 in Section V) that at
all times Ŝ k < V (t) + σi . Furthermore, Ŝ k is quantized andcan only assume 2 + ⌈L/σi ⌉ distinct values (remember thatσi ≈ Lk /φk so the second term is bounded by the ratio
between the min and max packet size in the system). The small
number of possible values permits sorting within a group using
6 This is trivially proven by substituting values in (4); as an example, Lk
between 64 bytes and 16 Kbytes, φk between 1 and 10−6 ) yield values
between 64 = 26 and 16 · 109 ≈ 234 , or 29 groups.
7 There is one case where the S k for certain newly backlogged groups
can be shifted backwards to preserve the ordering of EB; this exception is
described and its correctness is proved in Lemma 4.

5

a constant-time bucket sort algorithm, implemented using abucket list (Fig. 2), a short array with as many buckets as
the number of distinct values for Ŝ k . Each bucket contains
a FIFO list of all the flows with the same Ŝ k and F̂ k . For
practical purposes, 64 buckets are largely sufficient, so once
again each bucket can be mapped to a bit in a machine word,
and a constant-time Find First bit Set instruction can be used
to locate the first non-empty bucket, which contains the next
flow to serve.
The use of Ŝ k in Eq. (7) also saves another sorting step,
because, as we will see, the group sets defined in the next
section let us compute Eq. (7) in constant time.

because the transitions of a group i from ineligible to eligible(driven by the increase of V (t)), and from blocked to ready(driven by the increase of the Fj of the group that was blocking
group i) are not reversible until group i 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, and IB ∪ IR is sorted by both Si and Fi .
So, once the index of the first matching group is known (seeSec. IV-A3), 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
2

Fig. 2. A representation of bucket lists. The number of buckets (gray, eachcorresponding to a possible value of Ŝ k ), is fixed and independent of thenumber of flows in the group.

3
4
5
6
7

3) Group Sets and their properties: QFQ partitions backlogged groups into four distinct sets (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 andFFS on single machine words.
The sets are called ER, EB, IR, and IB (from the initials
of Eligible, Ineligible, Ready, and Blocked), and the partitioning is done using two properties:• Eligible: group i is Eligible at time t iff Si ≤ V (t). The
group is Ineligible otherwise.
• Blocked: independent of its own eligibility, a group i 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 thatwithin each set X the group index reflects the ordering byfinish time: (∀j, i ∈ X, j > i ⇒ Fj > Fi ). In particular, thefollowing properties hold:1) IB ∪ IR is sorted by Si as a result of the GBT property.
In fact, if a group i is ineligible, any flow k in the grouphas V (t) < S k < V (t) + σi . Due to the rounding we
can only have Si = ⌈V (t)/σi ⌉σi , and if i < j, we have
2σi ≤ σj hence Si ≤ Sj ;2) IB ∪ IR is also sorted by Fi because of the sorting by
Si and the fact that σi ’s are increasing with i;3) ER is sorted by Fi , as proven in Theorem 4 (Section V);
4) EB is sorted by Fi , 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 agroup, QFQ may need to move one or more other groups
from one set to another, but only on the paths
IB → IR , IR → ER , IB → EB , EB → ER

8
9
10
11
12
13
14
15
16
17
18

/ / Enqueue the input pkt of the input flow
enqueue ( in : pkt , in : flow ) {a p p e n d ( p k t , f l o w . q u e u e ) ; / / always enqueuei f ( f l o w . q u e u e . h e a d != p k t )r e t u r n ; / / Flow already backlogged, we are done.
/ / Update flow S k and F k according to Eq. (2).
f l o w . S = max ( f l o w . F , V) ;flow . F = flow . S + pkt . l e n g t h / flow . weight ;g = f l o w . g ro u p ; / / g is our groupi f ( g . b u c k e t l i s t . h e a d f l o w ==NULL | | f l o w . S<g . S ) {/ / Group g is surely idle or not eligible. Remove from IR and IB if/ / there, and compute the new group Si and Fi from Eq. (5) and (6).
s e t [ IR ] &= ˜ ( 1 < < g . i n d e x ) ;s e t [ IB ] &= ˜ ( 1 < < g . i n d e x ) ;g . S = flow . S & ˜ ( g . s l o t s i z e − 1) ;g . F = g . S + 2∗g . s l o t s i z e ;}b u c k e t i n s e r t ( flow , g ) ;19/ / If there is some backlogged group, at least one is/ / in ER; otherwise, make sure V ≥ g.S
i f ( s e t [ER ] == 0 && V < g . S )V = g.S ;

20
21
22
23
24

/ / compute new state for g, and insert in the proper set
s t a t e = compute group state ( g ) ;s e t [ s t a t e ] |= 1 < < g . inde x ;

25
26
27
28

}

29
30
31
32
33
34
35
36
37
38
39
40
41

/ / Compute the group’s state, see Section IV-3
int compute group state ( in : g ) {/ / First, eligibility tests = ( g . S <= V) ? ELIGIBLE : INELIGIBLE ;/ / Find lowest order group x > group.index. This is the group that/ / might block us. ffs from(d, i) returns the index of the first bit set/ / in d after position i
x = f f s f r o m ( s e t [ ER ] , g . i n d e x ) ;s += ( x != NO GROUP && g r o u p s [ x ] . F < g . F ) ?
BLOCKED : READY;
return s ;}Fig. 3.
The enqueue() function, called on packet arrivals, and compute group state() that implements the tests for eligibility and readiness.

1) Packet Enqueue: Function enqueue(), shown in Fig. 3,
is called 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 alreadybacklogged. Otherwise, the flow’s timestamps are updated(lines 7–8), and line 10 checks whether the group’s state needs
to be updated: this happens if the group was idle, or if the
new flow causes the group’s timestamp to decrease (in thiscase the group was ineligible: line 7 implies V (t) ≤ S k , the6second test in line 10 succeeds if S k < Si , hence V (t) < Si ).
The update is done by lines 11-18, which possibly remove
the group from the ineligible sets (lines 14–15), and update
the group’s timestamps (being the slot size 2i , the start time
calculation only needs to clear the last i bits of Sk , line 16).
Once the group’s timestamps are set, a constant-time bucket
insert (line 19) sorts the flow with respect to the otherflows in the group. At this point, if needed, V (t) is updated
according to Eq. (2). Finally, function compute group state()(Sec. IV-A3/Fig. 5) computes the new state of the group(which may have changed because of the new values of Si ,Fi and V (t)), and line 28 puts the group in its new set.
Note that an enqueue does not move other groups across
sets: their eligibility remains the same (V (t) changes only if
all other groups are idle); blocked/ready states also remainunchanged, though for less intuitive reasons8 .
2) Packet Dequeue: Function dequeue() in Fig. 4 is called
to return 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 ER is not
empty: a first FFS instruction (line 6) picks the group withthe lowest index in ER, then another FFS (line 7) is used
to locate the first flow in the bucket list, and the head packet
from that flow 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, toreflect 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
idle (lines 32–36), it is moved to the new set, and function
unblock groups() described in Sec. IV-A3 possibly unblocks
other groups.
Finally, lines 38–45 make sure that at least one backloggedgroup is eligible by bumping up V 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 V (t) grows after serving a flow. The propertiesof rounded timestamps are used to implement the check inconstant time. The algorithm is explained with the help ofFig. 6, which gives a graphical representation of the possible
values of Si ’s and V (t), and the binary representations ofV (t) (the vertical strings of binary digits). Since slot sizes
are powers of two (σi = 2i ), the binary representation of
8 If 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 j containing flow k just became backlogged, or its finish timedecreased. However S k ≥ V (t), hence Fj > ⌊V (t)/σj ⌋ σj + 2σj . Any
Ready group i < j will have Fi < ⌊V (t)/σi ⌋ σi + 3σi (one σi comes fromthe upper bound on S k , the other two come from the definition of Fi =Si + 2σi ). Hence Fi ≤ V (t) + 3σi . By definition j > i =⇒ σj ≥ 2σi , so
Fj ≥ Fi and the newly backlogged group j cannot block a previously Readygroup, even in the worst case (largest possible Fi , smallest possible Fj ).

1
2
3
4
5
6
7
8

p a c k e t d e q u e u e ( ) { / / Return the next packet to servei f ( s e t [ER ] == 0 )r e t u r n NULL;/ / Dequeue the first packet of the first flow of the group/ / in ER with the smallest index
g = g r o u p s [ f f s ( s e t [ ER ] ) ] ;flow = bucket head remove ( g . b u c k e t l i s t ) ;p k t = h e a d re mo v e ( f l o w . q u e u e ) ;9/ / Update flow timestamps according to Eq. (2)flow . S = flow . F ;p = f l o w . q u e u e . h e a d ; / / next packet in the queuei f ( p != NULL) {flow . F = flow . S + p . l e n g t h / flow . weight ;b u c k e t i n s e r t ( flow , g ) ;
}

10
11
12
13
14
15
16
17

old V = V ; / / Need the old value in make eligible()V += p k t . l e n g t h ; / / Account for packet just served

18
19
20

o l d F = g . F ; / / Save for later use
i f ( g . b u c k e t l i s t . h e a d f l o w == NULL) {s t a t e = IDLE ; / / F not significant now} else {g . S = g . b u c k e t l i s t . headflow . S ;g . F = g . b u c k e t l i s t . headflow . F ;s t a t e = compute group state ( g ) ;
}

21
22
23
24
25
26
27
28
29

/ / If g becomes IDLE, or if F has grown, may need to/ / unblock other groups and move g to its new set
i f ( s t a t e == IDLE | | g . F > o l d F ) {s e t [ER ]&= ˜ ( 1 < < g . i n d e x ) ;s e t [ s t a t e ] |=1 < < g . index ;u n b l o c k g r o u p s ( g . index , old F ) ;
}

30
31
32
33
34
35
36
37

x = s e t [ IR ] | s e t [ IB ] ; / / all ineligible groupsi f ( x != 0 ) { / / Someone is ineligible, may need to/ / bump V up according to Eq. (3)i f ( s e t [ ER ] == 0 )V = max (V , g r o u p s [ f f s ( x ) ] . S ) ;/ / Move newly eligible groups from IR/IB to ER/EB
m a k e e l i g i b l e ( old V , V) ;}return pkt ;

38
39
40
41
42
43
44
45
46
47

}

Fig. 4.

The dequeue() function, described in Section IV-A2.

the timestamps of the i-th group’s ends with i − 1 zeros; inany given slot belonging to group i, the value of the i-th bit
is constant during the whole slot. Whenever the i-th bit ofV (t) changes, the virtual time enters a new slot of size 2i .
As a consequence, on each V (t) update, the highest bit j thatchanges in V (t) indicates that all backlogged groups Gi , i ≤ j
are now eligible.
This is exactly the algorithm implemented by function
make eligible(): it computes the index j using a XOR followed
by a Find Last Set (FLS) operation; then computes the binary
mask of all indexes i ≤ j, and calls function move groups tomove groups whose index is in the mask from IR to ER andfrom IB to EB.
Function unblock groups() updates the set of blocked
groups. When the group j under service increases its finish
time or becomes idle, some groups i < j blocked by j might
become ready, i.e., do not violate anymore the ordering ofER ∪ IR. Theorem 6 in Section V proves which groups canbe unblocked; lines 21–22 verify the preconditions, and lines
25–27 move groups to ER and IR as needed.

7

1
2
3
4
5

/ / Move the groups in mask from the src to the dst set
mo v e g ro u p s ( i n : mask , i n : s r c , i n : d e s t ) {s e t [ d e s t ] | = ( s e t [ s r c ] & mask ) ;s e t [ s r c ] &= ˜ ( s e t [ s r c ] & mask ) ;
}

6
7
8
9
10
11
12
13
14
15
16

/ / Move from IR/IB to ER/EB all groups that become eligible as V (t)/ / grows from V1 to V2. This uses the logic described in Fig. 6
m a k e e l i g i b l e ( i n : V1 , i n : V2 ) {/ / compute the highest bit changed in V(t) using XOR
i = f l s ( V1 ˆ V2 ) ;/ / mask contains all groups with index j ≤ imask = ( 1 < < ( i + 1 ) ) − 1 ;mo v e g ro u p s ( mask , IR , ER ) ;mo v e g ro u p s ( mask , IB , EB ) ;
}

19
20
21
22
23
24
25
26
27
28

V. P ROOFS OF THE PROPERTIES USED IN QFQ

1

1

1

1

1

1

1

1

0

0

0

0

0

0

1

1

1

1

0

0

In this section we prove the properties used in Sec. IV.
The proofs are complete but slightly condensed due to spaceconstraints. All symbols are defined in Table I, and quantities(V (t), S k (t), ...) 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 genericfunction of time f (t), we define f (t+f (t). For1 ) ≡ limt→t+
1
notational convenience, we avoid writing f (t+)
if
f (t) isccontinuous at time tc . To further simplify the notation, if thefunction is discontinuous at a time instant td , we assume,
without losing generality, that f (td ) ≡ limt→t− f (t), i.e., thatdthe function is left-continuous.
We define the following two notations for convenience:xxand⌈x⌉σi ≡ ⌈ ⌉σi⌊x⌋σi ≡ ⌊ ⌋σi
σi
σi

0

0

1

1

0

0

1

1

0

0

For any positive quantity y < x + σi , we have

0

1

0

1

0

1

0

1

0

1

17
18

bitmaps, the sum of weights and a timestamp. Overall, even alarge configuration will require 4 KBytes of memory to holdthe entire state of 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.

/ / Unblock groups after serving group i with F=old F
u n b l o c k g r o u p s ( in : i , in : old F ) {x = f f s ( s e t [ ER ] ) ] ;i f ( x == NO GROUP | | g r o u p s [ x ] . F > o l d F ) {/ / Unblock all the lower order groups (Theorem 6)/ / mask contains all groups with index j < imask = ( 1 < < i ) − 1 ;mo v e g ro u p s ( mask , EB , ER ) ;mo v e g ro u p s ( mask , IB , IR ) ;}}Fig. 5. Functions to manage group sets after a flow has been served (seeSec. IV-A2).
Group
index

old_V

new_V

⌊y⌋σi ≤ ⌈x⌉σiV(t)may move to eligible

Fig. 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, sogroups zero and one are the candidates to become eligible (see Sec. IV-A3).

(8)

In fact, x can be written as x = nσi + δ, with 0 ≤ δ < σi . If
δ = 0 then y < (n + 1)σ1 ⇒ ⌊y⌋σi ≤ nσi , ⌈x⌉σi = nσi , andthe thesis holds; if δ > 0 then ⌊y⌋σi ≤ (n + 1)σi , ⌈x⌉σi =(n + 1)σi , and the thesis holds too.
A. Group GBT under QFQ

B. Time and Space Complexity
From the listings it is clear that QFQ has O(1) time complexity on packet arrivals and departures: the algorithm has
no loops, and all operations, including insertion in the bucket
list and finding the minimum timestamps, require constanttime. All arithmetic operations can be done using fixed pointcomputations, including the division by the flow weight (forefficiency, divisions are implemented as multiplications by the
inverse of the weight).
Note
P that while the algorithm has been described assumingφ=φk ≤ 1, the actual implementation supports arbitraryvalues for φ, replacing line 19 of the dequeue function with
V += pkt.length / φ. Changes in φ are tracked in real time
as flows come and go: new flow increasing φ immediately(this does 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
bytes (two timestamps, weight, group index and one pointer).
Each group contains a variable number of buckets (32 in theworst case, requiring one pointer each), plus two timestamps
and a bitmap. Finally, the main data structure contains five

We start by proving per-group upper bounds for Si (t)−V (t)(Theorem 1) and for V (t) − Fi (t) (Theorem 2, supported by
the two long Lemmas 1 and 2). The two bounds representa group-based variant of the Globally Bounded Timestamp(GBT) property, normally defined for the flow timestamps
in an exact virtual-time-based scheduler. We will use thesebounds to prove both the properties of the data structure andthe B/T-WFI of QFQ. Lemmas 1 and 2 are adapted versionsof the ones in [9], repeated here for convenience and withpermission from the author.
Theorem 1: Upper bound for Si (t) − V (t).
For any backlogged group i and ∀t


V (t)
(9)
σi = ⌈V (t)⌉σi
Si (t) ≤σi
Proof: By definition (5), at any time t and for any groupi, Si (t) is an integer multiple of σi and, for any backlogged
flow k of the group, Si (t) ≤ Ŝ k (t) = ⌊S k (t)⌋σi . It follows
that, if S k (t) < V (t) + 2σi , then (9) trivially holds. Hence,
to prove (9) we actually prove the latter inequality, i.e., that
S k (t) < V (t) + 2σi , and to prove it we consider only a8generic time instant t1 at which a generic packet for flow
k is enqueued/dequeued, as this is the only event upon which
S k (t) may increase.
According to (2), either S k (t+1 ) = V (t1 ), in which case thepacket is enqueued and the thesis trivially holds, or S k (t+1) =F k (t1 ). In this case flow k must have had a packet previously
dequeued at time tp < t1 .
When the packet was dequeued at tp flow k was certainly eligible, and V (t) is immediately incremented after the dequeuekkk
at tp , so we have F k (t1 ) = S k (t+p ) = S (tp ) + l (tp )/φ ≤kk+
V (tp ) + σi + l (tp )/φ ≤ V (tp ) + 2σi < V (tp ) + 2σi , which
proves the thesis.
Lemma 1: Let I(t) = {k : k ∈ B(t), S k (t) ≥ V (t)} be asubset of flows. Given a constant V ′ , ∀t : V (t) ≤ V ′ we have:Xlk (t) + φk [V ′ − F k (t)] ≤ V ′ − V (t)(10)
k∈I(t)

where lk (t) is the size of the first packet in the queue for flow
k at time t.
Proof: By definition, lk (t) = φk [F k (t) − S k (t)]. Thus,kfor flows in set I(t)φk [F k (t) − V (t)].
 k l (t) ≤P we havekk
Therefore: 0 ≥=k∈I(t) l (t) + φ [V (t) − F (t)]
k
P
k
′
k
′
k
l
(t)
+
φ
[V
(t)
−
V
]
+
φ
[V
−
F
(t)]
.
k∈I(t)
k
PThis implies:
l (t) + φk [V ′ − F k (t)]≤k∈I(t)
P
k
′
′
φ
[V
−
V
(t)]
≤
V
−
V
(t),
where
the
last
k∈I(t)
P
passage uses k∈I φk ≤ 1.
Lemma 2: Let X(t, M ) ≡ {k : F̂ k (t) ≤ M } be a set offlows. Given a constant V ′ , we have that ∀t : L + V ′ ≥ V (t):Xlk (t) + φk [V ′ − F k (t)] ≤ L + V ′ − V (t) (11)k∈X(t,V ′ )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 where X
is empty is true by assumption. For the inductive proof, we
assume (11) to hold at some time t1 .
Packet enqueue for an idle flow: say a packet of size l1of the idle flow k arrives at time t1 . V (t) does not change on
packet arrivals except for virtual time jumps, that are dealt with′later. If after the enqueue of the new packet k ∈/ X(t+
1 , V ),
k +′i.e., F̂ (t1 ) > V , we must consider two sub-cases. First, if
k ∈/ X(t1 , V ′ ) nothing changes. Second, if k ∈ X(t1 , V ′ )the positive component φk [V ′ − F k (t1 )] is removed from thesum. In both sub-cases the lemma holds. The remaining case′k +kis if k ∈ X(t+1 , V ). Since F̂ (t1 ) > F̂ (t1 ), this implies′kk ∈ X(t1 , V ). In this case l (t) is incremented by l1 , but
F k (t) is incremented by l1 /φk , so the left hand side of (11)remains unchanged and the lemma holds.
Virtual time jump: after a virtual time jump, all backlogged+k +flows have S k (t+1 ) ≥ Ŝ (t1 ) ≥ V (t1 ). With regard to the idle
flows, we assume that their virtual start and finish times arepushed to V (t+1 ). By doing so we do not lose generality, as
the virtual start times of these flows will be lower-boundedby V (t) when they become backlogged (again). Besides, it iseasy to see that pushing up their virtual finish times may only+
let the left side of (11) decrease. In the end S k (t+1 ) ≥ V (t1 )+′for all flows and, if V ≥ V (t1 ) then Lemma 1 applies and+the lemma holds. For other V ′ in [V (t+1 ) − L, V (t1 )[, theadditional L term in (11) absorbs any decrement on the righthand side. Therefore, the lemma holds.
Packet dequeue: flow k receives service at time t1 for its
head packet of size lk (t1 ). We have to distinguish two cases,
depending on V ′ and F̂ k (t1 ).
Case 1: V ′ ≥ F̂ k (t1 ). V (t) is incremented, and hence theright side of (11) decreases, exactly by lk (t1 ). With regard
to the left side, the variation of lk (t) can be seen as theresult of first decreasing by lk (t1 ), which balances the above
decrement of V (t), and then increasing by lk (t+1 ), which islk (t+
k1 )in turn balanced by incrementing F (t) by φk . Hence thelemma holds for this case.
Case 2: V ′ < F̂ k (t1 ). In this case all flows h ∈ X(t1 , V ′ )have F̂ h (t1 ) < F̂ k (t1 ), so they must have been ineligible
according to their rounded start time, otherwise the current
flow k would have not been chosen. Therefore, V (t1 ) <Ŝ h (t1 ) ≤ S h (t1 ) for all flows in X(t1 , V ′ ). Lemma 1 applies
then for all V ′ ≥ V (t1 ), i.e.,Xlk (t1 ) + φk [V ′ − F k (t1 )] ≤ V ′ − V (t1 ) (12)′k∈X(t+
1 ,V )k′
Because V (t+1 ) = V (t1 ) + l and we assume L + V ≥+′V (t1 ) after service, we only need to consider V with L +k
V ′ ≥ V (t+1 ) + l before service. Therefore+k′V ′ − V (t1 ) ≤ (L − lk ) + V ′ − (V (t+1 ) − l ) = L + V − V (t1 )(13)and the lemma holds after service also in this case, thus
completing the proof.
Theorem 2: Upper bound for V (t) − Fi (t)For any backlogged group i

V (t) ≤ Fi (t) + L(14)

Proof: To prove the thesis we will actually prove, bycontradiction, the more general inequality V (t) ≤ F̂ k (t) + L
for a generic flow k of group i. The only event that could leadto a violation of the assumption is serving a packet. Assume
that at t = t1 : V (t1 ) = V1 the lemma holds. A packet
p with rounded finish time F̂1 and length lp is served andafterwards at time t2 : V (t2 ) = V2 , there is a packet q withfinish time F2 , such that F̂2 + L < V2 . Denote with Ŝ1 andŜ2 the corresponding start times. We need to distinguish threecases.
Case 1: Packet q is eligible at time t1 according to its
rounded start time. Then, F̂2 ≥ F̂1 (both packets were eligibleat V1 and p was chosen). Applying Lemma 2 with t = t1 andV ′ = F̂2 results inXX
lk (t1 )+(F̂2 −F k (t1 ))φk ≤ L+F̂2 −V (t1 )k∈X(t1 ,F̂2 )k∈X(t1 ,F̂2 )(15)
Because F k (t) ≤ F̂ k (t), the second term on the left side of
the inequality is non-negative and therefore V1 + lp ≤ V1 +P
k
k:F̂ k (t)≤F̂2 l (t) ≤ V1 + L + F̂2 − V1 ≤ F̂2 + L.
Case 2: Packet q is not eligible at V1 according to its
rounded start time, but becomes eligible between V1 and V2 .

9Then, Ŝ2 ≥ V1 . Virtual time advances by at most L andtherefore: F̂2 ≥ Ŝ2 ≥ V1 ≥ V2 − L.
Case 3: Packet q is not eligible according to its rounded start
time after service to p, therefore V2 is reached by a virtual time
jump before q can be served. In this case: F̂2 ≥ Ŝ2 ≥ V2 ≥V2 − L. This concludes the proof.
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
the following theorem, which bounds the number of possible
timestamps within a group.
Theorem 3: At all times, only the first 2 + ⌈ σLi ⌉ consecutive
slots beginning from the head slot of a group may be non
empty.
Proof: Consider a generic flow k belonging to a group i.
A new virtual start time may be assigned to the flow (only) as
a consequence of the enqueueing/dequeueing of a new packet
pk,l at a time instant tp . As in the proof of Theorem 1, from (2)kS k (t+p ) may be equal to either (a) V (tp ), or (b) F (tp ), wherekk,l
we assume F (tp ) = 0 if p is the first packet of the flow
to be enqueued/dequeued.
In the first case, according to (14), S k (t+p ) = V (tp ) ≤Fi (tp ) + L ≤ Si (tp ) + 2σi + L ≤ Si (tp ) + 2σi + ⌈ σLi ⌉σi . In thesecond case, neglecting the trivial sub-case F k (sk,l−1 + ) = 0,
we can consider that flow k had to be a head flow when pk,l−1
was served. Hence, according to (5), S k (tp ) < Si (tp ) + σi .
kFrom (2), this implies S k (t+p ) = F (tp ) < Si (tp ) + 2σi .
Considering both cases, it follows that, ∀t S k (t) − Si (t) <(2 + ⌈ σLi ⌉)σi , which proves the thesis.
Using the following lemma, we want now to prove that ER
is ordered by virtual finish times.
Lemma 3: Let t be the time instant at which a previously
idle group i becomes backlogged, or at which the group,
previously ineligible, becomes eligible, or finally at which
the virtual finish time of the group decreases. We have that+Fh (t) ≤ Fi (t ) for any backlogged group h with h < i.
Proof: For Fi (t) to decrease, Si (t) must decrease as well.
According to the enqueue() and dequeue(), this can happen
only in consequence of the enqueueing of a packet of an empty
flow of the group. As this is exactly the same event that may
cause a group to become backlogged, then, from (2) we have+
Si (t ) ≥ ⌊V (t)⌋σi both if the group becomes backlogged and
if Fi (t) decreases. Substituting this inequality, which finallyholds also if the group becomes eligible at time t, and (9) inthe following difference we get:+Fh (t) − Fi (t )+Sh (t) + 2σh − Si (t ) − 2σi⌈V (t)⌉σh − ⌊V (t)⌋σi + 2σh − 2σi⌈V (t)⌉σi − ⌊V (t)⌋σi + 2σh − 2σi

=
≤
≤
≤0

(16)

where ⌈V (t)⌉σh ≤ ⌈V (t)⌉σi and the last inequality follows
from that, as i > h, σi ≥ 2σh .
The following theorem guarantees that ER is always ordered by virtual finish times.
Theorem 4: Set ER is ordered by group virtual finish time.

Proof: We will prove the thesis by induction. In the basecase ER = ∅ the thesis trivially holds. The ordering of ER
may change only when one or more groups enter the set. Thiscan happen as a consequence of 1) a group entering ER as
it becomes backlogged, 2) one or more groups moving fromIR to ER, 3) one or more groups moving from EB to ER.
Let i be a group entering ER at time t1 for one of the above
three reasons, and let the thesis hold before time t1 .
In the first case, thanks to Lemma 3 Fi (t+1 ) is not lower
than the virtual finish times of the groups in ER with lower
index. By definition of ER, Fi (t+1 ) is also not higher than thevirtual finish times of the groups in ER with higher index.
In the second case, given a group h ∈ ER with h < i,Si (t1 ) ≥ Sh (t1 ) because either group h was already in ER
before time t1 , or group h belonged to IR, which is orderedby virtual start times according to [Sec.IV-3, item 2]. Thisimplies Fi (t1 ) ≥ Fh (t1 ) because σi ≥ 2σh . By definition ofIR, Fi (t1 ) is also not higher than the virtual finish times of
the groups in ER with higher index.
In the third case, since group i is not blocked any more,Fi (t1 ) is not higher than the virtual finish times of the groups
in ER with higher index. With regard to the groups with lower
index than i, for group i to be blocked before time t1 there had
to be a group b ∈ ER with b > i and Fb (t1 ) < Fi (t1 ). Since
we assume that ER is ordered by virtual finish time before
time t1 , then Fb (t1 ), and hence Fi (t1 ) is not lower than thevirtual finish times of all the lower index groups in ER.
To prove that EB enjoys the same order property as ER,
we need first a further lemma. The validity of the lemma
depends on the timestamp back-shifting performed by QFQ
when inserting a newly backlogged group into EB. Hence
this is the right place to explain in detail this operation.
When an idle group i becomes blocked after enqueueing apacket of a flow k at time tp , the timestamps of flow k are
not updated using the following variant of (2):kS k (t+p ) ← max min(V (tp ), Fb (tp )), F (tp )
(17)
k
k +
k
F k (t+p ) ← S + l (tp )/φ
where b is the lowest order group in ER such that b > i.
Basically, with respect to the exact formula, Fb (tp ) is usedinstead of V (tp ) if V (tp ) > Fb (tp ). This is done because
otherwise the ordering by virtual finish time in EB may be
broken. It would be easy to show that this would happen if an
idle group becomes blocked when V (t) is too higher than thevirtual finish time of some other blocked group h < i.
With regard to worst-case service guarantees, in caseV (tp ) > Fb (tp ) in (17), group i 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 pair oftimestamps backwards, provided that this does not lead to aninconsistent schedule, i.e., provided that the resulting worstcase 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 i become backlogged have

10

arrived at a time instant tp ≤ tp at which V (tp ) = Fb (tp ),group i would have however got a virtual finish time higher
than Fb (tp ). Hence group i should not have been served before
group b, exactly as it happens in the schedule resulting fromtimestamping group i with (17) at time tp .
We can now introduce the intermediate lemma we need to
finally prove the ordering in EB.
Lemma 4: If a pair of groups h and i with h < i are blocked
at a generic time instant t2 , then Sh (t2 ) ≤ Fi (t2 ).
Proof: We consider two alternative cases. The first is that
Sh (t2 ) has been last updated at a time instant t1 ≤ t2 using(17). The second is that, according to (2) and (5) there are atleast one head flow k of group h and a time instant t1 ≤ t2
such that Sh (t2 ) = ⌊F k (t1 )⌋σh .
In the first case we have Sh (t2 ) ≤ Fb (t1 ), where b is thelowest order group in ER such that b > h. We can consider
two sub-cases. First, group i is already backlogged and eligible
at time t1 . It follows that, if i ≥ b then Fi (t1 ) ≥ Fb (t1 ).
Otherwise, from the definition of b, group i is necessarily
blocked, and Fi (t1 ) > Fb (t1 ) must hold again for group b
not to be blocked. In the end, regardless of whether group i isready or blocked, Fi (t2 ) ≥ Fi (t1 ) > Fb (t1 ) = Sh (t2 ) and thethesis holds. In the other sub-case, i.e., group i is not readyand eligible at time t1 , thanks to Lemma 3 group i cannot
happen to have a virtual finish time lower than Fh (t1 ) during(t1 , t2 ]. Hence Fi (t2 ) ≥ Fh (t1 ) = Fh (t2 ) > Sh (t2 ).
In the other case, i.e., Sh (t2 ) = ⌊F k (t1 )⌋σh , we prove thethesis by contradiction. Suppose that Sh (t2 ) > Fi (t2 ). Flow kmust have necessarily been served with F k (t0 ) = F k (t1 ) at
some time t0 ≤ t1 . In addition, for Sh (t2 ) > Fi (t2 ) to hold,F k (t1 ) > Fi (t2 ) and hence F k (t0 ) > Fi (t2 ) should hold aswell. As flow k had to be a head flow at time t0 , it would
follow thatFh (t0 ) ≥ F k (t0 ) > Fi (t2 )(18)
We consider two cases.
First, group i is backlogged at time t0 . If Fi (t0 ) < Fh (t0 ),then Si (t0 ) = Fi (t0 ) − 2σi < Fh (t0 ) − 2σi < Sh (t0 ), because
σi > σh . Hence, both group h and i would be eligible,and group h could not be served at time t0 . In follows that
Fi (t0 ) ≥ Fh (t0 ) should hold. This inequality and (18) would
imply Fi (t0 ) > Fi (t2 ). Should not Fi (t) decrease during[t0 , t2 ], the absurd Fi (t2 ) > Fi (t2 ) would follow. But, fromenqueue() and dequeue() it follows that the only event thatcan let Fi (t) decrease is the enqueueing of a packet of an idle
flow of group i that causes Si (t) to decrease (lines 12-18 ofenqueue). Let Fi,min be the minimum value that Fi (t) may
assume in consequence of this event.
Since ∀t ∈ [t0 , t2 ] V (t) ≥ Sh (t0 ), according to (2), (5)and (18), Fi,min ≥ ⌊Sh (t0 )⌋σi + 2σi ≥ Sh (t0 ) − σh + 2σi =Fh (t0 ) − 3σh + 2σi > Fh (t0 ) > Fi (t2 ), which again would
imply the absurd Fi (t2 ) > Fi (t2 ).
The second case is that group i is not backlogged at time
t0 . As the event that would let the group become backlogged
after time t0 is the same that might have let Fi (t) decrease in
the other case, then, using the same arguments as above, wewould get the same absurd.
In the end, Sh (t2 ) ≤ Fi (t2 ) must hold.

The following theorem guarantees that EB is always ordered by virtual finish time (hence, as previously proven for
ER this order is never broken during QFQ operations).
Theorem 5: Set EB is ordered by group virtual finish time.
Proof: We will prove the thesis by induction. In the basecase EB = ∅ the thesis trivially holds. The only event uponwhich the the ordering of EB may change is when one or moregroups enters the set. The three events that may cause a group
to become blocked are 1) the enqueueing/dequeueing of apacket of a flow of an idle group j > i, which lets group j get alower virtual finish time than group i (groups with lower orderthan i can never block group i); 2) the enqueueing/dequeueingof a packet of a flow of group i itself, which lets the virtualfinish time of group i become higher than the virtual finish ofsome higher order group; 3) the growth of V (t), which causes
one or more groups to move from IB to EB.
With regard to the first event, it is worth noting that group j
can cause group i to become blocked only if group j becomesbacklogged or if Fj (t) decreases. Let t1 be the time instantat which one of these two events occurs and such that EB isordered up to time t1 . Thanks to Lemma 3, Fi (t1 ) ≤ Fj (t+1)
and hence the event cannot let group i become blocked.
Suppose now that, at time t1 , group i enters EB as aconsequence of either a packet of a flow of the group being
enqueued/dequeued or the growth of V (t). We will prove that,given two any blocked groups h < i and j > i, Fh (t1 ) ≤++Fi (t+
1 ) and Fi (t1 ) ≤ Fj (t1 ) hold (where Fi (t1 ) = Fi (t1 ) incase group i enters EB from IB).
With regard to a blocked group h < i, if group i enters EB
as a consequence of a packet enqueue/dequeue, then, from
Lemma 4 and the fact that, as Fi (t) is an integer multiple ofσi , Fi (t+1 ) ≥ Fi (t1 ) + σi , we haveFi (t+
1 ) − Fh (t1 )Fi (t1 ) + σi − Sh (t1 ) − 2σh

≥
≥0

(19)

where the last inequality follows from σi ≥ 2σh . On the other
hand, if group i enters EB from IB, then Si (t1 ) ≥ Sh (t1 )because either group h was already eligible before time t1 , orgroup h belonged to IB, which is ordered by virtual start time
according to [Sec.IV-3, item 2]. This implies Fi (t1 ) ≥ Fh (t1 )because σi ≥ 2σh .
With regard to a blocked group j > i, let b > j > i be
the highest order group that is blocking group j at time t.
Independently of the reason why group i enters EB, from
Lemma 4 we have+

Si (t ) ≤ Fb (t) ≤ Fj (t) − σj(20)

where the last inequality follows from Fb (t) < Fj (t) and thefact that both Fj (t) and Fb (t) are integer multiples of σj .
++Using (20) we have: Fi (t ) = Si (t ) + 2σi ≤ Fj (t) − σj +2σi , i.e.,+

Fi (t ) ≤ Fj (t)(21)

because, since j > i, σj ≥ 2σi .
Finally, we can prove the theorem that allows QFQ toquickly choose the groups to move from EB/IB to ER/IR.

11

Theorem 6: Group unblocking Let i be the group thatwould be served on the next packet dequeue at time t, andassume that there is no group j : j > i, Fj (t) = Fi (t); in this+case, if group i is actually served and Fi (t ) > Fi (t) or ifgroup i becomes idle at time t, then all and only the groups
in EB/IB and with order lower than i must be moved into
ER/IR.
Proof: To prove the thesis, we first prove that group i isthe only group that can block a group h < i. The proof isby contradiction. Suppose for a moment that a group j > iblocks group h. Since Fi (t) < Fj (t) must hold for group i not
to be blocked, and both Fi (t) and Fj (t) are integer multiplesof σi , then Fi (t) ≤ Fj (t)− σi . Combining this inequality with
Lemma 4, we get Sh (t) ≤ Fj (t) − σi and hence, consideringthat σi ≥ 2σh , Fh (t) = Sh (t) + 2σh ≤ Fj (t) − σi + 2σh ≤Fj (t). This contradicts the fact that group j blocks group h.
As a consequence, if Fi (t) increases, then, thanks to (19)and (21), all and only the blocked groups h < i become ready.
The same happens if group i becomes idle as a consequenceof a packet dequeue.

Theorem 2, then Si (t2 ) = Fi (t2 ) − 2σi > V (t2 ) − L − 2σi .
Hence we have :W k (t1 , t2 ) = φk V k (t1 , t2 ) ≥φk (S k (t2 ) − F k (t1 )) >k
φ (Si (t2 ) − (S k (t1 ) + σi )) >(24)kφ (V (t2 ) − L − 2σi − (V (t1 ) + σi )) =kkk
φ (V (t2 ) − V (t1 )) − φ L − 3φ σi >φk W (t1 , t2 ) − 2φk L − 3φk σi

VI. S ERVICE G UARANTEES

Comparison with other schedulers: in a perfectly fair ideal
fluid system such as the GPS server, B-WFIk = 0 (see [2]),whereas repeating the same passages of the proof in case ofexact timestamps (i.e., exact WF2 Q+ with stepwise V (t)), theresulting B-WFIk would be Lk + 2φk L.
The B-WFIs for S-KPS and GFQ have not been computed by their authors. However both these algorithms and
QFQ implement the same policy (WF2 Q+), differing only
in how they approximate the timestamps. Generalizing theprevious proof, we can show that GFQ has a slightly
lower B-WFIkGF Q = 2φk σi + 2φk L, whereas S-KPS has
B-WFIkS−KP S = B-WFIkQF Q = 3φk σi + 2φk L.
Relative fairness: The relative fairness bound, RFB, is definedas the maximum difference, over any time interval [t1 , t2 ] andpair of flows k and p, between the normalized service given
to two continuosly backlogged flows:

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.
A. Bit Guarantees
The B-WFIk guaranteed to a flow k is defined as:9
B-WFIk ≡ max φk W (t1 , t2 ) − W k (t1 , t2 )
[t1 ,t2 ](22)

where [t1 , t2 ] is any time interval during which the flow
is continuously backlogged; φk W (t1 , t2 ) is the minimum
amount of service the flow should have received according to
its share of the link bandwidth; and W k (t1 , t2 ) is the actual
amount of service provided by the scheduler to the flow.
Theorem 7: B-WFI for QFQ For a flow k belonging togroup i QFQ guarantees
B-WFIk = 3φk σi + 2φk L(23)

IMPORTANT NOTE: flow k belongs to group i, so φk σivaries between Lk and 2Lk and the B-WFIk is always bounded
by a small multiple of the packet size, same as for other nearoptimal schedulers. In addition, Theorem 1, as well as thetheorems and lemmas it depends on, are proven without everusing the link rate. Hence this theorem holds also for timevarying link rates.
Proof: In this proof we express timestamps (V (t), F k (t),etc.) as functions of time to avoid ambiguities. We consider
two cases. The first one is when flow k is eligible at time t1 .
In this case, as for the virtual time V k (t) of flow k in the realsystem, consider that V k (t1 ) ≤ F k (t1 ), and V k (t2 ) ≥ S k (t2 )trivially hold. In addition, ∀t, V (t) ≤ Fi (t) + L as proven in
9 This definition is slightly more general than the original one in [2], wheret2 was constrained to the completion time of a packet.

The last inequality follows from the fact that, because of theimmediate increment of V (t) as a packet is dequeued (seeupdateV()), V (t2 ) − V (t1 ) ≥ W (t1 , t2 ) − L.
The other case is when flow k is not eligible at time t1 .
This implies that V k (t1 ) is exactly equal to S k (t1 ). Hence,
considering that S k (t1 ) ≤ V (t1 ) + σi , we have:
W k (t1 , t2 )φ (S (t2 ) − S k (t1 ))φk (Si (t2 ) − S k (t1 ))kφ (V (t2 ) − L − 2σi − (V (t1 ) + σi )φk W (t1 , t2 ) − 2φk L − 3φk σi
k

k

≥
≥
>
>

(25)

W k (t1 , t2 ) W p (t1 , t2 )
(26)
−
φk
φp
∀k,p,[t1 ,t2 ]Consider two flows, k and p, belonging, respectively, togroups i and j, and continuously backlogged during a timeinterval [t1 , t2 ]. Equation (6), Theorem 2, and the fact thata group is served only if eligible, give an upper bound to
the normalized service received by a flow in the interval,
k
1 , t2 )resulting in W (t≤ W (t1 , t2 ) + L + 4σi . The proof
φkof Theorem 7 establishes a lower bound for the normalized
service. Substituting these two extremes in (26) and taking
the maximum over all possible flow/group pairs, we have
RFB ≡

max

RFB ≤ 3L + 4 max(σi , σj ) + 3 min(σi , σj )(27)kAs for GFQ and S-KPS we have RF BS−KP S = 2L+ L
+
φk

Lp
Lk
Lp
φp +3(σi +σj ) and RF BGF Q = 2L+ φk + φp +2(σi +σj ). To

put the bound for FRR in a form that allows it to be comparedmore easily against the bound for QFQ, we assume that all
packets have the same length (otherwise RF BF RR may behigher), and get RF BF RR = max(4σi + φLk + 10σj , 4σj +L
φp + 10σi ) (in the best case for FRR, i.e., for C = 2).

12
s3

s4

B. Time Guarantees
s0

Expressing the service guarantees in terms of time is only
possible if the link rate is known. The T-WFIk guaranteed toa flow k on a link with constant rate R is defined as:
Qk (t+a)(28)
T-WFIk ≡ max tc − ta −φk R
where ta and tc are, respectively, the arrival and completiontime of a packet, and Qk (t+a ) is the backlog of flow k justafter the arrival of the packet.
Theorem 8: T-WFI for QFQ For a flow k belonging togroup i QFQ guarantees
1(29)
R
The proof, omitted for brevity, is conceptually similar tothe one for the B-WFI. Here again, note that the factor σi /R(or equivalent) is present in the T-WFI of any near-optimalscheduler. For comparison, a perfectly fair ideal fluid system
would have T-WFIk = 0, whereas for WF2 Q+, which uses
exact timestamps, repeating the same passages of the proofk+ 2L)/R
yields T-WFIk = ( L
φkSame as for the B-WFI, the T-WFI of S-KPS happens tobe equal to that of QFQ, whereas the T-WFI of GFQ is lower
than that of QFQ by σi /R. Finally, about FRR, as alreadyshown in Section II, the T-WFI of FRR in a realistic scenario
is not lower than (24σi + 19L) R1 .

k0

r0

r1

r2

s1

k1

s2

k2

k3

k4

Fig. 7. Simulated scenario. Flows f0 and f1 are originated by nodes S0 and
S1 , whereas S2 generates 50 CBR flows to perturbate the traffic. All routers
run the same scheduling algorithm.

T-WFIk = (3σi + 2L)

VII. E XPERIMENTAL R ESULTS
We evaluate the performance of QFQ by comparing its service
properties and actual run times with those of other schedulingalgorithms. Due to space limitations we only report a subset
of our experimental results. The algorithms selected for theexperiments presented here are DRR, to represent the classof high performance round robin schedulers; WF2 Q+, as areference point for its optimal service properties, and S-KPS,
as an 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 theirsupport 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] and wecompared it to DRR, S-KPS and WF2 Q+.
The network topology used in the simulations is inspiredby the one used in [7], and is depicted in Fig. 7. Links R0 -R1
and R1 -R2 have 10 Mbit/s bandwidth and 10 ms propagation
delay; all the other links have 100 MBit/s and 1 ms. The
observed flows are f0 (a 32 Kbit/s CBR from S0 to K0 ), andf1 (a 512 Kbit/s CBR from S1 to K1 ). Interfering flows area 512 Kbit/s CBR from S1 to K1 (same as f1 ), fifty 160
Kbit/s CBR flows from S2 to K2 , and two best effort flows,
one from S3 to K3 and one from S4 to K4 , each generated
from its own Pareto source with mean on and off times of
100 ms, α = 1.5, and mean rate of 2 MBit/s (larger thanthe unallocated bandwidth of the links between the routers, inorder to saturate their queues).

DRR
S-KPS
QFQ
WF2 Q+

f0 (32 Kbit/s)
avg ± stddev

max

f1 (512 Kbit/s)
avg ± stddev

max

134.87 ± 34.28
46.28 ± 5.42
43.16 ± 5.60
34.39 ± 0.35

216.99
59.91
47.56
35.20

126.32 ± 30.64
22.59 ± 0.60
22.76 ± 0.61
22.59 ± 0.61

206.40
23.34
23.33
23.33

TABLE IIS IMULATION RESULTS FOR THE TOPOLOGY OF F IG . 7. E ND - TO - END
DELAYS ( AVERAGE / STDDEV, MAX ) IN MS FOR THE OBSERVED FLOWS .

Table II shows the end-to-end delays (average, stddev andmaximum) experienced by f0 and f1 during the last 15
seconds of simulation (the total simulation time was 20 s, thefirst five where not considered to let the values settle). QFQ
performs as expected, with delays similar to the ones measured
for S-KPS, given the common nature that the two schedulers
share. DRR shows much larger delays and deviations, whichis also expected because of the inherent O(N ) WFI of thisfamily of schedulers.
The “max” value for the low bandwidth flows is in goodaccordance with the WFI values computed in Section VI: thedelay component inversely proportional to the flow’s rate isbest for WF2 Q+ and grows as we move to QFQ, S-KPS
and DRR. The larger standard deviation of the delays in
QFQ and S-KPS, compared to WF2 Q+ comes from the useof approximate timestamps, which gives QFQ and S-KPS a
WFI larger than that of WF2 Q+. Also note how the effect ofapproximations is higher for f0 (a low rate flow) than for f1 ,which is a high rate flow.
B. Run-time Performance
Together with the good service guarantees, the most interesting
feature of QFQ is the constant (independent of the number offlows) and small per-packet execution time, which makes thealgorithm extremely practical.

13

Fig. 8. Our testing environment: a controller drives the scheduler modulewith programmable sequences of requests.

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
and the total amount of traffic queued in the scheduler. These
parameters may impact the behaviour of the schedulers, byinfluencing the code paths taken by the algorithms, and thememory usage and access patterns. The latter are extremely
important on modern CPUs, where cached and non-cachedaccess 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 ofenqueue() and dequeue() operations, but the problem is not
relevant. First, in the steady state, there is approximately thesame number of calls for the two functions. Only when alink is severely overloaded the number of enqueue() will bemuch larger than its counterpart, but in this case dropping apacket (in the enqueue()) is very inexpensive. Second, in mostalgorithms it is possible to move some operations between
enqueue() and dequeue(), so it is really the sum of the twocosts that counts to judge the overall performance of analgorithm.

Test cases: our tests include the following algorithms:
NONE the baseline case, measures the cost of packet generationand disposal, including memory-touching operations. Packets generated by the controller are stored in a FIFO queue,
and extracted when the controller calls dequeue();
FIFO the simplest possible scheduler, an unbounded FIFO queue.
Compared to the baseline case, here we exercise thescheduler’s API, which causes one extra function calls andcounter updates on each request;
DRR the Deficit Round Robin scheduler, where each flow has aconfigurable quantum size;
QFQ QFQ, as described in this paper. We use 19 groups, packet
sizes up to 2 KBytes, and weights between 1 and 216 ;S-KPS our implementation from the description in [9], with someminor optimizations, and revised by the original authors.

Internal parameters (e.g., lmin , lmax ) have been set tovalues similar to those used for QFQ;WF2Q+the WF2 Q+ algorithm taken from the FreeBSD’s dummynet code. It has O(log N ) scaling properties, but it
is of interest to determine the break-even point between
schedulers with different asymptotical behaviour.

Flow distributions: we ran extensive tests with different combinations and number of flows (from 1 to 128K), with various
weight and packet size distributions. These configurations
show how the schedulers depend on the number of flow, 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 5N and 30N packets,
respectively (where N is the number of active flows), and thencompletely drain the scheduler; FULL keeps the scheduler
constantly busy, with a total backlog between 3N and 30N
packets. The bursty patterns try to reproduce operation on anormally unloaded link, whereas the FULL pattern mimics the
behaviour of a fully loaded link driven by TCP or otherwise
adaptive flows, which modify their offered load depending on
available bandwidth.
enqueue() + dequeue() time, ns
700
WF2Q+
S-KPS

600
500
time (ns)To study the actual performance of our algorithm, andcompare it with other alternatives, we have measured the C
versions of QFQ and various other schedulers, including SKPS, which we implemented as part of the Dummynet [4]traffic shaper, running on FreeBSD, Linux and Windows.

400
300
QFQ

200

DRR
FIFO
NONE

100
0
1

4

16

64

256
1k
Flows

4k

32k

Fig. 9.
Scaling properties of the various algorithms. WF2 Q+ grows as
O(log N ), reaching 2000 ns for 32k flows (see Table III).

C. Results
Table III and Figure 9 report some of the most significant
test results, measured on a low-end desktop machine (2.1GHz
CPU, 32-bit OS, 667MHz memory bandwidth), with code
compiled with gcc -O3. Different platforms perform proportionally to the platform’s performance (e.g., a 3 GHz Nehalem
CPU is almost twice as fast; a 200 MHz MIPS CPU on a lowcost Access Point is 30-40 times slower in running the same
experiments). Similarly, the point where cache effects become
visible varies depending on available cache sizes.
Figure 9 shows clearly that all O(1) algorithms do notdepend on the number of flows, whereas WF2Q+ shows the
expected O(log N ) behaviour. We see that DRR and FIFO
are really inexpensive, and most of the time in the test is
consumed by the packet generator (the curve labeled NONE
in the figure), which accounts for approximately 60 ns per
enqueue/dequeue pair. All schedulers, and the generator itself,

14Time (nanoseconds) for an enqueue()/dequeue() pair andpacket generation. Standard deviations are within 3% of
the average (not reported to reduce the clutter in the table)
8 flows
NONE FIFO DRR QFQ S-KPS WF2 Q+
SMALL
62
80
102
168
458
356
LARGE
60
82
104
162
530
350
FULL
60
80
102
163
543
344
512 flows
NONE FIFO DRR QFQ S-KPS WF2 Q+
SMALL
62
82
111
170
468
732
LARGE
65
84
110
172
550
730
FULL
64
85
110
175
560
740
32768 flows
NONE FIFO DRR QFQ S-KPS WF2 Q+
SMALL
90
114
185
230
550
1900
LARGE
103
126
158
234
603
1880
FULL
62
117
147
222
601
1690
1:32k,2:4k,4:2k,8:1k,128:16,1k:1 flows
NONE FIFO DRR QFQ S-KPS WF2 Q+
SMALL
91
120
167
247
598
1868
LARGE
107
131
160
250
595
1734
FULL
92
119
160
255
612
1715
TABLE IIIA SUBSET OF EXPERIMENTAL RESULTS , FOR DIFFERENT FLOW
DISTRIBUTIONS AND LOAD CONDITIONS .

show a modest increase of the execution time as the numberof flows goes (on this particular platform) above 4k. This is
likely due to the working set of the algorithm overflowing
the available cache, which causes cache misses that impact
on the total execution time. In absolute terms, QFQ behaves
really well, consuming about 100-110 ns (excluding the traffic
generation) up to the point where cache misses start tomatter. S-KPS also has reasonably good performance, taking
approximately 500 ns (2.5 . . . 3 times the cost of QFQ).
Finally, we would like to note that while WF2Q+ has
obvious scalability issues, for configurations with a small
number of flows it can still be a viable alternative.
The final block of the table reports the result of experimentswith a large mix of flows using different weights. This casedoes not show significant differences with the case where allflows have the same parameters.
Table III and Figure 9 and other experiments not reported
here, show that algorithms can have peculiar behaviours incertain 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 flowfrom the group leaves the group empty and triggers unnecessary calls to unblock groups() and make eligible(). S-KPS
seems to have slightly better performance in the presence ofsmall 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 tobe processed. These variations tend to be small in absoluteand relative terms, but are measurable as we are dealing withextremely fast algorithms where even small changes in the
instruction counts affect the performance.

QFQ is a significant step towards the feasibility of software
packet processing on 10 Gbit/s links. At these speeds, the perpacket budget varies between 67.2 and 1230 ns per packet (for64 and 1518 byte frames). QFQ’s speed (100-150 ns/pkt) fits
well in the budget, together with recent results on fast packet
I/O [14].
VIII. C ONCLUSIONSIn this paper we presented QFQ, an approximate implementation of WF2 Q+ which 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 very small and localized data structures, which makeit amenable to a hardware implementation. Together with adetailed description of the algorithm, we provide a theoreticalanalysis of its service properties, and present an accurate
performance analysis, comparing QFQ with a variety of otherschedulers. The experimental results show that QFQ lives up
to its promises: it is faster than other schedulers with optimal
service guarantees, only two times slower than DRR, andoperates, even in software, at a rate compatible with 10Gbit/s
interfaces.
QFQ and the other algorithms analyzed here are available
at [5] as well as part of standard distributions of FreeBSD
and Linux, and are included in the Dummynet [4] traffic
shaper/network emulator for FreeBSD, Linux and Windows.
R EFERENCES[1] http://www.isi.edu/nsnam/ns/.
[2] Jon C. R. Bennet and Hui Zhang. Hierarchical packet fair queueing
algorithms. IEEE/ACM Transactions on Networking, 5(5):675–689,
1997.
[3] Jon C. R. Bennett and Hui Zhang. WF2 Q: Worst-case fair weighted fairqueueing. Proceedings of IEEE INFOCOM ’96, pages 120–128, March
1996.
[4] Marta Carbone and Luigi Rizzo. Dummynet revisited. ACM SIGCOMM
Computer Communication Review, 40(2):12–20, 2010.
[5] Fabio Checconi, Paolo Valente, and Luigi Rizzo. QFQ: Efficient Packet
Scheduling with Tight Bandwidth Distribution Guarantees (full paperand experimental code). http://info.iet.unipi.it/∼luigi/qfq/.
[6] Chuanxiong Guo. SRR: An O(1) time complexity packet scheduler forflows in multi-service packet networks. Proceedings of ACM SIGCOMM
2001, pages 211–222, August 2001.
[7] Chuanxiong Guo. G-3: An O(1) Time Complexity Packet Scheduler
That Provides Bounded End-to-End Delay. Proceedings of IEEE
INFOCOMM 2007, pages 1109–1117, May 2007.
[8] Martin Karsten. SI-WF2 Q: WF2 Q approximation with small constantexecution overhead. Proceedings of INFOCOM 2006, pages 1–12, April
2006.
[9] Martin Karsten. Approximation of generalized processor sharing withstratified interleaved timer wheels. IEEE/ACM Transactions on Networking, 18(3):708–721, 2010.
[10] Abdesselem Kortebi, Luca Muscariello, Sara Oueslati, and James
Roberts. Evaluating the number of active flows in a scheduler realizing
fair statistical bandwidth sharing. SIGMETRICS Performance Evaluation
Review, 33(1):217–228, 2005.
[11] Luciano Lenzini, Enzo Mingozzi, and Giovanni Stea. Tradeoffs between
low complexity, low latency, and fairness with deficit round-robinschedulers. IEEE/ACM Transactions on Networking, 12(4):681–693,
2004.
[12] Larry L. Peterson and Bruce S. Davie. Computer Networks - A systems
Approach. Morgan Kaufmann Publishers, 2010.
[13] Sriram Ramabhadran and Joseph Pasquale. The stratified round robinscheduler: design, analysis and implementation. IEEE/ACM Transactions on Networking, 14(6):1362–1373, 2006.
[14] Luigi Rizzo. Revisiting network I/O APIs: the netmap framework.
Communications of the ACM, 55(3):45–51, March 2012.

15[15] M. Shreedhar and George Varghese. Efficient fair queuing using deficit
round robin. IEEE/ACM Transactions on Networking, 4(3):375–385,
1996.
[16] S.J.Golestani. A self-clocked fair queueing scheme for broadband
applications. Proceedings of IEEE INFOCOM ’94, pages 636–646, June
1994.
[17] Donpaul C. Stephens, Jon C.R. Bennett, and Hui Zhang. Implementing
scheduling algorithms in high-speed networks. IEEE Journal on Selected
Areas in Communications, 17(6):1145–1158, June 1999.
[18] Dimitrios Stiliadis and Anujan Varma. A general methodology for designing efficient traffic scheduling and shaping algorithms. Proceedingsof IEEE INFOCOM ’97, pages 326–335, April 1997.
[19] Ion Stoica and H. Abdel-Wahab. Earliest eligible virtual deadline first:
A flexible and accurate mechanism for proportional share resource
allocation. Technical Report 95-22, Department of Computer Science,
Old Dominion University, November 1995.
[20] Subhash Suri, George Varghese, and Girish Chandranmenon. Leap
forward virtual clock: A new fair queuing scheme with guaranteed delays
and throughput fairness. Proceedings of IEEE INFOCOM ’97, pages
557–565, April 1997.
[21] Paolo Valente. Exact gps simulation and optimal fair schedulingwith logarithmic complexity. IEEE/ACM Transactions on Networking,15(6):1454–1466, 2007.
[22] Paolo Valente. Extending WF2 Q+ to support a dynamic traffic mix.
Proceedings of AAA-IDEA 2005, pages 26–33, June 2005.
[23] Jun Xu and Richard J. Lipton. On fundamental tradeoffs between delay
bounds and computational complexity in packet scheduling algorithms.
IEEE/ACM Transactions on Networking, 13(1):15–28, 2005.
[24] Xin Yuan and Zhenhai Duan. Fair round-robin: A low complexity packet
scheduler with proportional and worst-case fairness. IEEE Transactions
on Computers, 58(3):365–379, 2009.