ABSTRACT
The increasing demand for customer centric evaluation of systems, mostly related with the assessment of the quality of service that they can deliver, requires the development of techniques properly designed to model and to study the movement of specific entities generically referred to as "customers". Stochastic Well-Formed Net(SWN) are naturally suited for the representation of systems in which "customers" of different categories compete for the use of common resources. Color classes of SWN are easily associated with these different categories, leaving to the peculiar features of the formalism the possibility of exploiting all the symmetries existing into the representation for the efficient and effective computation of the measures of interest. Within this application context, the computation of first passage time distribution measures in Stochastic Well-Formed Net (SWN) is becoming of primary interest. Customers however are not primitive entities in the formalism and an approach similar to that previously developed for Generalized Stochastic Petri Nets (GSPN) is suggested to overcome this problem in which P-semiflows are used to identify the circulating "customers". In this paper we propose an original algorithm for computing some P-semiflows of colored PNs (in particular of SWNs) in parametric form by exploiting the peculiarities of the objective of this investigation, and extend the customer centric first passage time computation approach previously developed for GSPNs, to make it suitable for SWN models. Moreover, the paper proposes an enhancement of the SWN notation in order to provide a way to ease the modeler in the specification of customer scheduling policies that may affect the computation of first passage time distributions. This extension, inspired by Queueing Petri Nets, adds to SWN some "syntactic sugar" that allows to include in the model queueing places which are automatically replaced by appropriate submodels, before solving the model.
- M. Ajmone Marsan, G. Balbo, G. Conte, S. Donatelli, and G. Franceschinis. Modelling with Generalized Stochastic Petri Nets. J. Wiley, New York, NY, USA, 1995.Google Scholar
- S. Baarir, M. Beccuti, D. Cerotti, M. De Pierro, S. Donatelli, and G. Franceschinis. The GreatSPN tool: recent enhancements. SIGMETRICS Performance Evaluation Review, Special Issue on Tools for Performance Evaluation, 36(4):4-9, 2009. Google ScholarDigital Library
- G. Balbo, M. Beccuti, M. De Pierro, and G. Franceschinis. Stochastic Petri Nets sensitivity to token scheduling policies. In OR2010: Proc. of Int. Conf. Operations Research "Mastering Complexity". LNCS Springer, 2010. To appear.Google Scholar
- G. Balbo, M. Beccuti, M. De Pierro, and G. Franceschinis. First passage time computation in tagged GSPNs with queue places. The Computer Journal, First published online: July 22, 2010. Google ScholarDigital Library
- F. Bause and P. Kritzinger. Stochastic Petri Nets - An Introduction to the Theory, 2nd ed. F. Vieweg & Sohn Verlag, Braunschweig/Wiesbaden, Germany, 2002. ls4-www.informatik.uni-dortmund.de/QM/MA/fb/spnbook2.html.Google Scholar
- M. Beccuti, S. Baarir, G. Franceschinis, and J.-M. Ilié. Efficient lumpability check in partially symmetric systems. In 3rd Int. Conf. on Quantitative Evaluation of Systems, pages 211-221, Riverside, CA, USA, September 2006. IEEE CS Press. Google ScholarDigital Library
- L. Bodrog, G. Horvath, S. Racz, and M. Telek. A tool support for automatic analysis based on the tagged customer approach. In Proc. of the 3rd int. conf. on the QEST'06, pages 323-332, Washington, DC, USA, 2006. IEEE CS Press. Google ScholarDigital Library
- J. T. Bradley. Derivation of passage-time densities in pepa models using ipc: The imperial pepa compiler. In Proc. of the 11th IEEE/ACM Int. Symposium MASCOTS03, pages 344-351. IEEE CS Press, 2003.Google ScholarCross Ref
- G. Chiola, C. Dutheillet, G. Franceschinis, and S. Haddad. Stochastic well-formed coloured nets for symmetric modelling applications. IEEE Trans. on Computers, 42(11):1343-1360, nov 1993. Google ScholarDigital Library
- A. Clark and S. Gilmore. State-aware performance analysis with extended stochastic probes. In EPEW08: Proc. of the 5th European Performance Engineering Workshop, LNCS 5261, pages 125-140. Springer, 2008. Google ScholarDigital Library
- J.-M. Couvreur, S. Haddad, and J. F. Peyre. Generative Families of Positive Invariants in Coloured Nets Sub-Classes. In Proc. of the 12th International Conference on ATPN, pages 51-70, Chicago, Illinois, USA, 1993. LNCS Springer. Google ScholarDigital Library
- N. Dingle, P. Harrison, and W. Knottenbelt. Uniformisation and Hypergraph Partitioning for the Distributed Computation of Response Time Densities in Very Large Markov Models. Journal of Parallel and Distributed Computing, 64(8):309-920, 2004. Google ScholarDigital Library
- N. J. Dingle and W. J. Knottenbelt. Automated Customer-Centric Performance Analysis of Generalised Stochastic Petri Nets Using Tagged Tokens. Electron. Notes TCS, 232:75-88, 2009. Google ScholarDigital Library
- K. Jensen. Coloured Petri nets. Basic Concepts, Analysis Methods and Practical Use (vol.1,2,3). Springer Inc., New York, NY, USA, 1997. Google ScholarDigital Library
- S. Kounev. Performance Modeling and Evaluation of Distributed Component-Based Systems Using Queueing Petri Nets. IEEE Trans. Softw. Eng., 32(7):486-502, 2006. Google ScholarDigital Library
- S. Wau Men Au-Yeung. Response Times in Healthcare Systems. PhD thesis, Imperial College, London, 2008. pubs.doc.ic.ac.uk/response-times-in-healthcare.Google Scholar
Index Terms
- Computing first passage time distributions in stochastic well-formed nets
Recommendations
Discrete Time Stochastic Petri Nets
Basic graph models of processes, such as Petri nets, have usually omitted the concept of time as a parameter. Time has been added to the Petri net model in two ways. The timed Petri net (TPN) uses a fixed number of discrete time intervals. The ...
Computing Bounds for the Performance Indices of Quasi-Lumpable Stochastic Well-Formed Nets
Structural symmetries in stochastic well-formed colored Petri nets (SWN's) lead to behavioral symmetries that can be exploited by using the symbolic reachability graph (SRG) construction algorithm. The SRC allows one to compute an aggregated ...
Stochastic Well-Formed Colored Nets and Symmetric Modeling Applications
The class of stochastic well-formed colored nets (SWN's) was defined as a syntactic restriction of stochastic high-level nets. The interest of the introduction of restrictions in the model definition is the possibility of exploiting the symbolic ...
Comments