A new packet schedulingarchitecture for FreeBSD
Luigi Rizzo, Università di Pisa
May 13, 2010

Introduction
Packet scheduling is necessary when demand exceeds available
resources. So far, FreeBSD had only limited packet schedulingsupport:◮ ALTQ, three schedulers: PRI, CBQ, HFSC (only on
output interfaces, device-specific);◮ Dummynet, in/out but only one scheduler (WF2Q+);
We need something better, to support:◮ more modern (and efficient) schedulers;◮ more complex usage scenarios;◮ research on packet schedulers;◮ customer demand.
2 / 49

Overview of the talk
Topics covered in this talk:◮ some packet scheduling theory, discussing architectures,
service properties, and performance;◮ scheduling support in Dummynet – user view
(how to make use of the new features);◮ scheduling support in Dummynet – kernel side
(how to extend/build new schedulers).
Work supported by the ONELAB2 project - www.onelab.eu
QFQ is joint work with Fabio Checconi and Paolo Valente, partly
supported by the NETOS project - Univ. di Pisa.

3 / 49

Packet scheduling backgroundPacket scheduling background..
.

Why do we care about packet scheduling ?
◮ arbitrate access to common resources;◮ provide service guarantees and resource isolation;◮ overprovisioning is not always possible/desirable, today’s
CPUs are too fast;◮ links are very fast too, so schedulers must keep up withhigh data rates and number of flows.
5 / 49Problem setting and definitions◮ Basic building block: flatscheduler;◮ characterised in terms of“service guarantees”, memory
and time complexity;◮ basic schedulers can becomposed in a hierarchicalfashion;◮ again, we can try to characterise
the aggregate scheduler.

..
.

6 / 49[Non-]Schedulers
Some solutions are not real schedulers:◮ Policers:
each flow is given a maximum bandwidth (e.g. using
leaky bucket, O(1) time);◮ make sure total bandwidth ≤ link capacity→ there is never congestion;◮ excess bandwidth is not used.
◮◮ Queue management policies (RED, RIO, ...):

randomly mark/drop packets as queue size grows;
responsive flows (e.g. TCP) will react reducing theirrate. The feedback stabilizes the system;◮ ineffective on non-responsive flows.
◮◮

7 / 49

Real Schedulers◮ Priority-based schedulers:◮◮

simple to implement, often O(1) time complexity;
one gets guarantees, other may starve.

◮ Round Robin (and variants):◮◮

also O(1) time complexity;
no starvation, but O(N) delays due to RR policy.

◮ Fair Queueing (and variants):◮◮

small, well defined service/delay guarantees;O(log N) . . . O(1) time complexity.

◮ Hierarchical schedulers: compositions of the above.
◮◮

much harder to analyse;
often, O(N) time complexity.
8 / 49Priority and Round Robin
Each flow is assigned a Priority. Flows are served in strictpriority order (Round Robin within the same priority).
◮ priority management is O(1) . . . O(log N) . . . O(N)(ffs(), binary heap, linear scan);◮ Round Robin management is always O(1);In Round Robin variants (Deficit RR, Weighted RR), a flow’s“weight” indicates the share of bandwidth it should receive:◮ in each slot, give service proportional to the weight;◮ inherent O(N) delay and burstiness:... A B CCCCCC D E F ... Z A B CCCCCC ...
◮ reducing the delay requires more complex (andtime-consuming) data structures to serve high-weightflows more often.
9 / 49Proportional share
Proportional share schedulers try to emulate, on a
Packet-by-Packet basis, the behaviour of a “Fluid System”:
W=1

...

W=2
W=1

W=1
W=2
W=2

◮ label each flow with a weight Φi ;◮ assign bandwidth to backlogged flows proportionally totheir weight: Ri = RΦi /P

j∈B Φj◮ ideally, this should be true over any time interval;◮ in practice, some difference is unavoidable;◮ the emulation cost ranges from O(1) to O(N) dependingon the algorithm.
10 / 49

Hierarchical schedulers◮ Useful to implement different aggregation of resources◮ at least O(depth) complexity for the infrastructure;◮ very likely to go to O(N) if nodes do not scale (e.g. needto explore all children on a dequeue).
11 / 49

Service Guarantees
Many definitions for Service Guarantees. We consider thedeviations of our actual scheduler (Packet System) from theservice offered by an Ideal Fluid System.
W=1

...

W=2
W=1

W=1
W=2
W=2

