zbMATH — the first resource for mathematics

Infinite- and finite-buffer Markov fluid queues: A unified analysis. (English) Zbl 1046.60078
Summary: We study Markov fluid queues where the net fluid rate to a single-buffer system varies with respect to the state of an underlying continuous-time Markov chain. We present a novel algorithmic approach to solve numerically for the steady-state solution of such queues. Using this approach, both infinite- and finite-buffer cases are studied. We show that the solution of the infinite-buffer case is reduced to the solution of a generalized spectral divide-and-conquer (SDC) problem applied on a certain matrix pencil. Moreover, this SDC problem does not require the individual computation of any eigenvalues and eigenvectors. Via the solution for the SDC problem, a matrix-exponential representation for the steady-state queue-length distribution is obtained. The finite-buffer case, on the other hand, requires a similar but different decomposition, the so-called additive decomposition (AD). Using the AD, we obtain a modified matrix-exponential representation for the steady-state queue-length distribution. The proposed approach for the finite-buffer case is shown not to have the numerical stability problems reported in the literature.

60K25 Queueing theory (aspects of probability theory)
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
Full Text: DOI
[1] Akar, N. and Sohraby, K. (1997). An invariant subspace approach in M/G/1 and G/M/1 type Markov chains. Stoch. Models 13, 381–416. · Zbl 0896.60061 · doi:10.1080/15326349708807433
[2] Anick, D., Mitra, D. and Sondhi, M. M. (1982). Stochastic theory of a data handling system with multiple sources. Bell Syst. Tech. J. 61, 1871–1894.
[3] Asmussen, S. (1995). Stationary distributions for fluid flow models with or without Brownian motion. Stoch. Models 11, 21–49. · Zbl 0817.60086 · doi:10.1080/15326349508807330
[4] Bai, Z. and Demmel, J. W. (1993). Design of a parallel nonsymmetric eigenroutine toolbox, Part I. In Proc. 6th SIAM Conf. Parallel Processing for Scientific Computing, Vol. 1 , eds R. F. Sincovec et al. , Society for Industrial and Applied Mathematics, Philadelphia, PA, pp. 391–398.
[5] Bai, Z., Demmel, J. and Gu, M. (1997). Inverse free parallel spectral divide and conquer algorithms for nonsymmetric eigenproblems. Numer. Math. 76, 389–396. · Zbl 0876.65021 · doi:10.1007/s002110050264
[6] Chan, T. F. (1987). Rank revealing \(QR\) factorizations. Linear Algebra Appl. 88/89, 67–82. · Zbl 0624.65025 · doi:10.1016/0024-3795(87)90103-0
[7] Demmel, J. and Kågström, B. (1987). Computing stable eigendecompositions of matrix pencils. Linear Algebra Appl. 88/89, 139–186. · Zbl 0627.65032 · doi:10.1016/0024-3795(87)90108-X
[8] Demmel, J. and Kågström, B. (1993). The generalized Schur decomposition of an arbitrary pencil \(A-\lambda B\): robust software with error bounds and applications. I. Theory and algorithms. ACM Trans. Math. Software 19, 160–174. · Zbl 0889.65042 · doi:10.1145/152613.152615 · www.acm.org
[9] Fiedler, M. and Voos, H. (2000). New results on the numerical stability of the stochastic fluid flow model analysis. In Proc. NETWORKING 2000, Broadband Communications, High Performance Networking, and Performance of Communication Networks , Springer, Paris, pp. 446–457.
[10] Gardiner, J. D. and Laub, A. J. (1986). A generalization of the matrix-sign-function solution for algebraic Riccati equations. Internat. J. Control 44, 823–832. · Zbl 0598.15012 · doi:10.1080/00207178608933634
[11] Kågström, B. and Dooren, P. V. (1992). A generalized state-space approach for the additive decomposition of a transfer matrix. J. Numer. Linear Algebra Appl. 1, 165–181.
[12] Kosten, L. (1984). Stochastic theory of data-handling systems with groups of multiple sources. In Performance of Computer Communication Systems , eds H. Ruding and W. Bux, Elsevier, Amsterdam, pp. 321–331.
[13] Kulkarni, V. G. (1997). Fluid models for single buffer systems. In Frontiers in Queuing: Models and Applications in Science and Engineering , ed. J. H. Dshalalow, CRC Press, Boca Raton, FL, pp. 321–338. · Zbl 0871.60079
[14] Mitra, D. (1988). Stochastic theory of a fluid model of producers and consumers coupled by a buffer. Adv. Appl. Prob. 20, 646–676. · Zbl 0656.60079 · doi:10.2307/1427040
[15] Nagarajan, R., Kurose, J. F. and Towsley, D. (1991). Approximation techniques for computing packet loss in finite-buffered voice multiplexers. IEEE J. Selected Areas Commun. 9, 368–377.
[16] Rogers, L. C. G. (1994). Fluid models in queueing theory and Wiener–Hopf factorization of Markov chains. Ann. App. Prob. 4, 390–413. JSTOR: · Zbl 0806.60052 · doi:10.1214/aoap/1177005065 · links.jstor.org
[17] Schwartz, M. (1994). Broadband Integrated Networks . Prentice-Hall, Upper Saddle River, NJ.
[18] Sun, X. and Quintana-Orti, E. S. (2004). Spectral division methods for block generalized Schur decompositions. To appear in Math. Computation . · Zbl 1054.65034 · doi:10.1090/S0025-5718-04-01667-9
[19] Sun, X. and Quintana-Orti, E. S. (2003). The generalized Newton iteration for the matrix sign function. SIAM J. Sci. Comput. 24, 669–683. · Zbl 1016.65018 · doi:10.1137/S1064827598348696
[20] Tijms, H. C. (1986). Stochastic Modelling and Analysis: A Computational Approach . John Wiley, New York. · Zbl 0606.90128
[21] Tucker, R. (1988). Accurate method for analysis of a packet speech multiplexer with limited delay. IEEE Trans. Commun. 36, 479–483. · Zbl 0668.34074 · doi:10.1109/9.14446
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.