In this paper, we compute the actual worst-case end-to-end delay for a flow in a feed-forward network of first-in–first-out (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 that are generally more accurate than those found in the previous work, which are computed under more restrictive assumptions.

Exact Worst-case Delay in FIFO-multiplexing Feed-forward Networks

STEA, GIOVANNI
2015-01-01

Abstract

In this paper, we compute the actual worst-case end-to-end delay for a flow in a feed-forward network of first-in–first-out (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 that are generally more accurate than those found in the previous work, which are computed under more restrictive assumptions.
2015
Bouillard, Anne; Stea, Giovanni
File in questo prodotto:
File Dimensione Formato  
2015 TNET.pdf

solo utenti autorizzati

Descrizione: versione pubblicata
Tipologia: Versione finale editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 2.61 MB
Formato Adobe PDF
2.61 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
TNET.pdf

accesso aperto

Tipologia: Documento in Post-print
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 781.92 kB
Formato Adobe PDF
781.92 kB Adobe PDF Visualizza/Apri

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/501671
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 22
  • ???jsp.display-item.citation.isi??? 21
social impact