◮ each flow has a weight Φi , and should receive a fractionPΦi / j Φj of the total link capacity at any time;◮ the Fluid System serves all flows simultaneously;◮ the Packet System serves one packet at a time, is non
preemptable, online, and possibly work-conserving.

12 / 49

Service Guarantees (2)Because of its nature, a Packet System cannot guarantee
perfect sharing at all times. The magnitude of deviations is anindicator of the quality of the scheduler.
◮ various quality metrics including
B-WFI = max [Φk W (∆t) − Wk (∆t)]
k,∆t

B-WFI is the maximum lag in terms of service, there is asimilar definition in terms of time (T-WFI).
◮ In the best possible Packet System (e.g. WF2 Q),
B-WFI = 1 MSS (Optimal B-WFI);◮ tradeoff between guarantees and complexity:
Xu-Lipton 2002: optimal B-WFI requires Ω(log N) time;
Valente 2004: an O(log N) version of WF2 Q;◮ breaking the O(log N) barrier implies relaxed guarantees.
13 / 49

Do we really care about WFI ?
Is the WFI an invention of bored academics ?
◮ No. A large WFI means that a flow needs to have a large

queue to store traffic while it is not served.
◮ Example: a round-robin scheduler has O(N) WFI. With
50K queues, a flow using half of the link’s capacity needs
a queue of 25K packets;◮ traffic goes out in huge bursts;◮ the burstiness propagates downstream.

14 / 49

Timestamp based schedulers
Timestamp based schedulers emulate a fluid scheduler asfollows:◮ compute, at each time, how much service the flow would
receive in the Fluid system (Virtual Time);◮ mark packet with their Start and Finish time in the fluid
system;◮ schedule packets according to their Finish times;◮ to reduce burstiness, do not consider packets that havenot started yet in the fluid system (Eligibility)
W=1

...

W=2
W=1

W=1
W=2
W=2

15 / 49

Guarantees of Timestamp based schedulers
Computing the timestamps, and sorting on them, is what
creates the complexity bound Ω(log N).
◮ Schedulers using exact timestamps (WF2 Q) have
B-WFI=1 MSS (optimal B-WFI);◮ cannot do better due to non-preemption, andwork-conserving policy;◮ the use of approximate timestamps reduces complexity,
but causes slightly larger lags:
B-WFI ≤ c·MSS for some constant c (near-optimal
B-WFI).

16 / 49

State of the art of packet schedulers◮ Priority-based schedulers are fast but give no guarantees

except to the flow with highest priority;◮ Round Robin schedulers have O(1) time but poor
guarantees (O(N) B-WFI);◮ some timestamp-based schedulers such as WF2 Q give
optimal service guarantees in O(log N) time;◮ approximated variants of timestamp-based schedulers(KPS - Karsten 2006; GFQ - Stephens,Bennet,Zhang
1999) have near-optimal guarantees and O(1) timecomplexity (but several times slower than RR).
◮ QFQ (Checconi, Valente, Rizzo 2010) has O(1) time andis almost as fast as RR.
17 / 49

QFQ features
QFQ is a practical O(1) approximated timestamp-basedscheduler with◮ near-optimal guarantees (B-WFI ∼5 MSS);◮ truly constant complexity, independent of number of flows
and configuration parameters;◮ uses very simple CPU instructions;◮ it’s real, not just a paper design;◮ 110 ns/pkt on common workstations, compared to 55 ns
for DRR and 400 ns for KPS.
◮ more details on “GoogleTechTalks qfq” andhttp://info.iet.unipi.it/∼luigi/qfq/
QFQ makes Fair Queueing feasible in software (or inexpensive
hardware) at GBit/s rates.
18 / 49

Choosing the right scheduler
We have many algorithms with different features. How do wechoose ?
◮ the decision depends a lot on the operating conditions.
For large N, asymptotic complexity is important. For
small N, or certain weight distributions, guarantees or
actual run times are more important;◮ theory can tell us about worst-case service guarantees andasymptotic complexity;◮ we need measurements to determine the run-time
constants.

19 / 49

Testing scheduler performance
In-kernel measurements are very hard:◮ very difficult to set up a suitable test environment;◮ packet generation, reception, device drivers and othercosts dominate the measurements;
Controller

We make our measurements
PacketScheduler
by running the kernel code in
generator
userspace:◮ can easily generate traffic at 40Mpps and more (compare
to 200..500Kpps on the wire for the same hardware);◮ can generate traffic for a programmable number of flows,
packet size and weight distribution;◮ can control the operating point of the scheduler during
tests.
20 / 49

