Robust Distributed Routing in Dynamical Networks–Part II: Strong Resilience, Equilibrium Selection and Cascaded Failures
Robust Distributed Routing in Dynamical Networks–Part II: Strong Resilience, Equilibrium Selection and Cascaded Failures
复制标题
动态网络中的鲁棒分布式路由——第二部分：强弹性、均衡选择和级联故障
DOI：
10.1109/tac.2012.2209975
复制
发表时间：
2013
影响因子：
6.8
通讯作者：
Emilio Frazzoli
中科院分区：
文献类型：
--
作者：
G. Como;K. Savla;D. Acemoglu;M. Dahleh;Emilio Frazzoli
针对分布式路由策略，分析了动态网络的强弹性特性。后者的特征在于这样的性质，即在非目的地节点处的流出在其传出链路之间被分割的方式被允许仅取决于关于传出链路上的当前粒子密度的本地信息。网络的强弹性被定义为沿链路方向的流量减少使得流入目的节点的渐近总流量严格小于源点的总流出的下确界和。证明了一类响应局部信息的分布式路由策略，在这样的局部信息约束下，对于具有单一起点-目的地对的非循环动态网络，能够产生最大可能的强弹性。证明了最大可实现的强恢复能力等于网络的最小节点剩余容量。后者取决于未受干扰的网络的极限流量，并且被定义为在所有非目的地节点中，在从该节点传出的所有链路上，未受扰动的网络的最大流量和极限流量之间的差值之和的最小值。我们提出了一个简单的凸优化问题来求解无扰动网络的均衡流，在满足强弹性保证的条件下最小化平均延迟，并讨论了在交通网络中使用通行费来诱导这种均衡流的方法。最后，我们提供了说明性的仿真来讨论级联故障与网络的弹性特性之间的关系。
Strong resilience properties of dynamical networks are analyzed for distributed routing policies. The latter are characterized by the property that the way the outflow at a non-destination node gets split among its outgoing links is allowed to depend only on local information about the current particle densities on the outgoing links. The strong resilience of the network is defined as the infimum sum of link-wise flow capacity reductions making the asymptotic total inflow to the destination node strictly less than the total outflow at the origin. A class of distributed routing policies that are responsive to local information is shown to yield the maximum possible strong resilience under such local information constraints for an acyclic dynamical network with a single origin-destination pair. The maximal achievable strong resilience is shown to be equal to the minimum node residual capacity of the network. The latter depends on the limit flow of the unperturbed network and is defined as the minimum, among all the non-destination nodes, of the sum, over all the links outgoing from the node, of the differences between the maximum flow capacity and the limit flow of the unperturbed network. We propose a simple convex optimization problem to solve for equilibrium flows of the unperturbed network that minimize average delay subject to strong resilience guarantees, and discuss the use of tolls to induce such an equilibrium flow in traffic networks. Finally, we present illustrative simulations to discuss the connection between cascaded failures and the resilience properties of the network.