Timed Petri net models of queueing systems

Zuberek, W.M.

Proc. 7-th Annual Int. Phoenix Conf. on Computers and Communications (PCCC'88); Scottsdale, AZ, 16-18 March 1988, pp.324-329.

Abstract:

It is shown that for timed Petri nets with exponentially distributed firing times (M-timed Petri nets), the state space can be generated directly from net specifications, and then the stationary probabilities of states can be obtained by standard methods, developed for analysis of (continuous-time) Markov chains. Numerous performance measures can be derived from stationary probabilities of states. For unbounded nets (models of open network systems are usually unbounded), the state space is infinite, a transformation is thus needed that "folds" this infinite space into a finite representation, used for effective evaluation of probabilities. The paper presents a short theoretical background for performance evaluation using timed Petri nets followed by several examples of closed and open network models of simple computer systems.

Keywords:

Timed Petri nets, queueing systems, state space generation, Markov chains.

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, W. Reisig, G. Rozenberg (eds.), Advances in Petri Nets 1986, vol.1: "Petri nets - central models and their properties", vol.2: "Petri nets - applications and relationship to other models of concurrency" (Proc. of the Advanced Course, Bad Honnef, 1986; Lecture Notes in Computer Science 254 and 255); Springer-Verlag 1987.
• J.P. Buzen, "Fundamental operational laws of computer system performance"; Acta Informatica, vol.7, no.2, pp.167-182, 1976.
• D. Ferrari, Computer systems performance evaluation; Prentice-Hall, Englewood Cliffs NJ, 1978.
• G. Florin, S. Natkin, "One-place unbounded stochastic Petri nets: ergodic criteria and steady-state solutions"; Journal of Systems and Software, vol.1, no.2, pp.103-115, 1986.
• 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.
• L. Kleinrock, Queueing systems, vol.1: "Theory", vol.2: "Computer applications"; J. Wiley & Sons 1975, 1976.
• P.M. Merlin, D.J. Farber, "Recoverability of communication protocols - implications of a theoretical study"; IEEE Trans. on Communications, vol.24, no.9, pp.1036-1049, 1976.
• I. Mitrani, "Probabilistic modelling of distributed computing systems"; in Distributed Computing Systems Programme, D.A. Duce (ed.), pp.139-153, Peregrinus Ltd., London 1984.
• 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, Englewood Cliffs NJ, 1981.
• C. Ramchandani, "Analysis of asynchronous concurrent systems by timed Petri nets"; Project MAC Technical Report MAC-TR-120, Massachusetts Institute of Technology, Cambridge MA, 1974.
• R.R. Razouk, "The derivation of performance expressions for communication protocols from timed Petri nets"; Computer Communication Review, vol.14, no.2, pp.210-217, 1984.
• W. Reisig, Petri nets - an introduction; Springer-Verlag 1985.
• G. Rozenberg (ed.), Advances in Petri Nets 1987 (Lecture Notes in Computer Science 266); Springer-Verlag 1987.
• 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, "Inhibitor D-timed Petri nets and performance analysis of communication protocols"; INFOR Journal, vol.24, no.3, pp.231-249, 1986.
• W.M. Zuberek, "Timed Petri nets in modelling and evaluation of multiprocessor systems"; Proc. Int Conf. on Parallel Processing, St. Charles IL, pp.695-698, 1987.
• W.M. Zuberek, "Stochastic Petri nets and timed Petri nets in modelling and performance evaluation"; Proc. APICS Annual Computer Science Conf., Wolfville, Canada, pp.66-82, 1987.