Test harness
The kernel sources also include some test code to build andrun schedulers in user space. This is very useful both forcorrectness and performance testing.
Controller

Packetgenerator

Scheduler./ test - alg rr - qmin 4 n - qmax 30 n - flowsets 1::512 ,8::64
dn_rr
n 5004288 10000000 time 0.683968
136.676./ test - alg qfq - qmin 4 n - qmax 30 n - flowsets 1::512 ,8::64
dn_qfqn 5004288 10000000 time 0.974142
194.661./ test - alg kps - qmin 4 n - qmax 30 n - flowsets 1::512 ,8::64
dn_kpsn 5004288 10000000 time 2.855963
570.70321 / 49

Scheduler Performance comparison
Sample results on a 2.3GHz Athlon with 667MHz memory.
enqueue() + dequeue() time, ns
700
WF2Q+
600

S-KPS

time (ns)

500
400
300
QFQ

200

DRR
FIFO
NONE

100
0
1

4

16

64

256
1k
Flows

4k

32k
22 / 49

Scheduler Performance comparison (2)Same data in tabular format – average time (ns) for an
enqueue()/dequeue() pair and packet generation. StD within
3% of the average.
Flows
1
8
64
512
4k
32k
mix

NONE FIFO DRR QFQ KPS WF2Q+
62
83
105 221 450
210
60
80
102 163 543
344
59
80
100 158 540
526
64
85
110 175 560
740
74
102
157 197 590
1110
62
117
147 222 601
1690
1:32k,2:4k,4:2k,8:1k,128:16,1k:1 flows
92
119
160 255 612
1715

23 / 49

More on performance
CPU type and speed, memory (and cache) size and speed has
a big impact on performance. As an example, QFQ with 32k
flows:◮ 220ns on 2.3GHz Athlon w/ 666 MHz RAM;◮ 110ns on fast Nehalem w/ 1.3GHz RAM;
◮ 8000ns on Asus WL500GP (240 MHz MIPSEL);
Remember that scheduling is only one block in the packet
processing chain. On the same 2.3GHZ Athlon:◮ 500..1000ns within the device driver;◮ another 500..2000ns within ipfw and IP layer.

24 / 49

Packet scheduling inDummynet – User view

Dummynet
Dummynet is a network emulator developed in 1997 on
FreeBSD, and substantially revised in recent years.
Now available on FreeBSD, OSX, Linux/Openwrt, Windows.

◮ intercepts packets in various points of the protocol stack;◮ passes packets through a classifier (ipfw) and then topipes or queues, which model communication links;◮ on exit, packets are reinjected in the protocol stack or in
the classifier.
26 / 49

Packet scheduling using dummynet◮ Use dummynet to create bottleneck link(s):the bottleneck can be a close approximation of anotherbottleneck downstream;◮ it can be used to enforce service limitations;◮ we can also enforce limitations on incoming traffic.
◮◮ use the classifier to select packets subject to scheduling,

and group them into flows.

27 / 49

User interface/sbin/ipfw is the main user interface
for the system. Use is very simple.
◮ define a link and its scheduler..
.

ipfw sched 4 config type qfq bw 4 Mbit / s◮ define the weight of each queue
ipfw queue 1 config weight 10 sched 4
ipfw queue 2 config weight 3 sched 4◮ send traffic to the queues using the classifier
ipfw add 100 queue 1 out src - ip 1.2.3.4
ipfw add 100 queue 2 out src - ip 1.2.3.5

More details later.
28 / 49

Classifier
A classifier is used to send traffic to different pipes.

◮ we use FreeBSD’s ipfw, which is easy to use and has alarge number of packet matching options;◮ ipfw has been extend with custom features:
multiple passes, to emulate complex networks;
probabilistic match, to emulate multipath and reordering;◮ table lookup, to speed up classification and dispatch.
◮◮

29 / 49

Pipes

A pipe models basic features of a link:◮ queue with configurable size and management policy(FIFO, RED);◮ programmable link bandwidth;◮ deterministic propagation delay;
In this context (scheduling) we are only interested in
bandwidth.
30 / 49

Queues and Schedulers
We can split a dummynet pipe into components – queue,scheduler, link – so we can:◮ attach multiple queues to one scheduler;◮ configure scheduler features (algorithm, weights, etc.);◮ dynamically generate queues and scheduler instances.

