On the relations among product-form stochastic models
Andrea Marin · ARCA (Università Ca' Foscari Venezia) · 2009
Product-form stochastic models are characterized by a Markovian stochastic process that fulfills a set of properties that allows an efficient steady state analysis. According to this approach, the model is decomposed into several components. Each of these components has an underlying stochastic process that is in general much simpler than the joint one. The product-form property states that the steady state probabilities of the joint process can be expressed as the normalized product of the steady state proabilities of its interacting components. Product-form stochastic models are widely used for performance evaluation purposes in the study of communication protocols, software or hardware architectures. Product-form stochastic models can be defined using several high-level formalisms. For example BCMP theorem provides a product-form solution for a class of Markovian queueing networks. In this thesis we use two results, the M ⇒ M property and the Reversed Compound Agent Theorem (RCAT) to explore the relations among several product-form model classes belonging to different formalisms: queueing networks (QN), stochastic Petri nets (SPN), generalized stochastic Petri nets (GSPN), Markovian Process Algebra (MPA). We identify new classes of product-form GSPNs, and we prove that previous results on product-form SPNs can be studied using RCAT. From a practical point of view we show how to map multiclass queueing stations of BCMP types into GSPNs with a finite structure maintaining a strong equivalence relation (in particular the average performance indices and the product-form property are preserved). As a consequence we are able to study hybrid models in product-form where their interaction and compositions are formally defined by GSPNs. An algorithm is defined in order to translate BCMP QNs into GSPNs according to the previous theoretical results. The algorithm can be easily extended to allow the modeler to specify new stations using GSPNs.