Inhibitor D-timed Petri nets and performance analysis of communication protocols

Zuberek, W.M.

INFOR Journal - Special Issue on Communication System Performance, vol.24, no.3, pp.231-249, 1986.

Abstract:

It is shown that the behavior of inhibitor free-choice Petri nets with deterministic firing times can be represented by probabilistic state graphs. For bounded Petri nets the corresponding state graphs are finite, and stationary descriptions can thus be obtained by standard techniques used for analysis of Markov chains. An immediate application of such a model is performance analysis of systems of asynchronous concurrent processes, and in particular communication protocols. Places of Petri nets model queues of messages, transitions represent events in communication networks, inhibitor arcs are used to indicate priorities of simultaneous events, and probabilities associated with free-choice classes correspond to relative frequencies of random events. The alternating bit protocol is used as an illustration of analysis.

Keywords:

Timed Petri nets, free-choice Petri nets, inhibitor Petri nets, state descriptions, state graphs, stationary probabilities, communication protocols, alternating bit protocol.

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. Advanced Course on General Net Theory of Processes and Systems, Hamburg, 1979); Lecture Notes in Computer Science 84, Springer-Verlag 1980.
• G. Berthelot, R. Terrat, "Petri nets 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-46, North-Holland, 1983.
• G. von Bochmann, C.A. Sunshine, "A survey of formal methods"; in Computer Network Architectures and Protocols, P.E. Green Jr (ed.), pp.561-578, Plenum Press, 1982.
• A.A.S. Danthine, "Protocol representation with finite state models"; in Computer Network Architectures and Protocols, P.E. Green Jr (ed.), pp.579-606, Plenum Press, 1982.
• 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.
• D. Ferrari, Computer systems performance evaluation; Prentice Hall 1981.
• K. Garg, "An approach to performance specification of communication protocols using timed Petri nets"; Proc. 4th Int. Conf. on Distributed Computer Systems, pp.202-212, San Francisco CA, 1984.
• W. Jurgensen, S.T. Vuong, "Formal specification and validation of ISO transport protocol components using Petri nets"; Computer Communication Review, vol.14, no.2, pp.75-82, 1984.
• 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.
• A. Pattavina, S. Trigila, "Combined use of finite-state machines and Petri nets for modelling communicating processes"; Electronics Letters, vol.20, no.22, pp.915-916, 1984.
• 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.
• H. Rudin, C.H. West (eds.), Protocol Specification, Testing and Verification III (Proc. of the IFIP WG 6.1 Third International Workshop, Ruschlikon, Switzerland, May/June 1983); North-Holland 1983.
• G.D. Schultz, D.B. Rose, C.H. West, J.P. Gray, "Executable representation and validation of SNA"; in Computer Network Architectures and Protocols, P.E. Green Jr (ed.), pp.671-705, Plenum Press, 1982.
• J. Sifakis, "Use of Petri nets for performance evaluation"; in Measuring, Modelling and Evaluating Computer Systems, pp.75-93, North-Holland 1977.
• Y. Yemini, J.F. Kurose, "Towards the unification of the functional and performance analysis of protocols or, is the alternating-bit protocol really correct"; in Protocol Specification, Testing and Verification II, C. Sunshine (ed.), pp.189-196, North-Holland 1982.
• W.M. Zuberek, "Timed Petri nets and preliminary performance evaluation"; Proc. IEEE 7-th Annual Symp. on Computer Architecture, La Baule, France, pp.89-96, 1980.
• W.M. Zuberek, "Application of timed Petri nets to analysis of multiprocessor realizations of digital filters"; Proc. 25 Midwest Symp. on Circuits and Systems, Houghton MI, 1982.
• W.M. Zuberek, "Performance evaluation using extended timed Petri nets"; Proc. Int. Workshop on Timed Petri Nets, Torino, Italy, pp.272-278, 1985.