Abstract

Partitioning a large network into a connected hierarchy is a proven technique for scalability and manageability. Although a significant body of work is devoted to this area of interest, a reference to survivable hierarchical networks where each partition remains $k$-connected is missing ($k\ge 2$). A $k$-connected partition ensures functional network organization even after any $k-1$ failures occur. In optical networks, a failure of a physical component (e.g., a cable or line-card) disrupts multiple logical links that share the component. Such a shared risk link group (SRLG) failure is more common than a single link or node failure in the logical topology. Hence, we study the significance of a $k$-SRLG-connected ($k$SC) partitioning problem for optical networks. For a given network, we show that finding 2-SRLG-connected (2SC) partitioning, the simplest case, is NP-complete. We provide mathematical formulations and propose a distributed-scalable heuristic solution. We also solve 2SC partitioning with flexible mapping onto the physical topology, where lightpaths can be added to guarantee a solution. Simulation results verify that the $k$SC partitioning scheme performs better than traditional 1-connected partitioning schemes with regard to system survivability, stability, and repartitioning overhead.

© 2015 Optical Society of America

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)

Online Partitioning for Scalable and Survivable Optical Networks

M. M. Hasan and Jason P. Jue
J. Opt. Commun. Netw. 1(2) A133-A142 (2009)

Backup Reprovisioning After Shared Risk Link Group (SRLG) Failures in WDM Mesh Networks

Xu Shao, Yong Kee Yeo, Yuebin Bai, Jian Chen, Luying Zhou, and Lek Heng Ngoh
J. Opt. Commun. Netw. 2(8) 587-599 (2010)

On Shared Risk Link Group Optimization [Invited]

Guangzhi Li, Dongmei Wang, Timothy Gallivan, and Robert Doverspike
J. Opt. Commun. Netw. 4(11) B52-B57 (2012)

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)