Stochastic Petri nets (SPN) are a Markovian formalism for qualitative and quantitative analysis of discrete event dynamic systems. Among other uses, they have been used extensively in performance evaluation of telecommunication systems, computer systems and networks. Analysis of an SPN model usually requires stationary analysis of a continuous-time Markov chain (CTMC) underlying the SPN, whose state space for many practical models is too large to be analysed by direct methods. This serious drawback is shared with many other modelling formalisms and is usually referred to as state space explosion. Usually simulation can be employed to analyse such models. An alternative is to restrict the SPN formalism to product-form SPNs, a class of nets whose unnormalised stationary probability distribution can be obtained in closed form, making stationary analysis much simpler. In this thesis we present algorithms for stationary analysis of SPN models based on efficient encoding of state spaces and transition functions by multi-way decision diagrams, an efficient data structure. After a short introduction to SPNs and their stationary analysis, we start with simulation of SPNs and present an algorithm for perfect simulation in SPNs that can be used to directly obtain samples from the stationary distribution. After this, we turn to simulation of product-form SPNs and present simulation stopping criteria that exploit the product-form property. Finally, we present an algorithm for fast computation of normalizing constant, needed for the normalisation of stationary probabilities in the analysis of product-form models.

Algorithms for stationary analysis of stochastic Petri nets / Stojic, Ivan. - (2017 Mar 01).

Algorithms for stationary analysis of stochastic Petri nets

Stojic, Ivan
2017-03-01

Abstract

Stochastic Petri nets (SPN) are a Markovian formalism for qualitative and quantitative analysis of discrete event dynamic systems. Among other uses, they have been used extensively in performance evaluation of telecommunication systems, computer systems and networks. Analysis of an SPN model usually requires stationary analysis of a continuous-time Markov chain (CTMC) underlying the SPN, whose state space for many practical models is too large to be analysed by direct methods. This serious drawback is shared with many other modelling formalisms and is usually referred to as state space explosion. Usually simulation can be employed to analyse such models. An alternative is to restrict the SPN formalism to product-form SPNs, a class of nets whose unnormalised stationary probability distribution can be obtained in closed form, making stationary analysis much simpler. In this thesis we present algorithms for stationary analysis of SPN models based on efficient encoding of state spaces and transition functions by multi-way decision diagrams, an efficient data structure. After a short introduction to SPNs and their stationary analysis, we start with simulation of SPNs and present an algorithm for perfect simulation in SPNs that can be used to directly obtain samples from the stationary distribution. After this, we turn to simulation of product-form SPNs and present simulation stopping criteria that exploit the product-form property. Finally, we present an algorithm for fast computation of normalizing constant, needed for the normalisation of stationary probabilities in the analysis of product-form models.
1-mar-2017
29
Informatica
Balsamo, Simonetta
File in questo prodotto:
File Dimensione Formato  
956114-1186362.pdf

accesso aperto

Tipologia: Tesi di dottorato
Dimensione 1.5 MB
Formato Adobe PDF
1.5 MB 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: https://hdl.handle.net/10579/10300
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact