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  which is the main material for this course along with the expository paper . 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 , 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  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  and  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.
 Jean-Yves Le Boudec, Patrick Thiran, Network calculus, Springer-Verlag, ISBN 3-540-42184-X.
 Jean-Yves Le Boudec, "Network calculus made easy", Technical Report 96/218, DI-EPFL, CH-1015 Lausanne, Switzerland, December 1996. Download from CiteSeer.
 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.
 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.
Maintained by Peter Johansson, <firstname.lastname@example.org>|
Last modified: Fri May 14 15:54 2004
This page is made in GNU Emacs.|
No fancy WYSIWYG!