TY - JOUR
T1 - SRLG failure localization in optical networks
AU - Ahuja, Satyajeet S.
AU - Ramasubramanian, Srinivasan
AU - Krunz, Marwan
N1 - Funding Information:
Manuscript received September 19, 2009; revised July 12, 2010; accepted November 01, 2010; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor S. Subramaniam. Date of publication January 20, 2011; date of current version August 17, 2011. This work was supported in part by the National Science Foundation (NSF) under Grants CNS-1016943, CNS-0435490, CNS-0904681, and IIP-0832238; Raytheon; and the “Connection One” Center. Any opinions, findings, conclusions, or recommendations expressed in this paper are those of the author(s) and do not necessarily reflect the views of the NSF. An abridged version of this paper was presented at the IEEE International Conference on Computer Communications (INFOCOM), Phoenix, AZ, April 15–17, 2008.
PY - 2011/8
Y1 - 2011/8
N2 - We introduce the concepts of monitoring paths (MPs) and monitoring cycles (MCs) for unique localization of shared risk linked group (SRLG) failures in all-optical networks. An SRLG failure causes multiple links to break simultaneously due to the failure of a common resource. MCs (MPs) start and end at the same (distinct) monitoring location(s). They are constructed such that any SRLG failure results in the failure of a unique combination of paths and cycles. We derive necessary and sufficient conditions on the set of MCs and MPs needed for localizing any single SRLG failure in an arbitrary graph. When a single monitoring location is employed, we show that a network must be (k+2)-edge connected for localizing all SRLG failures, each involving up to k links. For networks that are less than (k+2)-edge connected, we derive necessary and sufficient conditions on the placement of monitoring locations for unique localization of any single SRLG failure of up to k links. We use these conditions to develop an algorithm for determining monitoring locations. We show a graph transformation technique that converts the problem of identifying MCs and MPs with multiple monitoring locations to a problem of identifying MCs with a single monitoring location. We provide an integer linear program and a heuristic to identify MCs for networks with one monitoring location. We then consider the monitoring problem for networks with no dedicated bandwidth for monitoring purposes. For such networks, we use passive probing of lightpaths by employing optical splitters at various intermediate nodes. Through an integer linear programming formulation, we identify the minimum number of optical splitters that are required to monitor all SRLG failures in the network. Extensive simulations are used to demonstrate the effectiveness of the proposed monitoring technique.
AB - We introduce the concepts of monitoring paths (MPs) and monitoring cycles (MCs) for unique localization of shared risk linked group (SRLG) failures in all-optical networks. An SRLG failure causes multiple links to break simultaneously due to the failure of a common resource. MCs (MPs) start and end at the same (distinct) monitoring location(s). They are constructed such that any SRLG failure results in the failure of a unique combination of paths and cycles. We derive necessary and sufficient conditions on the set of MCs and MPs needed for localizing any single SRLG failure in an arbitrary graph. When a single monitoring location is employed, we show that a network must be (k+2)-edge connected for localizing all SRLG failures, each involving up to k links. For networks that are less than (k+2)-edge connected, we derive necessary and sufficient conditions on the placement of monitoring locations for unique localization of any single SRLG failure of up to k links. We use these conditions to develop an algorithm for determining monitoring locations. We show a graph transformation technique that converts the problem of identifying MCs and MPs with multiple monitoring locations to a problem of identifying MCs with a single monitoring location. We provide an integer linear program and a heuristic to identify MCs for networks with one monitoring location. We then consider the monitoring problem for networks with no dedicated bandwidth for monitoring purposes. For such networks, we use passive probing of lightpaths by employing optical splitters at various intermediate nodes. Through an integer linear programming formulation, we identify the minimum number of optical splitters that are required to monitor all SRLG failures in the network. Extensive simulations are used to demonstrate the effectiveness of the proposed monitoring technique.
KW - Failure localization
KW - network monitoring
KW - optical networks
KW - shared risk link group (SRLG) failure
UR - http://www.scopus.com/inward/record.url?scp=80051784096&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=80051784096&partnerID=8YFLogxK
U2 - 10.1109/TNET.2010.2103402
DO - 10.1109/TNET.2010.2103402
M3 - Article
AN - SCOPUS:80051784096
SN - 1063-6692
VL - 19
SP - 989
EP - 999
JO - IEEE/ACM Transactions on Networking
JF - IEEE/ACM Transactions on Networking
IS - 4
M1 - 5699383
ER -