Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-00778113
Contributor : Anne Bouillard <>
Submitted on : Friday, January 18, 2013 - 5:21:33 PM
Last modification on : Thursday, July 1, 2021 - 5:58:02 PM

Identifiers

  • HAL Id : hal-00778113, version 1

Citation

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

Share

Metrics

Record views

360