Analysis of Fair Queueing schedulers in Real Systems
Luigi Rizzo
Universita‘ di Pisa

Paolo Valente
Universita‘ di Modena e Reggio Emilia

Abstract2

O(log N ) cost in the number of flows is considered too
high, there have been several proposal with O(1) complexity and only constant deviation from the optimalschedulers [6, 9, 4]. One of them, QFQ [4] has a speed
comparable to robin schedulers while giving the same
quasi-optimal service guarantees of the best fair queueing schedulers. It is also readily available in major operating systems, either natively (FreeBSD, Linux) or as
part of the dummynet traffic shaper [3].
An element is missing in the picture though. The
analysis of packet schedulers is normally done assuming that the communication device can report the exact
number of bits transmitted at any time, and is directly
attached to the scheduler with no interposed buffering. None of these assumptions holds in practice. First,
network interfaces operate on a packet-by-packet basis,and do not export a real-time indication of the numberof bits transmitted. Second, communication links, especially the high-speed ones, are equipped with FIFO
queues (sometimes even large ones) to drive the device
and absorb the latency and jitter in the hardware andsoftware components that produce packets: memories,
buses, interrupt service routines, etc.. The existence of
the FIFO prevents the link from becoming idle whileaccessing the next packet to be transmitted, but its implicit principle of operation is that the link appears as
having a service rate which is bursty and sometimes
much higher than what it is really capable of.
The amount of buffer can be large, even in the orderof tens of packets on very fast links, and the device iscapable of absorbing large batches of packets at once.
This causes two phenomena, which this paper is addressing.
First, the fact that a link may absorb large bursts
in very short intervals may cause traffic to be subject
to a delay which is, intuitively, at least as large as the
FIFO size. Second, the extra delay with respect to thenon-FIFO case can even exceed the size of the FIFO,
due to the way the scheduler is implemented. The
phenomenon is relevant especially in high speed links,
where FIFOs can be significantly large.
In this paper we consider a class of fair queueing

2

Research on fair queueing schedulers (WF Q, WF Q+
and approximated variants) has led to the design of very
efficient algorithms, whose performance ranges from optimal fairness and delay guarantees at O(log N ) cost, toquasi-optimal guarantees at O(1) cost.
These guarantees have been computed assuming thatthe number of bits transmitted by the communication
link is known at any time instant, and that the scheduler
is directly attached to the communication link with nointerposed buffering.
Both assumptions are unfortunately unrealistic.
Real communication devices normally include FIFOs,
possibly very deep ones, between the scheduler and thetransmit unit, to avoid that the links becomes idle while
the next packet to transmit is selected. The presenceof the FIFO has a huge effect on the service guarantees of the scheduler, introducing extra error terms that
may be significantly larger than those computed ignoring buffering.
In this paper we make two contributions: i) provide
analytical bounds of the effect of FIFOs on the service
guarantees of fair queueing schedulers, and ii) put theotherwise dry formulas into practical scenarios, by instantiating the various parameters with realistic values,and comparing several schedulers in presence of variable
FIFO size, packet sizes and flow weights. These results
should help designers to make informed decisions andsound tradeoff when building systems.

1.

INTRODUCTION

Research on packet scheduling has explored many
theoretical and practical aspects related to the design
and implementation of these systems. Several service
metrics such as the Relative Fairness [8] and Worstcase Fairness [2] have been defined to determine thequality of a schedulers. We know how closely a packetbased scheduler can emulate an ideal, fluid system [7]providing perfect bandwidth sharing, and the complexity bounds involved in such emulation [12]. Optimalalgorithms matching these lower bounds have been defined [11]. For high speed schedulers, when even the1schedulers that include WF2 Q+ and its approximatedvariants (this class has been defined for the first timein [6]), and make the following contributions: i) we propose a simple modification to these schedulers to approximate the number of bits transmitted, and we provide an analysis of the guarantees that these schedulers
provide if they are modified as suggested and if they
are followed by a FIFO before the actual communication link; ii) we instantiate the result for WF2 Q+ andits approximated variants. To the best of our knowledge, there are no published results on either of the twoitems. Furthermore, the second contribution is very important in practice because it helps designing systems(choosing algorithms and FIFO sizes) to match the required speed of operation and service guarantees.
The rest of the paper is structured as follows. Section 2 provides a description of the problem that we are
addressing, with an example to clarify how the issue
has practical consequences. Section 3 briefly describes
related work. Section 4 defines the terms used in the paper, and some background on timestamp-based packet
schedulers. Readers familiar with the topic may skim
over this part, but please refer to it to make sure that
there is no ambiguity on the system model and definitions used here (there are some differences in the literature). The core of the paper starts with Section 4.4
where we define a realistic model of a link scheduler
with output FIFO, and summarize our proof technique.
Supporting lemmas are presented in Section 5, whereas
Section 6 contains the proofs of our main results and a
discussion of their implications.

2.

P1
...
...

A

...
...

Pn
Q

t
P1
...

...

...

B

Pn
Q
t

Figure 1: The example in Section 2: squares
represent packet arrivals, crosses are departures,
flow Q has a much higher weight than the Pi ’s.
Case A: an ideal link without fifo dequeues one
packet at a time, insuring a prompt and smoothservice to flow Q. Case B: a scheduler is followed
by a deep FIFO. A large number of low-weightflows are served immediately, delaying service to
Q until the FIFO runs dry.
Assume a system where at some initial time a setof packets arrives at the scheduler for flows P1 ..PN , allwith the same weight φ1 . Shortly afterwards, the scheduler receives a request for new transmission, and after
another short interval a set of packets arrive for flow Q,
which has a much higher weight than the other flows(for simplicity assume all packets have length L). All
packets arriving initially will be marked with the same
< s0 , s0 + L/φ0 > pair, as the virtual clock does notadvance during the arrival of the burst.
Figure 1-A shows the case of a scheduler driving an
ideal link. P1 first packet is served first, but when thescheduler is invoked next it will start serving packets
from Q according to the weights of the backlogged flows.
Figure 2-A shows the virtual time markings corresponding to this case.
Conversely, Figure 1-B represents the evolution of thesystem with a deep FIFO between the scheduler andthe link. After the arrival of the initial packets, thescheduler is requested to refill the FIFO at once. The
subsequent packets for Q will then have to wait a longtime before being dequeued. Also, the timestamps ofQ’s packets will be much higher (see Figure 2-B) than in
the other case due to the initial burst of packets served.
Eventually the correct rate will be granted to Q, but
only after a possibly large initial delay.
In contrast, in the idealized system without a FIFO
between the scheduler and the link, the packet for P1
will be served immediately, but the virtual clock will
only advance by a modest amount, and this will permit

