We consider a model of two interdependent networks, where every node in one network depends on one or more supply nodes in the other network and a node fails if it loses all of its supply nodes. We develop algorithms to compute the failure probability of a path, and obtain the most reliable path between a pair of nodes in a network, under the condition that each supply node fails independently with a given probability. Our work generalizes the classical shared risk group model, by considering multiple risks associated with a node and letting a node fail if all the risks occur. Moreover, we study the diverse routing problem by considering two paths between a pair of nodes. We define two paths to be $d$-failure resilient if at least one path survives after removing $d$ or fewer supply nodes, which generalizes the concept of disjoint paths in a single network, and risk-disjoint paths in a classical shared risk group model. We compute the probability that both paths fail, and develop algorithms to compute the most reliable pair of paths.
翻译:我们考虑了两个相互依存网络的模式,一个网络的每个节点依赖于另一个网络的一个或多个供应节点,如果一个节点失去所有供应节点,则一个节点失效。我们开发了算法,以计算路径的失败概率,并获得网络中两个节点之间的最可靠路径,条件是每个节点以给定的概率独立失败。我们的工作概括了典型的共享风险组模式,考虑了与节点相关的多重风险,并在所有风险发生时让节点失效。此外,我们通过考虑两个节点之间的两条路径来研究不同的路径问题。我们定义了两条路径,如果在删除了美元或更少的供应节点后至少一条路径能够存活下去,那么两条路径将具有以美元为单位的无故障能力,这把单一网络中断开的路径的概念概括化为单一网络,在传统共享风险组模式中的风险-不连接路径。我们计算了两条路径失败的概率,并发展了最可靠的路径的算法。