Home | Current | Past volumes | About | Login | Notify | Contact | Search
 Probability Surveys > Vol. 5 (2008) open journal systems 

Stability of queueing networks

Maury D. Bramson, University of Minnesota

Queueing networks constitute a large family of stochastic models, involving jobs that enter a network, compete for service, and eventually leave the network upon completion of service. Since the early 1990s, substantial attention has been devoted to the question of when such networks are stable. This monograph presents a summary of such work. Emphasis is placed on the use of fluid models in showing stability, and on examples of queueing networks that are unstable even when the arrival rate is less than the service rate. The material of this volume is based on a series of nine lectures given at the Saint-Flour Probability Summer School 2006, and is also being published in the Springer Lecture Notes series.

Creative Common LOGO

Full Text: PDF

Bramson, Maury D., Stability of queueing networks, Probability Surveys, 5, (2008), 169-345 (electronic). DOI: 10.1214/08-PS137.


[AnAFKLL96]    Andrews, M., Awerbuch, B., Fernandez, A., Kleinberg, J., Leighton, T., and Liu, Z. (1996). Universal stability results for greedy contention-resolution protocols. In Symposium on Computer Science, 1996. MR1450636

[As03]    Asmussen, S. (2003). Applied Probability and Queues, second edition. Springer, New York. MR1978607

[AtN78]    Athreya, K.B. and Ney, P. (1978). A new approach to the limit theory of recurrent Markov chains. Trans. Amer. Math. Soc. 245, 493–501. MR0511425

[AzKR67]    Azema, J., Kaplan-Duflo, M. and Revuz, D. (1967). Mesure invariante sur les classes récurrentes des processus de Markov. Z. Wahrscheinlichkeitstheorie verw. Geb. 8, 157–181. MR0222955

[BaB99]    Baccelli, F. and Bonald, T. (1999). Window flow control in FIFO networks with cross traffic. Queueing Systems 32, 195–231. MR1720554

[BaF94]    Baccelli, F. and Foss, S.G. (1994). Ergodicity of Jackson-type queueing networks I. Queueing Systems 17, 5–72. MR1295406

[Ba76]    Barbour, A.D. (1976). Networks of queues and the method of stages. Adv. Appl. Prob. 8, 584–591. MR0440729

[BaCMP75]    Baskett, F., Chandy, K.M., Muntz, R.R., and Palacios, F.G. (1975). Open, closed and mixed networks of queues with different classes of customers. J. Assoc. Comput. Mach. 22, 248–260. MR0365749

[BoKRSW96]    Borodin, A., Kleinberg, J., Raghavan, P., Sudan, M., and Williamson, D.P. (1996). Adversarial queueing theory. In Symposium on Computer Science, 1996. MR1427534

[Bo86]    Borovkov, A.A. (1986). Limit theorems for queueing networks. Theory of Probability and its Applications 31, 413–427. MR0866868

[BoZ92]    Botvich, D.D. and Zamyatin, A.A. (1992). Ergodicity of conservative communication networks. Rapport de Recherche 1772, INRIA.

[Br94a]    Bramson, M. (1994). Instability of FIFO queueing networks. Ann. Appl. Probab. 4, 414–431. (Correction 4 (1994), 952.) MR1272733

[Br94b]    Bramson, M. (1994). Instability of FIFO queueing networks with quick service times. Ann. Appl. Probab. 4, 693–718. MR1284981

[Br95]    Bramson, M. (1995) Two badly behaved queueing networks. Stochastic Networks, 105–116. IMA Math. Appl. 71. Springer, New York. MR1381007

[Br96a]    Bramson, M. (1996). Convergence to equilibria for fluid models of FIFO queueing networks. Queueing Systems 22, 5–45. MR1393404

[Br96b]    Bramson, M. (1996). Convergence to equilibria for fluid models of head-of-the-line proportional processor sharing queueing networks. Queueing Systems 23, 1–26. MR1433762

[Br98a]    Bramson, M. (1998). Stability of two families of queueing networks and a discussion of fluid limits. Queueing Systems 28, 7–31. MR1628469

[Br98b]    Bramson, M. (1998). State space collapse with application to heavy traffic limits for multiclass queueing networks. Queueing Systems 30, 89–148. MR1663763

