Stochastic networks with multiple stable points. (English) Zbl 1130.60086

Summary: This paper analyzes stochastic networks consisting of a set of finite capacity sites where different classes of individuals move according to some routing policy. The associated Markov jump processes are analyzed under a thermodynamic limit regime, that is, when the networks have some symmetry properties and when the number of nodes goes to infinity. An intriguing stability property is proved: under some conditions on the parameters, it is shown that, in the limit, several stable equilibrium points coexist for the empirical distribution. The key ingredient of the proof of this property is a dimension reduction achieved by the introduction of two energy functions and a convenient mapping of their local minima and saddle points. Networks with a unique equilibrium point are also presented.


60K25 Queueing theory (aspects of probability theory)
60K35 Interacting random processes; statistical mechanics type models; percolation theory
Full Text: DOI arXiv Euclid


[1] Antunes, N., Fricker, C., Robert, P. and Tibi, D. (2006). Analysis of loss networks with routing. Ann. Appl. Probab. 16 2007–2026. · Zbl 1121.60100
[2] Borst, S. C., Hegde, N. and Proutière, A. (2006). Capacity of wireless network with intra- and inter-cell mobility. IEEE Infocom .
[3] Bovier, A. (2003). Markov processes and metastability. Lecture Notes TUB .
[4] Bovier, A. (2004). Metastability and ageing in stochastic dynamics. In Dynamics and Randomness II (Santiago de Chile) (A. Maas, S. Martinez and J. San Martin, eds.) 17–79. Kluwer, Dordrecht. · Zbl 1085.82011
[5] Bovier, A., Eckhoff, M., Gayrard, V. and Klein, M. (2004). Metastability in reversible diffusion processes I. Sharp asymptotics for capacities and exit times. J. Eur. Math. Soc. 6 399–424. · Zbl 1076.82045
[6] Catoni, O. and Cerf, R. (1995/97). The exit path of a Markov chain with rare transitions. European Series in Applied and Industrial Mathematics. Probab. Statist. 1 95–144 (electronic). · Zbl 0869.60063
[7] Darling, R. W. R. and Norris, J. R. (2005). Structure of large random hypergraphs. Ann. Appl. Probab. 15 125–152. · Zbl 1062.05132
[8] den Hollander, F. (2004). Metastability under stochastic dynamics. Stochastic Process. Appl. 114 1–26. · Zbl 1075.60127
[9] Freidlin, M. I. and Wentzell, A. D. (1998). Random Perturbations of Dynamical Systems , 2nd ed. Springer, New York. Translated from the 1979 Russian original by Joseph Szücs. · Zbl 0522.60055
[10] Gibbens, R. J., Hunt, P. J. and Kelly, F. P. (1990). Bistability in communication networks. In Disorder in Physical Systems (G. Grimmett and D. Welsh, eds.) 113–127. Oxford Univ. Press, New York. · Zbl 0721.60103
[11] Gupta, P. and Kumar, P. R. (2000). The capacity of wireless networks. IEEE Trans. Inform. Theory 46 388–404. · Zbl 0991.90511
[12] Karpelevich, F. I., Pechersky, E. A. and Suhov, Yu. M. (1996). Dobrushin’s approach to queueing network theory. J. Appl. Math. Stochastic Anal. 9 373–397. · Zbl 0876.60074
[13] Kelly, F. P. (1979). Reversibility and Stochastic Networks . Wiley, Chichester. · Zbl 0422.60001
[14] Kelly, F. P. (1986). Blocking probabilities in large circuit-switched networks. Adv. in Appl. Probab. 18 473–505. JSTOR: · Zbl 0597.60092
[15] Kelly, F. P. (1991). Loss networks. Ann. Appl. Probab. 1 319–378. · Zbl 0743.60099
[16] Kermarrec, A.-M., Massoulié, L. and Ganesh, A. J. (2003). Probabilistic reliable dissemination in large-scale systems. IEEE Trans. Parallel and Distributed Systems 14 248–258.
[17] Liggett, T. M. (1985). Interacting Particle Systems . Springer, New York. · Zbl 0559.60078
[18] Marbukh, V. (1993). Loss circuit switched communication network: Performance analysis and dynamic routing. Queueing Syst. 13 111–141. · Zbl 0780.90051
[19] Olivieri, E. and Vares, E. M. (2005). Large Deviations and Metastability . Cambridge Univ. Press. · Zbl 1075.60002
[20] Ramanan, K., Sengupta, A., Ziedins, I. and Mitra, P. (2002). Markov random field models of multicasting in tree networks. Adv. in Appl. Probab. 34 58–84. · Zbl 1004.60051
[21] Rogers, L. C. G. and Williams, D. (1987). Diffusions , Markov Processes , and Martingales 2 : Itô Calculus . Wiley, New York. · Zbl 0627.60001
[22] Spitzer, F. (1975). Markov random fields on an infinite tree. Ann. Probab. 3 387–398. · Zbl 0313.60072
[23] Sznitman, A. S. (1989). Topics in propagation of chaos. École d ’ Été de Probabilités de Saint Flour XIX–1989 . Lecture Notes in Math. 1464 165–251. Springer, Berlin. · Zbl 0732.60114
[24] Zachary, S. (1983). Countable state space Markov random fields and Markov chains on trees. Ann. Probab. 11 894–903. · Zbl 0524.60056
[25] Zachary, S. and Ziedins, I. (1999). Loss networks and Markov random fields. J. Appl. Probab. 36 403–414. · Zbl 0954.60086
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.