Date | Topics | Material |
Lecture 1  (Jan 9) |
Review of Packet Switch Architectures
Introduction to Scheduling and Shaping Motivation (Sigcomm 2017 presentation) |
(slides)
(slides),   (slides) (slides) (video) |
Lecture 2  (Jan 16) | Fair Queueing (GPS, WFQ) |
(slides)
(slides) |
Lecture 3  (Jan 23) |
Variations of Fair Queueing
(WRR, DRR, SCFQ, SFQ, WF2Q) |
(slides) |
Lecture 4  (Jan 30) | Hierarchical Schedulers |
(slides) (slides) |
Feb 6 | Rescheduled | |
Lecture 5  (Feb 13) |
Scheduling algorithms in Linux ("TC" and "Qdisc")
Linux TC Workshop |
(slides)
see Assignments |
Lecture 6  (Feb 20) |
Theory of Scheduling and Shaping: Network Calculus
|
(slides)
(slides) (slides) |
Lecture 7  (Feb 27) |
SCED (Service Curve Earliest Deadline First) Guaranteed Rate Scheduling |
(slides:(SCED))
(slides(VirtualClock)) (slides: (Guar. Rate)) |
Lecture 8  (Mar 5) |
Quality of Service QoS)
Schedulability Conditions |
(slides)
(slides) |
Lecture 9  (Mar 12) |
Data structures for scheduling and shaping
|
(slides)
(slides) |
Lecture 10  (Mar 19) |
Google’s B4 network (Sigcomm 2013)
BwE: Bandwidth enforcer (Sigcomm 2015) Carousel (Sigcomm 2017) (revisited) |
(video: data center)
(slides: B4) (video: BwE) (PDF: Carousel) (video: Carousel) |
Lecture 11 
(Mar 26) |
PIFO (Sigcomm 2016)
Universal Packet Scheduling (NSDI 2016) |
(slides)
(video)
(slides) (video) |
Lecture 12  (Apr 2) |
Eiffel (NSDI 2019)
Loom (NSDI 2019) |
(slides)
(Loom:slides) |
Lecture 13  (Apr 9) |
Time Sensitive Networking (TSN)
Urgency Based Scheduler (IEEE 802, 2016) |
(TSN:slides)
(UBS:slides) (UBS:slides) |
Additional:
The paper by Demers/Keshav/Shenker presents the first solution to the at the time open problem of devising a scheduling algorithm that can satisfy fairness properties. Parekh/Gallager studied the properties of fair queueing, in a fluid-flow and a packetized version. These papers are the starting point for decades of research on fair queueing.
Soon after the publication of the Parekh/Gallager papers, researchers started to work on making Weighted Fair Queueing more practical or improving its properties. The Deficit Round Robin (DRR) scheduler had a big impact on practical implementations, even though it is unable to guarantee fairness properties as the other schedulers. The last reference is a whitepaper from a routing vendor (Juniper), which describes how fair queueing is used in actual routers.
Required:Required:
Required:
SCED is a method to build scheduling algorithms that realize arbitrary service curves. This is done by tagging packets with a target departure time ("deadlines"), which are computed from the convolution of the arrivals and the given service curve), and transmitting packets in the order of deadlines. A schedulability condition is available that can determine if all deadlines can be met.
The objective of guaranteed rate scheduling is ensure that a flow
at a link with rate C receives a guaranteed rate r ≤ C, independent of the traffic
of other flows. (The rate guarantee may be enhanced by a delay guarantee.)
VirtualClock is an example of a scheduling algorithms with a guaranteed rate.
The well-known weakness of VirtualClock is that a flow, after having obtained
a rate in excess of the guarantee, may not receive any service for a period of time.
Using network calculus concepts, it can be shown that VirtualClock
is a network element that ensures a lower service curve
close to S(t) = rt.
Since a lower service curve at time t makes a rate guarantee over the interval [0,t),
the received service over short time intervals can deviate arbitrarily from the
guaranteed rate.
"Strict service curves" and "Adaptive service curves" are notions of service curves
that can ensure rate guarantees over short time intervals. While conceptually easier
than adaptive service curves, strict service curves are not
suitable for delay guarantees. The Packet-Scale Rate Guarantee (PSRG) scheduler
is a scheduling algorithm that realizes a max-plus adaptive service curve.
Note that fair scheduling algorithms also provide rate guarantees
with rate
Φi ⁄
∑j Φj (for flow i).
In fact, GPS and WFQ (the latter approximately)) offer strict rate guarantees.
Adaptive service curves:
PSRG and max-plus adaptive service curves:
The IEEE 802.1 task group on time-sensitive networking (TSN) defines standards for Ethernet transmissions with bounded delays and no loss. We are interested in looking at shaper and scheduler designs in the TSN standards, such as Credit Based Shaper (CBS) and Urgency Based Scheduler (now referred to as Asynchronous Traffic Shaping (ATS)).
Due Date | Assignment |
Jan 30 |
Assignment 1 (PDF) Files for Part 1: Sender.java Receiver.java ReadFileWriteFile.java data.txt movietrace.data Source files for Part 3: (all files should be stored in the same subdirectory "TokenBucket":) TokenBucket.java TokenBucketReceiver.java TokenBucketSender.java Bucket.java Buffer.java Documentation for source files for Part 3: Javadoc |
Mar 27 |
Lab S1 Lab S2 |
Mar 19 |
Assignment 2 (PDF) Files for Assignment 2: (all files should be stored in the same subdirectory "PacketScheduler":) Buffer.java PacketScheduler.java SchedulerReceiver.java SchedulerSender.java Documentation for source files for Assignment 2: Javadoc |