Inhibitor D-Timed Petri Nets And Pereormance Analysis Of Communication Protocols

Abstract

It is shown that the behaviour 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 jseri^ormance analysis of systems of asynchronous concurrent processes and, in particular, communicatioii 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.

Résumé

Dans cet article, on démontre que le comportement de; réseaux de Petri a choix libre, dont les temps de franchissement sont deterministes, peut être réprésents par des graphes d’etat probabilistes. Puisque les graphes correspondant aux réseaux de Petri bornés sont finis, des relations stationnaires peuvent être obtenues par les techniques standards utilisées dans l’snalyse des chaines de Markov. Ce modèle peut être appliqué directement pour analyser la performance des systèmes concourantes, et en particulier des systèmes de communication. Les positions des réseaux de Petri servent comme la modèles des files des messages, les transitions représent des événements dans les réseaux de transmission, les arcs d’inhibidon servent pour indication des priorités des événements simultanés, et le probabilites des transitions correspondent aux frequences relatives des événement aléatoires. Le protocol du “bit alterne” sert à illustrer l’ analyse.

Additional information

Notes on contributors

Wlodzimierz Zuberek

W.M. ZUBEREK is an Associate Professor of Computer Science at Memorial University of Newfoundland in St John’s. He received his M SC in Electronic Engineering and PH D in Computer Science both from the Warsaw Technical University in Warsaw, Poland. His research interests include computer-aided design tools, perfonnance evaluation, and modelling techniques, and also specifications of programming languages, language design, and compiling methods.