DESCRIPTION OF THE PROBLEM

We describe our problem with an example, shownin Figure 1. A weighted-fair-queueing scheduler is incharge of arbitrating access to a shared link for a number of flows. The scheduler assigns the link to flows proportionally to a parameter φk , called the flow’s weight.
The ideal, infinitely precise subdivision of the link’s
capacity (often called “fluid scheduling”) is approximated on a packet-by-packet basis, trying to serve flows
as close as possible to what would happen in a fluid system. To this end, the scheduler1 marks a packet i witha “virtual” start time si (think of it as derived froma “virtual clock” advancing with the actual number ofbits transmitted by the link, and a virtual finish timefi = si + li /φk where li is the length of the packet.
Whenever the link becomes idle, the scheduler selects
for transmission the packet with minimum fi (undersome constraints), and then waits until the transmission is complete to select the next one.
1
This is a simplified (but correct for the example at hand)description of how a fair queueing scheduler works. A complete definition of the algorithm will be presented in Section 4.2.

2

P1

Pn

introducing a metric similar to the T-WFI. Followup
works include WF2 Q+, which, using a simplified virtualtime function reduces the complexity to O(log N ) (theoriginal WF2 Q had O(N ) complexity; much later, Valente [11] proved that also WF2 Q can be implementedin O(log N ) time). Xu and Lipton [12] then prove anΩ(log N ) bound on the time complexity for any exact
GPS emulation. The tradeoffs between complexity andservice guarantees have been explored in a number ofworks [6, 9, 4], presenting O(1) schedulers with quasioptimal service guarantees. Constant-time fair queueing schedulers have also been built starting from RoundRobin schedulers, some of which [13] integrate concepts
used in virtual-time based schedulers to achieve optimal
service guarantees.
With only one exception, the analysis in all the papers cited so far has been done in the assumption thatthe number of bits transmitted is known at any time
instant and that any queueing occurs in the scheduler:
once a packet leaves the scheduler, it immediately starts
being transmitted on the output link.
To our knowledge, there is only one recent work [5]that still carries out analysis assuming that the numberof bits transmitted is known, but that does account for
output buffering. The latter is considered because thescheduler proposed in this work has a large worst-caseper-packet execution time, and an output buffer could
absorb part of this time. The analysis in [5] is however limited to the evaluation of the time that a packet
spends in the buffer, and does not address the impact
on the service properties of the scheduler.

A

Q

Vk(t)

P1

B
Pn
Q

Vk(t)

Figure 2: Same example as in Figure 1, this timeshown in terms of packet timestamps. In case B,
the immediate service of many low-weight packets makes the start time for Q’s packets muchhigher than in case A.
serving Q with the proper rate (in the example, half ofthe total link capacity) almost right away.
As a result, with the same sequence of (real time)
arrivals to the scheduler, and a link with the same capacity, packet Q might be subject to a much higher
delay, possibly even exceeding the size of the FIFO.
The purpose of this paper is to evaluate how large isthe additional delay, and how it is affected by the FIFO
size and the weights of the flows. Considering that thetradeoffs to build efficient (O(1) instead of O(log N )time) schedulers is paid in terms of a small reorderingof output packets, it is important to understand how
the effect of the FIFO compares to the previous approximation.
Note that the example given above is extremely realistic. On many traffic sources or routers, incoming
traffic often comes in bursts, (corresponding to the processing of a receive interrupt, or the generation of a large
TCP segment split into packets). Similarly, communication hardware (especially high speed NICs) have large
output queues or internal FIFOs to make sure that thelink does not starve between subsequent packet transmissions.

3.

4. DEFINITIONS AND SYSTEM MODEL
In this Section we define the concepts and symbols
used in the scheduling literature, which sometimes uses
different notations for the same concepts. For convenience, all symbols used in this paper are listed in Table 1.
For ease of exposition, we often use the notation
f (t1 , t2 ) ≡ f (t2 ) − f (t1 )where f (t) is a function of the time.
We assume that any discontinuous function of the timeis left-continuous, i.e., if t0 is a discontinuity point fora function f (t), then f (t0 ) = limǫ→0 f (t0 + |ǫ|), andf (t−0 ) = limǫ→0 f (t0 − |ǫ|).

RELATED WORKThe analysis of packet scheduling starts with the seminal work by Parekh and Gallager [7] who show how a
fluid system (GPS) can be emulated on a packet bypacket basis using a “virtual time” concept. Subsequently, Bennet and Zhang [2] show that a simplistic
emulation of a fluid system may lead to large burstiness in the output. They introduce the concept of “eligibility” and design WF2 Q, the first of a family of algorithms with bounded delay with respect to GPS, also

4.1 System model
Consider a system as in Figure 3, in which N packet
flows (defined in whatever meaningful way) share a common transmission link serving one packet at a time. The
link has a time-varying rate, with W (t) being its “workfunction”, or the total number of bits transmitted in[0, t]. A system is called work conserving if the link isused at full capacity whenever there are packets queued.
3Symbol∗k

Meaning
A superscript indicates a quantity related to aflow∗mA subscript indicates a quantity related to apacketN
Total number of flowsh, kFlow index
L, Lk
Max length of any packet in the system/flowφkWeight of flow k
lkLength of the head packet in flow k; lk = 0 when
the flow is idle∗(t1 , t2 )Given a generic function ∗(t), the notation∗(t1 , t2 ) ≡ ∗(t2 ) − ∗(t1 ) indicates the difference
between the values in t2 and t1
W (t), W k (t) The “work function”, i.e. number of bits transmitted (globally, or for flow k) in [0, t]
V (t), V k (t)System/flow virtual time, see Eq. (3)Sk, F k,Exact virtual start and finish times of flow k or
Sm , F m
packet m, see Eq. (2)Ŝ k , F̂ k ,Approximated flow/packet timestamps, see SecŜm , F̂mtion 4.3of service W k (t1 , t2 ) received by a flow and the total
amount of service W (t1 , t2 ) delivered by the system inthe time interval [t1 , t2 ] are measured in number of bits
transmitted during the interval.
The analysis of the schedulers considered in this paper uses the concept of corresponding systems [2, Definition 1]: two systems are corresponding if they have thesame work function W (t), serve the same set of flows
with the same weights in both systems, and are subject
to the arrival pattern.

4.2 WF2 Q+
The schedulers we consider are approximated variants of the WF2 Q+ algorithm, and we call them AFQ(Approximated Fair Queueing) schedulers.
Here we outline the WF2 Q+ algorithm for the case ofa variable-rate link (see [1, 10] for a complete description). WF2 Q+ is a packet scheduler that approximates,on a packet-by-packet basis, the service provided by acorresponding work-conserving ideal fluid system thatdelivers the following, almost perfect bandwidth distribution over any time interval during which a flow is
continuously backlogged:k

W (t), W (t) The “work function” describing the input to the
FIFOk

V (t), V (t)
k

S ,F

k

S̃ k , F̃ k
B(t)Qk (t)

System/flow virtual time corresponding to W (t)Counterparts of S k and F k obtained using V (t)instead of V (t) in (2)Counterparts of Ŝ k and F̂ k obtained using V (t)instead of V (t) in Eq. (2)The set of backlogged flows at time t
Backlog of flow k at time t

W k (t1 , t2 ) ≥ φk W (t1 , t2 ) − (1 − φk )LThe fluid and the packet system differ in that the former may serve multiple packets in parallel, whereas thelatter has to serve one packet at a time, and is non preemptive. To define the scheduling policy of WF2 Q+,
we need to introduce the concept of eligibility, first defined in [2, Section 3]: a packet is defined as eligible ata given time instant if it has already started in the fluid
system by that time. Accordingly, we define a flow as
eligible if its head packet is eligible.
WF2 Q+ operates as follows. Each time the link isready, the scheduler starts to serve, among the eligible
packets, the next one that would be completed in thefluid system; ties are arbitrarily broken. WF2 Q+ is awork-conserving on-line algorithm, hence it succeeds infinishing 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 time function V k (t) that grows as the normalized amount of service received by the flow (i.e., actual
service received, divided by the flow’s weight). Besides,
when the flow turns from idle to backlogged, V k (t) is
set to the maximum between its current value and thevalue of a further function, the system virtual time V (t),defined below.
In addition to V k (t), each flow is conceptually2 associated with a virtual time Vfkluid (t) also in the fluid sys-

Table 1: Definitions of the symbols used in thepaper.
W(t)

A

(1)

AFQ (theoretical)

Figure 3: The system model used in the literature: a scheduler (AFQ) drives directly an ideal
link with work function W (t).

A scheduler (the AFQ block in the figure) sits between
the flows and the link: arriving packets are immediately
enqueued, and the next packet to serve is chosen anddequeued by the scheduler when the link is ready.
In our model, each flow k is assigned a fixed weightφk >P0. Without losing generality, we assume thatkφ= N
k=1 φ ≤ 1.
A flow is defined backlogged /idle if it owns/does not
own packets not yet completely transmitted. We call
B(t) the set of flows backlogged at time t. Each flowuses a FIFO queue to hold the flow’s own backlog.
We call head packet of a flow the packet at the headof the queue, and lk its length; lk = 0 when a flow
is idle. We say that a flow is receiving service if oneof its packets is being transmitted. Both the amount2
this parameter is not needed in the implementation but we
use it to prove Lemma 2.

4

tem. Vfkluid (t) is computed with the same rules as V k (t),but, of course, since the amount of service received bya flow in the packet system scheduled by WF2 Q+ may
differ with that in the corresponding fluid system, thevalues of V k (t) and Vfkluid (t) may differ.
For every packet of flow k, we define the virtual startand finish time of the packet as the value of V k (t) when
the packet starts and finishes to be served in the fluid
system. Using this definition, we define the virtual startand finish time of flow k, S k (t) and F k (t), as the virtual start and finish times of its head packet at timet. These timestamps need to be updated only when theflow becomes backlogged, or when its head packet is dequeued. On these events S k (t) and F k (t) are updated
as follows: max(V (tp ), F k (t−p )) on newlykbacklogged flow;
S (tp ) ← k −F (tp )
on packet dequeue;
F k (tp ) ← S k (tp ) + lk /φk(2)
where tp is the time when a packet enqueue/dequeue occurs, and lk is the packet size. V (t) is the system
P kvirtualtime function defined as follows (assuming
φ ≤ 1):k
V (t2 ) ≡ max V (t1 ) + W (t1 , t2 ), min S (t2 )
(3)

W(t)

B

W(t)

AFQ
FIFO

Figure 4: A: the system model used in the literature, ignoring the presence of the FIFO and assuming W (t) is known exactly within the scheduler. B: a real system, made of an AFQ scheduler feeding a dequeue unit with work function
W (t), followed by a FIFO and the output link.
C: the corresponding fluid system for the firstpart of B), serving multiple packets at a time,with the same work function W (t).
stages in the algorithm, making them constant-time operations.
The way approximations are computed varies, but inall cases we have:k∈B(t2 )Note that the instantaneous link rate needs not be known
to update V (t), and just W (t1 , t2 ) (the amount of datatransferred in [t1 , t2 ]) suffices. At system start up, V (0) =0, S k (0) ← 0 and F k (0) ← 0. The scheduling policy of
WF2 Q+ is implemented using only V (t), and the virtual start and finish times of the flows, as detailed in
the next paragraph.

