The lecture covers link scheduling algorithms in packet switched networks, with an emphasis on
scheduling algorithms that provide service guarantees on delay, fairness,
and delay variations (delay jitter).
Topics include the delay analysis and the development of schedulability
conditions that determine if a set of service guarantees can be satisfied.
The course addresses the stateoftheart of representing and analyzing
scheduling algorithms in the context of the deterministic network calculus.
The course also covers implementation techniques of link scheduling algorithms.
refer to draft chapters available through the Portal.
 Review of Packet Switching
Most textbooks on computer networks are suitable as reading for this part of the lecture. Below are additional references.
 Scheduling (FIFO, SP, EDF)

J. Liebeherr, D. E. Wrege, and D. Ferrari.
"Exact Admission Control in ContinuousMedia Networks with Bounded Delay Services."
IEEE/ACM Transactions on Networking, 4(6):885901, December 1996.
(Paper)
(DOI: 10.1109/90.556345)
 "Chapter 4: Link Scheduling," Access through UofT Portal.
 Taxonomy

H. Zhang.
"Service disciplines for guaranteed performance service in packetswitching networks."
Proceedings of the IEEE, 83(10):13741396,
Oct 1995.
(DOI: 10.1109/5.469298)
 Fair Scheduling (GPS, WFQ)
 Chapter 5: Fair Scheduling. Access through UofT Portal.

A. K. Parekh and R. G. Gallager.
"A generalized processor sharing approach to flow control in integrated services networks: The singlenode case."
IEEE/ACM Transactions on Networking (ToN),
1(3):344357, June 1993.

A. K. Parekh and R. G. Gallager.
"A generalized processor sharing approach to flow control in integrated
services networks: the multiple node case."
IEEE/ACM Transactions on Networking (ToN),
2(2):13750, April 1994.

A. Demers, S. Keshav, S. Shenker.
"Analysis and simulation of a fair queueing algorithm."
Proc. ACM SIGCOMM, pages 112, August 1989.
 Variations of Fair Scheduling (WRR, DRR, SCFQ, SFQ, WF2Q)

