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

Anne Bouillard; Bruno Gaujal; Sébastien Lagrange; Eric Thierry

2nd International ICST Conference on Performance Evaluation Methodologies and Tools

Research Article

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

Download751 downloads

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.4108/valuetools.2007.1949,
    author={Anne Bouillard and Bruno Gaujal and S\^{e}bastien Lagrange and Eric Thierry},
    title={Optimal routing for end-to-end guarantees: the price of multiplexing},
    proceedings={2nd International ICST Conference on Performance Evaluation Methodologies and Tools},
    proceedings_a={VALUETOOLS},
    year={2010},
    month={5},
    keywords={},
    doi={10.4108/valuetools.2007.1949}
}

Anne Bouillard
Bruno Gaujal
Sébastien Lagrange
Eric Thierry
Year: 2010
Optimal routing for end-to-end guarantees: the price of multiplexing
VALUETOOLS
ICST
DOI: 10.4108/valuetools.2007.1949

Anne Bouillard¹^,*, Bruno Gaujal²^,*, Sébastien Lagrange³^,*, Eric Thierry⁴^,*

1: ENS Cachan / IRISA Campus de Beaulieu 35000 Rennes, France
2: INRIA / LIG 51, Av Jean Kuntzmann 38330 Montbonnot, France
3: INRIA / LISA 62, Av Notre Dame du Lac 49000 Angers, France
4: ENS Lyon / IXXI 46 Allée d’ Italie 69007 Lyon, France

*Contact email: Anne.Bouillard@irisa.fr, Bruno.Gaujal@inria.fr, Sebastien.Lagrange@istia.univangers._fr, Eric.Thierry@ens-lyon.fr

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.

Published: 2010-05-16
Modified: 2011-09-14

: http://dx.doi.org/10.4108/valuetools.2007.1949

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

Abstract

About EAI

Community

Publish with EAI