New developments
in link emulationand packet schedulingin FreeBSD, linux and Windows
Luigi Rizzo, Università di Pisa
March 29, 2010

SummarySome recent, network related projects at UNIPI:◮ The dummynet emulator: new features,performance, Linux and Windows ports(mostly supported by the ONELAB2 project - EuropeanCommission)◮ Fast packet scheduling algorithms: QFQ(joint work with Fabio Checconi and Paolo Valente, partly
supported by the NETOS project - Univ. di Pisa)

2 / 43

Dummynet

Why emulation

Emulation is a standard tool in protocol and application
testing. It gives you:◮ ease of configuration/setup;◮ reproducibility;◮ more realistic results than simulation.
Several existing options:◮ dummynet, NISTnet, tc+netem, netpath...

4 / 43

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 and then to pipes,

which model communication links;◮ on exit, packets are reinjected in the protocol stack or in
the classifier.
5 / 43

User interface/sbin/ipfw is the main user interface for the system.
Use is very simple:
ipfw
ipfw
ipfw
ipfw

add 100 pipe 1 out dst - ip 1.2.3.4
add 100 pipe 2 in src - ip 1.2.3.4
pipe 1 config bw 256 Kbit / s delay 12 ms
pipe 2 config bw 4 Mbit / s delay 2 ms

6 / 43

Main applications◮ link emulator (protocol/app testing):◮◮

in-node emulator (workstation, Planetlab);transparent bridge;◮ local traffic shaping:◮◮share or reserve bandwidth for certain apps;outgoing or incoming traffic shaping;◮ traffic shaper in testbeds (Emulab/Planetlab) or ISPs:◮◮

must scale to thousands of pipes;
needs extra features for quick classification/demux.
7 / 43

Emulation in Planetlab
As part of the ONELAB2 project, we added dummynet as an
in-node emulator in Planetlab:◮ users can define independent emulated links;◮ a frontend hides the complexity of configuration:◮ client and server modes create typical configurations.

netconfig config client 22 ,80 IN bw 6 Mbit / s OUT bw 256 Kbit / s
8 / 43

Dummynet internals: Pipes◮ Only model basic features of a link:queue with configurable size and management policy(FIFO, RED);◮ programmable link bandwidth;◮ deterministic propagation delay;◮◮ avoid non deterministic behaviour:

do not deal with error/loss/delay models;◮ use real traffic to cause perturbations;◮◮ ... except for some useful features:◮◮

random packet drop and random rule match;
you don’t have to use them if you don’t like the model.
9 / 43

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.
◮◮

10 / 43

Beyond pipes: queues, schedulers, links
More complex configurations require to split a pipe in its
components – queue, scheduler, link – so we can:◮ attach multiple queues to one scheduler;◮ configure scheduler features (algorithm, weights, etc.);◮ model more complex links (e.g. radio).

11 / 43Per-flow queues / Flowsets
A flowset is an abstraction used to model per-flow queues. It
has several attributes:◮ a flow-mask, used to create per-flow queues;◮ a scheduler to which queues are attached to;◮ weight/priority and other scheduling parameters;
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
mask dst - ip 0 xff weight 1luigi - pc
my - subnet /24

fs 1

fs 2
mask ...

x.1
x.2
...
x.255

12 / 43

LinksLinks can model more than bandwidth and delay:◮ uniform random loss;
ipfw pipe 1 config plr 0.06 // 6% loss on this link

◮ reordering (through probabilistic matching):// 30% of packets go to pipe 1 , 70% go to pipe 2
ipfw add 100 prob 0.3 pipe 1 dst - ip 1.2.3.4
ipfw add 100 pipe 2 dst - ip 1.2.3.4
ipfw pipe 1 config delay 100 ms
ipfw pipe 2 config delay 20 ms◮ MAC overheads (preambles, contentions, link-level rxmit):◮

use profiles or model the MAC as a scheduler.
13 / 43

Link Profiles
Profiles model the extra air-time for a packet transmission◮ an empirical function gives the distribution of extra
air-time;◮ not tied to a specific technology. Can be used for wirelessor wired links of various kinds;◮ can model low level features (preambles, inter-framegaps...) or more complex ones (contentions,retransmissions, collisions);◮ of course it is not as precise as full emulation.
14 / 43

SchedulersSchedulers arbitrate access of multiple flows to the same link..
.

◮ newly designed API supports configurable schedulers:

FIFO, DRR, PRIO, WF2Q+, QFQ, KPS;
◮ a MAC layer is a scheduler, too. An 802.11b scheduler

will be available shortly;◮ schedulers have masks, too:
ipfw queue 1 config sched 5 weight 10 // used for ssh
ipfw queue 2 config sched 5 weight 1 // all other traffic
ipfw add 100 queue 1 out proto tcp src - port 22 ,53
ipfw add 100 queue 2 out// each /24 subnet has its own instanceipfw sched 5 config type QFQ mask src - ip 0 xffffff00
15 / 43

Schedulers (cont)
The scheduler API makes dummynet a tool for testingschedulers, too:
◮ 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 *. c120553
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

16 / 43

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

fs 2

schedmask src-ip

mask src-ip

mask dst-ip

...
...

17 / 43

Testing framework
We have support to run schedulers in user space.
Controller

Packetgenerator

Scheduler◮ generate traffic for a programmable number of flows,packet size and weight distribution;◮ carefully control the operating point of the scheduler;./ test - alg rr - qmin 4 n - qmax 30 n - flowsets 1::512 ,8::64dn_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.70318 / 43

Accuracy
At least three main factors influence the accuracy ofemulation:◮ timer accuracy (20 µs .. 1 ms or less);◮ competing traffic (120 µs .. 1.2 ms per competing link);◮ Operating System interference (virtually unbounded;
normally in the 30 .. 200 µs range).
Accuracy can be improved addressing these three factors.
100 µs is a reasonable target on modern hardware.

19 / 43Performance
Per-packet processing is the main factor limiting performance.
◮ detailed analysis in April 2010 CCR paper;◮ split classifier + scheduling + emulation cost;◮ classifier cost is C + O(R) (number of rules). Normally
400 .. 1000 ns with up to 20 rules.
◮ scheduling from O(1) to O(log N);◮ emulation: O(log N), 700 .. 1500 ns with 1 .. 1000 flows.
Overall, 2-3 µs/pkt on entry level PC hardware.

20 / 43

Porting
Dummynet has been recently ported to Linux and Windows.
◮ We use the same codebase for all platforms;◮ very little conditional code (except in headers);◮ glue libraries to map FreeBSD kernel APIs to underlying
OS APIs.
Main differences between platforms:◮ internal packet representation;◮ locking;◮ packet filtering hooks;◮ timers (API and resolution);◮ module loading/unloading;◮ userland/kernel communication.
21 / 43

Packet representation

In-kernel packet representation
is similar in principle, different in details between BSD(mbufs), Linux (skbufs) andWindows (NDIS PACKET).
◮ create mbuf lookalikes on entry, fill with metadata from

native representation;◮ internally, only use mbufs;◮ destroy the wrapper on exit.

22 / 43

Locking and other OS APIs

◮ mostly dealt with through macros, preprocessor magic

and wrapper functions;◮ a 1:1 mapping between equivalent functions was almostalways possible;◮ hardest part was locating the right API to use (e.g.,ExSetTimerResolution() on Windows);◮ changing kernel APIs are very challenging too (Linuxnetfilter API is a moving target even within 2.6.X);

23 / 43

Availability and Credits
See http://info.iet.unipi.it/∼luigi/dummynet/
Supported operating systems:◮ FreeBSD (since 1998), OSX (2006)◮ Linux/OpenWRT (2009)◮ Windows XP, Windows 7 (2010)
Credits:◮ Marta Carbone (Linux port)◮ Fabio Checconi (QFQ, KPS)
◮ Riccardo Panicucci (scheduler API)
◮ Francesco Magno (Windows port)

24 / 43

O(1) packet scheduling at highdata rates

O(1) packet scheduling at high data rates..
.

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.
26 / 43

Problem setting and definitions
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;
27 / 43Service Guarantees
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◮ 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.
28 / 43

State of the art of fast 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 poorguarantees (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,Zhang1999) have near-optimal guarantees and O(1) timecomplexity (but several times slower than RR).

