Tight performance bounds in the worst-case analysis of feed-forward networks - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2010

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

Résumé

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 (service/arrival 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 recently, 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 multiplex-ing, with concave arrival curves and 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.
Fichier principal
Vignette du fichier
bouillard_INFOCOM10.pdf (176.7 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01583741 , version 1 (07-09-2017)

Identifiants

  • HAL Id : hal-01583741 , version 1

Citer

Anne Bouillard, Laurent Jouhet, Éric Thierry. Tight performance bounds in the worst-case analysis of feed-forward networks. IEEE INFOCOM 2010 - IEEE Conference on Computer Communications, Mar 2010, San Diego, United States. ⟨hal-01583741⟩
293 Consultations
149 Téléchargements

Partager

Gmail Facebook X LinkedIn More