Skip to Main content Skip to Navigation

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

Anne Bouillard 1 Laurent Jouhet 2 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
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 [Schmitt-Infocom08], 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 {\em any} feed-forward network under blind multiplexing, 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.
Document type :
Complete list of metadata

Cited literature [33 references]  Display  Hide  Download
Contributor : Anne Bouillard Connect in order to contact the contributor
Submitted on : Monday, November 2, 2009 - 9:59:47 AM
Last modification on : Friday, February 4, 2022 - 3:15:12 AM
Long-term archiving on: : Wednesday, September 22, 2010 - 1:53:03 PM


Files produced by the author(s)


  • HAL Id : inria-00408717, version 2


Anne Bouillard, Laurent Jouhet, Eric Thierry. Tight performance bounds in the worst-case analysis of feed-forward networks. [Research Report] RR-7012, INRIA. 2009, pp.22. ⟨inria-00408717v2⟩



Record views


Files downloads