Matrix Methods for Queuing Problems

Abstract

Queuing networks are often analyzed to determine their behavior under different traffic situations. The analysis may indicate the effect of increasing servers on the waiting times of customers. It may also indicate whether the network can become so overloaded that no customer can be served. Most of the quantities of interest (the blocking probabilities and waiting times for various traffic streams) can be expressed in terms of the steady-state probabilities that are the solution of the local balance or Kolmogorov equations. For most models currently used, these probabilities can be expressed analytically as a product of quantities that can be easily ascertained. However, when the current state of the system dictates future action, such an analytic expression is not always available and the balance equations must be solved explicitly. Even for systems with relatively small numbers of queues (say 4) and a small number of waiting spaces and servers per queue (say 20), the number of linear equations can be huge, i.e. much more than 10,000, and hence these equations are rarely solved. However, most of the equations are sparse, highly structured, and possess enough algebraic structure that it is possible to solve some modest systems. In this paper we will discuss various methods to solve for the steady state probabilities which form a normalized null-vector of a singular matrix. These methods have been traditionally used to solve nonsingular linear systems that arise during the solution of partial differential equations. We show that when applying certain well known iterative techniques the ordering of equations is important, but that the traffic flow usually dictates an appropriate ordering. Our experience in applying various techniques to a queue overflow problem and to a tandem queue problem is described.