Abstract
The Markovian Arrival Process (MAP), which contains the Markov Modulated Poisson Process (MMPP) and the Phase-Type (PH) renewal processes as special cases, is a convenient traffic model for use in the performance analysis of Asynchronous Transfer Mode (ATM) networks. In ATM networks, packets are of fixed length and the buffering memory in switching nodes is limited to a finite numberK of cells. These motivate us to study the MAP/D/1/K queue. We present an algorithm to compute the stationary virtual waiting time distribution for the MAP/D/1/K queue via rational approximations for the deterministic service time distribution in transform domain. These approximations include the well-known Erlang distributions and the Padé approximations that we propose. Using these approximations, the solution for the queueing system is shown to reduce to the solution of a linear differential equation with suitable boundary conditions. The proposed algorithm has a computational complexity independent of the queue storage capacityK. We show through numerical examples that, the idea of using Padé approximations for the MAP/D/1/K queue can yield very high accuracy with tractable computational load even in the case of large queue capacities.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
J. Abate, G.L. Choudhury and W. Whitt, Asymptotics for steady-state tail probabilities in structured Markov queueing models, Stoch. Models 10(1) (1994).
J. Abate and W. Whitt, The Fourier-series method of inverting transforms of probability distributions, Queueing Systems 10 (1992) 5–88.
J. Abate and W. Whitt, Numerical inversion of Laplace transforms of probability distributions, ORSA J. Comp. 7 (1995) 36–43.
N. Akar, Performance analysis of an asynchronous transfer mode multiplexer with Markov modulated inputs, Ph.D. Thesis, Bilkent University, Ankara, Turkey (1994).
N. Akar and E. Arikan, Padé approximations in the analysis of the MMPP/D/1 system,Proc. ITC Spon. Sem., Bangalore (1993) pp. 137–143.
N. Akar and K. Sohraby, An invariant subspace approach in M/G/1 and G/M/1 type Markov chains, submitted to Commun. Stat. Stoch. Models.
N. Akar and K. Sohraby, On computational aspects of the invariant subspace approach to teletraffic problems and comparisons, submitted to Commun. Stat. Stoch. Models.
D. Anick, D. Mitra and M.M. Sondhi, Stochastic theory of a data handling system with multiple sources, Bell Syst. Tech. J. 61 (1982) 1871–1894.
S. Asmussen and G. Koole, Marked point processes as limits of Markovian arrival streams, J. Appl. Prob. 30 (1993) 365–372.
A. Baiocchi, Analysis of the loss probability of MAP/G/1/K queue, Part I: Asymptotic theory, Commun. Stat. Stoch. Models 10(4) (1994) 867–8793.
A. Baiocchi and N. Blefari-Melazzi, Analysis of the loss probability of the MAP/G/1/K queue, Part II: Approximations and numerical results, Commun. Stat. Stoch. Models 10(4) (1994) 895–925.
C. Blondia, The N/G/1 finite capacity queue, Commun. Stat. Stoch. Models 5(2) (1989) 273–294.
C.T. Chen,Linear System Theory and Design (Holt, Rinehart and Winston, New York, 1984).
G.L. Choudhury, D.M. Lucantoni and W. Whitt, Squeezing the most out of ATM, to appear in IEEE Trans. Commun.
A.I. Elwalid and D. Mitra, Fluid models for the analysis and design of statistical multiplexing with loss priorities on multiple classes of bursty traffic,INFOCOM'92 (1992) pp. 415–425.
A.I. Elwalid and D. Mitra, Effective bandwidth of general Markovian traffic sources and admission control of high speed networks, IEEE/ACM Trans. Networking 1(3) (1993) 329–343.
G.H. Golub and C.F. Van Loan,Matrix Computations (The Johns Hopkins University Press, Baltimore, 1989).
L. Gün, Experimental techniques on matrix-analytical solution techniques — extensions and comparisons, Commun. Stat. Stoch. Models 5(4) (1989) 669–682.
H. Heffes and D.M. Lucantoni, A Markov modulated characterization of packetized voice and data traffic and related statistical multiplexer performance, IEEE JSAC 4(6) (1986) 856–868.
I. Ide, Superposition of interrupted Poisson processes and its application to packetized voice multiplexers,Proc. ITC-12 (1988).
T. Kailath,Linear Systems (Prentice-Hall, Englewood Cliffs, NJ, 1980).
L. Kleinrock,Queueing Systems, Vol. 1: Theory (Wiley-Interscience, 1975).
A. Kuczura, The interrupted Poisson process as an overflow process, Bell Syst. Tech. J. 52 (1973) 437–448.
G. Latouche and V. Ramaswami, A logarithmic reduction algorithm for quasi-birth-death processes, J. Appl. Prob. 30 (1993) 650–674.
D.M. Lucantoni, New results for the single server queue with a batch Markovian arrival process, Stoch. Models 7 (1991) 1–46.
D.M. Lucantoni, G.L. Choudhury and W. Whitt, The transient BMAP/G/1 queue, Commun. Stat. Stoch. Models 10(1) (1994) 145–182.
D.M. Lucantoni, K.S. Meier-Hellstern and M.F. Neuts, A single-server queue with server vacations and a class of non-renewal arrival processes, Adv. Appl. Prob. 22 (1990) 676–705.
C.B. Moler and C. Van Loan, Nineteen dubious ways to compute the matrix exponential, SIAM Rev. 20 (1978) 801–836.
M.F. Neuts, A versatile Markovian point process, J. Appl. Prob. 16 (1979) 764–779.
M.F. Neuts,Matrix-geometric Solutions in Stochastic Models (The Johns Hopkins University Press, Baltimore, MD, 1981).
V. Ramaswami, The N/G/1 queue and its detailed analysis, Adv. Appl. Prob. 12 (1980) 222–261.
V. Ramaswami, Nonlinear matrix equations in applied probability — solution techniques and open problems, SIAM Rev. 30 (1988) 256–263.
H. Saito, M. Kawarasaki and H. Yamada, An analysis of statistical multiplexing in an ATM transport network, IEEE JSAC 9(3) (1991) 359–367.
P. Skelly, M. Schwartz and S. Dixit, A histogram-based model for video traffic behavior in an ATM multiplexer, IEEE/ACM Trans. Networking 1(4) (1993) 446–459.
T.E. Stern and A.I. Elwalid, Analysis of separable Markov-modulated rate models for information-handling systems, Adv. Appl. Probl. 23 (1991) 105–139.
R.C.F. Tucker, Accurate method for analysis of a packet-speech multiplexer with limited delay, IEEE Trans. Commun. 36(4) (1988) 479–483.
J. Vlach and K. Singhal,Computer Methods for Circuit Analysis and Design (Van Nostrand Reinhold, New York, 1983).
W. Whitt, Tail probabilities with statistical multiplexing and effective bandwidths for multi-class queues, Telecom. Syst. 2 (1993) 71–107.
R.W. Wolff,Stochastic Modeling and the Theory of Queues (Prentice Hall, Englewood Cliffs, NJ, 1989).
W.M. Wonham,Linear Multivariable Control: A Geometric Approach (Springer, New York, 1974).
J. Ye and S.Q. Li, Analysis of multi-media traffic queues with finite buffer and overload control, Part I: Algorithm,Proc. IEEE INFOCOM (1991) pp. 1464–1474.
J. Ye and S.Q. Li, Analysis of multi-media traffic queues with finite buffer and overload control, Part II: Applications,Proc. IEEE INFOCOM (1992) pp. 848–859.
Author information
Authors and Affiliations
Additional information
This work was done when the author was with the Bilkent University, Ankara, Turkey and the research was supported by TÜBITAK under Grant No. EEEAG-93.
Rights and permissions
About this article
Cite this article
Akar, N., Arikan, E. A numerically efficient method for the MAP/D/1/K queue via rational approximations. Queueing Syst 22, 97–120 (1996). https://doi.org/10.1007/BF01159395
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01159395