Computer Sciences Dept.

Operational Aspects of Centralized Queueing Networks

James Bouhana

We consider mathematical models of multiprogrammed computer systems expressed in the form of closed queueing networks. Such models have traditionally required detailed parameters (e.g., transition probabilities, meanservice times) for both their specification and solution. The primary goal of this thesis is to investigate the extent to which easily-measured operational data can be used in queueing network analysis. Much of the discussion pertains to centralized networks, which generalize the central server model of Buzen in that a customer need not return immediately to the central server after having completed service at a peripheral server. A new methodology of network analysis which proceeds by way of considering nested similarity transformations of a network's transition matrix is introduced. Using this method we derive, for centralized networks, eigenvector equations for the mean number of per-customer visits to each server and the mean total per-customer service time (i.e., mean resource usage) for each server. We show that for separable centralized networks having simple load-independent (SLI) servers, mean resource usages alone are sufficient for determining both a network solution and all associated marginal distributions. Further applying the method of similarity transformations, we prove that a general flow conservation equation is equivalent to the condition that server utilization ratios remain invariant with respect to the level of multiprogramming. For separable networks which are not necessarily centralized, the product-form solution of Gordon and Newel1 is used to develop a new equation relating server utilization to a network's solution parameters. The equation is coupled with the recent operational results of Denning and Buzen to show that for networks having SLI servers, single device utilizations measured at consecutive levels of multiprogramming can be used to derive mean queue lengths and certain marginal distributions pertinent to the device. An algorithm is then presented for deriving multiprogrammed device utilizations given only the mono-programmed utilizations of all devices. We then conclude that monoprogrammed device utilizations alone are sufficient for determining certain marginal distributions at any level of multiprogramming. Some interesting results expressing the variation of mean queue lengths under pre- and post-saturation conditions are also presented.

Download this report (PDF)

Return to tech report index

Computer Science | UW Home