Home | Articles | Past volumes | About | Login | Notify | Contact | Search
 Stochastic Systems open journal systems 

Heavy traffic approximation for the stationary distribution of a generalized Jackson network: The BAR approach

Anton Braverman, Cornell University
J.G. Dai, Cornell University
Masakiyo Miyazawa, Tokyo University of Science

In the seminal paper of Gamarnik and Zeevi [17], the authors justify the steady-state diffusion approximation of a generalized Jackson network (GJN) in heavy traffic. Their approach involves the so-called limit interchange argument, which has since become a popular tool employed by many others who study diffusion approximations. In this paper we illustrate a novel approach by using it to justify the steady-state approximation of a GJN in heavy traffic. Our approach involves working directly with the basic adjoint relationship (BAR), an integral equation that characterizes the stationary distribution of a Markov process. As we will show, the BAR approach is a more natural choice than the limit interchange approach for justifying steady-state approximations, and can potentially be applied to the study of other stochastic processing networks such as multiclass queueing networks.

Keywords: Stochastic processing networks, single class networks, multiclass networks, stationary distributions, heavy traffic approximation, interchange of limits, reflecting Brownian motions, SRBM.

Creative Common LOGO

Full Text: PDF

Braverman, Anton, Dai, J.G., Miyazawa, Masakiyo, Heavy traffic approximation for the stationary distribution of a generalized Jackson network: The BAR approach, Stochastic Systems, 7, (2017), 1-54 (electronic). DOI: 10.1214/15-SSY199.


[1]    Baccelli, F. and Brémaud, P. (2003). Elements of queueing theory: Palm martingale calculus and stochastic recurrences, vol. 26 of Applications of Mathematics. 2nd ed. Springer, Berlin. MR1957884

[2]    Berman, A. and Plemmons, R. J. (1979). Nonnegative matrices in the mathematical sciences. Academic Press, New York. MR0544666

[3]    Boucherie, R. J. and van Dijk, N. M. (2011). Queueing networks: a fundamental approach. International Series in Operations Research & Management Science, Springer. http://dx.doi.org/10.1007/978-1-4419-6472-4. MR2829413

[4]    Bramson, M. and Dai, J. G. (2001). Heavy traffic limits for some queueing networks. Ann. Appl. Probab., 11 49–90. http://dx.doi.org/10.1214/aoap/998926987. MR1825460

[5]    Braverman, A. and Dai, J. G. (2017). Stein’s method for steady-state diffusion approximations of M∕Ph∕n + M systems. Ann. Appl. Probab., 27 550–581. http://dx.doi.org/10.1214/16-AAP1211. MR3619795

[6]    Braverman, A., Dai, J. G. and Feng, J. (2016). Stein’s method for steady-state diffusion approximations: an introduction through the Erlang-A and Erlang-C models. Stochastic Systems, 6 301–366. http://www.i-journals.org/ssy/viewarticle.php?id=212&layout=abstract.

[7]    Budhiraja, A. and Lee, C. (2009). Stationary distribution convergence for generalized Jackson networks in heavy traffic. Math. Oper. Res., 34 45–56. http://dx.doi.org/10.1287/moor.1080.0353. MR2542988

[8]    Chen, H. and Mandelbaum, A. (1991). Discrete flow networks: bottleneck analysis and fluid approximations. Math. Oper. Res., 16 408–446. http://dx.doi.org/10.1287/moor.16.2.408. MR1106809

[9]    Chen, L. H. Y., Goldstein, L. and Shao, Q.-M. (2011). Normal approximation by Stein’s method. Probability and its Applications (New York), Springer, Heidelberg. http://dx.doi.org/10.1007/978-3-642-15007-4. MR2732624

[10]    Chung, K. L. (2001). A Course in Probability Theory. 3rd ed. Academic Press (An Imprint of Elsevier). MR1796326

[11]    Dai, J. G. (1995). On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models. Annals of Applied Probability, 5 49–77. http://links.jstor.org/sici?sici=1050-5164(199502)5:1<49:OPHROM>2.0.CO;2-4&origin=MSN. MR1325041

[12]    Dai, J. G., Dieker, A. and Gao, X. (2014). Validity of heavy-traffic steady-state approximations in many-server queues with abandonment. Queueing Systems, 78 1–29. http://dx.doi.org/10.1007/s11134-014-9394-x. MR3238006

[13]    Dai, J. G. and Kurtz, T. G. (1994). Characterization of the stationary distribution for a semimartingale reflecting Brownian motion in a convex polyhedron. Preprint. MR1346729

[14]    Dai, J. G., Miyazawa, M. and Wu, J. (2014). A multi-dimensional SRBM: geometric views of its product form stationary distribution. Queueing Systems, 78 313–335. (arXiv version can be downloaded at the website), http://arxiv.org/abs/1312.1758. MR3269261

[15]    Down, D. and Meyn, S. (1994). Piecewise linear test functions for stability of queueing networks. Proceedings of the 33rd Conference on Decision and Control 2069–2074. http://dx.doi.org/10.1109/CDC.1994.411432.

[16]    Gamarnik, D. and Stolyar, A. L. (2012). Multiclass multiserver queueing system in the Halfin-Whitt heavy traffic regime: asymptotics of the stationary distribution. Queueing Systems, 71 25–51. http://dl.acm.org/citation.cfm?id=2339029. MR2925789

