Abstract
In this paper, 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abate, J., Whitt, W.: Asymptotics for M/G/1 low-priority waiting-time tail probabilities. Queueing Syst. 25, 173–233 (1997)
Alfa, A.S.: Matrix-geometric solution of discrete time MAP/PH/1 priority queue. Nav. Res. Logist. 45, 23–50 (1998)
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)
Bender, E.: Asymptotic methods in enumeration. SIAM Rev. 16, 485–513 (1974)
Borovkov, A.A., Mogul’skii, A.A.: Large deviations for Markov chains in the positive quadrant. Russ. Math. Surv. 56, 803–916 (2001)
Bousquet-Mélou, M.: Walks in the quarter plane: Kreweras’ algebraic model. Ann. Appl. Probab. 15, 1451–1491 (2005)
Cohen, J.W., Boxma, O.J.: Boundary Value Problems in Queueing System Analysis. North-Holland, Amsterdam (1983)
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)
Drekic, S., Woolford, D.G.: A preemptive priority queue with balking. Eur. J. Oper. Res. 164, 387–401 (2005)
Fayolle, G., Iasnogorodski, R.: Two coupled processors: the reduction to a Riemann–Hilbert problem. Z. Wahrscheinlichkeitstheor. Verw. Geb. 47, 325–351 (1979)
Fayolle, G., King, P.J.B., Mitrani, I.: The solution of certain two-dimensional Markov models. Adv. Appl. Probab. 14, 295–308 (1982)
Fayolle, G., Iasnogorodski, R., Malyshev, V.: Random Walks in the Quarter-Plane. Springer, New York (1991)
Flajolet, P., Odlyzko, A.: Singularity analysis of generating functions. SIAM J. Discrete Math. 3, 216–240 (1990)
Flatto, L.: Two parallel queues created by arrivals with two demands II. SIAM J. Appl. Math. 45, 861–878 (1985)
Flatto, L., McKean, H.P.: Two queues in parallel. Commun. Pure Appl. Math. 30, 255–263 (1977)
Flatto, L., Hahn, S.: Two parallel queues created by arrivals with two demands I. SIAM J. Appl. Math. 44, 1041–1053 (1984)
Foley, R.D., McDonald, D.R.: Join the shortest queue: stability and exact asymptotics. Ann. Appl. Probab. 11, 569–607 (2001)
Foley, R.D., McDonald, R.D.: Large deviations of a modified Jackson network: stability and rough asymptotics. Ann. Appl. Probab. 15, 519–541 (2005)
Foley, R.D., McDonald, R.D.: Bridges and networks: exact asymptotics. Ann. Appl. Probab. 15, 542–586 (2005)
Gail, H.R., Hantler, S.L., Taylor, B.A.: Analysis of a non-preemptive priority multiserver queue. Adv. Appl. Probab. 20, 852–879 (1988)
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)
Haque, L.: Tail behaviour for stationary distributions for two-dimensional stochastic models. Ph.D. Thesis, Carleton University, Ottawa, ON, Canada (2003)
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)
He, Q., Li, H., Zhao, Y.Q.: Light-tailed behaviour in QBD process with countably many phases. Stoch. Models 25, 50–75 (2009)
Hou, Q.-H., Mansour, T.: Kernel method and linear recurrence system. J. Comput. Appl. Math. 216, 227–242 (2008)
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)
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)
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)
Kurkova, I.A., Suhov, Y.M.: Malyshev’s theory and JS-queues. Asymptotics of stationary probabilities. Ann. Appl. Probab. 13, 1313–1354 (2003)
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)
Lieshout, P., Mandjes, M.: Asymptotic analysis of Lévy-driven tandem queues. Queueing Syst. 60, 203–226 (2008)
Maertens, T., Walraevens, J., Bruneel, H.: Priority queueing systems: from probability generating functions to tail probabilities. Queueing Syst. 55, 27–39 (2007)
Malyshev, V.A.: An analytical method in the theory of two-dimensional positive random walks. Sib. Math. J. 13, 1314–1329 (1972)
Malyshev, V.A.: Asymptotic behaviour of stationary probabilities for two-dimensional positive random walks. Sib. Math. J. 14, 156–169 (1973)
Mandjes, M.: Large Deviations for Gaussian Queues: Modelling Communication Networks. Wiley, New York (2007)
McDonald, D.R.: Asymptotics of first passage times for random walk in an orthant. Ann. Appl. Probab. 9, 110–145 (1999)
Miller, D.R.: Computation of steady-state probabilites for M/M/1 priority queues. Oper. Res. 29(5), 945–958 (1981)
Mishna, M.: Classifying lattice walks restricted to the quarter plane. J. Comb. Theory Ser. A 116, 460–477 (2009)
Miyazawa, M.: The Markov renewal approach to M/G/1 type queues with countably many background states. Queueing Syst. 46, 177–196 (2004)
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)
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)
Miyazawa, M.: Tail decay rates in double QBD processes and related reflected random walks. Math. Oper. Res. 34(3), 547–575 (2009)
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)
Morrison, J.A.: Processor sharing for two queues with vastly different rates. Queueing Syst. 57, 19–28 (2007)
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)
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)
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)
Takine, T.: A nonpreemptive priority MAP/G/1 queue with two classes of customers. J. Oper. Res. Soc. Jpn. 39, 266–290 (1996)
van Uitert, M.J.G.: Generalized processor sharing queues. Ph.D. Thesis, Eindhoven University of Technology, Eindhoven, The Netherlands (2003)
Wischik, D.: Sample path large deviations for queues with many inputs. Ann. Appl. Probab. 11, 379–404 (2001)
Wright, P.: Two parallel processors with coupled inputs. Adv. Appl. Probab. 24, 986–1007 (1992)
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)
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)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Li, H., Zhao, Y.Q. Exact tail asymptotics in a priority queue—characterizations of the preemptive model. Queueing Syst 63, 355 (2009). https://doi.org/10.1007/s11134-009-9142-9
Received:
Revised:
Published:
DOI: https://doi.org/10.1007/s11134-009-9142-9
Keywords
- Exact tail asymptotics
- Light tail
- Geometric decay
- Decay rate
- Double QBD process
- Preemptive priority queue
- Generating functions