Doctoral School Lecture "Network Calculus"

Where, when, who, what

The class on Monday June 6 is in room INM011

Room: BC 04 except if mentioned otherwise

Time Date Teacher Contents Homework
8:15 - 10:00 09.03.2005 Patrick Thiran Chapters 1 and 3
8:15 - 10:00 23.03.2005 Patrick Thiran Chapters 1 and 3
16:15 - 18:00 08.04.2005 Patrick Thiran Chapters 1 and 3
8:15 - 10:00 13.04.2005 Patrick Thiran Chapters 1 and 3
16:15 - 18:00 29.04.2005 Jean-Yves Le Boudec Section 1.7 None
16:15 - 18:00 06.05.2005 Jean-Yves Le Boudec Section 1.7 Exercices 1.29, 1.31, 1.32, 1.34
10:15 - 12:00 Room INM 011 09.05.2005 Jean-Yves Le Boudec Sections 2.1 and 2.4 Exercices 2.1, 2.2 and 2.3
16:15 - 18:00 13.05.2005 Patrick Thiran Chapters 4 and 5
16:15 - 18:00 20.05.2005 Patrick Thiran Chapters 4 and 5
16:15 - 18:00 27.05.2005 Jean-Yves Le Boudec Chapters 6, 7 and 8 Exercises
10:15 - 12:00 Room INM 011 06.06.2005 Jean-Yves Le Boudec Chapters 6, 7 and 8
16:15 - 18:00 10.06.2005 Jean-Yves Le Boudec Chapters 6, 7 and 8 Reading Assignment, see below
16:15 - 18:00 17.06.2005 Reading group slot 1 Presentation of term paper
10:15 - 12:00 Room INM 011 20.06.2005 Reading group slot 2 Presentation of term paper

Time	Date	Teacher	Contents	Homework
8:15 - 10:00	09.03.2005	Patrick Thiran	Chapters 1 and 3
8:15 - 10:00	23.03.2005	Patrick Thiran	Chapters 1 and 3
16:15 - 18:00	08.04.2005	Patrick Thiran	Chapters 1 and 3
8:15 - 10:00	13.04.2005	Patrick Thiran	Chapters 1 and 3
16:15 - 18:00	29.04.2005	Jean-Yves Le Boudec	Section 1.7	None
16:15 - 18:00	06.05.2005	Jean-Yves Le Boudec	Section 1.7	Exercices 1.29, 1.31, 1.32, 1.34
10:15 - 12:00 Room INM 011	09.05.2005	Jean-Yves Le Boudec	Sections 2.1 and 2.4	Exercices 2.1, 2.2 and 2.3
16:15 - 18:00	13.05.2005	Patrick Thiran	Chapters 4 and 5
16:15 - 18:00	20.05.2005	Patrick Thiran	Chapters 4 and 5
16:15 - 18:00	27.05.2005	Jean-Yves Le Boudec	Chapters 6, 7 and 8	Exercises
10:15 - 12:00 Room INM 011	06.06.2005	Jean-Yves Le Boudec	Chapters 6, 7 and 8
16:15 - 18:00	10.06.2005	Jean-Yves Le Boudec	Chapters 6, 7 and 8	Reading Assignment, see below
16:15 - 18:00	17.06.2005	Reading group slot 1	Presentation of term paper
10:15 - 12:00 Room INM 011	20.06.2005	Reading group slot 2	Presentation of term paper

Slides

Introduction
Arrival curves (Sections 1.1, 1.2, 3.1 of the book)
Service curves (Sections 1.3, 1.4, 1.5, 2.2 of the book)
System theoretic aspects (Chapters 4, 5 (in part), 9 (in part) of the book)

Exercices

Chapter 1: arrival curves. Exercices 1.5 and 1.6
Chapter 1: arrival curves. Exercices 1.12 (misprint: assume beta to be convex and not concave) and 1.25
Reading Assignment: http://www.internet2.edu/~shalunov/writing/premium-service-failure.html
Answer the following questions in writing (1 to 50 lines):
1. What is Shalunov's main argument for claiming that Premium cannot be implemented satisfactorily ?
2. Propose one solution to his concern

Grading

Grade: 50% term paper + 50% final exam
The final exam is during the exam session (oral examination).
The paper will be presented during the last lecture of the semester. The paper can either be taken from the list below, or can be proposed by you. In both cases, you need to send the title of the paper to the instructors, who will validate your choice. You will be evaluated on the clarity of the presentation and your ability to summarize the paper (what is the problem addressed in the paper, what are the findings, how are they obtained, what are the possible shortcomings)

Final marks are converted to the swiss academic scale, which is in the interval [1, 6], where 4 is the minimum to pass. The mapping is: P = round (0.75 + 0.05 P') where P' is the mark on 100 and P is the mark on 6; round is the function that rounds to the nearest half integer, by excess (for example, round (2.34) = 2.5 ). P >= 4 corresponds to P' > 55.

Reading list

H. Kim and J. Hou, Network Calculus Based Simulation for TCP Congestion Control: Theorems, Implementation and Evaluation, Proc. IEEE-Infocom, Hong Kong, March 2004. Presented by Andrea Bergamini.
D. Starobinski and M. Sidi, Stochastically Bounded Burstiness for Communication Networks, IEEE Transactions on Information Theory, Vol. 46, No. 1, pp. 206-212, January 2000. Presented by Jean-Paul Wagner.
C.-S. Chang, D.-S. Lee and C.-Y. Yue, Providing Guaranteed Rate Services in the load balanced Birkhoff-von Neumann switches, Proc. IEEE-Infocom, San Francisco, March 2003. Presented by Abishek Garg.
Baccelli, F. and Hong, D. (2000) "TCP is Max-Plus Linear", Technical Report, August 2000, RR-3986, INRIA Rocquencourt. Proc. of SIGCOMM, September 2000.
H. Meyr and F. Munscher, "A unified algebraic representation of the MAP algorithm and its approximations", preprint pdf Presented by Ignace Wafo.
S. Gaubert and M. Plus.Methods and Applications of (max,+) Linear Algebra
F. Ciucu, A. Burchard, and J. Liebeherr, A Network Service Curve Approach for the Stochastic Analysis of Networks, Proceedings SIGMETRICS, 2005 (to appear). Presented by Gianluca Rizzo.
M. Zafer and E. Modiano, "A Calculus Approach to Minimum Energy Transmission Policies with Quality of Service Guarantees," IEEE Infocom, March, 2005 (or Y. Liu, A. Maxiaguine, S. Chakraborty, W. Tsang Ooi. "Processor Frequency Selection for SoC Platforms for Multimedia Applications". Proc. of the 25th IEEE International Real-Time Systems Symposium (RTSS 2004), IEEE Computer Society, Lisbon, Portugal, pages 336-345, December, 2004). Presented by M. Derin Harmanci.