Exact worst-case delay for FIFO-multiplexing tandems

Abstract : This paper computes the actual worst-case end-to end delay for a flow in a tandem of FIFO multiplexing service curve nodes, where flows are shaped by concave, piecewise linear arrival curves, and service curves are convex and piecewise linear. Previous works only computed bounds on the above quantity, which are not always tight. We show that the solution entails taking the maximum among the optimal solution of a number of Linear Programming problems. However, the number and size of LP problems grows exponentially with the tandem length. Furthermore, we present approximate solution schemes to find both upper and lower delay bounds on the worst-case delay. Both of them only require to solve just one LP problem, and they produce bounds which are generally more accurate than those found in the previous work. Finally, we elaborate on how the worst-case scenario should be constructed.
Type de document :
Communication dans un congrès
VALUETOOLS, Oct 2012, Cargèse, France. pp.158-167, 2012
Liste complète des métadonnées

Contributeur : Anne Bouillard <>
Soumis le : vendredi 18 janvier 2013 - 17:21:33
Dernière modification le : jeudi 22 novembre 2018 - 14:40:10


  • HAL Id : hal-00778113, version 1


Anne Bouillard, Giovanni Stea. Exact worst-case delay for FIFO-multiplexing tandems. VALUETOOLS, Oct 2012, Cargèse, France. pp.158-167, 2012. 〈hal-00778113〉



Consultations de la notice