29 / 43

Our result
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;◮ 110 ns/pkt on common workstations, compared to 55 nsfor DRR and 400 ns for KPS.
Fair Queueing in software (or inexpensive hardware) is feasible
at GBit/s rates.

30 / 43

QFQ overview
QFQ operates as other timestamp-based schedulers:◮ track the behaviour of a Fluid System;◮ for each packet, compute Virtual Start and Finish times;◮ schedule in Finish time order among packets that are i)available and ii) already started in the Fluid Server.
The sorting steps imply a O(logN) complexity.
◮ use approximated sorting to reduce complexity;◮ use careful approximations to preserve guarantees;◮ use extra data structures to reduce constants.

31 / 43

QFQ data structuresenqueue()dequeue()◮ Approximated sorting based on rounded timestamps andsplitting flows into a constant number of groups;◮ flow i belongs to group ⌈log2 Li /Φi ⌉;◮ rounding intervals grow exponentially.
32 / 43

QFQ data structures – sorting

enqueue()dequeue()◮ Use approximate timestamps for sorting, but exact values

when computing timestamps;◮ within each group, there is only a finite number of slots,

so we can use bucket sort;◮ for selection purposes, use same (F − S) for all flows in agroup, so the order on F and S is the same.
33 / 43

QFQ data structures – selection

enqueue()dequeue()◮ Manage four Set of Groups. In each set, index reflects

Virtual Time ordering;◮ the eligible flow with minimum F can be found with one

FFS instruction instead of scanning the groups;◮ moving groups between sets does not require loops,

either.
34 / 43

QFQ – enqueueenqueue()dequeue()◮ bucket-insert in the group;◮ update group state and sets.

35 / 43

QFQ – dequeueenqueue()dequeue()◮ locate first bit in set ER;◮ serve first flow in the first slot of the corresponding group;◮ possibly put the flow in a new slot;◮ update group state and sets.
36 / 43Service guarantees
Service guarantees for QFQ:
B-WFIk = 3φk σi + 2φk L(remember that Lk /Φk < σi ≤ 2Lk /Φk )  k

L1kT-WFI = 3 k + 2L
φR
(R is the link’s rate).

37 / 43

Experimental results
Measurements taken by running the kernel code in userspace:
Controller

Packetgenerator

Scheduler◮ generate traffic for a programmable number of flows,packet size and weight distribution;◮ carefully control the operating point of the 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.70338 / 43Performance comparison – scalabilityenqueue() + dequeue() time, ns
700
WF2Q+
S-KPS

600time (ns)500
400300
QFQ

200DRR
FIFO
NONE

100
0
1

41664

256
1k
Flows

4k

32k
39 / 43Mixed workloads
Measurement results in ns for an enqueue()/dequeue() pairand packet generation. Standard deviations are within 3% ofthe average.
Flows NONE FIFO DRR QFQ KPS WF2Q+
16283 105 221 450
21086080 102 163 543
344645980 100 158 540526
512
64
85 110 175 560
740
4k
74
102 157 197 590
1110
32k62117 147 222 601
1690
1:32k,2:4k,4:2k,8:1k,128:16,1k:1 flowsmix
92
119 160 255 612
1715

40 / 43

Conclusions◮ QFQ is a Timestamp-based scheduler with near optimal

service guarantees and true O(1) run time;◮ 110 ns/pkt, only 2 times slower than RR and 4 times
faster than comparable algorithms;◮ already available as part of dummynet, together withseveral other schedulers;◮ technical report and code at
http://info.iet.unipi.it/∼luigi/qfq/◮ Joint work with Fabio Checconi and Paolo Valente;◮ soon available as a Click module;

41 / 43

Future work

Future work:◮ detailed performance analysis on low-end hardware(OpenWRT platforms);◮ identify performance bottlenecks, memory accesspatterns;◮ investigate feasibility of hardware implementations(including NETFPGA).

42 / 43

Links and further info

◮ For dummynet

http://info.iet.unipi.it/∼luigi/dummynet/◮ For QFQ
http://info.iet.unipi.it/∼luigi/qfq/
For everything else, there’s www.google.com

43 / 43