×

zbMATH — the first resource for mathematics

Tail asymptotics for a generalized two-demand queueing model – a kernel method. (English) Zbl 1235.60132
Summary: We consider a generalized two-demand queueing model (the same model was studied in [P. E. Wright, Adv. Appl. Probab. 24, No. 4, 986–1007 (1992; Zbl 0760.60093)]). Using this model, we show how the kernel method can be applied to a two-dimensional queueing system for exact tail asymptotics in the stationary joint distribution and also in the two marginal distributions. We demonstrate in detail how to locate the dominant singularity and how to determine the detailed behavior of the unknown generating function around the dominant singularity for a bivariate kernel, which is much more challenging than the analysis for a one-dimensional kernel. This information is the key for characterizing exact tail asymptotics in terms of asymptotic analysis. This approach does not require a determination or presentation of the unknown generating function(s).

MSC:
60K25 Queueing theory (aspects of probability theory)
30E15 Asymptotic representations in the complex plane
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] Banderier, C., Bousquet-Mélou, M., Denise, A., Flajolet, P., Gardy, D., Gouyou-Beauchamps, D.: Generating functions of generating trees. Discrete Math. 246, 29–55 (2002) · Zbl 0997.05007 · doi:10.1016/S0012-365X(01)00250-3
[3] Bender, E.: Asymptotic methods in enumeration. SIAM Rev. 16, 485–513 (1974) · Zbl 0294.05002 · doi:10.1137/1016082
[4] 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
[5] Cohen, J.W., Boxma, O.J.: Boundary Value Problems in Queueing System Analysis. North-Holland, Amsterdam (1983) · Zbl 0515.60092
[6] 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
[7] 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
[8] Fayolle, G., Iasnogorodski, R., Malyshev, V.: Random Walks in the Quarter-Plane. Springer, New York (1991) · Zbl 0932.60002
[9] Flajolet, P., Odlyzko, A.: Singularity analysis of generating functions. SIAM J. Discrete Math. 3, 216–240 (1990) · Zbl 0712.05004 · doi:10.1137/0403019
[10] Flajolet, F., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009) · Zbl 1165.05001
[11] 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
[12] 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
[13] 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
[14] Guillemin, F., van Leeuwaarden, J.: Rare event asymptotics for a random walk in the quarter plane. Queueing Syst. 67, 1–32 (2011) · Zbl 1210.60100 · doi:10.1007/s11134-010-9197-7
[15] Knuth, D.E.: The Art of Computer Programming, Fundamental Algorithms, vol. 1, 2nd edn.. Addison–Wesley, Reading (1969) · Zbl 0191.18001
[16] 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
[17] Li, H., Zhao, Y.Q.: Exact tail asymptotics in a priority queue–characterizations of the preemptive model. Queueing Syst. 63, 355–381 (2009) · Zbl 1209.90116 · doi:10.1007/s11134-009-9142-9
[18] Li, H., Zhao, Y.Q.: Exact tail asymptotics in a priority queue–characterizations of the non-preemptive model, accepted by Queueing Systems. (2010)
[19] Li, H., Zhao, Y.Q.: A kernel method for exact tail asymptotics–random walks in the quarter plane, submitted (2010)
[20] 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
[21] Malyshev, V.A.: An analytical method in the theory of two-dimensional positive random walks. Sib. Math. J. 13, 1314–1329 (1972)
[22] 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
[23] Miyazawa, M.: Tail decay rates in double QBD processes and related reflected random walks. Math. Methods Oper. Res. 34, 547–575 (2009) · Zbl 1213.60151 · doi:10.1287/moor.1090.0375
[24] Miyazawa, M., Rolski, T.: Tail asymptotics for a Lévey-driven tandem queue with an intermediate input. Queueing Syst. 63, 323–353 (2009) · Zbl 1209.90117 · doi:10.1007/s11134-009-9146-5
[25] 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
[26] Wright, P.: Two parallel processors with coupled inputs. Adv. Appl. Probab. 24, 986–1007 (1992) · Zbl 0760.60093 · doi:10.2307/1427722
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.