×

zbMATH — the first resource for mathematics

Waiting time and queue length analysis of Markov-modulated fluid priority queues. (English) Zbl 07271266
Summary: This paper considers a multi-type fluid queue with priority service. The input fluid rates are modulated by a Markov chain, which is common for all fluid types. The service rate of the queue is constant. Various performance measures are derived, including the Laplace-Stieltjes transform and the moments of the stationary waiting time of the fluid drops and the queue length distributions. An Erlangization-based numerical method is also provided to approximate the waiting time and the queue length distributions up to arbitrary precision. All performance measures are formulated as reward accumulation problems during busy periods of simple Markovian fluid flow models, for which efficient matrix-analytic solutions are provided, enabling us to solve large models with several hundred states.
MSC:
60K25 Queueing theory (aspects of probability theory)
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90B22 Queues and service in operations research
60J25 Continuous-time Markov processes on general state spaces
65C40 Numerical analysis or methods applied to Markov chains
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Miller, RG Jr, Priority queues, Ann. Math. Stat., 31, 86-103 (1960) · Zbl 0089.34401
[2] Takine, T., A nonpreemptive priority MAP/G/1 queue with two classes of customers, J. Oper. Res. Soc. Jpn., 39, 2, 266-290 (1996) · Zbl 0870.90063
[3] Horváth, G., Efficient analysis of the MMAP[K]/PH[K]/1 priority queue, Eur. J. Oper. Res., 246, 1, 128-139 (2015) · Zbl 1346.90252
[4] Ramaswami, V.: Matrix analytic methods for stochastic fluid flows. In: Teletraffic Engineering in a Competitive World—Proceedings of the 16th International Teletraffic Congress (ITC 16), Elsevier, pp. 1019-1030 (1999)
[5] Knessl, C.; Tier, C., A simple fluid model for servicing priority traffic, IEEE Trans. Autom. Control, 46, 6, 909-914 (2001) · Zbl 1017.90012
[6] Liu, Y.; Gong, W., On fluid queueing systems with strict priority, IEEE Trans. Autom. Control, 48, 12, 2079-2088 (2003) · Zbl 1364.90127
[7] Narayanan, A., Kulkarni, V.: First passage times in fluid models with an application to two priority fluid systems. In: Proceedings of IEEE International Computer Performance and Dependability Symposium. IEEE, pp. 166-175 (1996)
[8] Zhang, J.: Performance study of Markov modulated fluid flow models with priority traffic. In: INFOCOM’93. Proceedings. Twelfth Annual Joint Conference of the IEEE Computer and Communications Societies. Networking: Foundation for the Future. IEEE, pp. 10-17 (1993)
[9] Choi, BD; Choi, KB, A Markov modulated fluid queueing system with strict priority, Telecommun. Syst., 9, 1, 79-95 (1998)
[10] Tzenova, E.I., Adan, I., Kulkarni, V.G.: A two-priority fluid flow model: joint steady state distribution of the buffer content processes. Technische Universiteit Eindhoven, Department of Mathematics and Computing Science, TU/e (2004)
[11] Takine, T., The workload in the MAP/G/1 queue with state-dependent services: its application to a queue with preemptive resume priority, Stoch. Models, 10, 1, 183-204 (1994) · Zbl 0791.60088
[12] Kulkarni, VG, Fluid models for single buffer systems, Front. Queueing Models Appl. Sci. Eng., 321, 338 (1997) · Zbl 0871.60079
[13] Kankaya, HE; Akar, N., Solving multi-regime feedback fluid queues, Stoch. Models, 24, 3, 425-450 (2008) · Zbl 1148.60071
[14] Ahn, S.; Ramaswami, V., Efficient algorithms for transient analysis of stochastic fluid flow models, J. Appl. Probab., 42, 531-549 (2005) · Zbl 1085.60065
[15] Ramaswami, V.; Woolford, DG; Stanford, DA, The Erlangization method for Markovian fluid flows, Ann. Oper. Res., 160, 1, 215-225 (2008) · Zbl 1140.60357
[16] Kulkarni, VG; Tzenova, E., Mean first passage times in fluid queues, Oper. Res. Lett., 30, 5, 308-318 (2002) · Zbl 1146.90373
[17] Bean, NG; O’Reilly, MM, A stochastic two-dimensional fluid model, Stoch. Models, 29, 1, 31-63 (2013) · Zbl 1267.60082
[18] Dzial, T.; Breuer, L.; da Silva Soares, A.; Latouche, G.; Remiche, M-A, Fluid queues to solve jump processes, Perform. Eval., 62, 1, 132-146 (2005)
[19] Takine, T.; Takahashi, Y., On the relationship between queue lengths at a random instant and at a departure in the stationary queue with BMAP arrivals, Stoch. Models, 14, 3, 601-610 (1998) · Zbl 0906.60066
[20] Kim, NK; Chang, SH; Chae, KC, On the relationships among queue lengths at arrival, departure, and random epochs in the discrete-time queue with D-BMAP arrivals, Oper. Res. Lett., 30, 1, 25-32 (2002) · Zbl 1002.60085
[21] Lucantoni, DM; Meier-Hellstern, KS; Neuts, MF, A single-server queue with server vacations and a class of non-renewal arrival processes, Adv. Appl. Probab., 22, 676-705 (1990) · Zbl 0709.60094
[22] Wang, W-G; Wang, W-C; Li, R-C, Alternating-directional doubling algorithm for M-matrix algebraic Riccati equations, SIAM J. Matrix Anal. Appl., 33, 1, 170-194 (2012) · Zbl 1258.65045
[23] Golub, GH; Nash, S.; Van Loan, C., A Hessenberg-Schur method for the problem AX+XB=C, IEEE Trans. Autom. Control, 24, 6, 909-913 (1979) · Zbl 0421.65022
[24] Bernstein, DS, Matrix Mathematics: Theory, Facts, and Formulas (2009), Princeton: Princeton University Press, Princeton
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.