A Characterization of Product-Form Queuing Networks

Publisher Website
Google Scholar
Abstract
Queuing network models have proved effective in the design and analysis of computing systems. The class of queuing network models having product-form solutions is amenable to efficient, general solution techniques. The purpose of this paper is to characterize such queuing systems. With this characterization it will be easy to determine whether the product-form algorithms can be used to analyze a system. The product-form property was introduced in the papers of Jackson [4] and Gordon and Newell [3], which also gave the formal solution for the state probabilities in the network. In both of these papers the authors assumed negative exponential service-time distributions and conventional first-come-first-serve service disciplines. A number of researchers have attempted to relax the restrictive assumptions in these early papers. Their results are summarized and extended in the paper of Baskett et al. [1], who show that certain disciplines (processor sharing, infinite servers, and last-come-first-serve preemptive resume) have product form if the service distribution has a rational Laplace transform. They also show that product-form solutions are possible for multiple classes of customers. Muntz [7] investigates the closely related M =--* M property, which is that Poisson arrivals imply Poisson departures. Muntz shows that a network of queues with the M =* M property has product form. The M =~ M property is a beautifully elegant way of characterizing product form, since the characterization is achieved by specifying the input/output properties rather than by analyzing the internal details of the system.