Bottlenecks in Markovian Queueing Networks

Phil Pollett

Abstract: We consider the problem of identifying bottlenecks in closed queueing networks with state-dependent service rates. A particular queue is said to be a bottleneck if the number of customers in that queue grows without bound as the total number of customers in the network becomes large. Whittle (1968) proved that if there is a unique queue with maximal traffic, then it is certain to be a bottleneck. Later, Brown and Pollett (1982) gave conditions under which queues that share maximal traffic behave individually as bottlenecks. In this paper we will show that the problem of identifying bottlenecks can be reduced to one of finding them in an isolated subnetwork with suitably modified arrival rates. Several special cases will be studied, which illustrate a range of behaviour. For example, it is possible for a subnetwork to exhibit bottleneck behaviour, yet each queue in that subnetwork is not strictly a bottleneck.

Acknowledgement: This worked was funded by the Australian Research Council.

The author:

Last modified: 28th January 1998