Probability and Statistics with Reliability, Queuing, and Computer Science Applications, 2nd Edition

Chapter 9Networks of Queues

9.1 Introduction

We have studied continuous-time Markov chains of the birth–death type in Chapter 8. Such CTMCs are characterized by a simple product-form solution [equation (8.34)] and a large number of applications. When we remove the restriction of nearest-neighbor transitions only, we may not have the convenient product-form solution. It is logical to ask whether there is a class of Markov chains that subsumes birth–death processes and that possesses a product-form solution. One important generalization of the birth–death process that we consider is a network of queues. Such networks can model problems of contention that arise when a set of resources is shared. A node or a service center represents each resource. Thus, in a model for computer system performance analysis, we may have a service center for the CPU(s), a service center for each I/O channel, and possibly others. A service center may have one or more servers associated with it. If a job requesting service finds all the servers at the service center busy, it will join the queue associated with the center, and at a later point in time, when one of the servers becomes idle, a job from the queue will be selected for service according to some scheduling discipline. After completion of service at one service center, the job may move to another service center for further service, reenter the same service center, or leave the system.

We shall consider two types of networks: open and closed. ...