Tight performance bounds in the worst-case analysis of feed-forward networks Bouillard, Anne; Jouhet, Laurent; Thierry, Eric

User activity

Share to:
View the summary of this work
Bouillard, Anne ; Jouhet, Laurent ; Thierry, Eric
Appears In
Discrete Event Dynamic Systems
Algorithms -- Analysis; Computers; linear programming
To access, purchase, authenticate, or subscribe to the full-text of this article, please visit this link: http://dx.doi.org/10.1007/s10626-015-0213-2 Byline: Anne Bouillard (1), Eric Thierry (2) Keywords: Network calculus; Feed-forward networks; Blind multiplexing; Linear programming 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 et al. 2008), 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. Author Affiliation: (1) ENS/INRIA, Paris, France (2) ENS Lyon, Lyon, France Article History: Registration Date: 13/05/2015 Received Date: 13/07/2012 Accepted Date: 13/05/2015 Online Date: 16/06/2015 Article note: This work has been partially funded by the French National Agency for Research (ANR PEGASE-SEGI-009-02)
Work ID

2 editions of this work

Find a specific edition
Thumbnail [View as table] [View as grid] Title, Author, Edition Date Language Format Libraries

User activity

e.g. test cricket, Perth (WA), "Parkes, Henry"

Separate different tags with a comma. To include a comma in your tag, surround the tag with double quotes.

Be the first to add a tag for this work

Be the first to add this to a list

Comments and reviews

What are comments? Add a comment

No user comments or reviews for this work

Add a comment

Show comments and reviews from Amazon users