S k (t) − ∆S k ≤ Ŝ k (t) ≤ S k (t) ≤F k (t) ≤ F̂ k (t) ≤ F k (t) + ∆F k

(4)

where ∆S k and ∆F k are non-negative quantities (∆S k =∆F k = 0 in WF2 Q+). For brevity, hereafter we use thegeneric name AFQ (Approximated Fair Queueing), torefer to any of these variants and to WF2 Q+ itself.
AFQ uses the approximated timestamps to computethe virtual time, i.e., it uses Ŝ k (t2 ) instead of S k (t2 )in (3), and to choose the next packet to transmit (Sec 4.2.1),
while it uses the exact timestamps to charge flows forthe work received (Eq. (2)).

4.2.1 Scheduling decisions
In terms of virtual times, flow k is eligible at time
t if V (t) ≥ S k (t). In addition, the fluid system serves
flows so as to complete packets in virtual finish timeorder [1, 10]. WF2 Q+ can then be implemented asfollows: each time the next packet to transmit is requested, the scheduler (dequeues and) returns the headpacket of the eligible flow with the smallest virtual finish time. The second argument of the max operator in
Eq. (3) guarantees that the system is work-conserving.

4.4 Introducing an output queue
As mentioned, the service guarantees of packet schedulers are generally computed on the model in Figure 3,
which assumes that i) the exact value of W (t) is known
when updating V (t), and ii) the link requests a new
packet to transmit only once the previous one has been
fully transmitted.
These two assumptions are almost never truein a real system.
First, network interfaces (commonly called NICs) operate on a packet-by-packet basis, and do not export areal-time indication of the number of bits transmitted.
Even the notification of transmission completions, avail-

