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.

Exact Worst-case Delay for FIFO-multiplexing Tandems

STEA, GIOVANNI
2012-01-01

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.
2012
9781936968633
File in questo prodotto:
File Dimensione Formato  
40/95170971898112201721119070212985620809

solo utenti autorizzati

Tipologia: Versione finale editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 328.26 kB
Formato Unknown
328.26 kB Unknown   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/155070
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 16
  • ???jsp.display-item.citation.isi??? ND
social impact