Optimal Link-Disjoint Node-“Somewhat Disjoint” Paths

Yallouz, Jose and Rottenstreich, Ori and Babarczi, Péter and Mendelson, Avi and Orda, Ariel (2016) Optimal Link-Disjoint Node-“Somewhat Disjoint” Paths. In: IEEE International Conference on Network Protocols (ICNP), 2016. nov. 8-11., Singapore. (In Press)

Text ICNP_Restricted_common_ver4.pdf - Accepted Version Restricted to Registered users only Download (327kB)

Abstract

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 study, we investigate the gap between the optimal node-disjoint and linkdisjoint solutions. Specifically, we formalize several optimization problems that aim at finding minimum-weight 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.

Actions (login required)

Edit Item