Closed queueing networks have proven to be valuable tools for system performance analysis. In this paper, we broaden the applications of such networks by incorporating populations of {em branching customers: whenever a customer completes service at some node of the network, it is replaced by N>=0 customers, each routed independently to a next node, where N has a given, possibly node-dependent branching distribution. Applications of these branching and queueing networks focus on {em stable regimes, where the customer population iteratively dies out in finite expected time; at customer depletions the network is immediately supplied with a new set of customers according to a given initial-state distribution. In our first result, we give a necessary and sufficient condition for stability. An analysis of queue-length distributions seems much more difficult, even under exponential assumptions. Homogeneous, infinite-server networks and n-server single node networks are exceptions for which we give exact results, but our main response to the added difficulty is to give an asymptotic analysis of exponential networks with slowly varying population sizes. We model the behavior of such networks by that of a sequence of closed queueing networks differing only in population size, in analogy with the approach of nearly completely decomposable systems. The theoretical foundations of this approximation technique require limit laws, which we provide for throughputs and for stationary queue-length distributions.

, , ,
CWI
Department of Operations Research, Statistics, and System Theory [BS]

Bayer, N, Coffman, E.G, & Kogan, Y.A. (1995). An asymptotic analysis of closed queueing networks with branching populations. Department of Operations Research, Statistics, and System Theory [BS]. CWI.