×

zbMATH — the first resource for mathematics

Geometric tail of queue length of low-priority customers in a nonpreemptive priority MAP/PH/1 queue. (English) Zbl 1238.60106
The authors earlier studied a discrete-time BMAP/PH/1 queue with preemptive service discipline [Stoch. Models 21, No. 2–3, 799–820 (2005; Zbl 1069.60085)]. In this paper, they study the geometric decay of the tail probability of low-priority customers of a priority MAP/PH/1 queue with non-preemptive service discipline. They use a quasi birth and death (QBD) process to describe a queue with the queue length of high-priority customers playing the role of level and the queue length of low-priority customers together with the phases of arrival and service processes of both classes describing a phase in each level. This treatment make the G-matrix and R-matrix of the QBD block upper triangular with identical blocks on each diagonal. They obtain a generating function equation for the stationary distribution of the queue length of low-priority customers. They also derive a sufficient condition for geometric decay. Numerical methods are presented.

MSC:
60K25 Queueing theory (aspects of probability theory)
90B22 Queues and service in operations research
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abate, J., Whitt, W.: Asymptotics for M/G/1 low-priority waiting-time tail probabilities. Queueing Syst. 25, 173–233 (1997) · Zbl 0894.60088 · doi:10.1023/A:1019104402024
[2] Berger, A.W., Whitt, W.: Effective bandwidths with priorities. IEEE/ACM Trans. Netw. 6, 447–460 (1998) · doi:10.1109/90.720887
[3] Berger, A.W., Whitt, W.: Extending the effective-bandwidth concept to networks with priority classes. IEEE Commun. Mag. 2–7 (1998)
[4] Berman, A., Plemmons, R.J.: Nonnegative Matrices in the Mathematical Science. Academic Press, San Diego (1979) · Zbl 0484.15016
[5] Bertsimas, D., Paschalidis, I.C., Tsitsiklis, J.N.: Asymptotic buffer overflow probabilities in multiclass multiplexers: An optimal control approach. IEEE Trans. Autom. Control 43, 315–335 (1998) · Zbl 0949.93078 · doi:10.1109/9.661587
[6] Delas, S., Mazumdar, R.R., Rosenberg, C.P.: Tail asymptotics for HOL priority queues handling a large number of independent stationary sources. Queueing Syst. 40, 183–204 (2002) · Zbl 1001.90019 · doi:10.1023/A:1014323618507
[7] Elwalid, A.I., Mitra, D.: Analysis, approximations and admission control of a multi-service multiplexing system with priorities. In: Proc. IEEE INFOCOM’95, Boston, MA, 2–6 April, pp. 463–472 (1995) · Zbl 0862.60089
[8] Falkenberg, E.: On the asymptotic behavior of the stationary distribution of Markov chains of M/G/1-type. Stoch. Models 10, 75–97 (1994) · Zbl 0791.60087 · doi:10.1080/15326349408807289
[9] Foley, R.D., McDonald, D.R.: Bridges and networks: exact asymptotics. Ann. Appl. Probab. 15, 542–586 (2005) · Zbl 1085.60068 · doi:10.1214/105051604000000675
[10] Glynn, P.W., Whitt, W.: Logarithmic asymptotics for steady-state tail probability in a single-server queues. Appl. Probab. Adv. 31, 131–156 (1999) · Zbl 0805.60093 · doi:10.2307/3214953
[11] Graham, A.: Kronecker Products and Matrix Calculus with Applications. Ellis Horwood, Chichester (1986) · Zbl 0663.26001
[12] Haque, L., Liu, L., Zhao, Y.Q.: Sufficient conditions for a geometric tail in a QBD process with countably many levels and phases. Stoch. Models 77–99 (2005) · Zbl 1065.60133
[13] Hashida, O., Takahashi, Y.: A discrete-time priority queue with switched batch Bernoulli process inputs and constant service times. In: Jensen, A., Iversen, V.B. (eds.) Teletraffic and Datatraffic in a Period of Change, pp. 521–526. North Holland, Amsterdam (1991)
[14] Khamisy, A., Sidi, M.: Discrete-time priority queueing systems with two-state Markov modulated arrival process. In: INFOCOM 91, pp. 1456–1463 (1991)
[15] Kingman, J.C.F.: A convexity property of positive matrices. Q. J. Math. 12, 283–284 (1961) · Zbl 0101.25302 · doi:10.1093/qmath/12.1.283
[16] Latouche, G., Ramaswami, V.: Introduction to matrix analytic methods in stochastic modeling. In: ASA-SIAM. (1999) · Zbl 0922.60001
[17] Li, H., Miyazawa, M., Zhao, Y.Q.: Geometric decay in a QBD process with countable background states with applications to a join-the-shortest-queue model. Stoch. Models 413–438 (2007) · Zbl 1124.60074
[18] Lucantoni, D.M.: New results on the single server queue with a batch Markovian arrival process. Stoch. Models 7, 1–46 (1991) · Zbl 0733.60115 · doi:10.1080/15326349108807174
[19] Lucantoni, D.M., Meier-Hellstern, K.S., Neuts, M.F.: A single-server queue with server vacations and a class of non-renewal arrival process. Adv. Appl. Probab. 22, 676–705 (1990) · Zbl 0709.60094 · doi:10.2307/1427464
[20] Miyazawa, M., Zhao, Y.Q.: The stationary tail asymptotics in the GI/G/1 type queue with countably many background states. Adv. Appl. Probab. 36, 1231–1251 (2004) · Zbl 1136.60366 · doi:10.1239/aap/1103662965
[21] Neuts, M.F.: A versatile Markovian point process. J. Appl. Probab. 16, 764–779 (1979) · Zbl 0422.60043 · doi:10.2307/3213143
[22] Neuts, M.F.: Matrix-Geometric Solutions in Stochastic Models. The Johns Hopkins University Press, Baltimore (1981) · Zbl 0469.60002
[23] Neuts, M.F.: Structured stochastic matrices of the M/G/1 type and their applications. Marcel Dekker, New York (1989) · Zbl 0695.60088
[24] Sidi, M., Segall, A.: Structured priority queueing systems with applications to packet-radio networks. Perform. Eval. 3, 265–275 (1983) · Zbl 0521.90051 · doi:10.1016/0166-5316(83)90036-6
[25] Subramanian, V., Srikant, R.: Tail probabilities of low-priority waiting times and queue lengths in MAP/GI/1 queue. Queueing Syst. 34, 215–236 (2000) · Zbl 0942.90019 · doi:10.1023/A:1019161120564
[26] Takahashi, Y., Fujimoto, K., Makimoto, N.: Geometric decay of the steady-state probabilities in a Quasi-Birth-And Death process with a countable number of phases. Stoch. Models 17, 1–24 (2001) · Zbl 0985.60074 · doi:10.1081/STM-100001397
[27] Takine, T., Sengupta, B., Hasegawa, T.: An analysis of a discrete-time queue for broadband ISDN with priorities among traffic classes. IEEE Trans. Commun. 42, 1837–1845 (1994) · doi:10.1109/TCOMM.1994.582893
[28] Takine, T.: A nonpreemptive priority MAP/G/1 queue with two classes of customers. J. Oper. Res. Soc. Jpn. 39, 266–290 (1996) · Zbl 0870.90063
[29] Takine, T.: The nonpreemptive priority MAP/G/1 queue. Oper. Res. 47, 917–927 (1999) · Zbl 0986.60087 · doi:10.1287/opre.47.6.917
[30] Tweedie, R.L.: Operator-geometric stationary distribution for Markov chains, with application to queueing models. Adv. Appl. Probab. 14, 392–433 (1982) · Zbl 0484.60072 · doi:10.2307/1426527
[31] Xue, J., Alfa, A.S.: Tail probability of low-priority queue length in a discrete-time priority BMAP/PH/1 queue. Stoch. Models 21, 799–820 (2005) · Zbl 1069.60085 · doi:10.1081/STM-200056025
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.