J. C. Bennett, H. Zhang.
"WF^{2}Q: worstcase fair weighted fair queueing."
Proc. IEEE INFOCOM, pp. 120128, March 1996.
(DOI: 10.1109/INFCOM.1996.497885

J. C. Bennett, H. Zhang.
"Hierarchical packet fair queueing algorithms."
Proc. ACM SIGCOMM, pp. 143156, August 1996.
(DOI: 10.1109/90.649568

P. Goyal, H. M. Vin, H. Chen.
"Starttime fair queueing: a scheduling algorithm for integrated services
packet switching networks."
Proc. ACM SIGCOMM, pp. 157168, August 1996.
(DOI: 10.1145/248157.248171

S. J. Golestani.
"A selfclocked fair queueing scheme for broadband applications."
Proc. IEEE INFOCOM, pp. 636646, June 1994.
(DOI: 10.1109/INFCOM.1994.337677)

S. J. Golestani.
"Network Delay Analysis of a Class of Fair Queueing Algorithms."
IEEE Journal on Selected Areas in Communications (JSAC),
13(6):10571070, August 1995.
(DOI: 10.1109/49.400661)

M. Shreedhar, G. Varghese.
"Efficient fair queuing using deficit roundrobin."
IEEE/ACM Transactions on Networking,
4(3):375385, June 1996.
(DOI: 10.1109/90.502236)

C. Semeria.
"Supporting Differentiated Service Classes: Queue Scheduling Disciplines."
Juniper Networks, White Paper, 2001.
(Paper)
 MinPlus and MaxPlus Network Calculus
The network calculus is a methodology for the
analysis of communication networks, which
exploits that many computer network models become
tractable for analysis if they are expressed in a minplus or maxplus algebra.
While the minplus network calculus is more convenient for
capacity provisioning in a network, the maxplus network calculus
is very suitable to express the operation of scheduling or shaping algorithms.
There are two excellent textbooks available on the topic:
 C.S. Chang. "Performance Guarantees in Communication Networks."
Springer Verlag 2000.
(available as hard copy from the library)
 J. Y. LeBoudec and P. Thiran.
"Network Calculus."
Springer Verlag, Lecture Notes in Computer Science, LNCS 2050, 2001.
(available online at http://ica1www.epfl.ch/PS_files/netCalBookv4.pdf)
An elementary introduction to the minplus network calculus is given in:

Chapters 13. Access through UofT Portal.
For the maxplus network calculus refer to:

J. Liebeherr.
"Duality of the MaxPlus and MinPlus Network Calculus."
Foundations and Trends in Networking, 11(34):139–282,
2017.
(Paper)
(DOI: 10.1561/1300000059)
 Service Curve Earliest Deadline First (SCED)
A SCED scheduler 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.
 H. Sariowan, R. L. Cruz, G. C. Polyzos.
"SCED: a generalized scheduling policy for guaranteeing qualityofservice."
IEEE/ACM Transactions on Networking,
7(5,):669684, 1999.
(DOI: 10.1109/90.803382)
For maxplus SCED, refer to:

J. Liebeherr.
"Duality of the MaxPlus and MinPlus Network Calculus (Chapter 12)."
Foundations and Trends in Networking, 11(34):101–130,
2017.
(Paper)
(DOI: 10.1561/1300000059)
 Guaranteed Rate Scheduling
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 wellknown weakness of VirtualClock is that a flow that has 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 the VirtualClock
is a (packetized) version of a network element that ensures a lower service curve
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 PacketScale Rate Guarantee (PSRG) scheduler
is a scheduling algorithm that realizes a maxplus adaptive service curve.
Note: Some older research views Fair Queueing algorithms as examples of
Guaranteed Rate scheduling. When doing so, it ignores that fair
schedulers, such as WFQ, guarantee rates over arbitrary small time intervals.
Relevant papers on Guaranteed Rate scheduling:

D. Stiliadis and A. Varma.
"Latencyrate servers: a general model for analysis of traffic scheduling algorithms."
IEEE/ACM Transactions on Networking, 6(5):611624, 1998.
(DOI:10.1109/90.731196)

P. Goyal, S. Lam, and H. Vin.
"Determining endtoend delay bounds in heterogeneous networks."
Multimedia Systems, 5(3):157163, 1997.
(DOI: 10.1007/s005300050052)
 J. Y. LeBoudec and P. Thiran.
"Network Calculus."
Springer Verlag, Lecture Notes in Computer Science, LNCS 2050, 2001. (see Section 2.1)
(available online at http://ica1www.epfl.ch/PS_files/netCalBookv4.pdf)
Adaptive service curves:

R. Agrawal, R. L. Cruz, C. M. Okino, and R. Rajan.
"A framework for adaptive service guarantees."
In Proc. of the Annual Allerton Conference on Communication
and Computing, Volume 36, pages 693–702, 1998.
(Link)

C. M. Okino.
"A framework for performance guarantees in communication networks."
PhD thesis, University of California San Diego, 1998.
(Link)
PSRG and maxplus adaptive service curves:

J. C. R. Bennett, K. Benson, A. Charny, W. F. Courtney, and J.Y. Le Boudec.
"Delay jitter bounds and packet scale rate guarantee for expedited forwarding."
IEEE/ACM Transactions on Networking, 10(4):529–540, 2002.
(DOI: 10.1109/TNET.2002.801404)

J. Liebeherr,
"Duality of the MaxPlus and MinPlus Network Calculus (Chapter 12)."
Foundations and Trends in Networking. Vol. 11, No. 34, pp. 101–130,
2017.
(Paper)
(DOI: 10.1561/1300000059)
 Hierarchical Scheduling Algorithms
The motivation for hierarchical scheduling is to support resource management
policies that share link bandwidth at an output link at multiple levels, e.g.,
between organizations, between traffic classes, and between flows in a class.

S. Floyd and V. Jacobson.
"Linksharing and Resource Management Models for Packet Networks,"
IEEE/ACM Transactions on Networking, 3(4):365386, August 1995.
(DOI: 10.1109/90.413212)

J. C. Bennett, H. Zhang.
"Hierarchical packet fair queueing algorithms."
IEEE/ACM Transactions on Networking, 5(5):675689, October 1997.
(also: Proc. ACM SIGCOMM, pp. 143156, August 1996.)
(DOI: 10.1109/90.649568

I. Stoica, H. Zhang, and T. S. E. Ng.
"A hierarchical fair service curve algorithm for linksharing, realtime, and priority services."
IEEE/ACM Transactions on Networking, 8(2):185199, April 2000.
(also: Proc. ACM SIGCOMM, pp. 249262, August 1997.)
(DOI: 10.1145/263109.263175
(Technical Report)

Nonworkconserving Schedulers,
Scheduling with Jitter Control
Schedulers are `nonworkconserving' if they may not transmit trafffic even though there
is a backlog. Nonworkconserving scheduling is applied for two reasons: (1) pernode
traffic shaping, and (2) delay jitter control.
With pernode traffic shaping, traffic arriving to each node must first pass through a
traffic shaper, with the purpose of reducing the burstiness of a flow, which
may have increased when traffic was multiplexed at the previous node.
Delay jitter refers to the variations of delay experienced by a traffic flow.
Bounds on delay jitter control the difference between the maximum and the minimum
delay.
In the network calculus, bounds on the delay jitter are ensured by a "damper" network element.

H. Zhang.
"Service disciplines for guaranteed performance service in packetswitching networks."
Proceedings of the IEEE, 83(10):13741396,
Oct 1995.
(DOI: 10.1109/5.469298)

R. L. Cruz.
"SCED+: Efficient Management of Quality of Service Guarantees."
IEEE INFOCOM, pages 625634, April 1998.
(DOI:10.1109/INFCOM.1998.665083)
 C.S. Chang. "Performance Guarantees in Communication Networks."
Springer Verlag 2000. (Sections 2.3.6, 6.3.3).
 RealTime Scheduling
Long before they became a topic in packet networks, scheduling algorithms
were studied extensively by the realtime systems community (main conferences are RTSS and RTAS). The object of study is scheduling of multiple
tasks (processes) in a realtime operating system.
A particular assumption is that tasks are
"periodic," that is, tasks arrive periodically after a fixed time interval,
and that the deadline of a task is equal to its period.
The foundation of realtime scheduling was established in the early 1970's by
the seminal "Liu & Layland paper".

C. L. Liu and J. W. Layland,
"Scheduling Algorithms for Multiprogramming in a Hard Real Time Environment,"
Journal of the ACM,
Vol. 20, No. 1, pp. 4661, January 1973.
(DOI: 10.1145/321738.321743)