Network Calculus

| Aggregate Scheduling | Publication List | Lectures | Book

What is Network Calculus ?

Network Calculus Bounds
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:

If you want to learn more about this exciting topic, read the
Network Calculus book. It is available for free download.

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

Back to top of the page



Stability and Bounds in Aggregate Scheduling Networks

Stability in aggregate scheduling networks


The Problem


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.

Our Approach

As hard bounds on delay and backlog are required at each node, our approach is a deterministic one, and is based on a worst case analysis of the network behavior. Our starting point is a very general network model, on which we apply the algebraic tools from Network Calculus. Being a worst case analysis, it can easily lead to overpessimistic results and loose bounds: Therefore, we tackle the problem by retaining all the complexity of the general network model, without introducing any of the simplifying assumptions that limit the effectiveness and the applicability of the main existing results.

Our Main Achievements


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.

Publications


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]

Back to top of the page



Network Calculus Lectures

Back to top of the page