HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

An Algorithmic Toolbox for Network Calculus

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 : Network Calculus offers powerful tools to analyze the performances in communication networks, in particular to obtain deterministic bounds. This theory is based on a strong mathematical ground, notably by the use of (min,+) algebra. However the algorithmic aspects of this theory have not been much addressed yet. This paper is an attempt to provide some efficient algorithms implementing Network Calculus operations for some classical functions. Some functions which are often used are the piecewise affine functions which ultimately have a constant growth. As a first step towards algorithmic design, we present a class containing these functions and closed under the Network Calculus operations: the piecewise affine functions which are ultimately pseudo-periodic. They can be finitely described which enables us to propose some algorithms for each of the Network Calculus operations. We finally analyze their computational complexity.
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Thursday, January 11, 2007 - 1:23:13 PM
Last modification on : Friday, February 4, 2022 - 3:15:48 AM
Long-term archiving on: : Tuesday, September 21, 2010 - 11:54:51 AM


Files produced by the author(s)


  • HAL Id : inria-00123643, version 2


Anne Bouillard, Eric Thierry. An Algorithmic Toolbox for Network Calculus. [Research Report] RR-6094, INRIA. 2007, pp.44. ⟨inria-00123643v2⟩



Record views


Files downloads