Performance evaluation using unbounded timed Petri nets

Zuberek, W.M.

Proc. 3-rd Int. Workshop on Petri Nets and Performance Models (PNPM'89); Kyoto, Japan, 11-13 December 1989, pp.180-186.

Abstract:

Unbounded timed Petri nets discussed in this paper are place-unbounded free-choice place/transition nets with exponentially distributed firing times associated with transitions of a net. In such nets the infinite state space is generated by a finite set of linear equations. The regularity of this linear description can be used for a "projection" (or "folding") of the infinite state space into an equivalent finite representation that can be described by a finite set of nonlinear equilibrium equations. The solution of these equations determines the stationary probabilities of the states. Many performance measures can be obtained directly from this stationary solution. Furthermore, such unbounded nets can eliminate the state explosion problem of some models by using unbounded but simple approximations to bounded but complex models.

Keywords:

Timed Petri nets, unbounded nets, state space generation, performance approximation.

References:

• T. Agerwala, "Putting Petri nets to work"; IEEE Computer Magazine, vol.12, no.12, pp.85-94, 1979.
• M. Ajmone Marsan, G. Conte, G. Balbo, "A class of generalized stochastic Petri nets for the performance evaluation of multiprocessor systems"; ACM Trans. on Computer Systems, vol.2, no.2, pp.93-122, 1984.
• W. Brauer (ed.), Net theory and applications (Proc. of the Advanced Course on General Net Theory of Processes and Systems, Hamburg 1979; Lecture Notes in Computer Science 84), Springer-Verlag 1980.
• J.B. Dugan, A. Bobbio, G. Ciardo, K. Trivedi, "The design of a unified package for the solution of stochastic Petri net models"; Proc. Int. Workshop on Timed Petri Nets, Torino, Italy, pp.6-13, 1985.
• D. Ferrari, Computer systems performance evaluation; Prentice-Hall 1978.
• M.A. Holliday, M.K. Vernon, "A generalized timed Petri net model for performance evaluation"; Proc. Int. Workshop on Timed Petri Nets, Torino, Italy, pp.181-190, 1985.
• F. Krueckeberg, M. Jaxy, "Mathematical methods for calculating invariants in Petri nets"; in Advances in Petri Nets 1987 (Lecture Notes in Computer Science 266), G. Rozenberg (ed.), pp.104-131, Springer-Verlag 1987.
• M.K. Molloy, "Performance analysis using stochastic Petri nets"; IEEE Trans. on Computers, vol.31, no.9, pp.913-917, 1982.
• J.L. Peterson, Petri net theory and the modeling of systems; Prentice-Hall 1981.
• R.R. Razouk, C.V. Phelphs, "Performance analysis using timed Petri nets"; in Protocol Specification, Testing, and Verification IV (Proc. of the IFIP WG 6.1 Fourth Int. Workshop, Skytop Lodge PA, June 11-14, 1984); Y. Yemini, R. Strom, S. Yemini (eds.), pp.561-576, North-Holland 1985.
• W. Reisig, Petri nets - an introduction (EATCS Monographs on Theoretical Computer Science 4); Springer-Verlag 1985.
• J. Sifakis, "Use of Petri nets for performance evaluation"; in Measuring, modelling and evaluating computer systems, pp.75-93, North-Holland 1977.
• W.M. Zuberek, "M-timed Petri nets, priorities, preemptions, and performance evaluation of systems"; in Advances in Petri Nets 1985 (Lecture Notes in Computer Science 222), G. Rozenberg (ed.), pp.478-498, Springer-Verlag 1986.
• W.M. Zuberek, "On generation of state space for timed Petri nets"; Proc. ACM Annual Computer Science Conf., Atlanta GA, pp.239-248, 1988.