31 / 49

QueuesA queue contains all packets for the same flow;..
.

◮ identified by a numeric ID, carries a weight and otherper-flow scheduling parameters;◮ multiple queues are attached to one scheduler◮ ipfw rules send traffic to the queues.
ipfw
ipfw
ipfw
ipfw

queue 1
queue 2
add 100
add 100

config sched 5
config sched 5queue 1 src - ip
queue 2 src - ip

weight 10
weight 1
1.2.3.4
1.2.3.6

32 / 49

Dynamic creation of queues
To configure multiple, per-flow queues with similar features we
can use a flow-mask:
ipfw queue 1 config weight 4 sched 5
ipfw queue 2 config weight 1 sched 5 mask dst-ip 0xff

(this “template” is called a flowset in the code).
◮ the mask is applied to the 5-tuple of each packet;◮ a new queue is created for each different value after
masking;
Weight and other parameters are
fs 1
fs 2
mask ...
the same for all queues createdx.1
through masking. In particular,
x.2...
all such queues talk to the same
x.255
scheduler.
33 / 49

Schedulers
Schedulers arbitrate queues accessing the same link..
.

◮ users can define the scheduler type and link speed

ipfw sched 5 config type QFQ bw 4Mbit/s◮ currently available choices are FIFO, DRR, PRIO,

WF2Q+, QFQ, KPS;
Schedulers can also be used as generic flow-processing hooks(e.g. for deep packet/flow inspection, ...).
34 / 49

Dynamic creation of schedulers
Schedulers have a scheduler mask, used for dynamic creationof scheduler instances:
ipfw sched 5 config type QFQ bw 4Mbit/s mask src-ip 0xff
◮ the mask is applied to the 5-tuple of packets;◮ a new scheduler instance is created for each value after

masking;◮ the various instances do not share anything (unlike
dynamic queues, which are attached to the samescheduler);
Useful e.g. for ISPs with multiple independent customers.

35 / 49

Overall structure
Relation between flowsets, masks, queues and schedulers.
fs 1

fs 2

sched

mask src-ip

mask src-ip

mask dst-ip

...
...

36 / 49

Advanced configurations
Configurations should exploit masks and ipfw tables to reducethe cost of the classifier.
Often, one table per direction can be used for most of thedispatching:ipfw add queue tablearg out src - ip table (1)ipfw table 1 add 1.2.3.0/2 4 20 // this goes to queue 20
ipfw table 1 add 1.2.3.8 21 // privilege d IP to queue 21
ipfw table 1 add 1.2.4.0/2 0 25 // this goes to queue 25...
// flowset 20 creates one queue per IP
ipfw queue 20 config sched 3 weight 5 mask src - ip 0 xff
ipfw queue 21 config sched 3 weight 20// flowset 25 creates one queue per /24 subnet
ipfw queue 25 config sched 4 mask src - ip 0 xf00

37 / 49

Summary (user view)◮ use ipfw rules to pass packets to queues;◮ ipfw tables very useful to produce compact and efficient

rulesets;◮ use masks on queues and schedulers to dynamically create
instances of flows and schedulers with similar attributes;◮ pick one of many schedulers according to yourrequirements.

38 / 49

Packet scheduling inDummynet – Kernel view

Dummynet – Packet flow within the kernel
Packets going through dummynet normally follow this path:◮ input interface or local source;◮ pfil hooks ipfw check hook() ;◮ ipfw processing ipfw chk() ;◮ initial dummynet dispatch dummynet io() .
Enqueue into the scheduler occurs here;◮ delayed reinject dummynet task(), dummynet send() .
Dequeue from the scheduler occurs here.

40 / 49

Dummynet – Internal data structures
Internally, most dummynet structures (including
scheduler-related ones) are managed through hash tables:◮ a global hash table contains flowsets. Initial packet
dispatch always searches this table;◮ a global hash table contains schedulers. This is usedduring configurations to attach queues to schedulers;◮ per-flowset hash table contains queues. Looked up after
applying masks;◮ per-scheduler hash table contains scheduler instances.
Looked up when a new queue is created.
A priority queue (heap) is used to store pending events.

41 / 49

Interfacing with schedulers
The packet scheduling infrastracture takes care of all common
operations:◮ module management;◮ applying queue and scheduler masks;◮ creation of queues and scheduler instances;◮ locking and memory allocations;◮ commonly used data structures (hash tables, heaps,
hashing);
Schedulers only need to provide enqueue() and dequeue()
handlers, plus a few callbacks called by constructors anddestructors of the various data structures.
42 / 49

