Network Calculus

General information

Suggested credits

5

Prerequisites

Description

Network calculus is a new system theory which applies to deterministic queuing systems found in e.g. communication networks. The theory and a lot of the existing results when applying it to the domain of computer networks are presented in the book [1] which is the main material for this course along with the expository paper [2]. The theory is however applicable to a variety of problems concerning flows in networks, see the link to a context for network calculus below for an overview.

To get a feeling for the type of problems studied and how they are analyzed we suggest the following. A quick introduction to the subject is to first browse through [3], which is one of the first applications of this type of analysis to computer networks. There a traditional algebraic approach is used to compute (upper bounds on) the delay in network elements under the assumption that 1) Traffic at ingress is shaped in a specific manner and 2) Network elements offer some sort of guarantees. Continuing by browsing through [4] where Chang, based on the seminal work by Cruz, showed that since the functions being used are non-decreasing functions (i.e. "number of bits transmitted/received up to time t") the calculus is much simpler and more elegant if instead of the usual algebra of real numbers we use (min,+)-algebra (where the addition operation is replaced with "min" and the multiplication is replaced with "+"). He shows that these two operations form a semiring, he defines the (min,+)-convolution, the sub-additive closure of a non-decreasing sequence/function and proves the optimality of leaky bucket shaping.

In [1] and [2] Boudec et al extends the above work by showing how to analytically model various types of network guarantees (IntServ, Guaranteed-Rate Schedulers, etc.); how the intuition behind DiffServ was flawed and delay guarantees for EF PHB (Expedited Forwarding Per Hop Behaviour) works only if the network load is dramatically limited (basically proving that DiffServ is flawed).

The organisers of this course are members of the Image Coding Group. We have recently become aware of network calculus and and think that this is an interesting and important theory. Our plan is to let the participants take an active part of the course by presenting some of the material during the seminars.

We've found a short presentation by Guy Cohen of the Max Plus group at INRIA of the context for network calculus which you can read here.

Literature

[1] Jean-Yves Le Boudec, Patrick Thiran, Network calculus, Springer-Verlag, ISBN 3-540-42184-X.

[2] Jean-Yves Le Boudec, "Network calculus made easy", Technical Report 96/218, DI-EPFL, CH-1015 Lausanne, Switzerland, December 1996. Download from CiteSeer.

[3] Rene Cruz, "Quality of Service guarantees in virtual circuit switched networks", IEEE Journal on Selected Areas in Communications, 13(6):1048-1056, Aug 1995. Download from IEEE Explore.

[4] Cheng-Shang Chang, "On deterministic traffic regulation and service guarantees: A systematic approach by filtering", IEEE Transactions on Information Theory, Vol. 44, pp. 1097-1110, 1998. Download from IEEE Explore.

Examination

To receive the credits, presence at at least eight of the seminars, giving one seminar and correctly solved problems are required.

Examiner

Thomas Kaijser

Organizer & maintainer of the web-pages

Peter Johansson

Organisation

The course will consist of ten seminars.

At each seminar, one or two of the participants will give a (two hour) lecture on one of the chapters in the book, and give a few problems (one or more, possibly from the book) to the other participants. Written solutions to the problems should be handed in at the next seminar.

Preliminary schedule

No.WeekDayDateTimePlace
17We11/213-15A
28Tu17/215-17A
39We25/212-14N
410Th4/313-15A
511We10/313-15A
612Fr19/313-15A
713Fr26/313-15A
814We31/313-15A
917We21/413-15A
1018We28/413-15A
1119Fr7/515-17A
1219Fr19/515-16A
A = Algoritmen
N = Nollstället

Seminars

1. Startup meeting.

Literature: -
Contents: Course organisation details, a little bit of background. Assignment of lectures to the participants.
Speaker: Peter & Thomas

2. Introduction

Literature: [1], chapter 1-1.4.2
Contents: Arrival curve, service curve, backlog, virtual delay.
Speaker: Robert
Lecture notes: Power point presentation or Postscript.
Problems: 1.3, 1.5, 1.8, 1.13 from [1].

3. Basic Min-plus calculus.

Literature: [1], chapter 3-3.1.6
Contents: Min-plus calculus, dioid, concave, convex, star-shaped functions, convolution.
Speaker: Jonas
Lecture notes: postscript or PDF.
Problems: 3.1, 3.2, 3.3 from [1].

4. Network calculus basics.

Literature: [1], chapter 3.1.7-3.1.8,1.4.3
Contents: Subadditive functions, subadditive closure, concatenation of systems, pay bursts only once.
Lecture notes: PDF or LaTeX (prosper)
Speaker: Jonas, Peter

5. Network calculus basics, cont.

Literature: [1], chapter 1.4.4-1.6.2
Contents: Strict service curves, greedy shapers, maximum service curves, delay from backlog.
Speaker: Peter

6. Network calculus basics, cont.

Literature: [1], chapter 1.6.3-1.7.3.
Contents: Variable/fixed delay, packetization.
Speaker: Peter Problems: 1.18, 1.19 from [1].

7. Min-plus calculus continued.

Literature: [1], chapter 3.1.9-3.1.11
Contents: Deconvolution, vertical and horizontal deviation.
Speaker: Harald
Lecture notes: PDF

8. Max-plus calculus and beginning of system theory.

Literature: [1], chapter 3.2-4.1.6 (up to thm 4.1.1)
Contents: Max-plus calculus, min-plus and max-plus operators, upper and lower semi-continuity, isotone operators, linear operators.
Speaker: Harald Problems: in PDF format.

9. Packetization.

Literature: [1], chapter 1.7.4
Contents: Packetized greedy shaper.
Speaker: K-G
Lecture notes: PDF

10. Effective bandwidth, GPS.

Literature: [1], chapter 1.8-2.1.5
Contents: Effective bandwidth, GPS and guaranteed rate nodes.
Speaker: K-G
Problems: 1.31, 1.38 and exercise left to the reader in example GPS after definition 2.1.1 from [1].

11. Min-plus & max-plus system theory.

Literature: [1], chapter 4.1.6-4.5
Contents: Linear, causal, shift-invariant and idempotent operators, closure of an operator, fixed point equations (time/space methods).
Speaker: Thomas
Problems: in PDF format.

Participants




This page is made in GNU Emacs.
No fancy WYSIWYG!