3rd International ICST Conference on Performance Evaluation Methodologies and Tools

Research Article

Computation of a (min,+) multi-dimensional convolution for end-to-end performance analysis.

Download324 downloads
  • @INPROCEEDINGS{10.4108/ICST.VALUETOOLS2008.4349,
        author={Anne Bouillard and Laurent Jouhet and Eric Thierry},
        title={Computation of a (min,+) multi-dimensional convolution for end-to-end performance analysis.},
        proceedings={3rd International ICST Conference on Performance Evaluation Methodologies and Tools},
        publisher={ICST},
        proceedings_a={VALUETOOLS},
        year={2010},
        month={5},
        keywords={Network Calculus worst case end-to-end bounds },
        doi={10.4108/ICST.VALUETOOLS2008.4349}
    }
    
  • Anne Bouillard
    Laurent Jouhet
    Eric Thierry
    Year: 2010
    Computation of a (min,+) multi-dimensional convolution for end-to-end performance analysis.
    VALUETOOLS
    ICST
    DOI: 10.4108/ICST.VALUETOOLS2008.4349
Anne Bouillard1,*, Laurent Jouhet2,*, Eric Thierry2,*
  • 1: ENS Cachan / IRISA, Campus de Beaulieu, 35000 Rennes, France
  • 2: ENS Lyon / IXXI, 46 Allée d'Italie, 69007 Lyon, France
*Contact email: Anne.Bouillard@irisa.fr, Laurent.Jouhet@ens-lyon.fr, Eric.Thierry@ens-lyon.fr

Abstract

Network Calculus is an attractive theory to derive deterministic bounds on end-to-end performance measures. Nevertheless bounding tightly and quickly the worst-case delay or backlog of a flow over a path with cross-traffic remains a challenging problem.

This paper carries on with the study of configurations where a main flow encounters some cross-traffic flows which interfere over connected sub-paths. We also assume that no information is available about scheduling policies at the nodes (blind multiplexing). Such configurations were first analyzed in [25, 27] where a "Pay Multiplexing Only Once" (PMOO) phenomenon was identified, and then in [6, 7] where a (min, +) multi-dimensional operator was introduced to compute a minimum service curve for the whole path. Under standard assumptions (concave arrival curves and convex service curves), we prove some properties of this new operator and we show how to use it to derive bounds on delays and backlogs in polynomial time.

We also discuss the simpler case when there is no cross-traffic. Then the analysis is known to boil down to the (min, +) convolution of all the service curves over the path. For convex and piecewise affine service curves, a specific theorem enables one to compute efficiently the convolution. This theorem has been used by several authors [6, 8, 17, 21, 22, 25, 27], but they all refer to a proof which sets only one part of the theorem [5]. We provide a new proof based on the Legendre-Fenchel Transform. We also investigate the complexity of computing performances bounds in this case.