| Aggregate Scheduling | Publication List | Lectures | Book

Network Calculus is a collection of results based on Min-Plus algebra, which applies to deterministic queuing systems found in communication networks.

It can be used for example to understand:

- why re-shaping delays can be ignored in shapers or spacer-controllers;
- a common model for schedulers;
- deterministic effective bandwidth;
- and much more.

Network Calculus is also the name of a project at EPFL/ICA.

In this project we considered networks of FIFO aggregate scheduling nodes. A crucial issue in these networks is: Can we derive a bound to the maximum delay that a packet can experience when traversing the network, and to the maximum queue size at each node? For these networks these are still open questions: instability in FIFO networks is an old problem. A recent result by Andrews shows that, contrary to common sense, no matter how low the maximum node utilization is in the network, it is possible to build an example of an unstable FIFO network. Answering to these question is of great importance in order to offer some form of service guarantees in Differentiated Services networks, in Network-On-Chips, and on very high speed switches.

We elaborated a very general method to derive sufficient conditions for stability, based on the properties of a nonlinear operator over a large variable space. The method is general and modular, and is able to incorporate all present (and possibly, future) network calculus results about output bounds at aggregate schedulers, and node concatenation results.

As an application of this method, we derived an algorithm that tests some sufficient conditions for stability on networks of leaky bucket constrained flows. This algorithm allows to derive inner bound to the stability region which are much larger than those obtainable with any of the existing results.

By a simplification procedure, we derived a version of the RIN result which applies to heterogeneous network settings, and to leaky bucket constrained flows, and that is able to bring on realistic network scenarios, to an average node utilization which is more than three times higher than the maximum node utilization obtainable with existing results.

G. Rizzo, "Stability and bounds in aggregate scheduling networks", PhD Dissertation, EPFL Lausanne, Feb. 2008.

G. Rizzo, J.Y. Le Boudec, "Stability and Delay Bounds in Heterogeneous Networks of Aggregate Schedulers", to appear in INFOCOM 2008, Phoenix, Apr. 2008

G. Rizzo, J.Y. Le Boudec, "Generalization of the RIN Result to Heterogeneous Networks of Aggregate Schedulers and Leaky Bucket Constrained Flows", Proc. of the 15th IEEE ICON 2007, Adelaide, Nov. 07.

G. Rizzo, J.Y. Le Boudec, "Pay bursts only once" does not hold for non-FIFO Guaranteed Rate nodes, Performance Evaluation, vol. 62, num. 1-4 (2005), p. 366-381.

G. Rizzo, J.Y. Le Boudec, "Generalization of the RIN Result to Heterogeneous Networks of Aggregate Schedulers and Leaky Bucket Constrained Flows", Technical report. – 2007 [LCA-REPORT-2007-006]

G. Rizzo, J.Y. Le Boudec, "Stability and Delay Bounds in Heterogeneous Networks of Aggregate Schedulers", Technical report. – 2007 [LCA-REPORT-2007-007]

G. Rizzo, J.Y. Le Boudec, "Pay bursts only once" does not hold for non-FIFO Guaranteed Rate nodes, Technical report. – 2005 [LCA-REPORT-2005-018]

- A Short Course (2 to 3 hours) ppt
- EPFL Doctoral School click here
- Pisa July 2003 click here
- Other Network Calculus Tutorials (powerpoint + zipped): Sigmetrics June 2002, ENS May 2001 (systems theory aspects)