Methodological construction of product-form stochastic Petri nets for performance evaluation

Product-forms in Stochastic Petri nets (SPNs) are obtained by a compositional technique for the first time, by combining small SPNs with product-forms in a hierarchical manner. In this way, performance engineering methodology is enhanced by the greatly improved efficiency endowed to the steady-state solution of a much wider range of Markov models. Previous methods have relied on analysis of the whole net and so are not incremental—hence they are intractable in all but small models. We show that the product-form condition for open nets depends, in general, on the transition rates, whereas closed nets have only structural conditions for a product-form, except in rather pathological cases. Both the “building blocks” formed by the said small SPNs and their compositions are solved for their product-forms using the Reversed Compound Agent Theorem (RCAT), which, to date, has been used exclusively in the context of process-algebraic models. The resulting methodology provides a powerful, general and rigorous route to product-forms in large stochastic models and is illustrated by several detailed examples.

► In this paper we consider stochastic Petri net (SPN) models and derive the conditions for the stationary state probabilities to be in product-form with respect to some simple small components called building blocks.
► We characterise the SPNs which can be defined as compositions of these building blocks and show that, under some possibly rate-dependent constraints, these have also product form solution.
► We point out that this methodology is not only theoretically interesting but also important from a practical point of view, since compositionality of stochastic models results really enhanced and efficient derivation of relevant performance indices is possible even for large models.
► We show that modular engineering of software (and hardware) architectures can exploit these results for quantitative model analysis by means of some application example.