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.



Lecture Schedule (tentative):


Date Topics Material
Lecture 1  (Jan 8) Review of Packet Switch Architectures
Introduction to Scheduling and Shaping
Motivation (Sigcomm 2017 presentation)
PPT
PPT,   PPT
PDF Video
Lecture 2  (Jan 14) Fair Queueing (GPS, WFQ) PPT
PDF (updated)
Lecture 3  (Jan 21) Variations of Fair Queueing
(WRR, DRR, SCFQ, SFQ, WF2Q)
Lecture 4  (Jan 27) Hierarchical Shapers and Schedulers
Lecture 5  (Feb 4) Theory of Shaping: Network Calculus
Lecture 6  (Feb 11) Guaranteed Rate Scheduling
SCED (Service Curve Earliest Deadline First)
  (Feb 19) Family Day (University closed)
Lecture 7  (Feb 25) Traffic control (tc) in Linux
Lecture 8  (Mar 4) Emulab workshop
Lecture 9  (Mar 11) Data structures for scheduling and shaping:
Priority queues, calendar queues, timing wheel
Lecture 10  (Mar 18) Google’s B4 network and Bandwidth enforcer
Lecture 11  (Mar 25) PIFO (Sigcomm 2016)
Carousel (Sigcomm 2017)
Lecture 12  (Apr 1)
Universal Packet Scheduling (NSDI 2016)
Eiffel (NSDI 2018)
Lecture 13  (Apr 9) Urgency Based Scheduler (IEEE 802, 2016)



Reading

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

Reading list for remaining lectures will be posted shortly.



Assignments

Due Date Assignment
Jan 21
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




 

 

 

 

General Info

Lecture Schedule

Reading

Assignments