[Br99]    Bramson, M. (1999). A stable queueing network with unstable fluid model. Ann. Appl. Probab. 9, 818–853. MR1722284

[Br01]    Bramson, M. (2001). Earliest-due-date, first-served queueing networks. Queueing Systems 39, 79–102. MR1865459

[BrD01]    Bramson, M. and Dai, J.G. (2001). Heavy traffic limits for some queueing networks. Ann. Appl. Probab. 11, 49–90. MR1825460

[Bu56]    Burke, P.J. (1956). The output of a queueing system. Operat. Res. 4, 699–704. MR0083416

[ChTK94]    Chang, C.S., Thomas, J.A., and Kiang, S.H. (1994). On the stability of open networks: a unified approach by stochastic dominance. Queueing Systems 15, 239–260. MR1266795

[Ch95]    Chen, H. (1995). Fluid approximations and stability of multiclass queueing networks: work-conserving disciplines. Ann. Appl. Probab. 5, 637–655. MR1359823

[ChM91]    Chen, H. and Mandelbaum, A. (1991). Discrete flow networks: Bottleneck analysis and fluid approximations. Math. Oper. Res. 16, 408–446. MR1106809

[ChY01]    Chen, H. and Yao, D.D. (2001). Fundamentals of Queueing Networks. Springer, New York. MR1835969

[Da95]    Dai, J.G. (1995). On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models. Ann. Appl. Probab. 5, 49–77. MR1325041

[Da96]    Dai, J.G. (1996). A fluid limit model criterion for instability of multiclass queueing networks. Ann. Appl. Probab. 6, 751–757. MR1410113

[DaHV99]    Dai, J.G., Hasenbein, J.J., and Vande Vate, J.H. (1999). Stability of a three-station fluid network. Queueing Systems 33, 293–325. MR1742573

[DaHV04]    Dai, J.G., Hasenbein, J.J., and Vande Vate, J.H. (2004). Stability and instability of a two-station queueing network. Ann. Appl. Probab. 14, 326–377. MR2023024

[DaM95]    Dai, J.G. and Meyn, S.P. (1995). Stability and convergence of moments for multiclass queueing networks via fluid limit models. IEEE Trans. Automat. Control 40, 1889–1904. MR1358006

[DaV96]    Dai, J.G. and Vande Vate, J.H. (1996). Virtual stations and the capacity of two-station queueing networks. Preprint. MR1410113

[DaV00]    Dai, J.G. and Vande Vate J.H. (2000). The stability of two-station multitype fluid networks. Operations Research 48, 721–744. MR1792776

[DaWa93]    Dai, J.G. and Wang, Y. (1993). Nonexistence of Brownian models of certain multiclass queueing networks. Queueing Systems 13, 41–46. MR1218843

[DaWe96]    Dai, J.G. and Weiss, G. (1996). Stability and instability of fluid models for re-entrant lines. Math. of Oper. Res. 21, 115–134. MR1385870

[Da84]    Davis, M.H.A. (1984). Piecewise deterministic Markov processes: a general class of nondiffusion stochastic models. J. Roy. Statist. Soc. Ser. B 46, 353–388. MR0790622

[Da93]    Davis, M.H.A. (1993). Markov Models and Optimization. Chapman & Hall, London. MR1283589

[Do53]    Doob, J.L. (1953). Stochastic Processes. Wiley, New York. MR0058896

[DoM94]    Down, D. and Meyn, S.P. (1994). Piecewise linear test functions for stability of queueing networks. Proc. 33rd Conference on Decision and Control, 2069–2074.

[Du96]    Dumas, V. (1996). Approches fluides pour la stabilité et l’instabilité de réseaux de files d’attente stochastiques à plusieurs classes de clients. Doctoral thesis, Ecole Polytechnique.

[Du97]    Dumas, V. (1997). A multiclass network with non-linear, non-convex, non-monotonic stability conditions. Queueing Systems 25, 1–43. MR1458584

[Dur96]    Durrett, R. (1996). Probability: Theory and Examples, second edition. Duxbury Press, Belmont. MR1609153