4.3 Approximated variants of WF2 Q+
The exact WF2 Q+ algorithm as described above, hasΩ(log N ) complexity in the number of flows [12]. In order to implement the same policy in O(1) time, several
schedulers [6, 9, 4] label flows with approximated virtual start and finish times Ŝ k (t) and F̂ k (t), in addition
to the exact values defined in (2). Lowest-cost examples are QFQ [4], S-KPS [6] and the scheduler proposedin [9], which we call GFQ hereafter. The approximatedvalues help reducing the complexity of certain sorting5

1. We first prove a few preliminary lemmas (Section 5)that are needed in the proofs of the main theorems
in this paper.
Readers not interested in the details of the subsequent proofs may skip this section.

Work

dW
W(t)
W(t)

2. We then prove our main results (Section 6), namely
the various fairness indexes (B-WFI, RFI and TWFI) for a generic AFQ scheduler in presence ofa FIFO and approximated work function. Theseequations are mostly mechanical derivations fromthe definitions and the previous lemmas. We also
extend these (sometimes hard to read) results withapproximated (and coarser) bounds trying to reduce the huge number of terms in these equations.

time

Figure 5: W (t) is within a band of height ∆Wabove W (t).
able through memory mapped registers or interrupts,
can be delayed by several microseconds, corresponding
to tens/hundreds of packets on high speed links. Secondly, to make sure that the link does not remain idle
while the scheduler (firmware or software) provides thenext packet to send, NICs typically implement i) a large
ring buffer, where the operating system can push outgoing transmissions, and ii) an internal FIFO that drains
the ring buffer and drives the link.
A realistic model of a communication device is thus
the one in Figure 4-B, where the scheduler is drainedby a dequeue unit that takes care of inserting packets
in the FIFO queue. We denote as W (t) the sum of thesizes of the packets dequeued from AFQ during [0, t].
In other words, W (t) is the amount of work delivered
to the FIFO up to time t. As shown in Figure 5, thework function W (t) has a stepwise shape and lies in aband of height ∆W on top of W (t), where ∆W equals
the maximum capacity of the FIFO plus the size of thepacket under service on the link.
Filling and draining the ring and the FIFO typicallyoccurs with some hysteresis, so that the buffers are filleduntil a high water mark is reached, then drained until
a low water mark or a sufficient amount of time haveelapsed, and so on. In formula, we have
∆W = max W (t) − W (t) ≥ 0.

3. Finally, we compare these results with those derived in the literature for various scheduling algorithms, both with and without FIFOs. Also,
we provide realistic estimates of the service guarantees using values (queue and packet sizes, data
rates, etc.) from actual hardware and software.

4.6 Proof machineryWe compute the B-WFI and the RFI by lower-bounding
the amount of service W k (t1 , t2 ) given by the system in
Figure 4-B to a flow during any time interval in which
the flow is continuously backlogged in the scheduler(left part of Figure 4-B)3 . To lower-bound W k (t1 , t2 )we model our system as the cascade shown in Figure 4B. The scheduler uses W (t) as the work function, andEquations 2 and 3 to compute the virtual time V (t)kkand the timestamps S (t) and F (t). We call S̃ k (t)and F̃ k (t) the approximate versions of the flows’ timestamps. The virtual time V (t) then becomes(6)
V (t2 ) ≡ max V (t1 ) + W (t1 , t2 ), min S̃ k (t2 )k∈B(t2 )and the relation between timestamps is
k

k

(5)

S (t) − ∆S k ≤ S̃ k (t) ≤ S (t) ≤The presence of the FIFO, and the different work
functions used to drain the scheduler may change theorder in which packets are served between the ideal(Figure 4-A) and the actual (Figure 4-B) systems. Section 2 gives one example of what can happen, but there
are many other pathological patterns that may occur,
affecting the service guarantees of the overall system.

F (t) ≤ F̃ k (t) ≤ F (t) + ∆F k

t

k

k

(7)

For some derivations, we compare the behaviour of the(packet) AFQ scheduler on the left of Figure 4-B, with
its corresponding fluid system shown in Figure 4-C. The
two have the same input pattern and the same work
function W (t), but the packet systems serves one packet
at a time whereas the fluid system may serve multiple
flows in parallel.
While it may seem counterintuitive, it is easier tokcompute a lower bound to W (t1 , t2 ), the amount ofwork received by a flow on entry to the FIFO during

4.5 Our contribution
As a consequence, our goal, and the main contribution of this paper, is to evaluate the service properties
of systems modeled as in Figure 4-B, hence taking into
account the impact of FIFOs and the uncertainty on
the work function W (t). The goal is achieved in threesteps:The quantity of interest is W k (t1 , t2 ), i.e. packets actuallykexiting the link, and not W (t1 , t2 ), which only refers topackets entering the FIFO.
3

6

[t1 , t2 ], than a lower bound to W k (t1 , t2 ). In this respect, in Section 5.2 we compute two slightly differentkbounds to W (t1 , t2 ). From the first bound we immediately get the T-WFI. Using the second bound we compute instead the B-WFI and the T-WFI by a few simple
steps. Especially, we achieve the latter result thanks to
the following reduction.

We start by comparing the completion time of packet
transmissions in the packet and the fluid systems. Let
pm be the m−th packet served in the packet system(the two systems do not necessarily complete packets
in the same order) and call tpm and tfm their completion
times in the two systems.
kkthen tpm ≤ tfm (if the exact
Lemma 1. If F m = F̃mand the approximated virtual finish time of packet pm
are equal, then pm will complete in the packet system
not later than in the fluid one).

4.7 Problem reduction
The bound on W k (t1 , t2 ) can be derived by one onk
W (t1 , t̂), the amount of work received by a flow on
entry to the FIFO in a suitable interval [t1 , t̂]. To thispurpose, let I = [t̂, t2 ] be the interval such that all packets that are in the FIFO or under service4 at time t2
have been dequeued during I. By definition, the sum ofkthe sizes of all these packets is W (t̂, t2 ), and we havekk

