Abstract
We are concerned with the stationary distributions of reflecting processes on multidimensional nonnegative orthants and other related processes, provided they exist. Such stationary distributions arise in performance evaluation for various queueing systems and their networks. However, it is very hard to obtain them analytically, so our interest is directed to analytically tractable characteristics. For this, we consider tail asymptotics of the stationary distributions.
The purpose of this paper is twofold. We first overview the current approaches to attack the problem from a unified viewpoint. We then take up two approaches, Markov additive and analytic function approaches, which are recently developed by the author and his colleagues. We discuss their possible extensions. We mainly consider the tail asymptotics for two-dimensional reflecting processes, but also discuss how we can approach the case of more than two dimensions.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
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
Alsmeyer G (1994) On the Markov renewal theorem. Stoch Process Appl 50:37–56
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
Chang CS (1995) Sample path large deviations and intree networks. Queueing Syst 20:7–36
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
Collamore J (1996) Hitting probabilities and large deviations. Ann Probab 24:2065–2078
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
Flajolet P, Sedqewick R (2009) Analytic combinatorics. Cambridge University Press, Cambridge
Flatto L, Hahn S (1984) Two parallel queues by arrivals with two demands I. SIAM J Appl Math 44:1041–1053
Flatto L, McKean HP (1977) Two queues in parallel. Commun Pure Appl Math 30:255–263
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
Foley RD, McDonald DR (2005b) Bridges and networks: exact asymptotics. Ann Appl Probab 15:542–586
Ethier SN, Kurtz TG (1986) Markov processes: characterization and convergence. Wiley, New York
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 (2003) A broader view of Brownian networks. Ann Appl Probab 13:1119–1150
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 (1961) Two similar queues in parallel. Ann Math Stat 32:1314–1323
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 (2007) Brownian tandem queues. Math Methods Oper Res 66:275–298
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
Ney P, Nummelin E (1987b) Markov additive processes II. Large deviations. Ann Probab 15:593–609
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
Seneta E (1981) Non-negative matrices and Markov chains, 2nd edn. Springer, New York
Serfozo RF (1999) Introduction to stochastic networks. Springer, New York
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
Zhao YQ, Li W, Braun WJ (2003) Censoring, factorizations and spectral analysis for transition matrices with block-repeating entries. Methodol Comput Appl Probab 5:35–58
Author information
Authors and Affiliations
Corresponding author
Additional information
This invited paper is discussed in the comments available at doi:10.1007/s11750-011-0181-0, doi:10.1007/s11750-011-0182-z, doi:10.1007/s11750-011-0183-y, doi:10.1007/s11750-011-0184-x.
Rights and permissions
About this article
Cite this article
Miyazawa, M. Light tail asymptotics in multidimensional reflecting processes for queueing networks. TOP 19, 233–299 (2011). https://doi.org/10.1007/s11750-011-0179-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-011-0179-7
Keywords
- Queueing network
- Reflecting random walk
- Semi-martingale reflecting Brownian motion
- Stationary distribution
- Tail asymptotic
- Tail decay rate
- Large deviations
- Light tail
- Stability
- Stationary inequality
- Server collaboration
- Join the shortest queue
- Markov additive process
- Convergence domain
- Multidimensional moment generating function