SRLG-Diverse Routing With the Star Property
The notion of Shared Risk Link Groups (SRLG) has been introduced to capture survivability issues where some links of a network fail simultaneously. In this context, the diverse routing problem is to find a set of pair-wise SRLG-disjoint paths between a given pair of end nodes of the network. This problem has been proved NP-complete in general and some polynomial instances have been characterized. In this paper, the authors investigate the diverse routing problem in networks where the SRLGs are localized and satisfy the star property. This property states that a link may be subject to several SRLGs, but all links subject to a given SRLG are incident to a common node.