[Fi89]    Filonov, Y.P. (1989). A criterion for the ergodicity of discrete homogeneous Markov chains. (Russian). Ukrain. Mat. Zh. 41, 1421–1422; translation in Ukrainian Math. J. 41, 1223–1225. MR1034693

[Fo91]    Foss, S.G. (1991). Ergodicity of queueing networks. Sib. Math. J. 32, 183–202. MR1142079

[FoK04]    Foss, S.G. and Konstantopoulos, T. (2004). An overview of some stochastic stability methods. J. Oper. Res. Soc. Japan 47, 275–303. MR2174067

[FoK99]    Foss, S.G. and Kovalevskii, A. (1999). A stability criterion via fluid limits and its application to a polling system. Queueing Systems 32, 131–168. MR1720552

[Fo53]    Foster, F.G. (1953). On the stochastic matrices associated with certain queueing processes. Ann. Math. Stat. 24, 355–360. MR0056232

[GaH05]    Gamarnik, D. and Hasenbein, J.J. (2005). Instability in stochastic and fluid queueing networks. Ann. Appl. Probab. 15, 1652–1690. MR2152240

[Ge79]    Getoor, R. (1979). Transience and recurrence of Markov processes. In Séminaire de Probabilités XIV (J. Azéma, M. Yor editors), 397–409. Springer, Berlin. MR0580144

[Ha56]    Harris, T.E. (1956). The existence of stationary measures for certain Markov processes. Proc. 3rd Berkeley Symp., Vol. II, 113–124. MR0084889

[Ha97]    Hasenbein, J.J. (1997). Necessary conditions for global stability of multiclass queueing networks. Oper. Res. Lett. 21, 87–94. MR1482493

[Hu94]    Humes, C. (1994). A regular stabilization technique: Kumar-Seidman revisited. IEEE Trans. Automat. Control 39, 191–196. MR1258702

[Ja54]    Jackson, R.R.P. (1954). Queueing systems with phase-type service. Operat. Res. Quart. 5, 109–120.

[Ja63]    Jackson, R.R.P. (1963). Jobshop-like queueing systems. Mgmt. Sci. 10, 131–142.

[KaM94]    Kaspi, H. and Mandelbaum, A. (1994). On Harris recurrence in continuous time. Math. Oper. Res. 19, 211–222. MR1290020

[Ke75]    Kelly, F.P. (1975). Networks of queues with customers of different types. J. Appl. Probab. 12, 542–554. MR0388571

[Ke76]    Kelly, F.P. (1976). Networks of queues. Adv. Appl. Prob. 8, 416–432. MR0415800

[Ke79]    Kelly, F.P. (1979). Reversibility and Stochastic Networks. Wiley, New York. MR0554920

[Kn84]    Knight, F.B. (1984). On the ray topology. Séminaire de Probabilités (Strasbourg) 18, 56–69. Springer, Berlin. MR0770948

[Ku93]    Kumar, P.R. (1993). Re-entrant lines. Queueing Systems 13, 87–110. MR1218845

[KuS90]    Kumar, P.R. and Seidman, T.I. (1990). Dynamic instabilities and stabilization methods in distributed real-time scheduling of manufacturing systems. IEEE Trans. Automat. Control 35, 289–298. MR1044023

[LuK91]    Lu, S.H. and Kumar, P.R. (1991). Distributed scheduling based on due dates and buffer priorities. IEEE Trans. Automat. Control 36, 1406–1416.

[MaM81]    Malyshev, V.A. and Menshikov, M.V. (1981). Ergodicity, continuity, and analyticity of countable Markov chains. Transactions of the Moscow Mathematical Society 1, 1–47.

[Me95]    Meyn, S.P. (1995). Transience of multiclass queueing networks via fluid limit models. Ann. Appl. Probab. 5, 946–957. MR1384361

[MeD94]    Meyn, S.P. and Down, D. (1994). Stability of generalized Jackson networks. Ann. Appl. Probab. 4, 124–148. MR1258176

[MeT93a]    Meyn, S.P. and Tweedie, R.L. (1993). Generalized resolvents and Harris recurrence of Markov processes. Contemporary Mathematics 149, 227–250. MR1229967

[MeT93b]    Meyn, S.P. and Tweedie, R.L. (1993). Stability of Markov processes II: continuous-time processes and sampled chains. Adv. Appl. Prob. 25, 487–517. MR1234294