0 ≤ W (t2 ) − W k (t2 ) ≤ W (t̂, t2 )Intuition for the proof: the packet system serves packets in strict finish time order, except when packets are
not eligible or not arrived. For all in-order bursts immediately after an out-of-order packet, the fluid systemcannot have started serving any of the packets in the
burst before the beginning of the burst in the packet
system, so it must finish the burst no earlier than thepacket system.
Proof. Let o be the smallest index for which all
packets have an approximated finish time no greaterthan pm , F̃i ≤ F m ∀i ∈ [o..m]. Since F i ≤ F̃i , and thefluid system (using exact timestamps) completes packets in finish time order, all packets po ..pm must also becompleted not earlier than tfm in the fluid system.
If o = 1 then from the origin of time the packet system has served only packets p1 ..pm , while the fluid system might have already started service for some subsequent packet. Remembering that both systems have thesame work function, the fluid system cannot be aheadof the packet system, hence tpm ≤ tfm .
If o > 1, then packet po−1 has a higher finish timethan po ..pm , none of which has started in the packet
system before tpo−1 . This means that at tpo−1 either they
had arrived yet, or they were not eligible (S̃ k (tPo−1 ) >
V (tP
)),
so
even
the
fluid
systemcannothave
startedo−1serving any of those before tpo−1 (the fluid system starts(8)

Using these two inequalities, we can then write:
W k (t1 , t2 ) = W k (t2 ) − W k (t1 ) ≥k

max{0, W k (t2 ) − W (t1 )} ≥kkk

max{0, W (t2 ) − W (t̂, t2 ) − W (t1 )} =
k

k

k

k

k

k

max{0, W (t2 ) − W (t2 ) + W (t̂) − W (t1 )} =(9)

max{0, W (t̂) − W (t1 )} =k

W (t1 , max{t1 , t̂})Intuitively, this equation relates the output service in[t1 , t2 ] with the service given to the scheduler during ashorter interval which excludes packets still staged in
the FIFO or in the link.
In Section 5.2, Lemma 5 we compute an upper boundk
to W (t1 , t2 ) for any time interval [t1 , t2 ] during whichflow k is continuously backlogged. In case t̂ > t1 ,from this bound we get immediately an upper boundk
to W (t1 , t̂) by just replacing t2 with t̂ (in fact, also
[t1 , t̂] is a time interval during which flow k is continuously backlogged).

5.

k

to serve a flow at time t only if S (t) ≤ V (t) andk
S (t) ≥ S̃ k (t) holds). As a consequence, between tpo−1
and tpm the fluid system must have done at least thesame amount of work as the packet system, hence proving again that tfm cannot precede tpm .

SUPPORTING LEMMAS

The following lemmas are intermediate results needed
to prove our service-guarantee bounds. We present themin bottom-up order.
Notation: For the reader’s convenience, on top of various equality or inequality signs we write the reason(typically a reference to one equation) why the relation
holds.

5.1 Globally Bounded Timestamps
The flow timestamps cannot deviate too much fromthe system’s virtual time V (t). This is the “Globally
Bounded Timestamp” property (GBT) defined in [9,Definition 3]. Here we compute a variant of this propk
erty that comes in handy to upper-bound W (t1 , t2 ).

4
We will often refer to these packets in the next Sections.
These packets have been fully served as far as AFQ is concerned, but have not yet emerged from the link, so from theuser’s perspective they are not served yet.

Lemma 2 (Lower bound for F̃ k (t)). For all times
t at which flow k is backlogged,F̃ k (t) − V (t) ≥ 0.
7

(10)

k

Proof. Let t be a generic time instant at which flow
k is backlogged, with pm at its head. We know that(kF t) ≤ F̃ k (t). If F (t) = F̃ k (t), Lemma 1 tells usthat the transmission completion times in the packetkF
and fluid systems are tPm ≤ tm . Denoted as V f luid (t)the virtual time of flow k in the fluid system, the latterkguarantees that V (t) ≤ V f luid (t) holds at all times.
Thus

5.2 Lower bounds for W (t1 , t2 )kThis section contains lower bounds5 to W (t1 , t2 ), expressed in terms of the virtual time V (t) or the work
function W (t). We use the former is used in the derivation of the RFI, wheres we substitute the latter in (9)to compute the B-WFI.
Lemma 4.
k

F
tP
t≤tP
m ≤tm
m
(2)
k
k
k
k
≤ V (tP
V (t) ≤ V f luid (t) ≤ V f luid (tPm)
m ) = F̃ (t).

φk V (t1 , t2 ) − φk(11)
The case F (t) < F̃ k (t) can be handled by considering what happens if packet pm is artificially extendedkso F (t) = F̃ k (t). The larger packet would still satisfy (11). Besides, whether or not the original packet
pm is replaced with a larger one, the values of V (t) andF k (t) are the same, because 1) the value of tpm does notdepend on the size of pm , 2) t < tpm , and 3) the sizeof pm does not influence either any timestamp or the
packet service order up to time tpm . Hence the thesis
holds also in this case.
kk

W (t1 , t2 ) =kφk V (t1 , t2 ) =ih kkφk V (t2 ) − V (t1 ) =
φk (V (t2 ) − V (t1 ) +ih kkφk V (t2 ) − V (t2 ) − (V (t1 ) − V (t1 ))(Upper bound for S (t)). At all timestk

S (t) ≤ V (t) + ∆S k +

Lk
− Lk
φk

(12)

k

(4)
Lk
− V (t2 ) ≥
k
φ
(10)
Lk
F̃ k (t2 ) − ∆F k − k − V (t2 ) ≥φ
Lk−∆F k − k .
φk

F (t2 ) −

k

(t−
p )).

or S (tp ) = F
In the first case the thesis holds
trivially. For the other case to hold, at least one packet
of flow k must have been already served before time tp .
Let t′p be the largest time instant, with t′p < tp , at whicha packet of flow k is served. Flow k has to be eligiblek ′′−at time t′p , i.e., S̃ k (t−p ) = S̃ (tp ) ≤ V (tp ) ≤ V (tp ) has
to hold. Besides, we can note that the virtual timeadvances by at least the size of pm at time tp , thusV (t−p ) ≤ V (tp ) − Lm ≤ V (t) − Lm holds. In the end,S̃ k (t−p ) ≤ V (t)−Lm . Using this inequality, we can write
k

k

(2)

k

−
S (tp ) = F (t−p ) = S (tp ) +As for the second term, we haveh ki
− V (t1 ) − V (t1 ) =h ki (12)− S (t1 ) − V (t1 ) ≥Lk− V (t1 ) + ∆S k + k − Lk V (t1 ) =φ
Lk− ∆S k + k − Lk
φ

(4)

Lm
≤
φk
k

k
S̃ k (t−p ) + ∆S +(2)k

V (t2 ) − V (t2 ) = S (t2 ) − V (t2 ) ≥its size. According to (2), either S (tp ) = V (tp ) ≤ V (t)k(15)

We can therefore prove the thesis by computing lowerkkbounds to the two terms V (t2 )−V (t2 ) and −(V (t1 )−kkV (t1 )). Remembering that by definition V (t) = S (t),for the first term we have

Note: differently from the previous bound, this boundapplies to the exact timestamp, as this is what we needin the proof of subsequent Lemma 4.
Proof. Given any time instant t, we consider thekksmallest time instant tp such that S (tp ) = S (t), andwe denote as pm the packet served at time tp , and lmk

W (t1 , t2 ) ≥

k
(14)
L
k
k
k
2 k + ∆S + ∆F − LφProof. Recalling the meaning of the virtual timekV (t) of flow k, we can write the following equalities,
where the last equality follows from summing and subk
tracting V (t2 ) − V (t1 ) to V k (t2 ) − V (t1 ):kLemma 3Lm
Lm φ ≤1≤ V (t) − Lm + ∆S k + k ≤φkφLkV (t) − Lk + ∆S k + k
φ
(13)

5

k

(16)

(17)

Remembering that by definition W (t1 , t2 ) ≥ 0, we couldkderive tighter bounds by writing W (t1 , t2 ) ≥ max {0, ...}.
However this would make the result even less readable, and
it is hardly useful given that the equation is later used in acontext where we take the maximum over any flow and/ortime intervals.

8

service oscillation will have a negative impact on the BWFIk . Furthermore, if a scheduler does not distributebandwidth to flows accordingtoo their weights, the overnkwill be equally penalall B-WFI = maxk B-WFI
ized.

Replacing the two bounds in (15), and rearranging
terms, we get the thesis.
Lemma 5.
k

W (t1 , t2 ) ≥
 k

L
k
k
k
k
k
φ W (t1 , t2 ) − φ 2 k + ∆S + ∆F + ∆W − L
φ(18)

Theorem 1
antees
B-WFIk ≤ 2φk ∆W + φk ∆F k + ∆S k + 2Lk − φk Lk(21)

Proof. We prove the thesis by upper-bounding theterm V (t1 , t2 ) in (14) as follows:
V (t2 ) − V (t1 )W (t2 ) − W (t1 )W (t2 ) − W (t1 )W (t2 ) − W (t1 ) − ∆W.

6.

Discussion: The B-WFI is made of three terms. 2φk ∆Waccounts for the uncertainty on W (t) and the presenceof the FIFO, and it affects high-weight flows more than
low-weight ones. This is interesting because, for instance, low bandwidth flows (interactive sessions, VOIP,etc.) multiplexed on a high bandwidth link will not be
impacted too badly by the presence of a FIFO even oflarge size. The term φk ∆F k + ∆S k accounts for theuse of approximate timestamps. In practice (see Table 2) the approximations on timestamps are ∝ 1/φkso this gives a constant component, comparable to thefinal term.
As an example, WF2 Q+ uses exact flow timestamps(∆S k = ∆F k = 0). The use of W (t) as work function,
without a FIFO makes ∆W = L (the packet under service). Assuming Lk = L, we have B-WFIk ≤ 2L + φk L.
In the case of QFQ, the approximation on timestamps
kso we end up with B-WFI≈
is ∆S k = ∆F k = 2 L
φk
6L + φk L
Conversely, when the FIFO exists and becomes large,
say M slots, the term 2φk M L becomes the dominant
one.

≥
(5)

≥

(5)

(B-WFI). For a flow k, AFQ guar-

(19)

≥

SERVICE PROPERTIES

We are now ready to compute various service properties of the AFQ family of schedulers, compare the results with the (exact, but theoretical) analysis provided
in the literature, and make practical considerations on
the impact of the FIFO on the service guarantees.
We focus on three metrics, which express from different points of view the deviation from an ideal behaviour: the Relative Fairness Index (RFI), introduced
in [8], the Bit Worst-Case Fairness Index (B-WFI), introduced in [1], and the Time Worst-Case Fairness Index (T-WFI), first introduced in [2].
The theorems stating the B-WFI and the RFI, as wellas the properties they depend on, are proven without
ever using the link rate. Hence these theorems hold also
for time-varying link rates.

Proof. By substituting (9) in (20), we get(9)

B-WFIk ≤6.1 B-WFIThe B-WFIk for a flow k is defined as:6

B-WFIk ≡ max φk W (t1 , t2 ) − W k (t1 , t2 )
[t1 ,t2 ]k(18)

φk W (t1 , t2 ) − W (t1 , max{t1 , t̂}) ≤φk W (t1 , t2 ) − φk W (t1 , max{t1 , t̂})+ kL+φk 2 k + ∆S k + ∆F k + ∆W − Lk =φφk W max{t1 , t̂}, t2 +
 (5)
 k
L
k
k
k
k
≤
+φ 2 k + ∆S + ∆F + ∆W − L
φ
 k

L
φk ∆W + φk 2 k + ∆S k + ∆F k + ∆W − Lk =φk2φ ∆W + φk ∆F k + ∆S k + 2Lk − φk Lk
(22)

(20)

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.
This metric indicates how much, in terms of service
received, a flow remains behind what it would receive
on an ideal scheduler. The metric is computed overany time interval in which flows are backlogged, so any
6This definition is slightly more general than the original
one in [1], where t2 was constrained to the completion timeof a packet.

6.2 T-WFI
9

given to two continuously backlogged flows:

The T-WFI is the counterpart of the B-WFI in termsof delays. Unlike the B-WFI, it can only be computed
if the work function W (t) is known. An exact computation is extremely difficult in practice because most links
have non-constant, and possibly even load-dependent
rate. As an example, wired ethernets have a fixed-size
preamble in front of each packet, irrespective of its size;
time-multiplexed media serve clients in periodic bursts;
radio links may have variable access time (depending
on collisions) and data rate (depending on channel conditions).
For simplicity, we make the computation assumingthat the link has a constant rate R, i.e. W (t1 , t2 ) =R(t2 − t1 ) when there is backlogged traffic. In this case,
the T-WFIk for flow k is defined as
Qk (ta )k(23)
T-WFI ≡ max tc − ta − k
φ R

RFI ≡

T-WFIk ≤ 2

Theorem 3(T-WFI). AFQ guarantees thatRFI ≤max ∆S + ∆F + ∆S + ∆F k +h,k
2Lk + ∆W
Lh + ∆W
h
k
−L +
−L
+
φh
φk


h

h

k

(27)

Discussion: the presence of the FIFO, and the approximation on timestamps, is more evident in the RFI, as
it uses normalized service as a metric. The deviations
from the ideal service (which are bounded in absolutevalues by a small multiple of the FIFO size) are amplified by 1/φk .
Same as for the B-WFI we have one term accounting
for the approximate timestamps (as before, there is an
implicit 1/φk in all these error terms), and another one
with components ∆W/φk accounting for the effect of
the FIFOs.

(T-WFI). For a flow k, AFQ guarLk∆S k + ∆F k + 2∆W − Lk
+
φk R
R

(26)

This metric was introduced in [8] and it is useful to determine how evenly a scheduler distributes excess bandwidth in case not all flows are backlogged. In fact, the
B-WFI only identifies if a flow goes below its assigned
fair share (something that the RFI does not capture).

where ta and tc are, respectively, the arrival and completion time of a packet, and Qk (ta ) is the backlog offlow k just after the arrival of the packet.
Theorem 2
anteesW h (t1 , t2 ) W k (t1 , t2 )−∀h,k,[t1 ,t2 ]
φh
φk
max

(24)

Proof. Given a packet p arriving at time ta , weprove the thesis in two steps: first we compute an upper bound to the time that elapses from ta to when
p is dequeued from AFQ, say time tc , then we add tothis upper bound the maximum time that may elapse
from time tc to the time instant tc at which p is finallytransmitted.
k
As for the first step, by definition of W (t) and tc ,kwe have that W (ta , tc ) = Qk (ta ). Using this equality
and (18), and recalling that the link works at constant
speed R, we can write

Proof. Consider two flows, h and k continuously
backlogged during a time interval [t1 , t2 ]. We can upperbound the normalized service received by flow h as follows:W h (t1 , t2 ) (5)≤φhhW (t1 , t2 ) + ∆W
=
φh
∆W
h
h
V (t2 ) − V (t1 ) + h ≤φ∆W (12)hh
S (t2 ) − F (t1 ) + h ≤φhL∆W (5)hV (t2 ) + ∆S h + h − Lh − F (t1 ) + h ≤φφh∆W (10)L
V (t2 ) + ∆S h + h − Lh − F̃ h (t1 ) + ∆F h + h ≤
φ
φ
h
L
∆W
V (t2 ) + ∆S h + h − Lh − V (t1 ) + ∆F h + h =
φ
φ
h
∆W
L
V (t1 , t2 ) + ∆S h + h − Lh + ∆F h + h
φ
φ
(28)

W (ta , tc ) (18)
≤
R
k
Lk
k
k
k
W (ta , tc ) 2 φk − L + ∆S + ∆F + ∆W
+
=
φk R
R
tc − ta ≤

k

L
k
k
k
Qk (ta ) 2 φk − L + ∆S + ∆F + ∆W
+
.
φk R
R

(25)
The thesis follows from considering that, since the
FIFO is emptied and the packet on the link is served at
a constant rate R, then tc − tc ≤ ∆W
R .

6.3 RFIThe Relative Fairness Index (RFI), is defined as the
maximum difference, over any time interval [t1 , t2 ] andpair of flows k and h, between the normalized service

As for the lower bound, we have77

10Same as in Section 5.2, we could derive tighter bounds by• a software FIFO, typically called “transmit ring”.
This is a circular list of packet buffers used asa mailbox between the operating system and the
NIC to queue packets to transmit. The role of thisqueue is to absorb the delay between the transmit
completion interrupts and the software actually reacting and providing more packets to send.

k

W (t1 , t2 )=φkW k (t2 ) − W k (t1 ) (8)≥φkk

W k (t2 ) − W (t1 ) (5)
≥
φk
k

(29)

The two queues serve two very different purposes andoperate on largely different timescales. The hardware
FIFO needs to amortize delays in the order of a few
microseconds at most, which may occur when there isheavy contention on the system bus, e.g. because oflong transactions.
Because the NIC cannot stop an ongoing transmission, the internal FIFO is normally storing at least one
maximum-sized frame (1518 bytes on a standard ethernet, up to 10-16 Kbytes if jumbo frames are used).
At 10..40 Gbit/s speeds, even a single frame might be
too short to absorb bus delays, which is a reason why
the internal FIFO is often much larger, between 32 and512 Kbytes. The other reason for having large internal
FIFOs is that many modern NICs implement TCP segmentation in hardware, so they must be able to store
large TCP segments (typically up to 64 Kbytes each)to split them into separate IP packets.
The role of the transmit ring is instead to cope withpossibly slow reaction from the operating system. With
packet rates in the range of millions of packets per
second, we cannot possibly expect the operating system to handle one interrupt per packet. Most modern NICs and operating systems implement a feature
called interrupt coalescing/mitigation, where the maximum interrupt frequency is bounded, and latencies in
the 20..100 µs range are quite common. On top of this,interrupt handlers might be delayed due to the CPU
being busy on other processes, and this motivates theuse of extremely large transmit rings. Common values
are 64..256 packets for low-speed hardware, and up to1024..4096 buffers for 10 Gbit/s links.
In summary, practical values of ∆W on existing systems may easily be as large as 100L and more.

k

W (t2 ) − ∆W − W (t1 ) (14)
≥
φk
Lk
∆W
V (t1 , t2 ) − 2 k + Lk − ∆S k − ∆F k − kφφ
Substituting (28) and (29) in (26), and taking the
maximum over all possible flow pairs, we get the thesis.

7.

COMPARISON OF AFQ SCHEDULERS

