Metastability in loss networks with dynamic alternative routing

DOI10.1214/21-AAP1711MaRDI QIDQ2135273zbMATH OpenOpenAlexFDO

Authors Sam Thomas

Publication date 6 May 2022

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.08691

zbMATH Keywords

dynamic alternative routingloss networkmetastabilitymixing times

Mathematics Subject Classification ID

Applications of Markov renewal processes (reliability, queueing networks, etc.) (60K20) Queueing theory (aspects of probability theory) (60K25) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30) Stochastic network models in operations research (90B15) Communication networks in operations research (90B18) Queues and service in operations research (90B22)

Abstract: Consider $N$ stations interconnected with links, each of capacity $K$, forming a complete graph. Calls arrive to each link at rate $lambda$ and depart at rate $1$. If a call arrives to a link $xy$, connecting stations $x$ and $y$, which is at capacity, then a third station $z$ is chosen uniformly at random and the call is attempted to be routed via $z$: if both links $xz$ and $zy$ have spare capacity, then the call is held simultaneously on these two; otherwise the call is lost. We analyse an approximation of this model. We show rigorously that there are three phases according to the traffic intensity $alpha:=lambda/K$: for $alphain(0,alph{a}_c)cup(1,infty)$, the system has mixing time logarithmic in the number of links $$; for $alphain(alph{a}_c,1)$ the system has mixing time exponential in $n$, the number of links. Here $alph{a}_c:=frac13(5sqrt10-13)approx0.937$ is an explicit critical threshold with a simple interpretation. We also consider allowing multiple rerouting attempts. This has little effect on the overall behaviour; it does not remove the metastability phase. Finally, we add trunk reservation: in this, some number $sigma$ of circuits are reserved; a rerouting attempt is only accepted if at least $sigma+1$ circuits are available. We show that if $sigma$ is chosen sufficiently large, depending only on $alpha$, not $K$ or $n$, then the metastability phase is removed.

Recommendations

• Fluctuations for a fully connected loss network with alternate routing
• Bounds and policies for dynamic routing in loss networks
• Propagation of chaos for a fully connected loss network with alternate routing
• scientific article; zbMATH DE number 786519
• Analysis of loss networks with routing
• Limit theorems for loss networks with diverse routing
• Stability and instability of routings through a queueing network

Cites work

• A limit result respecting graph structure for a fully connected loss network with alternative routing
• Dynamic Routing in Fully Connected Networks
• Dynamics for the mean-field random-cluster model
• Exponentially slow mixing in the mean-field Swendsen-Wang dynamics
• scientific article; zbMATH DE number 786519 (Why is no real title available?)
• scientific article; zbMATH DE number 4188945 (Why is no real title available?)
• Investigation of a fully connected channel switching network with many nodes and alternative routes
• Loss networks
• Stochastic networks
• The equilibrium states of large networks of Erlang queues
• Variable length path coupling

Cited in

(1)

• Large-time behaviour and the second eigenvalue problem for finite-state mean-field interacting particle systems

This page was built for publication: Metastability in loss networks with dynamic alternative routing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2135273)