Quick Information






General Information


Packet scheduling is the core component of many recent innovations in optimizing network performance and utilization. Modern networks rely on schedulers in two specific ways: 1) traffic shaping and hierarchical bandwidth sharing at end-hosts, and 2) scheduling in hardware switches. This course will give a survey of recent developments in the design of flexible scheduling and shaping methods, that are deployed in data centers and wide-area networks. Topics covered include (1) data structures for scheduling and shaping methods, (2) the scheduling architectures of Linux systems and commercial routers, (3) hierarchical bandwidth sharing. The course will also cover key scheduling techniques, with an emphasis on methods for fair queuing and service-curve based scheduling. Exposure will be given to formal descriptions of traffic control algorithms using concepts of the network calculus.




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)



Reading

Access to the papers via the DOI links requires authentication with your UTORID.


Assignments

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




 

 

 

 

General Info

Lecture Schedule

Reading

Assignments