Tight performance bounds in the worst-case analysis of feed-forward networks *

Anne Bouillard 1, 2, 3 Eric Thierry 4
1 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, CNRS - Centre National de la Recherche Scientifique : UMR 8548, Inria de Paris
Abstract : Network Calculus theory aims at evaluating worst-case performances in communication networks. It provides methods to analyze models where the traffic and the services are constrained by some minimum and/or maximum envelopes (arrival/service curves). While new applications come forward , a challenging and inescapable issue remains open: achieving tight analyzes of networks with aggregate multiplexing. The theory offers efficient methods to bound maximum end-to-end delays or local backlogs. However as shown in a recent breakthrough paper [28], those bounds can be arbitrarily far from the exact worst-case values, even in seemingly simple feed-forward networks (two flows and two servers), under blind multiplexing (i.e. no information about the scheduling policies, except FIFO per flow). For now, only a network with three flows and three servers, as well as a tandem network called sink tree, have been analyzed tightly. We describe the first algorithm which computes the maximum end-to-end delay for a given flow, as well as the maximum backlog at a server, for any feed-forward network under blind multiplexing, with piecewise affine concave arrival curves and piecewise affine convex service curves. Its computational complexity may look expensive (possibly super-exponential), but we show that the problem is intrinsically difficult (NP-hard). Fortunately we show that in some cases, like tandem networks with cross-traffic interfering along intervals of servers, the complexity becomes polynomial. We also compare ourselves to the previous approaches and discuss the problems left open.
Type de document :
Article dans une revue
Discrete Event Dynamic Systems, Springer Verlag, 2016, 26 (3), pp.383-411
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger

Contributeur : Anne Bouillard <>
Soumis le : jeudi 7 septembre 2017 - 16:20:12
Dernière modification le : mardi 16 janvier 2018 - 15:54:26


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01583622, version 1



Anne Bouillard, Eric Thierry. Tight performance bounds in the worst-case analysis of feed-forward networks *. Discrete Event Dynamic Systems, Springer Verlag, 2016, 26 (3), pp.383-411. 〈hal-01583622〉



Consultations de la notice


Téléchargements de fichiers