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