Light tail asymptotics in multidimensional reflecting processes for queueing networks
Tóm tắt
Từ khóa
Tài liệu tham khảo
Adan I, Foley RD, McDonald DR (2009) Exact asymptotics for the stationary distribution of a Markov chain: a production model. Queueing Syst 62:311–344
Arjas E, Speed TP (1973) Symmetric Wiener–Hopf factorizations in Markov additive processes. Z Wahrscheinlichkeitstheor Verw Geb 26:105–118
Avram F, Dai JG, Hasenbein JJ (2001) Explicit solutions for variational problems in the quadrant. Queueing Syst 37:259–289
Bertsimas D, Paschalidis IC, Tsitsiklis JN (1998) On the large deviations behavior of acyclic networks of G/G/1 queues. Ann Appl Probab 8:1027–1069
Borovkov AA (1998) Ergodicity and stability of stochastic processes. Wiley, New York. Translated from Russian
Borovkov AA, Mogul’skii AA (1996) The second rate function and the asymptotic problems of renewal and hitting the boundary for multidimensional random walks. Sib Math J 38:647–682
Borovkov AA, Mogul’skii AA (2000) Integro-local limit theorems including large deviations for sums of random vectors. II. Theory Probab Appl 45:3–22
Borovkov AA, Mogul’skii AA (2001) Large deviations for Markov chains in the positive orthant. Russ Math Surv 56:803–916
Bramson M, Dai JG, Harrison JM (2010) Positive recurrence of reflecting Brownian motion in three dimensions. Ann Appl Probab 20:753–783
Chao X, Miyazawa M, Pinedo M (1999) Queueing networks; customers, signals and product form solutions. Wiley, Chichester
Chen H, Yao DD (2001) Fundamentals of queueing networks, performance, asymptotics, and optimization. Springer, New York
Çinlar E (1975) Introduction to stochastic processes. Prentice–Hall, Englewood Cliffs
Dai JG, Miyazawa M (2010) Reflecting Brownian motion in two dimensions: exact asymptotics for the stationary distribution. http://queue3.is.noda.sut.ac.jp/miyazawa/mm-paper (submitted for publication)
Doetsch G (1974) Introduction to the theory and application of the Laplace transformation. Springer, Berlin
Dupuis P, Ellis RS (1997) A weak convergence approach to the theory of large deviations. Wiley, New York
Dupuis P, Ramanan K (2002) A time-reversed representation for the tail probabilities of stationary reflected Brownian motion. Stoch Process Appl 98:253–287
El Kharroubi A, Yaacoubi A, Tahar AB, Bichard K (2010) Variational problem in the non-negative orthant of ℝ3: reflective faces and boundary influence (submitted for publication)
Fayolle G, Iasnogorodski R (1979) Two coupled processors: the reduction to a Riemann–Hilbert problem. Z Wahrscheinlichkeitstheor 47:325–351
Fayolle G, Malyshev VA, Menshikov MV (1995) Topics in the constructive theory of countable Markov chains. Cambridge University Press, Cambridge
Fayolle G, Iasnogorodski R, Malyshev VA (1999) Random walks in the quarter-plane: algebraic methods, boundary value problems and applications. Springer, New York
Feller WL (1971) An introduction to probability theory and its applications, 2nd edn. Wiley, New York
Flatto L, Hahn S (1984) Two parallel queues by arrivals with two demands I. SIAM J Appl Math 44:1041–1053
Foley RD, McDonald DR (2001) Join the shortest queue: stability and exact asymptotics. Ann Appl Probab 11(3):569–607
Foley RD, McDonald DR (2005a) Large deviations of a modified Jackson network: stability and rough asymptotics. Ann Appl Probab 15:519–541
Fujimoto K, Takahashi Y, Makimoto N (1998) Asymptotic properties of stationary distributions in two stage tandem queueing systems. J Oper Res Soc Jpn 41:118–141
Gamarnik D (2002) On deciding stability of constrained homogeneous random walks and queueing systems. Math Oper Res 27:272–293
Gamarnik D (2007) Computing stationary probability distribution and large deviations rates for constrained homogeneous random walks. The undecidability results. Math Oper Res 32:257–265
Glynn P, Whitt W (1994) Logarithmic asymptotics for steady state tail probabilities in a single-server queue. J Appl Probab 31A:131–156
Grassmann WK, Heyman DP (1990) Equilibrium distribution of blocked-structured Markov chains with repeating rows. J Appl Probab 27:557–576
Guillemin F, van Leeuwaarden JSH (2011) Rare event asymptotics for a random walk in the quarter plane. Queueing Syst 67:1–32
Haque L, Liu L, Zhao YQ (2005) Sufficient conditions for a geometric tail in a QBD process with countably many levels and phases. Stoch Models 21:77–99
Harrison JM, Hasenbein JJ (2009) Reflected Brownian motion in the quadrant: tail behavior of the stationary distribution. Queueing Syst 61:113–138
Harrison JM, Williams RJ (1987) Brownian models of open queueing networks with homogeneous customer populations. Stochastics 22:77–115
He Q, Li H, Zhao YQ (2009) Light-tailed behavior in QBD process with countably many phases. Stoch Models 25:50–75
Hille E, Phillips RS (1957) Functional analysis and semi-groups. American Mathematical Society, Rhode Island
Ignatiouk-Robert I (2001) Sample path large deviations and convergence parameters. Ann Appl Probab 11:1292–1329
Ignatyuk IA, Malyshev VA, Scherbakov VV (1994) Boundary effects in a large deviation problems. Russ Math Surv 49:41–99
Katou K, Makimoto N, Takahashi Y (2008) Upper bound for the decay rate of the joint queue-length distribution in a two-node Markovian queueing system. Queueing Syst 58:161–189
Kella O, Miyazawa M (2001) Parallel fluid queues with constant inflows and simultaneous random reductions. J Appl Probab 38:609–620
Khanchi A (2010) Asymptotic hitting distribution for a reflected random walk in the positive quadrant. Stoch Models (to appear)
Kingman JFC (1970) Inequalities in the theory of queues. J R Stat Soc B 32:883–909
Kobayashi M, Miyazawa M (2011) The tail asymptotic behavior of the stationary distribution of a double M/G/1 process and their applications to a batch arrival Jackson network. http://queue3.is.noda.sut.ac.jp/miyazawa/mm-paper (submitted for publication)
Kobayashi M, Miyazawa M, Zhao YQ (2010) Tail asymptotics of the occupation measure for a Markov additive process with an M/G/1-type background process. Stoch Models 26:463–486
Kobayashi M, Sakuma Y, Miyazawa M (2011) Join the shortest queue among k parallel queues: tail asymptotics of its stationary distribution. In: The proceedings of the queueing symposium; stochastic models and their applications, Kyoto, Japan, pp 143–152
Kroese DP, Scheinhardt WRW, Taylor PG (2003) Spectral properties of the tandem Jackson network seen as a quasi-birth-and-death process. Ann Appl Probab 14:2057–2089
Kurkova LA, Suhov YM (2003) Malyshev’s theory and JS-queues. Asymptotics of stationary probabilities. Ann Appl Probab 13:1313–1354
Li H, Zhao YQ (2009) Exact tail asymptotics in a priority queue–characterizations of the preemptive model. Queueing Syst 63:355–381
Li H, Zhao YQ (2010) Tail asymptotics for a generalized two-demand queueing models—a kernel method (submitted)
Li H, Miyazawa M, Zhao YQ (2007) Geometric decay in a QBD process with countable background states with applications to shortest queues. Stoch Models 23:413–438
Lieshout P, Mandjes M (2008) Asymptotic analysis of Lévy-driven tandem queues. Queueing Syst 60:203–226
Majewski K (1996) Large deviations of stationary reflected Brownian motions. In: Kelly FP, Zachary S, Ziedins I (eds) Stochastic networks: theory and applications. Oxford University Press, London
Majewski K (1998) Large deviations of the steady state distribution of reflected processes with applications to queueing systems. Queueing Syst 29:351–381
Majewski K (2004) Large deviation bounds for single class queueing networks and their calculation. Queueing Syst 48:103–134
Markushevich AI (1977) Theory of functions, 2nd edn. American Mathematical Society, Providence. Translated by RA Silverman
Miyazawa M (2002) A paradigm of Markov additive processes for queues and their networks. In: The proceedings of the fourth international conference on matrix-analytic methods in stochastic models: matrix-analytic methods, theory and applications. World Scientific, Singapore, pp 265–289
Miyazawa M (2003) Conjectures on decay rates of tail probabilities in generalized Jackson and batch movement networks. J Oper Res Soc Jpn 46:74–98
Miyazawa M (2004) The Markov renewal approach for the stationary distributions in M/G/1 type queues with countably many background states. Queueing Syst 46:177–196
Miyazawa M (2009a) Two sided DQBD process and solutions to the tail decay rate problem and their applications to the generalized join shortest queue. In: Advances queueing theory and network applications, pp 3–33
Miyazawa M (2009b) Tail decay rates in double qbd processes and related reflected random walks. Math Oper Res 34:547–575
Miyazawa M, Kobayashi M (2010) Conjectures on tail asymptotics of the stationary distribution for a multidimensional SRBM. http://queue3.is.noda.sut.ac.jp/miyazawa/mm-paper (submitted for publication)
Miyazawa M, Rolski T (2009) Exact asymptotics for a Levy-driven tandem queue with an intermediate input. Queueing Syst 63:323–353
Miyazawa M, Taylor PG (1997) A geometric product-form distribution for a queueing network with non-standard batch arrivals and batch transfers. Adv Appl Probab 29:523–544
Miyazawa M, Zhao YQ (2004) The stationary tail asymptotics in the GI/G/1 type queue with countably many background states. Adv Appl Probab 36:1231–1251
Miyazawa M, Zwart B (2009) Wiener–Hopf factorizations for a multidimensional Markov additive process and their applications to reflected processes. http://queue3.is.noda.sut.ac.jp/miyazawa/mm-paper (submitted for publication)
Neuts MF (1981) Matrix-geometric solutions in stochastic models: an algorithmic approach. Johns University Press, Baltimore
Neuts MF (1989) Structured stochastic matrices of M/G/1 type and their applications. Dekker, New York
Neuts MF, Takahashi Y (1997) Asymptotic behavior of the stationary distributions in the GI/PH/c queue with heterogeneous servers. Z Wahrscheinlichkeitstheor 57:441–452
Ney P, Nummelin E (1987a) Markov additive processes I. Eigenvalue properties and limit theorems. Ann Probab 15:561–592
Nummelin E (1984) General irreducible Markov chains and non-negative operators. Cambridge University Press, Cambridge
Ozawa T (2011) Asymptotics for the stationary tail distributions in discrete-time two dimensional QBD processes. In: The proceedings of the queueing symposium; stochastic models and their applications, Kyoto, Japan, pp 254–263
Pitman JW (1974) An identity for stopping times of a Markov process. In: Williams EJ (ed) Studies in probability and statistics. Jerusalem Academic Press, Jerusalem, pp 41–57
Puhalskii AA, Vladimirov AA (2007) A large deviation principle for join the shortest queue. Math Oper Res 32:700–710
Reiman MI, Williams RJ (1988) A boundary property of semimartingale reflecting Brownian motions. Probab Theory Relat Fields 77:87–97. Correction: 80, 633 (1989)
Sadowsky JS (1995) The probability of large queue lengths and waiting times in a heterogeneous multiserver queue I: positive recurrence and logarithmic limits. Adv Appl Probab 27:567–583
Sadowsky JS, Szpankowski WS (1995) The probability of large queue lengths and waiting times in a heterogeneous multiserver queue I: tight limits. Adv Appl Probab 27:532–566
Sakuma Y, Miyazawa M (2005) On the effect of a finite buffer in a two node Jackson network. J Appl Probab 42:199–222
Sakuma Y, Miyazawa M, Zhao YQ (2006) Decay rate for a PH/M/2 queue with shortest queue discipline. Queueing Syst 53:189–201
Shwartz A, Weiss A (1995) Large deviations for performance analysis, queues, communications, and computing. Chapman & Hall, London
Sipser M (1997) Introduction to the theory of computability. PWS, Boston
Takahashi Y (1981) Asymptotic exponentiality of the tail of the waiting-time distribution in a PH/PH/c queue. Adv Appl Probab 13:619–630
Takahashi Y, Fujimoto K, Makimoto N (2001) 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
Taylor LM, Williams RJ (1993) Existence and uniqueness of semimartingale reflecting Brownian motions in an orthant. Probab Theory Relat Fields 96:283–317
Tang J, Zhao YQ (2008) Stationary tail asymptotics of a tandem queue with feedback. Ann Oper Res 160:173–189