Spectral decomposition approach for transient analysis of multi-server discrete-time queues

Abstract

Discrete time queueing systems are extensively used in modeling the ATM environment at the cell level. This paper examines the transient behavior of a discrete time FCFS multiple server queue. For the arrival process we assume a general discrete time Markovian batch arrival process, where the batch size distribution of the arrivals in successive slots is governed by a finite state discrete time Markov chain. We show that once the spectral decomposition of the "probability generating matrix" of the arrival process is obtained, the complete solution in the transform domain may be given. Using the complex analysis technique and Cauchy's integral formula, we present an efficient numerical method for the numerical calculation of a few performance measures of interest, namely transient probability of queue being empty, and the mean of the queue length distribution. We also generalize our numerical method in the situations where the superposition of a number of independent arrival sources are fed to the queue. It is shown that the numerical complexity of obtaining the transient solution in this case can be substantially reduced by using the approach based on the Kronecker product. The finite buffer case is also analyzed. © 1994.