Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Optimal routing for end-to-end guarantees: the price of multiplexing

Anne Bouillard 1, 2 Bruno Gaujal 3 Sébastien Lagrange 4 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
3 MESCAL - Middleware efficiently scalable
ID-IMAG - Informatique et Distribution, Inria Grenoble - Rhône-Alpes
Abstract : In this paper we show how Network Calculus can be used to compute the optimal route for a flow (w.r.t. end-to-end guarantees on the delay or the backlog) in a network in the presence of cross-traffic. When cross-traffic is independent, the computation is shown to boild down to a functional shortest path problem. When cross-traffic perturbates the main flow over more than one node, then the ``Pay Multiplexing Only Once'' phenomenon makes the computation more involved. We provide an efficient algorithm to compute the service curve available for the main flow and show how to adapt the shortest path algorithm in this case. This work is supported by the ARC INRIA COINC.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download
Contributor : Eric Thierry Connect in order to contact the contributor
Submitted on : Tuesday, June 5, 2007 - 9:32:22 AM
Last modification on : Thursday, September 29, 2022 - 2:58:07 PM
Long-term archiving on: : Thursday, April 8, 2010 - 6:54:07 PM


Files produced by the author(s)


  • HAL Id : ensl-00151655, version 1


Anne Bouillard, Bruno Gaujal, Sébastien Lagrange, Eric Thierry. Optimal routing for end-to-end guarantees: the price of multiplexing. 2007. ⟨ensl-00151655⟩



Record views


Files downloads