[MeT93c]    Meyn, S.P. and Tweedie, R.L. (1993). Stability of Markov processes III: Foster-Lyapunov criteria for continuous-time processes. Adv. Appl. Prob. 25, 518–548. MR1234295

[MeT93d]    Meyn, S.P. and Tweedie, R.L. (1993). Markov Chains and Stochastic Stability. Springer, London. MR1287609

[MeT94]    Meyn, S.P. and Tweedie, R.L. (1994). State-dependent criteria for convergence of Markov chains. Ann. Appl. Probab. 4, 149–168. MR1258177

[Mu72]    Muntz, R.R. (1972). Poisson Departure Processes and Queueing Networks, IBM Research Report RC 4145. A shortened version appeared in Proceedings of the Seventh Annual Conference on Information Science and Systems, Princeton, 1973, 435–440.

[Ne82]    Newell, G.F. (1982). Applications of Queueing Theory. Chapman and Hall. MR0737381

[Nu78]    Nummelin, E. (1978). A splitting technique for Harris recurrent Markov chains. Z. Wahrscheinlichkeitsth. verw. Geb. 43, 309–318. MR0501353

[Nu84]    Nummelin, E. (1984). General Irreducible Markov Chains and Non-Negative Operators. Cambridge University Press, Cambridge. MR0776608

[Or71]    Orey, S. (1971). Lecture Notes on Limit Theorems for Markov Chain Transition Probabilities. Van Nostrand Reinhold, London. MR0324774

[PeK89]    Perkins, J.R. and Kumar, P.R. (1989). Stable distributed real-time scheduling of flexible manufacturing/assembly/disassembly systems. IEEE Trans. Automat. Control 34, 139–148. MR0975573

[PuR00]    Puhalskii, A. and Rybko, A. (2000). Nonergodicity of a queueing network under nonstability of its fluid model. Probl. Inf. Transm. 36, 23–41. MR1746007

[Re57]    Reich, E. (1957). Waiting times when queues are in tandem. Ann. Math. Statist. 28, 768–773. MR0093060

[Re92]    Resnick, S.I. (1992). Adventures in Stochastic Processes. Birkhäuser, Boston. MR1181423

[RyS92]    Rybko, A.N. and Stolyar, A.L. (1992). Ergodity of stochastic processes that describe functioning of open queueing networks. Problems Inform. Transmission 28, 3–26 (in Russian). MR1189331

[Se94]    Seidman, T.I. (1994). “First come, first served” can be unstable! IEEE Trans. Automat. Control 39, 2166–2170. MR1295752

[Se99]    Serfozo, R. (1999). Introduction to Stochastic Networks. Springer, New York. MR1704237

[Sh88]    Sharpe, M. (1988). General Theory of Markov Processes. Academic Press, San Diego. MR0958914

[Si90]    Sigman, K. (1990). The stability of open queueing networks. Stoch. Proc. Applns. 35, 11–25. MR1062580

[St95]    Stolyar, A.L. (1995). On the stability of multiclass queueing networks: a relaxed sufficient condition via limiting fluid processes. Markov Process. Related Fields 1, 491–512. MR1403094

[StR99]    Stolyar, A.L. and Ramakrishnan, K.K. (1999). The stability of a flow merge point with non-interleaving cut-through scheduling disciplines. In Proceedings of INFOCOM 99.

[Wa82]    Walrand, J. (1982). Discussant’s report on “Networks of quasi-reversible nodes”, by F.P. Kelly. Applied Probability - Computer Science: The Interface, Volume 1, 27–29. Birkhäuser, Boston. MR0718495

[Wa83]    Walrand, J. (1983). A probabilistic look at networks of quasi-reversible queues. IEEE Trans. Info. Theory, IT-29, 825–836. MR0733189

[Wa88]    Walrand, J. (1988). An Introduction to Queueing Networks. Prentice-Hall, Englewood Cliffs.

[Wi98]    Williams, R.J. (1998). Diffusion approximations for open multiclass queueing networks: sufficient conditions involving state space collapse. Queueing Systems 30, 27–88. MR1663759

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

Probability Surveys. ISSN: 1549-5787