ANALYSIS OF GSPN MODELS - Modelling with Generalised Stochastic Petri Nets - page 109

6

ANALYSIS OF GSPN
MOD EL S

In this chapter we show how GSPN systems can be converted into Markov
chains and how their analysis can be performed to compute interesting per-
formance indices. The construction of the Markov chain associated with a
Stochastic Petri Net (SPN) system is described first, to set the ground for the
subsequent derivation of the probabilistic model associated with a GSPN.
Only GSPNs with finite state space are considered in this chapter, as they
yield Markov chains that are solvable with standard numerical techniques.
In particular, we are not discussing more advanced solution methods based
on matrix-geometric theory [28, 55] that allow the analysis of unbounded
GSPNs when their reachability graphs are characterized by regular repet-
itive structures. Some more advanced material is discussed in the second
part of the chapter where we illustrate reduction techniques that can be
employed to obtain smaller reachability graphs. Finally, the chapter ends
with a section devoted to GSPN simulation that can be used to estimate
performance indices of models with very general structures and whose state
space is either unbounded or simply too large to be treated with numerical
methods.

6.1 The Stochastic Process Associated with a SPN

In Chapter 5 we discussed the motivations behind the work of several au-
thors that led to the proposal of Stochastic Petri Nets (SPNs) [ 27, 51, 66] .
Due to the memoryless property of the exponential distribution of firing de-
lays, it is relatively easy to show [27, 51] that SPN systems are isomorphic
to continuous time Markov chains (CTMCs). In particular, a k-bounded
SPN system can be shown to be isomorphic to a finite CTMC. The CTMC
associated with a given SPN system is obtained by applying the following
simple rules:

123