Packet scheduler descriptor and module glue
static struct dn_alg rr_desc = {_SI( .type = ) DN_SCHED_RR,_SI( .name = ) "RR",_SI( .flags = ) DN_MULTIQUEUE,_SI( .schk_datalen = ) 0,
_SI( .si_datalen = ) sizeof(struct rr_si),_SI( .q_datalen = ) sizeof(struct rr_queue) - sizeof(struct dn_queue),_SI( .enqueue = ) rr_enqueue,_SI( .dequeue = ) rr_dequeue,_SI( .config = ) rr_config,_SI( .destroy = ) NULL,_SI( .new_sched = ) rr_new_sched,_SI( .free_sched = ) rr_free_sched,...
}
DECLARE_DNSCHED_MODULE(dn_rr, &rr_desc);

43 / 49

Enqueue() and dequeue()enqueue(si, q, m) enqueues mbuf m on queue q;◮ normally, just enqueue packet into q, and possibly dosome housekeeping on internal data structures;◮ q is only a hint, the scheduler can put the packet
somewhere else (e.g. priority or FIFO);◮ return 0 on success, 1 on drop;
After enqueue, m = dequeue(si) is called repeatedly to returnthe next packet to transmit:◮ m == NULL means no more packets queued;◮ packets can be tagged as ”to be dropped” (for schedulers
that may lose packets, e.g. those emulating wirelesslinks);◮ special values can request to postpone a transmission(non work conserving schedulers).
44 / 49

Example scheduler code: enqueue#ifdef _KERNEL... a ton of kernel headers#else#include <dn_test.h>#endif...
static int
rr_enqueue(struct dn_sch_inst *_si, struct dn_queue *q, struct mbuf *m) {struct rr_si *si = (struct rr_si *)(_si + 1);
struct rr_queue *rrq = (struct rr_queue *)q;
if (m != q->mq.head) {if (dn_enqueue(q, m, 0)) /* packet was dropped */return 1;
if (m != q->mq.head) /* already backlogged */return 0;}/* If reach this point, queue q was idle */if (rrq->status == 1) /* Queue is already in the queue list */return 0;/* Insert the queue in the queue list */rr_append(rrq, si);return 0;}
45 / 49

Source file organization
Most files are in sys/netinet/ipfw/◮ ip dn private.h basic data structures (queues, flowsets,scheduler instances);◮ dn sched.h scheduler API and related macros;◮ dn sched FOO.c implementation of algorithm FOO;
◮ test/ code for testing schedulers in userland.
Headers and basic schedulers (RR, PRIO, ...) are heavily
documented so they can be used as a reference to develop new
modules.

46 / 49

Available Schedulers
The current set of schedulers covers a wide range of options:
FIFO, DRR, PRIO, WF2Q+, KPS, QFQ.
◮ more are coming (e.g. an 802.11b/g scheduler);◮ adding a new scheduler is straightforward;◮ you can concentrate on your algorithm, don’t have toworry about classification, getting traffic, locking, etc..
> wc dn_sched *. c
120
553
229
939
653
2225
864
3466
307
1110
373
1854

3766
6367
16724
23302
7297
12080

dn_sched_fifo.c
dn_sched_prio.c
dn_sched_kps.c
dn_sched_qfq.c
dn_sched_ r r . c
dn_sched_wf2q.c

47 / 49

Conclusions ...
theory There are many ways to do packet scheduling;
theory one size does not fit all;user the packet scheduling architecture in dummynet permits
very flexible configurations;user works on Linux/OpenWRT and Windows, too (more on
this tomorrow);kernel adding a new scheduler is relatively straightforward;
kernel very useful tool for researchers on traffic scheduling;
kernel and there is some testing harness so you can debug andevaluate your algorithms in user space.

48 / 49

... credits, and future work
Thanks to the OneLab project (www.onelab.eu), the NETOS
project (info.iet.unipi.it/∼luigi/netos/) and Riccardo Panicucci
who did a lot of the coding.
Future work will cover:◮ more performance measurements;◮ optimize generic code paths;◮ support for hierarchical schedulers;◮ more schedulers (e.g. 802.11b/g almost complete);
More info at
http://info.iet.unipi.it/∼luigi/dummynet/

49 / 49