论文标题
具有动态替代路由的损失网络的亚竞争力
Metastability in Loss Networks with Dynamic Alternative Routing
论文作者
论文摘要
考虑与链接相互连接的$ n $站点，每个容量$ k $，形成完整的图形。呼叫以$λ$的价格到达每个链接，并以$ 1 $的价格出发。如果一个电话到达链接$ x y $，将电台$ x $和$ y $连接起来，则可以随机选择第三个站$ z $，并且试图通过$ z $进行呼叫：如果两个链接$ x z $＆z y $都有备用容量，那么这两个链接都会同时持有这些电话；否则电话将丢失。 我们分析了该模型的近似值。我们严格地表明，根据流量强度$α：=λ/k $：对于$α\ in（0，α_c）\ cup（1，\ infty）$，该系统在链接$ n：= = \ binom n2 $;对于$α\ in（α_c，1）$，该系统的时间指数为$ n $，链接数量。这里$α_c：= \ tfrac13（5 \ sqrt {10} -13）\大约0.937 $是一个明确的关键阈值，具有简单的解释。我们还考虑允许多次重新安排尝试。这对整体行为几乎没有影响。它不会删除亚稳定性阶段。 最后，我们添加了躯干保留：在此中，保留了一些数字$σ$的电路；仅当至少$σ+1 $电路可用时，才能接受重新安排尝试。我们表明，如果仅根据$α$而不是$ k $或$ n $选择$σ$，则删除了稳定阶段。
Consider $N$ stations interconnected with links, each of capacity $K$, forming a complete graph. Calls arrive to each link at rate $λ$ and depart at rate $1$. If a call arrives to a link $x y$, 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 $x z$ and $z y$ 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 $α:= λ/K$: for $α\in (0,α_c) \cup (1,\infty)$, the system has mixing time logarithmic in the number of links $n := \binom N2$; for $α\in (α_c,1)$ the system has mixing time exponential in $n$, the number of links. Here $α_c := \tfrac13 (5 \sqrt{10} - 13) \approx 0.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 $σ$ of circuits are reserved; a rerouting attempt is only accepted if at least $σ+1$ circuits are available. We show that if $σ$ is chosen sufficiently large, depending only on $α$, not $K$ or $n$, then the metastability phase is removed.
