Abstract

We consider the problem of survivability in multilayer networks. In single-layer networks, a pair of disjoint paths can be used to provide protection for a source–destination pair. However, this approach cannot be directly applied to layered networks where risk-disjoint paths may not always exist. In this paper, we take a new approach, which is based on finding a set of paths that may not be disjoint but together will survive any single risk. We start with two-layered communication networks, where the risks are fiber failures. We prove that in general, finding the minimum survivable path set (MSPS) is NP-hard, whereas if we restrict the length of paths the problem can be solved in polynomial time. We formulate the problem as an integer linear program (ILP), and use this formulation to develop heuristics and approximation algorithms. Moreover, we study the minimum cost survivable path set problem, where the cost is the number of fibers used, and thus, nonadditive. Finally, we generalize the survivability problem to the networks with more than two layers. By applying our algorithms for survivable path set, we assess the survivability of communication networks that operate relying on power from a power grid.

© 2014 IEEE

Cross-Layer Network Survivability Under Multiple Cross-Layer Metrics

Zhili Zhou, Tachun Lin, Krishnaiyan Thulasiraman, Guoliang Xue, and Sartaj Sahni
J. Opt. Commun. Netw. 7(6) 540-553 (2015)

Best Effort SRLG Failure Protection for Optical WDM Networks

Xu Shao, Yuebin Bai, Xiaofei Cheng, Yong-Kee Yeo, Luying Zhou, and Lek Heng Ngoh
J. Opt. Commun. Netw. 3(9) 739-749 (2011)

k-Connected Network Partitioning Under Shared Risk Link Groups

M. Masud Hasan, Farid Farahmand, and Jason P. Jue
J. Opt. Commun. Netw. 7(8) 695-706 (2015)

Domain-Disjoint Routing Based on Topology Aggregation for Survivable Multidomain Optical Networks

Chengyi Gao, Mohammad M. Hasan, and Jason P. Jue
J. Opt. Commun. Netw. 5(12) 1382-1390 (2013)

SRLG-Aware Topology Aggregation for Survivable Multi-domain Optical Networks

Chengyi Gao, Yi Zhu, and Jason P. Jue
J. Opt. Commun. Netw. 5(11) 1145-1156 (2013)