5

- Linear algebra.
- Elementary abstract algebra (groups, rings, fields).
- Basic knowledge about linear systems.

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.

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

- Price: 34 EUR at Springer-Verlag, £27.99 at Amazon.
- Due to a generous agreement between the authors and Springer-Verlag the book is also available for free download.
- Errata

[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.

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

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.

No. | Week | Day | Date | Time | Place |
---|---|---|---|---|---|

1 | 7 | We | 11/2 | 13-15 | A |

2 | 8 | Tu | 17/2 | 15-17 | A |

3 | 9 | We | 25/2 | 12-14 | N |

4 | 10 | Th | 4/3 | 13-15 | A |

5 | 11 | We | 10/3 | 13-15 | A |

6 | 12 | Fr | 19/3 | 13-15 | A |

7 | 13 | Fr | 26/3 | 13-15 | A |

8 | 14 | We | 31/3 | 13-15 | A |

9 | 17 | We | 21/4 | 13-15 | A |

10 | 18 | We | 28/4 | 13-15 | A |

11 | 19 | Fr | 7/5 | 15-17 | A |

12 | 19 | Fr | 19/5 | 15-16 | A |

N = Nollstället

Contents: Course organisation details, a little bit of background. Assignment of lectures to the participants.

Speaker: Peter & Thomas

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].

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].

Contents: Subadditive functions, subadditive closure, concatenation of systems, pay bursts only once.

Lecture notes: PDF or LaTeX (prosper)

Speaker: Jonas, Peter

Contents: Strict service curves, greedy shapers, maximum service curves, delay from backlog.

Speaker: Peter

Contents: Variable/fixed delay, packetization.

Speaker: Peter Problems: 1.18, 1.19 from [1].

Contents: Deconvolution, vertical and horizontal deviation.

Speaker: Harald

Lecture notes: PDF

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.

Contents: Packetized greedy shaper.

Speaker: K-G

Lecture notes: PDF

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].

Contents: Linear, causal, shift-invariant and idempotent operators, closure of an operator, fixed point equations (time/space methods).

Speaker: Thomas

Problems: in PDF format.

Maintained by Peter Johansson, <pejoh@isy.liu.se> Last modified: Fri May 14 15:54 2004 |
This page is made in GNU Emacs. No fancy WYSIWYG! |