Minimum-Weight Link-Disjoint Node-"Somewhat Disjoint" Paths

作者：Yallouz Jose^*; Rottenstreich Ori; Babarczi Peter; Mendelson Avi; Orda Ariel

来源：IEEE/ACM Transactions on Networking, 2018, 26(3): 1110-1122.

DOI：10.1109/TNET.2018.2823912

• Link-disjoint paths
• survivable routing
• selective common nodes
• minimum-weight paths
• Bellman-Ford

Network survivability has been recognized as an issue of major importance in terms of security, stability and prosperity. A crucial research problem in this context is the identification of suitable pairs of disjoint paths. Here, "disjointness" can be considered in terms of either nodes or links. Accordingly, several studies have focused on finding pairs of either link or node disjoint paths with a minimum sum of link weights. In this paper, we investigate the gap between the optimal node-disjoint and link-disjoint solutions. Specifically, we formalize several optimization problems that aim at finding minimumweight link-disjoint paths while restricting the number of its common nodes. We establish that some of these variants are computationally intractable, while for other variants we establish polynomial-time algorithmic solutions. Finally, through extensive simulations, we show that, by allowing link-disjoint paths share a few common nodes, a major improvement is obtained in terms of the quality (i.e., total weight) of the solution.

• 出版日期2018-6