Browse Prior Art Database

Original Publication Date: 1984-Jun-27
Included in the Prior Art Database: 2007-Mar-30

Publishing Venue

Software Patent Institute

Related People

Kritzinger, Pieter S.: AUTHOR [+2]


Pieter S. Kritzinger*

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 12% of the total text.

Page 1 of 18

RZ 1317 (#47484) 6/27/84 Computer Science 16 pages


Pieter S. Kritzinger*

IBM Zurich Research Laboratory, 8803 Ruschlikon, Switzerland

With the typing assistance of Judith Gygax

ABSTRACT: Consider a communication protocol represented by a
labeled directed graph in which the vertices represent states,
and the labels on each edge describe the expected duration and
the probability, respectively, of a transition between the
states. Applying analytical methods known from queueing network
theory, it is shown how to analyze the protocol for such per-
formance measures as the frequency and cycle times of a trans-
ition, irrespective of the distribution of the transition times.
It is also shown how to reduce the problem should the state
space become very large. The method has a practical application
in that developers of a protocol can identify in advance those
parts of the implementation which wi.ll be important to the
overall efficiency of the protocol.

* On leave from the University of Stellenbosch, South Africa.

June 8, 1984

[This page contains 1 picture or other non-text object]

Page 2 of 18

[This page contains 1 picture or other non-text object]

Page 3 of 18


Models of communication networks for the purpose of determin- ing performance measures such as throughput and delay t i m e were reported in the literature as far back as 1976 C43. Those analyses, by necessity, took account of the protocol involved a t the level of detail represented by the model, and therefore, in some sense, may be viewed as an analysis of the

performance of the protocol. In fact, the work of Tobagi
ill], as is the case for most delay analyses done for local networks C2,33, is indeed a stochastic analysis of the per- formance of the access protocol.

A different viewpoint was recently mooted by Rudin C 83, name- ly, t o predict the performance of a protocol direct from its formal definition. Traditionally, f?ormal models which speci- fy the syntactical behavior of communication protocols have not included t i m e in the specificati,on. In order to verify the t i m e efficiency of a protocol, as indeed t o verify its syntactical correctness, it is necessary to associate an elapsed or execution t i m e with every interstate transition i n the protocol. Where more than one transition is possible from a particular state, an indication has to be given, or an estimate made, of the probability of each such transition. This paper is concerned with the latter approach t o protocol performance. Apart from the work by RudinC8,93, there is very little related work reported in the literature. Shapiro 1103 presents an analysis of a one-bounded Petri-net model, which he calls a Random P e t r i N e t (RPN). Malloy 163 assigns an exponentially distributed firing time t o each transition in a, possi...