Browse Prior Art Database

Recursive Algorithms for Evaluating Queue Size Distribution in a Queue Network

IP.com Disclosure Number: IPCOM000079467D
Original Publication Date: 1973-Jul-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 4 page(s) / 85K

Publishing Venue

IBM

Related People

Kobayashi, H: AUTHOR [+2]

Abstract

It is well known to employ networks of queues to provide models of engineering systems. For example, a multiprogrammed, multiprocessing system can be well modeled in such network. Another example is the use of such a queueing network to model the transmission delay and buffer overflow problem in a communication network.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 4

Recursive Algorithms for Evaluating Queue Size Distribution in a Queue Network

It is well known to employ networks of queues to provide models of engineering systems. For example, a multiprogrammed, multiprocessing system can be well modeled in such network. Another example is the use of such a queueing network to model the transmission delay and buffer overflow problem in a communication network.

In the publication of J. R. Jackson, "Jobshop-Like Queueing Systems", Management Science, Vol. 10, No. 1, October 1963, there is discussed a general network of queues, and the joint distribution of queue size is set forth therein in terms of a relatively simple product form of marginal distributions when the service times are all exponentially distributed. In the publication of H. Kobayashi, "Application of Diffusion Approximation to Queuing Network", IBM Report RC3943, dated July 20, 1972, there are discussed the applications of the diffusion approximation to a network of queues, and approximate solutions are obtained of the joint queue size distribution in closed form. The results set forth in the Kobayashi publication are quite analogous to those obtained in the Jackson publication.

As a practical matter, the values of these closed-form solutions are limited, unless some efficient method is available for numerically evaluating the queue size distribution and related performance criteria parameters of a given system configuration. Examples of the performance criteria which are pertinent are, for example, utilization, throughput, response time, etc.

The recursive algorithm described herein enables the evaluation of the queue size distribution numerically for a general network of queues. The evaluation results obtained thereby are particularly useful to predict the performance of computers, data processing systems, etc. This algorithm provides a practical solution based on recursive algorithm principles and is readily implemented in languages such as APL and PL/I. With regard to the predictive value produced by the evaluation results of the algorithm, the latter can be employed in program packages to provide performance prediction which is based upon analytical models for various system configurations. By contrast, most of currently available performance prediction and evaluation mechanisms are based upon theory of a single server queue. The algorithm described herein is also a great improvement over the known types of performance prediction algorithms, in that it employs a network of queues which is a better model of a typical computer system.

The formulae for queue size distribution set forth herein are based upon the above-referred to Jackson publication and, accordingly, the notations of this publication wherever possible are preserved.

Considering the algorithm,...