Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-15T13:21:00.615Z Has data issue: false hasContentIssue false
  • English
  • Français

The equilibrium states of large networks of Erlang queues

Part of: Stochastic processes

Published online by Cambridge University Press:  15 July 2020

Davit Martirosyan  and
Philippe Robert Open the ORCID record for Philippe Robert [Opens in a new window]
Davit Martirosyan*
Affiliation:
INRIA
Philippe Robert*
Affiliation:
INRIA
*
*Postal address: INRIA Paris, 2 rue Simone Iff, F-75012 Paris, France. Email: [email protected]
**Postal address: INRIA Paris, 2 rue Simone Iff, F-75012 Paris, France. Email: [email protected], http://team.inria.fr/rap/robert
Get access Rights & Permissions [Opens in a new window]

Abstract

The equilibrium properties of allocation algorithms for networks with a large number of nodes with finite capacity are investigated. Every node receives a flow of requests. When a request arrives at a saturated node, i.e. a node whose capacity is fully utilized, an allocation algorithm may attempt to reallocate the request to a non-saturated node. For the algorithms considered, the reallocation comes at a price: either extra capacity is required in the system, or the processing time of a reallocated request is increased. The paper analyzes the properties of the equilibrium points of the associated asymptotic dynamical system when the number of nodes gets large. At this occasion the classical model of Gibbens, Hunt, and Kelly (1990) in this domain is revisited. The absence of known Lyapunov functions for the corresponding dynamical system significantly complicates the analysis. Several techniques are used. Analytic and scaling methods are used to identify the equilibrium points. We identify the subset of parameters for which the limiting stochastic model of these networks has multiple equilibrium points. Probabilistic approaches are used to prove the stability of some of them. A criterion of exponential stability with the spectral gap of the associated linear operator of equilibrium points is also obtained.

Keywords

Multiple equilibrium pointsscaled Markov processes

MSC classification

