A.S. Alfa

200

References Zhao Y.Q., Li W. and Alfa A.S. (1999). Duality Results for Block-Structured Transition Matrices. Journal of Applied Probability 36, 1045-1057.

B e n n y Van H o u d t University of Antwerp, Belgium This paper demonstrates how the matrix-analytic method (MAM) can be applied to obtain important characteristics, e.g., waiting time distributions, of discrete time queues. It combines a number of well-known results like the Geo/Geo/1 and P H / P H / 1 system, as well as some more recent developlnents like the G I / G I / 1 and exhaustive time limited P H / P H / 1 system. The paper gives a good flavor of the MAM and its flexibility. In the past, most queueing systems were studied by means of the MAM by letting the first/outer level of the Markov chain reflect the number of customers waiting in the queue. This approach is often very useful and is applied in Sections 2, 5 and 7. As this is a very natural thing to do, many researchers working in the applied field thought that if this approach did not work, then the MAM was not applicable. They got this impression mainly because most papers that appeared used this approach. However, the MAM is much more flexible and this is very well demonstrated in Sections 8 and 9 of this paper. Though, one must keep in mind that the matrix a(V)U obtained in section 8, after using the advantages of an unconventional state space arrangement, is nothing but the transition matrix of the classic approach if we observe the system only at arrival time instants. Also, the matrix a(V)U has a skip-free structure to the right which can be further exploited. This paper tbcusses on queueing systems where the arrival processes are renewal, e.g., Geo or PH, however, as noted by the author, it can often a]so be applied to systems with correlated arrivals (Alia (1995), in the paper). A lot of attention has also gone to applying the MAM to queueing systems with batch arrivals (e.g., D - B M A P / D / 1 queue, Blondia (1993), and

Discrete Time Queues and Matriz-analytic Methods

201

D-BMAP/PH/1 queue), or even to discrete time queues with multiple customer types where each customer as a different service requirement, Van Houdt and Blondia (2002). Another important issue which is not touched in this paper, is related to the computation of the G and R matrices which appear when applying the MAM. For the Quasi-Birth-Death (QBD) cases, one can use, among others, one of the tbllowing algorithms: the Logarithmic Reduction algorithm (Latouche and Ramaswami (1999)), the Invariant State Space approach, Akar and Sohraby (1997) or the Cyclic Reduction algorithm, Meini (1998), where the last was shown to be slightly more efficient. A variety of algorithms also exists tbr the GI/M/1 type Markov chains, see Akar and Sohraby (1997), Alia et ah (2002) and the references within. Another interesting approach used to obtain the matrix R, is to compute the G matrix of the time reversed M / G / 1 type Markov chain, Ramaswami (1990). The advantage of this approach is that one can apply an algorithm that converges quadratically (e.g., the Cyclic Reduction algorithm, Meini (1998)), as opposed to the linear convergence of many other algorithms that compute R in a direct manner. Markov chains of the M / G / 1 type are typical tbr queues with batch arrivals. In conclusion, I recommend this paper to any reader not too familiar to the MAM.

References Alfa A.S., Sengupta B., Takine T. and Xue J. (2002). A New Algorithm for Computing the Rate Matrix of GI/M/1 Type Markov Chains. Proceedings of the 4th International Conference on Matrix Analytic Methods, Adelaide, Australia, 1-16. Akar N. and Sohraby K. (1997). An Invariant Subspace Approach in M/G/1 and GI/M/1 Type Markov Chains. Stochastic Models 13, 381-416. Blondia C. (1993). A Discrete-Time Batch Markovian Aarrival Process as BISDN Trafi3c Model. Belgian Journal of Operations Research, Statistics and Computer Science 32. Latouche G. and Ramaswami V. (1999). Introduction to Matriz Analytic Methods and Stochastic Modeling. SIAM Series on Applied Probability. Meini B. (1998). Solving M/G/1 Type Markov Chains: Recent Advances and Applications. Stochastic Models 14, 479-496.

202

A.S. Alfa

Ramaswami V. (1990). A Duality Theorem for the Matrix Paradigms in Queueing Theory. Stochastic Models 6, 151-161. Van Houdt B. and Blondia C. (2002). The Delay Distribution of a Type k Customer in a First-Come-First-Served MMAP[KI/PH[K]/1 Queue. Journal of Applied Probability 39, 213-223.

Qiang Ye University of Kentucky, USA Continuous time queueing models are widely used often because of its simplicity in mathematical analysis. Many queueing problems in practice are, however, discrete time in nature. For example, today's telecommunication queueing systems, with mostly digital rather than analogue signals, are better treated with discrete time models. It is therefore desirable to develop theory and computational tools for discrete time queueing systems and to know the advantages and disadvantages of discrete time models when compared with continuous time models. The present paper by A. S. Alia aims to demonstrate that the discrete time queueing systems with matrix-analytic methods can be an efficient approach to solving many queueing problems. The paper presents several queueing systems that can be set up as discrete time quasi-birth-and-death processes and discuss the use of matrixanalytic methods (MAM) to solve these problems. After a review of the basic discrete queues such as Geo/Geo/1, Geo/Geo/c and their continuous time counterparts, the paper develops models and analysis for discrete time P H / P H / 1 systems. As special cases, Geo/PH/1, PH/Geo/1, Geo/D/1 systems are also included. It fhrther discusses the G I / G / 1 system as an I P H / I P H / 1 system. It also includes a finite but[%r system ( G I / G / 1 / K system), Ibr which a matrix-analytic like method can be developed. This is an excellent and timely survey. Various aspects of the discrete models are discussed in details. There is no doubt that it has successfully demonstrated usefulness and effectiveness of the discrete time approach when combined with the matrix-analytic methods. The shortcoming of the paper appears to be that, while presenting the discrete models, it has offered limited direct comparisons with the continuous time approach. For