D-timed Petri nets and modeling of timeouts and protocols

Zuberek, W.M.

Transactions of the Society for Computer Simulation, vol.4, no.4, pp.331-357, 1988.

Abstract:

D-timed Petri nets are Petri nets with deterministic firing times assigned to transitions of a net. Several classes of D-timed are discussed in this paper to show a hierarchy of models with increasing "modelling power". Conflict-free inhibitor nets are sufficient to model communication protocols with timeouts used to recover from lost and/or distorted messages but they introduce intermediate states which can be removed without any significant effect on the model's behaviour. Extended nets with interrupt arcs (or generalized inhibitor arcs) eliminate all such states. Finally, enhanced nets with two classes of transitions, immediate and timed transitions, are introduced to further reduce the state space. For each class a discrete-time description is provided which represents the behaviour of a net by a homogeneous semi-Markov discrete process. Many performance characteristics can thus be obtained using an approach similar to operational analysis.

Keywords:

Timed Petri nets, commmunication protocols, timeout mechanisms, reachability analysis, operational analysis, performance analysis.

References:

• Agerwala, T. 1979. "Putting Petri nets to work," IEEE Computer, 12(12):85-94.
• Ajmone Marsan, M., G. Balbo, G. Chiola, G. Conte. 1987. "Generalized stochastic Petri nets revisited: random switches and priorities," Proc. of the Int. Workshop on Petri Nets and Performance Models, Madison, WI.
• Ajmone Marsan, M., G. Conte, G. Balbo. 1984. "A class of generalized stochastic Petri nets for the performance evaluation of multiprocessor systems," ACM Trans. on Computer Systems, 2(2):93-122.
• Berthelot, G. and R. Terrat. 1982. "Petri net theory for the correctness of protocols," in Protocol Specification, Testing and Verification II, S. Sunshine (ed.), North-Holland.
• Brauer, W. (ed.) 1980. Net theory and applications (Proc. of the Advanced Course on General Net Theory of Processes and Systems; Lecture Notes in Computer Science 84), Springer-Verlag.
• Chiola, G. 1987. "Structural analysis for generalized stochastic Petri nets: some results and prospects," Proc. of the Eighth European Workshop on Application and Theory of Petri Nets, Zaragoza, Spain.
• Chretienne, Ph. 1985. "Transient and asymptotic behaviour analysis of a timed event graph" (in French), AFCET Technique et Science Informatique, 4(1):127-142.
• Danthine, A. 1982. "Protocol representation with finite state models," in Computer Network Architectures and Protocols, P.E. Green Jr (ed.), Plenum Press.
• Diaz, M. 1982. "Modeling and analysis of communication and cooperation protocols using Petri net based models," Computer Networks, 6(6):419-441.
• Feldbrugge, F. 1985. "Petri net tools," in Advances in Petri Nets 1985 (Lecture Notes in Computer Science 222), G. Rozenberg (ed.), Springer-Verlag.
• Garg, K. 1985. "An approach to performance specification of communication protocols using timed Petri nets," IEEE Trans. on Software Engineering, 11(1):1216-1225.
• Holliday, M.A. and M.K. Vernon. 1985. "A generalized timed Petri net model for performance evaluation," Proc. of the International Workshop on Timed Petri Nets, Torino, Italy.
• Jones, N.D., L.H. Landweber, Y.E. Lien. 1977. "Complexity of some problems in Petri nets,: Theoretical Computer Science, 4(3):277-299.
• Kleinrock, L. 1975 and 1976. Queueing systems. Vol.1: "Theory", Vol.2: "Computer applications", J. Wiley & Sons.
• Kosaraju, S.R. 1973. "Limitations of Dijkstra's semaphore primitives and Petri nets," Operating Systems Review, 7(4):122-126.
• Magott, J. 1984. "Performance evaluation of concurrent systems using Petri nets," Information Processing Letters, 18(1):7-13.
• Merlin, P.M. and D.J. Farber. 1976. "Recoverability of communication protocols - implications of a theoretical study," IEEE Trans. on Communications, 24(9):1036-1049.
• Molloy, M.K. 1982. "Performance analysis using stochastic Petri nets," IEEE Trans. on Computers, 31(9):913-917.
• Molloy, M.K. 1985. "Discrete time stochastic Petri nets," IEEE Trans. on Software Engineering, 11(4):417-423.
• Peterson, J.L. 1981. Petri net theory and the modeling of systems, Prentice-Hall.
• Ramchandani, C. 1974. "Analysis of asynchronous concurrent systems by timed Petri nets", Project MAC Technical Report MAC-TR-120, Massachusetts Institute of Technology, Cambridge, MA.
• Razouk, R.R. and C.V. Phelphs. 1985. "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.), North-Holland.
• Sifakis, J. 1977. "Use of Petri nets for performance evaluation," in Measuring, modelling and evaluating computer systems, North-Holland.
• Symons, F.J.W. 1980. "The description and definition of queueing systems by numerical Petri nets," Australian Telecommunication Journal, 13(2):20-31.
• Yemini, Y. and J.F. Kurose. 1982. "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.), North-Holland.
• Zuberek, W.M. 1980. "Timed Petri nets and preliminary performance evaluation," Proc. of the IEEE Seventh Annual Symp. on Computer Architecture, La Baule, France, 89-96.
• Zuberek, W.M. 1982. "Application of timed Petri nets to analysis of multiprocessor realizations of digital filters," Proc. of the 25th Midwest Symp. on Circuits and Systems, Houghton, MI, 134-139.
• Zuberek, W.M. 1986. "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.), Springer-Verlag, 478-498.
• Zuberek, W.M. 1986. "Inhibitor D-timed Petri nets and performance analysis of communication protocols," INFOR Journal, 24(3):231-249.