Skip to Main content Skip to Navigation

Some examples and counterexamples for (min,+) filtering operations

Anne Bouillard 1 Eric Thierry 2
1 DISTRIBCOM - Distributed and Iterative Algorithms for the Management of Telecommunications Systems
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : This paper collects a serie of examples and counterexamples encountered in the study of the algorithmics of Network Calculus operations. Network Calculus is a deterministic queuing theory which aims at providing bounds on the performances of communication networks thanks to a nice formalization in (min,+) algebra. Often presented as a (min,+) filtering theory by analogy with the (+,x) filtering of traditional system theory, it makes use a well-defined set of operations. Their algorithmic aspects have not been much addressed. For this reason, we describe and analyze in a previous report a set of algorithms implementing these Network Calculus operations for a well-chosen class of functions. During this work, we had to construct some examples and counterexamples in order to draw the limits of our results or to illustrate them. Many of them have been omitted in that report and are now presented in this companion-paper.
Complete list of metadata

Cited literature [5 references]  Display  Hide  Download
Contributor : Rapport de Recherche Inria <>
Submitted on : Thursday, January 11, 2007 - 1:26:31 PM
Last modification on : Thursday, January 7, 2021 - 4:28:49 PM
Long-term archiving on: : Tuesday, September 21, 2010 - 11:56:07 AM


Files produced by the author(s)


  • HAL Id : inria-00123709, version 2


Anne Bouillard, Eric Thierry. Some examples and counterexamples for (min,+) filtering operations. [Research Report] RR-6095, INRIA. 2007, pp.14. ⟨inria-00123709v2⟩



Record views


Files downloads