Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Recursive Algorithms for a General Network of Exponential Server Queues

IP.com Disclosure Number: IPCOM000079594D
Original Publication Date: 1973-Aug-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 7 page(s) / 100K

Publishing Venue

IBM

Related People

Kobayashi, H: AUTHOR [+2]

Abstract

It is known that a network of queues provides a good model for various types of systems in engineering and management science. For example, a complex multiprogram computer system can be well modelled in such network. In such modelling, the problem which is presented is the computation of queue size distribution for a general network of queues in O(NK/2/) operations, wherein N is the number of servers and K is the maximal number of jobs. The recursive algorithms described herein solve this problem, i.e., the following relatively general network of exponential server queues wherein: (1) The arrival rate Lambda(K) is a function of the total number K of jobs in the system. (2) The processing rate of each server station is a function of the local queue length at that station.

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 27% of the total text.

Page 1 of 7

Recursive Algorithms for a General Network of Exponential Server Queues

It is known that a network of queues provides a good model for various types of systems in engineering and management science. For example, a complex multiprogram computer system can be well modelled in such network. In such modelling, the problem which is presented is the computation of queue size distribution for a general network of queues in O(NK/2/) operations, wherein N is the number of servers and K is the maximal number of jobs. The recursive algorithms described herein solve this problem, i.e., the following relatively general network of exponential server queues wherein:
(1) The arrival rate Lambda(K) is a function of the total

number K of jobs in the system.
(2) The processing rate of each server station is a function of

the local queue length at that station. and,
(3) The routing is Markovian and state independent.

It is to be realized that a mathematical solution for the problem is provided in the publication of J. R. Jackson, "Jobshop-Like Queuing Systems", Management Science, Vol. 10, No. 1, October 1963. In this publication, there is discussed a relatively general open network of exponential server queues where the arrival rate may depend upon the total number of jobs in the system, and the processing rate of each station may depend upon the local queue length. However, Jackson's mathematical solution is computationally quite difficult and the recursive algorithms described herein address such computational difficulty. To this end, the described recursive algorithms are efficient for evaluating the required sums which extend over (/N+K/(N)) terms. These algorithms arc based upon a recursive evaluation of partial sums which guarantees numerical stability and accuracy and are also quite efficient, e.g., O(NK/2/), where N is the number of servers and K is the maximal number of jobs.

In the special case of constant utilization of but one server station, the latter expression reduces to O(NK).

Realistic queuing models of complex computer systems are quite important and the utilization of the aforementioned mathematical solutions, as rendered less computationally difficult by the recursive algorithms described herein, enables more realistic models than the currently employed closed- system models for the following reasons:
(1) Computer systems usually are open systems and it is quite

important to know the influence of varying job arrival rates
(2) There is enabled the taking into account of the

observed slowdown of the arrival

rate in the case of heavily loaded terminal systems
(3) The variable-processing rates permit the modelling

of multiprocessor server stations,

overhead caused by long internal queues, and pure

time delays.
(4) The influence of a fixed upper limit of jobs (limited access)

1

Page 2 of 7

and a forced lower limit (injection of background jobs).

As will become apparent, these recursive algorithms enable the taking into consideration...