Transformations of timed Petri nets and performance analysis

Zuberek, W.M. and Zuberek, M.S.

Proc. 33-rd Midwest Symp. on Circuit and Systems (Special Session on Petri Net Models), Calgary, Alberta, June 1990, pp.774-778.

Abstract:

There are two basic approaches to analysis of timed Petri net models, the so called reachability analysis and structural analysis. Reachability analysis is based of the space of reachable states while structural analysis derives properties of models from properties of model components and component interconnections. This paper discusses several simple transformations of timed nets that significantly simplify performance analysis preserving all important performance properties of the original model. In particular, they can convert a model that can be analyzed by the reachability approach only into an equivalent one (with respect to performance) that can be analyzed by structural methods.

Keywords:

Timed Petri nets, net transformations, performance 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.
• B. Berthomieu, M. Menasche, "An enumerative approach for analyzing time Petri nets"; Information Processing 83, R.E.A. Mason (ed.), pp.41-45, IFIP 1983.
• G.V. Bochmann, "A general transition model for protocols and communication services"; IEEE Trans. on Communications, vol.28, no.4, pp.643-650, 1980.
• J.P. Courtiat, J.M. Ayache, B. Algayres, "Petri nets are good for protocols"; Computer Communication Review, vol.14, no.2, pp.66-74, 1984.
• A. Danthine, "Protocol representation with finite-state models"; IEEE Trans. on Communications, vol.28, no.4, pp.632-643, 1980.
• 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.
• L. Kleinrock, Queueing systems, vol.1: Theory, vol.2: Computer applications; J. Wiley and 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.
• J.L. Peterson, "Petri net theory and the modeling of systems", Prentice-Hall 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.
• R.R. Razouk, C.V. Phelps, "Performance analysis using timed Petri nets"; Proc. Int. Conf. on Parallel Processing, Columbus OH, pp.126-128, 1984.
• W. Reisig, Petri nets - an introduction; 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.
• P. Zafiropulo, C.H. West, D.D. Cowan, D. Brand, "Towards analyzing and synthesizing protocols"; IEEE Trans. on Communications, vol.28, no.4, pp.651-661, 1980.
• W.M. Zuberek, "Extended D-timed Petri nets, timeouts, and analysis of communication protocols", Proc. ACM Annual Conference, Denver CO, 1985, pp.10-15.
• 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"; Trans. of the Society for Computer Simulation, vol.4, no.4, pp.331-357, 1987.