[17]    Gamarnik, D. and Zeevi, A. (2006). Validity of heavy traffic steady-state approximation in generalized Jackson networks. Ann. Appl. Probab., 16 56–90. http://dx.doi.org/10.1214/105051605000000638. MR2209336

[18]    Gurvich, I. (2014). Diffusion models and steady-state approximations for exponentially ergodic Markovian queues. The Annals of Applied Probability, 24 2527–2559. http://dx.doi.org/10.1214/13-AAP984. MR3262510

[19]    Gurvich, I. (2014). Validity of heavy-traffic steady-state approximations in multiclass queueing networks: the case of queue-ratio disciplines. Mathematics of Operations Research, 39 121–162. http://dx.doi.org/10.1287/moor.2013.0593. MR3173006

[20]    Gurvich, I., Huang, J. and Mandelbaum, A. (2014). Excursion-based universal approximations for the Erlang-A queue in steady-state. Mathematics of Operations Research, 39 325–373. http://dx.doi.org/10.1287/moor.2013.0606. MR3205550

[21]    Harrison, J. M. and Reiman, M. I. (1981). Reflected Brownian motion on an orthant. Ann. Probab., 9 302–308. http://links.jstor.org/sici?sici=0091-1798(198104)9:2<302:RBMOAO>2.0.CO;2-P&origin=MSN. MR0606992

[22]    Harrison, J. M. and Williams, R. J. (1987). Brownian models of open queueing networks with homogeneous customer populations. Stochastics, 22 77–115. http://dx.doi.org/10.1080/17442508708833469. MR0912049

[23]    Huang, J. and Gurvich, I. (2016). Beyond heavy-traffic regimes: universal bounds and controls for the single-server queue. Submitted for publication, http://papers.ssrn.com/sol3/papers.cfm?abstract_id=2784752.

[24]    Johnson, D. P. (1983). Diffusion approximations for optimal filtering of jump processes and for queueing networks. Ph.D. thesis, University of Wisconsin. http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:8316215.

[25]    Katsuda, T. (2010). State-space collapse in stationarity and its application to a multiclass single-server queue in heavy traffic. Queueing Syst., 65 237–273. http://dx.doi.org/10.1007/s11134-010-9178-x. MR2652044

[26]    Kingman, J. F. C. (1962). On queues in heavy traffic. J. Roy. Statist. Soc. Ser. B, 24 383–392. http://links.jstor.org/sici?sici=0035-9246(1962)24:2<383:OQIHT>2.0.CO;2-A&origin=MSN. MR0148146

[27]    Krantz, S. and Parks, H. (2013). The implicit function theorem: history, theory, and applications. Birkhäuser. http://link.springer.com/book/10.1007\%2F978-1-4614-5981-1. MR2977424

[28]    Miyazawa, M. (2015). Diffusion approximation for stationary analysis of queues and their networks: a review. J. Oper. Res. Soc. Japan, 58 104–148. http://dx.doi.org/10.15807/jorsj.58.104. MR3363214

[29]    Miyazawa, M. (2017). A unified approach for large queue asymptotics in a heterogeneous multiserver queue. Adv. in Appl. Probab., 49 182–220. http://dx.doi.org/10.1017/apr.2016.84. MR3631221

[30]    Reiman, M. I. (1984). Open queueing networks in heavy traffic. Mathematics of Operations Research, 9 441–458. http://dx.doi.org/10.1287/moor.9.3.441. MR0757317

[31]    Resnick, S. I. (1992). Adventures in stochastic processes. Birkhäuser, Boston. MR1181423

[32]    Ross, N. (2011). Fundamentals of Stein’s method. Probab. Surv., 8 210–293. http://dx.doi.org/10.1214/11-PS182. MR2861132

[33]    Serfozo, R. (2009). Basics of applied stochastic processes. Probability and its Applications (New York), Springer-Verlag, Berlin. MR2484222

[34]    Stadtmüller, U. and Trautner, R. (1981). Tauberian theorems for Laplace transforms in dimension D > 1. Journal für die reine und angewandte Mathematik, 323 127–138. http://eudml.org/doc/152337. MR0611447

[35]    Stein, C. (1986). Approximate computation of expectations. Lecture Notes-Monograph Series, 7. http://www.jstor.org/stable/4355512. MR0882007

[36]    Tezcan, T. (2008). Optimal control of distributed parallel server systems under the Halfin and Whitt regime. Mathematics of Operations Research, 33 51–90. http://search.proquest.com/docview/212618995?accountid=10267. MR2393541

[37]    Williams, D. (1991). Probability with Martingales. Cambridge mathematical textbooks, Cambridge University Press. MR1155402

[38]    Ye, H.-Q. and Yao, D. D. (2016). Diffusion limit of fair resource control—stationarity and interchange of limits. Mathematics of Operations Research, 41 1161–1207. http://dx.doi.org/10.1287/moor.2015.0773, http://dx.doi.org/10.1287/moor.2015.0773. MR3544792

[39]    Zhang, J. and Zwart, B. (2008). Steady state approximations of limited processor sharing queues in heavy traffic. Queueing Systems: Theory and Applications, 60 227–246. http://dx.doi.org/10.1007/s11134-008-9095-4. MR2461617

Home | Articles | Past volumes | About | Login | Notify | Contact | Search

Stochastic Systems. ISSN: 1946-5238