Primary: 60G55: Point processes
Secondary: 92D20: Protein sequences, DNA sequences
Type
Original Article
Information
Advances in Applied Probability , Volume 52 , Issue 2 , June 2020 , pp. 617 - 654
Copyright
© Applied Probability Trust 2020

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aldous, D. and Fill, J. A. (2002). Reversible Markov chains and random walks on graphs. Unfinished monograph, recompiled 2014. Available at http://www.stat.berkeley.edu/~aldous/RWG/book.html.Google Scholar
Antunes, N., Fricker, C., Robert, P. and Tibi, D. (2008). Stochastic networks with multiple stable points. Ann. Prob. 36, 255–278.CrossRefGoogle Scholar
Billingsley, P. (1999). Convergence of Probability Measures, 2nd edn. John Wiley, New York.CrossRefGoogle Scholar
Bovier, A. and den Hollander, F. (2015). Metastability: A Potential-Theoretic Approach. Springer, Cham.CrossRefGoogle Scholar
Budhiraja, A., Dupuis, P., Fischer, M. and Ramanan, K. (2015). Local stability of Kolmogorov forward equations for finite state nonlinear Markov processes. Electron. J. Prob. 20, 30 pp.CrossRefGoogle Scholar
Caputo, P., Dai Pra, P. and Posta, G. (2009). Convex entropy decay via the Bochner–Bakry–Émery approach. Ann. Inst. H. Poincaré Prob. Statist. 45, 734–753.CrossRefGoogle Scholar
Carrillo, J. A., McCann, R. J. and Villani, C. (2003). Kinetic equilibration rates for granular media and related equations: entropy dissipation and mass transportation estimates. Rev. Mat. Iberoam. 19, 971–1018.CrossRefGoogle Scholar
Chen, M.-F. (2010). Speed of stability for birth-death processes. Front. Math. China 5, 379–515.CrossRefGoogle Scholar
Dai Pra, P. and Posta, G. (2013). Entropy decay for interacting systems via the Bochner-Bakry-Émery approach. Electron. J. Prob. 18, 21 pp.CrossRefGoogle Scholar
Dawson, D. A., Tang, J. and Zhao, Y. Q. (2005). Balancing queues by mean field interaction. Queueing Systems 49, 335–361.CrossRefGoogle Scholar
Den Hollander, F. (2004). Metastability under stochastic dynamics. Stoch. Process. Appl. 114, 1–26.CrossRefGoogle Scholar
Erbar, M. and Maas, J. (2012). Ricci curvature of finite Markov chains via convexity of the entropy. Arch. Ration. Mech. An. 206, 997–1038.CrossRefGoogle Scholar
Erbar, M., Maas, J. and Tetali, P. (2015). Discrete Ricci curvature bounds for Bernoulli-Laplace and random transposition models. Ann. Fac. Sci. Toulouse Math. Ser. 6, 24, 781–800.CrossRefGoogle Scholar
Ethier, S. N. and Kurtz, T. G. (1986). Markov Processes: Characterization and Convergence. John Wiley, New York.CrossRefGoogle Scholar
Frank, T. D. (2005). Nonlinear Fokker-Planck Equations: Fundamentals and Applications. Springer, Berlin, Heidelberg.Google Scholar
Gibbens, R. J., Hunt, P. J. and Kelly, F. P. (1990). Bistability in communication networks. In Disorder in Physical Systems, Oxford University Press, New York, pp. 113–127.Google Scholar
Graham, C. and Méléard, S. (1993). Propagation of chaos for a fully connected loss network with alternate routing. Stoch. Process. Appl. 44, 159–180.CrossRefGoogle Scholar
Hunt, P. and Kurtz, T. (1994). Large loss networks. Stoch. Process. Appl. 53, 363–378.CrossRefGoogle Scholar
Jacobsen, M. (2006). Point Process Theory and Applications. Birkhäuser, Boston, MA.Google Scholar
Kelly, F. P. (1991). Loss networks. Ann. Appl. Prob. 1, 319–378.CrossRefGoogle Scholar
Kingman, J. F. C. (1993). Poisson processes. Oxford University Press, New York.Google Scholar
Last, G. and Brandt, A. (1995). Marked Point Processes on the Real Line. Springer, New York.Google Scholar
Liu, W. and Ma, Y. (2009). Spectral gap and convex concentration inequalities for birth-death processes. Ann. Inst. H. Poincaré Prob. Statist. 45, 58–69.CrossRefGoogle Scholar
Maas, J. (2017). Entropic Ricci curvature for discrete spaces. In Modern Approaches to Discrete Curvature, eds. Najman, L. and Romon, P., Springer, Cham, pp. 159–174.CrossRefGoogle Scholar
Malyshev, V. and Robert, P. (1994). Phase transition in a loss load sharing model. Ann. Appl. Prob. 4, 1161–1176.CrossRefGoogle Scholar
Marbukh, V. (1993). Loss circuit switched communication network: performance analysis and dynamic routing. Queueing Systems 13, 111–141.CrossRefGoogle Scholar
Muzychka, S. (2015). A class of nonlinear processes admitting complete study. Mosc. U. Math. Bull. 70, 141–143.CrossRefGoogle Scholar
Olivieri, E. and Vares, M. E. (2005). Large Deviations and Metastability (Encyclopedia Math. Appl. 100). Cambridge University Press.Google Scholar
Robert, P. (2003). Stochastic Networks and Queues. Springer, New York.CrossRefGoogle Scholar
Rybko, A. and Shlosman, S. (2005). Poisson hypothesis for information networks. I. Mosc. Math. J. 5, 679–704, 744.Google Scholar
Sznitman, A. (1991). Topics in propagation of chaos. In École d’Été de Probabilités de Saint-Flour XIX – 1989 (Lecture Notes Math. 1464), Springer, Berlin, pp. 167–243.Google Scholar
Thai, M.-N. (2015). Birth and death process in mean field type interaction. Preprint. Available at http://arxiv.org/abs/1510.03238 .Google Scholar
Tibi, D. (2010). Metastability in communication networks. Preprint. Available at http://arxiv.org/abs/1002.0796 .Google Scholar
Van Doorn, E., Zeifman, A. and Panfilova, T. (2010). Bounds and asymptotics for the rate of convergence of birth-death processes. Theory Prob. Appl. 54, 97–113.CrossRefGoogle Scholar
Verhulst, F. (1990). Nonlinear Differential Equations and Dynamical Systems. Springer, Berlin.CrossRefGoogle Scholar
Zelik, S. (2004). Asymptotic regularity of solutions of a nonautonomous damped wave equation with a critical growth exponent. Commun. Pure Appl. Anal. 3, 921.CrossRefGoogle Scholar