D-timed Petri nets and modeling of timeouts and protocols
Transactions of the Society for Computer Simulation,
vol.4, no.4, pp.331-357, 1988.
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
Timed Petri nets, commmunication protocols, timeout mechanisms,
reachability analysis, operational analysis, performance analysis.
Agerwala, T. 1979. "Putting Petri nets to work," IEEE Computer,
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,
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,
Danthine, A. 1982. "Protocol representation with finite state models,"
in Computer Network Architectures and Protocols, P.E. Green Jr (ed.),
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,
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,
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.