×

zbMATH — the first resource for mathematics

Exact tail asymptotics in a priority queue – characterizations of the preemptive model. (English) Zbl 1209.90116
Summary: We consider the classical preemptive priority queueing system with two classes of independent Poisson customers and a single exponential server serving the two classes of customers at possibly different rates. For this system, we carry out a detailed analysis on exact tail asymptotics for the joint stationary distribution of the queue length of the two classes of customers, for the two marginal distributions and for the distribution of the total number of customers in the system, respectively. A complete characterization of the regions of system parameters for exact tail asymptotics is obtained through analysis of generating functions. This characterization has never before been completed. It is interesting to note that the exact tail asymptotics along the high-priority queue direction is of a new form that does not fall within the three types of exact tail asymptotics characterized by various methods for this type of two-dimensional system reported in the literature. We expect that the method employed in this paper can also be applied to the exact tail asymptotic analysis for the non-preemptive priority queueing model, among other possibilities.

MSC:
90B22 Queues and service in operations research
60K25 Queueing theory (aspects of probability theory)
30E15 Asymptotic representations in the complex plane
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
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] Alfa, A.S.: Matrix-geometric solution of discrete time MAP/PH/1 priority queue. Nav. Res. Logist. 45, 23–50 (1998) · Zbl 0902.90061 · doi:10.1002/(SICI)1520-6750(199802)45:1<23::AID-NAV2>3.0.CO;2-N
[3] Alfa, A.S., Liu, B., He, Q.-M.: Discrete-time analysis of MAP/PH/1 multiclass general preemptive priority queue. Nav. Res. Logist. 50, 662–682 (2003) · Zbl 1044.90012 · doi:10.1002/nav.10083
[4] Bender, E.: Asymptotic methods in enumeration. SIAM Rev. 16, 485–513 (1974) · Zbl 0294.05002 · doi:10.1137/1016082
[5] Borovkov, A.A., Mogul’skii, A.A.: Large deviations for Markov chains in the positive quadrant. Russ. Math. Surv. 56, 803–916 (2001) · Zbl 1068.60034 · doi:10.1070/RM2001v056n05ABEH000398
[6] Bousquet-Mélou, M.: Walks in the quarter plane: Kreweras’ algebraic model. Ann. Appl. Probab. 15, 1451–1491 (2005) · Zbl 1064.05010 · doi:10.1214/105051605000000052
[7] Cohen, J.W., Boxma, O.J.: Boundary Value Problems in Queueing System Analysis. North-Holland, Amsterdam (1983) · Zbl 0515.60092
[8] 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
[9] Drekic, S., Woolford, D.G.: A preemptive priority queue with balking. Eur. J. Oper. Res. 164, 387–401 (2005) · Zbl 1068.90030 · doi:10.1016/j.ejor.2004.01.017
[10] Fayolle, G., Iasnogorodski, R.: Two coupled processors: the reduction to a Riemann–Hilbert problem. Z. Wahrscheinlichkeitstheor. Verw. Geb. 47, 325–351 (1979) · Zbl 0395.68032 · doi:10.1007/BF00535168
[11] Fayolle, G., King, P.J.B., Mitrani, I.: The solution of certain two-dimensional Markov models. Adv. Appl. Probab. 14, 295–308 (1982) · Zbl 0495.60087 · doi:10.2307/1426522
[12] Fayolle, G., Iasnogorodski, R., Malyshev, V.: Random Walks in the Quarter-Plane. Springer, New York (1991) · Zbl 0932.60002
[13] Flajolet, P., Odlyzko, A.: Singularity analysis of generating functions. SIAM J. Discrete Math. 3, 216–240 (1990) · Zbl 0712.05004 · doi:10.1137/0403019
[14] Flatto, L.: Two parallel queues created by arrivals with two demands II. SIAM J. Appl. Math. 45, 861–878 (1985) · Zbl 0579.90033 · doi:10.1137/0145052
[15] Flatto, L., McKean, H.P.: Two queues in parallel. Commun. Pure Appl. Math. 30, 255–263 (1977) · Zbl 0342.60064 · doi:10.1002/cpa.3160300206
[16] Flatto, L., Hahn, S.: Two parallel queues created by arrivals with two demands I. SIAM J. Appl. Math. 44, 1041–1053 (1984) · Zbl 0554.90041 · doi:10.1137/0144074
[17] Foley, R.D., McDonald, D.R.: Join the shortest queue: stability and exact asymptotics. Ann. Appl. Probab. 11, 569–607 (2001) · Zbl 1016.60078
[18] Foley, R.D., McDonald, R.D.: Large deviations of a modified Jackson network: stability and rough asymptotics. Ann. Appl. Probab. 15, 519–541 (2005) · Zbl 1063.60134 · doi:10.1214/105051604000000666
[19] Foley, R.D., McDonald, R.D.: Bridges and networks: exact asymptotics. Ann. Appl. Probab. 15, 542–586 (2005) · Zbl 1085.60068 · doi:10.1214/105051604000000675
[20] Gail, H.R., Hantler, S.L., Taylor, B.A.: Analysis of a non-preemptive priority multiserver queue. Adv. Appl. Probab. 20, 852–879 (1988) · Zbl 0671.60095 · doi:10.2307/1427364
[21] Gail, H.R., Hantler, S.L., Taylor, B.A.: On preemptive Markovian queue with multiple servers and two priority classes. Math. Oper. Res. 17, 365–391 (1992) · Zbl 0762.90028 · doi:10.1287/moor.17.2.365
[22] Haque, L.: Tail behaviour for stationary distributions for two-dimensional stochastic models. Ph.D. Thesis, Carleton University, Ottawa, ON, Canada (2003)
[23] 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 21(1), 77–99 (2005) · Zbl 1065.60133 · doi:10.1081/STM-200046489
[24] He, Q., Li, H., Zhao, Y.Q.: Light-tailed behaviour in QBD process with countably many phases. Stoch. Models 25, 50–75 (2009) · Zbl 1159.60348 · doi:10.1080/15326340802640974
[25] Hou, Q.-H., Mansour, T.: Kernel method and linear recurrence system. J. Comput. Appl. Math. 216, 227–242 (2008) · Zbl 1138.65108 · doi:10.1016/j.cam.2007.05.001
[26] Isotupa, K.P.S., Stanford, D.A.: An infinite-phase quasi-birth-and-death model for the non-preemptive priority M/PH/1 queue. Stoch. Models 18, 378–410 (2002) · Zbl 1009.60080
[27] Kao, E.P.C., Narayanan, K.S.: Computing steady-state probabilities of a non-preemptive priority multiserver queue. ORSA J. Comput. 2, 211–218 (1990) · Zbl 0760.60085
[28] Kroese, D.P., Scheinhardt, W.R.W., Taylor, P.G.: Spectral properties of the tandem Jackson network, seen as a quasi-birth-and-death process. Ann. Appl. Probab. 14(4), 2057–2089 (2004) · Zbl 1078.60078 · doi:10.1214/105051604000000477
[29] Kurkova, I.A., Suhov, Y.M.: Malyshev’s theory and JS-queues. Asymptotics of stationary probabilities. Ann. Appl. Probab. 13, 1313–1354 (2003) · Zbl 1039.60082 · doi:10.1214/aoap/1069786501
[30] Li, L., Miyazawa, M., Zhao, Y.: Geometric decay in a QBD process with countable background states with applications to a join-the-shortest-queue model. Stoch. Models 23, 413–438 (2007) · Zbl 1124.60074 · doi:10.1080/15326340701471042
[31] Lieshout, P., Mandjes, M.: Asymptotic analysis of Lévy-driven tandem queues. Queueing Syst. 60, 203–226 (2008) · Zbl 1156.90334 · doi:10.1007/s11134-008-9094-5
[32] Maertens, T., Walraevens, J., Bruneel, H.: Priority queueing systems: from probability generating functions to tail probabilities. Queueing Syst. 55, 27–39 (2007) · Zbl 1177.90096 · doi:10.1007/s11134-006-9003-8
[33] Malyshev, V.A.: An analytical method in the theory of two-dimensional positive random walks. Sib. Math. J. 13, 1314–1329 (1972)
[34] Malyshev, V.A.: Asymptotic behaviour of stationary probabilities for two-dimensional positive random walks. Sib. Math. J. 14, 156–169 (1973) · Zbl 0307.60060 · doi:10.1007/BF00967270
[35] Mandjes, M.: Large Deviations for Gaussian Queues: Modelling Communication Networks. Wiley, New York (2007) · Zbl 1125.60103
[36] McDonald, D.R.: Asymptotics of first passage times for random walk in an orthant. Ann. Appl. Probab. 9, 110–145 (1999) · Zbl 0937.60091 · doi:10.1214/aoap/1029962599
[37] Miller, D.R.: Computation of steady-state probabilites for M/M/1 priority queues. Oper. Res. 29(5), 945–958 (1981) · Zbl 0468.60089 · doi:10.1287/opre.29.5.945
[38] Mishna, M.: Classifying lattice walks restricted to the quarter plane. J. Comb. Theory Ser. A 116, 460–477 (2009) · Zbl 1183.05004 · doi:10.1016/j.jcta.2008.06.011
[39] Miyazawa, M.: The Markov renewal approach to M/G/1 type queues with countably many background states. Queueing Syst. 46, 177–196 (2004) · Zbl 1056.90035 · doi:10.1023/B:QUES.0000021148.33178.0f
[40] Miyazawa, M.: Doubly QBD process and a solution to the tail decay rate problem. In: Proceedings of the Second Asia-Pacific Symposium on Queueing Theory and Network Applications, Kobe, Japan (2007)
[41] Miyazawa, M.: Two sided DQBD process and solutions to the tail decay rate problem and their applications to the generalized join shortest queue. In: Yue, W., Takahashi, Y., Takagi, H. (eds.) Advances in Queueing Theory and Network Applications, pp. 3–33. Springer, New York (2009)
[42] Miyazawa, M.: Tail decay rates in double QBD processes and related reflected random walks. Math. Oper. Res. 34(3), 547–575 (2009) · Zbl 1213.60151 · doi:10.1287/moor.1090.0375
[43] 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(4), 1231–1251 (2004) · Zbl 1136.60366 · doi:10.1239/aap/1103662965
[44] Morrison, J.A.: Processor sharing for two queues with vastly different rates. Queueing Syst. 57, 19–28 (2007) · Zbl 1128.60081 · doi:10.1007/s11134-007-9043-8
[45] Motyer, A.J., Taylor, P.G.: Decay rates for quasi-birth-and-death process with countably many phases and tri-diagonal block generators. Adv. Appl. Probab. 38, 522–544 (2006) · Zbl 1101.60073 · doi:10.1239/aap/1151337083
[46] Sleptchenko, A., Adan, I.J.B.F., van Houtum, G.J.: Joint queue length distribution of multi-class, single-server queues with preemptive priorities. Preprint (2004) · Zbl 1330.60114
[47] 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), 1–24 (2001) · Zbl 0985.60074 · doi:10.1081/STM-100001397
[48] 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
[49] van Uitert, M.J.G.: Generalized processor sharing queues. Ph.D. Thesis, Eindhoven University of Technology, Eindhoven, The Netherlands (2003) · Zbl 1064.60183
[50] Wischik, D.: Sample path large deviations for queues with many inputs. Ann. Appl. Probab. 11, 379–404 (2001) · Zbl 1012.60085 · doi:10.1214/aoap/1015345296
[51] Wright, P.: Two parallel processors with coupled inputs. Adv. Appl. Probab. 24, 986–1007 (1992) · Zbl 0760.60093 · doi:10.2307/1427722
[52] 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
[53] Zhao, J.-A., Li, B., Cao, X.-R., Ahmad, I.: A matrix-analytic solution for the DBMAP/PH/1 priority queue. Queueing Syst. 53, 127–145 (2006) · Zbl 1104.60059 · doi:10.1007/s11134-006-8306-0
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.