We can now discuss the behaviour of the AFQ scheduler variants in presence of a FIFO and uncertainties
on the work functions.
The various options for schedulers are generally evaluated in terms of computational costs (both asymptotic
and actual), and service guarantees. For the latter, theanalysis performed with the ideal system model of Figure 3 might be misleading as it misses a component
which is sometimes significant. Most of the values aretaken from our previous work [4, Sec.6] because not all
papers included these results.
Table 2 summarizes the theoretical and actual service
guarantees for a few schedulers proposed in the literature (for simplicity we include only the B-WFI and the
RFI). For most of the approximated schedulers the results are expressed in terms of the σk parameters, which
determine how flows are grouped together. In general
σk = cLk /φk where the constant c is a small integer(1..4). The table shows clearly that the difference between WF2 Q+ and the approximated schedulers is justin the component φk σi , which is a small multiple of thepacket size. In presence of large buffers, this component
becomes negligible.

7.1 Buffer sizes in practice

8. CONCLUSIONS

Remember that the FIFO size involves every queue infront of the actual serializer (the unit that takes packets
and formats them into bits to be sent to the communication link). On most systems there are in fact at least
two queues involved:

In this paper we have proved analytically the service
properties of a large family of weighted fair queueing
schedulers implementing the WF2 Q+ algorithm or fast,
approximated versions, in presence of output FIFOs between the scheduler and the actual link, and without
exact knowledge of the transmit rate.
The result is of practical relevance because such elements exist in all hardware, and it is important to know
their impact when designing system with tight service
guarantees.
In retrospect, our main results, summarized in Section 6, are perhaps obvious (but now we have a formal• a hardware FIFO, which is internal to the NIC andserves to absorb the latency in accessing systembuses and memories;
considering that W k (t1 , t2 ) ≥ 0, but the gain of at most∆W/Φk would not change the 1/Φk behaviour of the RFI
at the price of an unreadable expression.

11

Scheduler(ideal)WF2 Q+
S-KPS
GFQ
QFQ
FRR
Scheduler(real)

∆S k

∆F k

B-WFI

RFI

0

0

Lk + 2φk L
2φk (σi + L)–
2L + L /φk + L /φP + 3(σi + σj )3φk (σi + 2L)

2L + Lk /φk + Lp /φP + 2(σi + σj )

k

k

4L
φk
Lk
φk
k
2L
φk

2L
φk
Lk
φk
k
4L
φk

n.a.
∆S k

n.a.
∆F k

AFQ

k

k

3φ (σi + 2L)
not available
B-WFI

3L + 4σi + 3σj
4σi + 10σj + L/φk
RFI (simplified)

2φk ∆W + φk (∆S k + ∆F k ) + 2Lk − φk Lknokk
2 maxk ∆S k + ∆F k + ∆W + 3L
−
L
k
2φo
n
k
k
2 maxk ∆W + 3L
−
L
2φk
o
n
k
k
2 maxk ∆W + 15L
k − L
2φ
n
o
k
k
2 maxk ∆W + 7L
−
L
k
2φ
o
n
15Lk
2 maxk ∆W + 2φk − Lk

WF2 Q+

0

S-KPS

4L
φk

k

2L
φk

k

2φk ∆W + 8Lk − φk Lkkk

2φk ∆W + 4Lk − φk Lk

GFQ
QFQ

2φk ∆W + 2Lk − φk Lk

0

L
φk
k
2L
φk

L
φk
k
4L
φk

p

2φk ∆W + 8Lk − φk Lk

Table 2: Service guarantees for various schedulers with ideal (no FIFO, exact W (t)) and real links(FIFO, W (t)). For many of these algorithms, bounds are computed in terms of a parameter, σk ≈ Lk /φkwhich determines how flows are grouped. We retain the original formulation for ease of reference.
For the RFI we indicate a simplified expression assuming that the flows h and k that maximize theexpression have the same parameters.
proof): the presence of a queue between the scheduler
and the link affects the various service metrics by anamount roughly proportional to twice the queue size.
The impact is less relevant for low-weight flows, which
only use a small fraction of the total link capacity. More
importantly, the scheduling perturbations induced by
the queue may render completely irrelevant the difference in service properties among different schedulers.

9.

[8] S.J.Golestani. A self-clocked fair queueing scheme
for broadband applications. Proceedings of IEEE
INFOCOM ’94 (June 1994), 636–646.
[9] Stephens, D. C., Bennett, J. C., and Zhang, H.
Implementing scheduling algorithms in high-speed
networks. IEEE Journal on Selected Areas inCommunications 17, 6 (June 1999), 1145–1158.
[10] Stiliadis, D., and Varma, A. A general
methodology for designing efficient traffic schedulingand shaping algorithms. Proceedings of IEEE
INFOCOM ’97 (April 1997), 326–335.
[11] Valente, P. Exact gps simulation and optimal fairscheduling with logarithmic complexity. IEEE/ACM
Transactions on Networking 15, 6 (2007), 1454–1466.
[12] Xu, J., and Lipton, R. J. On fundamental tradeoffs
between delay bounds and computational complexity
in packet scheduling algorithms. IEEE/ACM
Transactions on Networking 13, 1 (2005), 15–28.
[13] Yuan, X., and Duan, Z. Fair round-robin: A low
complexity packet scheduler with proportional andworst-case fairness. IEEE Transactions on Computers58, 3 (2009), 365–379.

REFERENCES[1] Bennet, J. C. R., and Zhang, H. Hierarchicalpacket fair queueing algorithms. IEEE/ACM
Transactions on Networking 5, 5 (1997), 675–689.
[2] Bennett, J. C. R., and Zhang, H. WF2 Q:
Worst-case fair weighted fair queueing. Proceedings ofIEEE INFOCOM ’96 (March 1996), 120–128.
[3] Carbone, M., and Rizzo, L. Dummynet revisited.
ACM SIGCOMM Computer Communication Review
40, 2 (2010), 12–20.
[4] Checconi, F., Valente, P., and Rizzo, L. QFQ:
Efficient Packet Scheduling with Tight Bandwidth
Distribution Guarantees.
http://info.iet.unipi.it/∼luigi/qfq/ .
[5] Karsten, M. SI-WF2 Q: WF2 Q approximation withsmall constant execution overhead. Proceedings ofIEEE INFOCOM 2006 (April 2006), 1–12.
[6] Karsten, M. Approximation of generalized processor
sharing with stratified interleaved timer wheels.
IEEE/ACM Transactions on Networking 18, 3 (2010),
708–721.
[7] Parekh, A. K., and Gallager, R. G. A generalized
processor sharing approach to flow control in
integrated services networks: the single-node case.
IEEE/ACM Transactions on Networking 1, 3 (June
1993), 344–357.

12