The departure process of discrete-time queueing systems with Markovian type inputs
Tóm tắt
This paper proposes a unified matrix-analytic approach to characterize the output processes of general discrete-time lossless/lossy queueing systems in which time is synchronized/slotted into fixed length intervals called slots. The arrival process can be continuous- or discrete-time Markovian processes. It can be either renewal or non-renewal. The service of a customer commences at the beginning of a slot, consumes a random number of slots, and completes at the end of a later slot. The service times are independent and follow a common and general distribution. Systems with and without server vacations are both treated in this paper. These queueing systems have potential applications in asynchronous transfer mode (ATM) networks, packet radio networks, etc. Since the output process of a node in a queueing network becomes an input process to some node at the next stage, the results of this paper can be used to facilitate end-to-end performance analysis which has attracted more and more attention in the literature.
Tài liệu tham khảo
N. Akar, N.C. Oğuz and K. Sohraby, Matrix-geometric solutions of M=G=1-type Markov chains: A unifying generalized state-space approach, IEEE J. Selected Areas Commun. 16(5) (1998) 626–639.
ATM User-Network Interface Specification, Version 3.0, The ATM Forum (Prentice-Hall, Englewood Cliffs, NJ, 1993).
D. Bertsekas and R. Gallager, Data Networks, 2nd ed. (Prentice-Hall, Englewood Cliffs, NJ, 1992).
C. Blondia, A discrete-time batch Markovian arrival process as B-ISDN traffic model, Belg. J. Oper. Res. Statist. Comput. Sci. 32(3,4) (1994) 3–23.
E. Cinlar, Introduction to Stochastic Processes (Prentice-Hall, Englewood Cliffs, NJ, 1975).
B. T. Doshi, Queueing systems with vacations - a survey, Queueing Systems 1 (1986) 29–66.
H.W. Ferng and J.F. Chang, Connection-wise end-to-end performance analysis of queueing networks with MMPP inputs, accepted for publication in Performance Evaluation (2000).
H.W. Ferng and J.F. Chang, Connection-wise end-to-end delay analysis in ATM networks, IEICE Trans. Commun. E83-B(3) (2000) 659–671.
W. Fischer and K.S. Meier-Hellstern, The Markov-modulated Poisson process (MMPP) cookbook, Performance Evaluation 18 (1993) 149–171.
M.W. Garrett and W. Willinger, Analysis, modeling, and generation of self-similar VBR traffic, in: Proc. ACM Sigcomm'94 (1994) pp. 269–280.
W.K. Grassmann, M.I. Taksar and D.P. Heyman, Regenerative analysis and steady state distribution for Markov chains, Oper. Res. 33 (1985) 1107–1116.
O. Hashida, Y. Takahashi and S. Shimogawa, Switched batch Bernoulli process (SBBP) and the discrete-time SBBP/G/1 queue with application to statistical multiplexer performance, IEEE J. Selected Areas Commun. 9(3) (1991) 394–401.
D.P. Heyman and M.J. Sobel, Handbooks in Operations Research and Management Science, Vol. 2, Stochastic Models (Elsevier, Amsterdam, 1990) chapter V.
P.J. Kuehn, Remainder on queueing theory for ATM networks, Telecommunication Systems 5 (1996) 1–24.
D.M. Lucantoni, New results on the single server queue with a batch Markovian arrival process, Commun. Statist. Stochastic Models 7(1) (1991) 1–46.
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. in Appl. Probab. 22 (1990) 676–705.
D.E. McDysan and D.L. Spohn, ATM Theory and Application (McGraw-Hill, New York, 1995).
M.F. Neuts, A versatile Markovian point process, J. Appl. Probab. 16 (1979) 746–779.
K. Pahlavan, A. Zahedi and P. Krishnamurthy, Wideband local access: wireless LAN and wireless ATM, IEEE Commun. Mag. 35(11) (1997) 34–40.
D. Park, H. Perros and H. Yamashita, Approximate analysis of discrete-time tandem networks with bursty and correlated input traffic and customer loss, Oper. Res. Lett. 15 (1994) 95–104.
V. Paxson and S. Floyd, Wide-area traffic: The failure of Poisson modeling, in: Proc. ACM Sigcomm'94 (1994) pp. 257–268.
H. Saito, The departure process of an N/G/1 queue, Performance Evaluation 11 (1990) 241–251.
H. Saito, Teletraffic Technologies in ATM Networks (Artech House, Boston/London, 1994).
G.D. Stamouli, M.E. Anagnostou and A.D. Georgantas, Traffic source models for ATM networks: A survey, Comput. Commun. 17(6) (1994) 428–438.
T. Takine, T. Suda and T. Hasegawa, Cell loss and output process analyses of a finite-buffer discrete-time ATM queueing system with correlated arrivals, IEEE Trans. Commun. 43(2-4) (1995) 1022–1037.
A.S. Tanenbaum, Computer Networks, 3rd ed. (Prentice-Hall, Englewood Cliffs, NJ, 1996).
S. Vamvakos and V. Anantharam, On the departure process of a leaky bucket system with long-range dependent input traffic, Queueing Systems 28 (1998) 191–214.
P.C. Yeh, Departure process and queueing analyses for several classes of single server queueing systems, Master thesis, chapter 3, Department of Electrical Engineering, National Taiwan University, Taipei, Taiwan (1998).