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)

[img] Text
ICNP_Restricted_common_ver4.pdf - Accepted Version
Restricted to Registered users only

Download (327kB)


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.

Item Type: Conference or Workshop Item (Paper)
Subjects: Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány
Depositing User: Dr Péter Babarczi
Date Deposited: 24 Aug 2016 12:04
Last Modified: 24 Aug 2016 12:04

Actions (login required)

Edit Item Edit Item