AESOP home


The Distribution of Cycle Times in Tree-Like Networks of Queues

Peter G. Harrison

Journal Article
The Computer Journal
Volume 27
Issue 1
Oxford Journals
DOI 10.1093/comjnl/27.1.27

The time delays experienced by tasks in computer systems are a prime interest for both the user community and installation management. Thus their prediction becomes an important objective for the computer performance analyst. Cycle time in scheduling systems and response time, an aggregation of cycle times, in interactive systems are typical examples. The statistical characteristics of time delays have been represented predominantly by simulation models. In analytical models, based on queueing network analysis, normally only their mean values have been derived using Little's law. An exact derivation is presented for the distribution of cycle times in so-called tree-like queueing networks. The analysis is performed for a choice of network structure which avoids the need for explicit tagging of some test customer. Thus expansion of the state space is not necessary. Cycle time distribution is derived in the form of its Laplace transform, from which its moments follow. Further, a recurrence relation for a uniformly convergent discrete representation of the distribution may be determined in a similar manner. Numerical examples show how the distribution of cycle time and its standard deviation vary as the population of a network increases, and how the exact formulae may be used to validate other types of model, such as approximate analytic or simulation.

Information from