AESOP home

Publications

An exact analysis of the distribution of cycle times in a class of queueing networks

Peter G. Harrison

Conference or Workshop Paper
SIGMETRICS'83, ACM SIGMETRICS conference on Measurement and Modeling of Computer Systems
July, 1983
pp.224–242
ACM
DOI 10.1145/800040.801411
Abstract

Prediction of detailed characteristics of the time delays experienced by customers in queueing networks is of great importance in various modelling and performance evaluation activities: operations research, computer systems and communication networks. Their statistical properties have been investigated predominantly by simulation techniques with the exception of mean value analyses for which Little's Law is applied. Theoretical studies of the probability distributions of time delays tend to be based on their Laplace transforms, which are of limited use, can be inverted analytically only in very simple cases and present substantial computation problems for numerical inversion. An exact derivation is presented for the distribution of cycle times in so called tree-like queueing networks. The analysis is performed for a network structure which is such that it is not necessary to mark a special customer, so avoiding expansion of the state space. Cycle time distribution is derived initially in the form of its Laplace Transform, from which its moments follow. A recurrence relation for a uniformly convergent discrete representation of the distribution then follows by a similar argument. Finally, the numerical results obtained for some simple test networks are presented and compared with those corresponding to an approximate method, hence indicating the accuracy of the latter.

Information from pubs.doc.ic.ac.uk/cycle-time-queueing.