Exact Worst-Case Delay in FIFO-Multiplexing Feed-Forward Networks

Anne Bouillard 1, 2, 3 Giovanni Stea 4
2 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8548
Abstract : In this paper we compute the actual worst-case end-to-end delay for a flow in a feed-forward network of FIFO-multiplexing service curve nodes, where flows are shaped by piecewise-affine concave arrival curves, and service curves are piecewise affine and convex. We show that the worst-case delay problem can be formulated as a mixed integer-linear programming problem, whose size grows exponentially with the number of nodes involved. Furthermore, we present approximate solution schemes to find upper and lower delay bounds on the worst-case delay. Both only require to solve just one linear programming problem, and yield bounds which are generally more accurate than those found in the previous work, which are computed under more restrictive assumptions.
Type de document :
Article dans une revue
IEEE/ACM Transactions on Networking, IEEE/ACM, 2015, IEEE/ACM Transactions on Networking, 23 (5), pp.1387 - 1400 〈10.1109/TNET.2014.2332071〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01255070
Contributeur : Anne Bouillard <>
Soumis le : mercredi 13 janvier 2016 - 10:41:38
Dernière modification le : samedi 8 décembre 2018 - 01:27:15
Document(s) archivé(s) le : samedi 16 avril 2016 - 06:30:11

Fichier

TNET_2014_Camera_Ready.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Anne Bouillard, Giovanni Stea. Exact Worst-Case Delay in FIFO-Multiplexing Feed-Forward Networks. IEEE/ACM Transactions on Networking, IEEE/ACM, 2015, IEEE/ACM Transactions on Networking, 23 (5), pp.1387 - 1400 〈10.1109/TNET.2014.2332071〉. 〈hal-01255070〉

Partager

Métriques

Consultations de la notice

504

Téléchargements de fichiers

137