Throughput analysis in timed Petri nets

Zuberek, W.M.

Proc. 35-th Midwest Symposium on Circuits and Systems; Washington, DC, 9-12 August 1992, pp.1576-1580.

Abstract:

It is shown that the steady-state behaviour of a class of timed Petri nets can be analysed using the concept of throughput and simple rules of operational analysis. Since such analysis is based on the average values of firing times rather than firing time distribution functions, the same approach can be applied to a variety of net models. Throughput analysis uses structural properties of nets only, so it avoids the potential problems of reachability analysis, it can be applied to unbounded nets, however, it does not provide as much information as can be obtained from analysis of the state space. Simple examples of of D-times and M-timed nets are used as an illustration of the proposed approach.

Keywords:

Timed Petri nets, throughput, operational analysis.

References:

• 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.
• G. Berthelot, R. Terrat, "Petri net theory for the correctness of protocols"; IEEE Trans. on Communications, vol.30, no.12, pp.2497-2505, 1982.
• S.C. Bruell, S. Ghanta, "Throughput bounds for generalized stochastic Petri net models"; Proc. Int. Workshop on Timed Petri Nets, Torino, Italy, pp.250-261, 1985.
• J.P. Buzen, "Fundamental operational laws of computer system performance"; Acta Informatica, vol.7, no.2, pp.167-182, 1976.
• J. Campos, G. Chiola, J.M. Colom, M. Silva, "Tight polynomial bounds for steady-state performance of marked graphs"; Proc. Int. Workshop on Petri Nets and Performance Models, Kyoto, Japan, pp.200-209, 1989.
• J. Campos, G. Chiola, M. Silva, "Properties and steady-state performance bounds for Petri nets with unique repetitive firing count vector"; Proc. Int. Workshop on Petri Nets and Performance Models, Kyoto, Japan, pp.210-220, 1989.
• G. Ciardo, J. Muppala, K. Trivedi, "SPNP - stochastic Petri net package"; Proc. Int. Workshop on Petri Nets and Performance Models, Kyoto, Japan, pp.142-151, 1989;
• P.J. Denning, J.P. Buzen, "The operational analysis of queueing network models"; ACM Computing Surveys, vol.10, no.3, pp.225-261, 1978.
• M. Diaz, "Modeling and analysis of communication and cooperation protocols using Petri net based models"; Computer Networks, vol.6, no.6, pp.419-441, 1982.
• 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.
• M.A. Holliday, "Deterministic time and analytical models of parallel architectures"; Ph.D. Thesis, Computer Science Department, University of Wisconsin - Madison, Technical Report #652, 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.
• P.J.B. King, Computer and communication systems performance modelling; Prentice-Hall 1990.
• E.D. Lazowska, J. Zahorjan, G.S. Graham, K.C. Sevcik, Quantitative system performance; Prentice-Hall 1984.
• 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.
• M.K. Molloy, "Performance analysis using stochastic Petri nets"; IEEE Trans. on Computers, vol.31, no.9, pp.913-917, 1982.
• K. Molloy, "Fast bounds for stochastic Petri nets"; Proc. Int. Workshop on Timed Petri Nets, Torino, Italy, pp.244-249, 1985.
• T. Murata, "Petri nets: properties, analysis and applications"; Proceedings of IEEE, vol.77, no.4, pp.541-580, 1989.
• S. Natkin, "Les reseaux de Petri stochastique"; These de Docteur Ingenieur, CNAM, Paris, France, 1980.
• 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.
• 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, "D-timed Petri nets and modelling of timeouts and protocols"; Transactions of the Society for Computer Simulation, vol.4, no.4, pp.331-357, 1988.

Available in pdf and postscript.