The equilibrium states of large networks of Erlang queues. (June 2020) - Martirosyan, Davit; Robert, Philippe
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.