Performance evaluation of large distributed systems plays a pivotal role in the design of Internet of Things (IoT) applications, or Big Data analysis, where high scalability and low response times are required. However, this performance assessment requires models, methodologies and tools tailored for this type of systems. Product-form queueing networks have been widely adopted for the analysis of sequential computations thanks to the availability of efficient algorithms for the computation of the average performance indices. However, this formalism has strong limitations since it does not allow one to model fork-join constructs or batches of jobs. Product-form stochastic Petri nets partially overcome these limitations but, on the other hand, general algorithms for the computation of the expected performance indices are not known or require strong assumptions on the model structure. In this paper, we define a new algorithm for the analysis of product-form stochastic Petri nets which works under much less restrictive assumptions than those previously proposed. The idea is that, in many cases, the entire state space of the model can be stored in memory thanks to multi-valued decision diagrams and the computation of the net's performance indices can take advantage of the tree structure that characterises this representation. Finally, we present a case study and several examples that will be used to study the performance of the algorithm for realistic scenarios.

Computation of the normalising constant for product-form models of distributed systems with synchronisation

Balsamo S.;Marin A.;
2019

Abstract

Performance evaluation of large distributed systems plays a pivotal role in the design of Internet of Things (IoT) applications, or Big Data analysis, where high scalability and low response times are required. However, this performance assessment requires models, methodologies and tools tailored for this type of systems. Product-form queueing networks have been widely adopted for the analysis of sequential computations thanks to the availability of efficient algorithms for the computation of the average performance indices. However, this formalism has strong limitations since it does not allow one to model fork-join constructs or batches of jobs. Product-form stochastic Petri nets partially overcome these limitations but, on the other hand, general algorithms for the computation of the expected performance indices are not known or require strong assumptions on the model structure. In this paper, we define a new algorithm for the analysis of product-form stochastic Petri nets which works under much less restrictive assumptions than those previously proposed. The idea is that, in many cases, the entire state space of the model can be stored in memory thanks to multi-valued decision diagrams and the computation of the net's performance indices can take advantage of the tree structure that characterises this representation. Finally, we present a case study and several examples that will be used to study the performance of the algorithm for realistic scenarios.
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0167739X19310313-main.pdf

non disponibili

Tipologia: Versione dell'editore
Licenza: Accesso chiuso-personale
Dimensione 889.52 kB
Formato Adobe PDF
889.52 kB Adobe PDF   Visualizza/Apri
paper.pdf

accesso aperto

Tipologia: Documento in Post-print
Licenza: Accesso gratuito (solo visione)
Dimensione 688.17 kB
Formato Adobe PDF
688.17 kB Adobe PDF Visualizza/Apri

I documenti in ARCA 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: http://hdl.handle.net/10278/3722985
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact