General Information

First class is Sep. 13, 2011, 12:00-1:30pm (BA 4164).
Syllabus

Course Description

The network calculus has evolved into an elegant framework for analytical performance evaluation of data networks. It provides methods to determine resource requirements of traffic flows in a network using an envelope description for arrivals and service. More recently, stochastic extensions of the network calculus, referred to as Stochastic Network Calculus have resulted in the discovery of new scaling laws of network delays, and an end-to-end analysis of a network with heavy-tailed traffic. This course discusses progress and discoveries on delay and backlog analysis over the past 20 years, that have led to the Stochastic Network Calculus methododology.

Lecture Schedule and Readings:

Week	Topics	Material	Reading
Week 1 (Sep 12-16)	Packet Switches Introduction to Deterministic Analysis	PPT PPT, PPT	[LectureNotes, Chp. 1.1-1.4]
Week 2 (Sep 19-23)	Traffic Envelopes and Regulators		[LectureNotes, Chp. 2.3-2.5]
Week 3 (Sep 26-30)	Introduction to Statistical Multiplexing Bufferless Multiplexer	PDF (PPT) PDF (PPT)	[LectureNotes, Chp. 5.1] [LectureNotes, Chp. 5.2]
Week 4 (Oct 3-7)	Statistical Envelopes		[LectureNotes, Chp. 5.3-5.4], [Boorstyn00]
Week 5 (Oct 10-14)	Lectures will be rescheduled
Week 6 (Oct 17-21)	Effective Bandwidth Exponentially Bounded Burstiness		[LectureNotes, Chp. 5.8], [Weiss95] [LectureNotes, Chp. 5.6], [Yaron93]
Week 7 (Oct 24-28)	Statistical Sample Path Envelopes		[LectureNotes, Chp. 6.1-6.4],
Week 8 (Oct 31-Nov 4)	Min-Plus Algebra Service Curves		[LectureNotes, Chp. 1.5], [LectureNotes, Chp. 2.1-2.2],
Week 9 (Nov 7-11)	Performance Bounds (deterministic)		[LectureNotes, Chp. 3.1-3.3],
Week 10 (Nov 14-18)	Statistical Service Curves		[Ciucu06], [Ghiassi11]
Week 11 (Nov 21-25)	Statistical Performance Bounds		[Ghiassi11]
Week 12 (Nov 28-Dec 2)	Scheduling and Delay Bounds	(PPT)	[Boorstyn00] [Liebeherr10]

Problem Sets

Homework 1 (Given: Oct 5, Due: Oct 19).
(PDF) (Link to trace)

Homework 2 (Given: Nov 2, Due: Nov 16).
(PDF)

Reading List

[LBT] refers to J.Y. Le Boudec, P. Thiran: Network Calculus, Version May 10, 2004.
Available online at http://ica1www.epfl.ch/PS_files/netCalBookv4.pdf .
[SNC] refers to Y. Jiang, Y. Liu: Stochastic Network Calculus, Springer 2008.
Available online at http://www.springerlink.com/content/978-1-84800-126-8#section=43531&page=3&locus=27
(Note: To access this book, you must be on the UofT network or login via the UofT portal).

[LectureNotes] refers to class notes written by the instructor (in draft form). Class notes are posted on Blackboard.

DOI refers to the Digital Object Identifer where online versions of the papers can be accessed, e.g., IEEE XPlore. When off-campus, you need to login to the library with your UTORid, to gain access to the papers.

[Boorstyn00] Statistical Service Assurances for Packet Scheduling Algorithms, R. Boorstyn, A. Burchard, J. Liebeherr and C. Oottamakorn, IEEE Journal on Selected Areas in Communications. 18(12):2651–2664, December 2000. [DOI].
[Weiss95] An introduction to large deviations for communication networks, A. Weiss, IEEE Journal on Selected Areas in Communications, 13(6):938-952, August 1995. [DOI].
[Yaron93] Performance and stability of communication networks via robust exponential bounds, Opher Yaron, Moshe Sidi. IEEE/ACM Transactions on Networking, 1(3): 372-385, June 1993. [DOI].

Ghiassi11

[Ghiassi11] The impact of link scheduling on long paths: Statistical analysis and optimal bounds, Y. Ghiassi-Farrokhfal, J. Liebeherr, and A. Burchard, Proceedings of IEEE Infocom 2011, Pages 1242-1250, April 2011. [DOI].
[Ciucu06] Scaling Properties of Statistical End-to-end Bounds in the Network Calculus, IEEE Transaction on Information Theory, 52(6):2300–2312, June 2006. [DOI].
[Liebeherr10] On the Impact of Link Scheduling on End-to-End Delays in Large Networks, (with Y. Ghiassi-Farrokhfal and A. Burchard) IEEE Journal on Selected Areas in Communications, Special Issue on Trading Rate for Delay at the Transport and Application Layers, 29(5):1009–1020, May 2011. DOI http://dx.doi.org/10.1109/JSAC.2011.110511. [DOI].