Trap avoidance and protection schemes in networks with shared risk link groups
Authors:
- 8 December 2003
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in Journal of Lightwave Technology
- Vol. 21 (11) , 2683-2693
Abstract
Shared risk link group (SRLG) has been widely recognized as an important concept in survivable optical networks. However, there are still several SRLG-related problems of both theoretical interest and practical importance that have not been explored fully. Specifically, there are two major issues that are still open: avoiding failures in path determination caused by "traps" and maximizing bandwidth sharing. These issues are more challenging when considering shared path protection in networks with SRLGs. In this paper, we address the above two open issues, starting with a heuristic approach to avoiding traps. In networks with SRLGs, a simple heuristic may run into traps up to 30% of the time. Integer linear programming (ILP)-based approaches, on the other hand, are not feasible for large SRLG networks. One of the widely used heuristics for trap avoidance is based on K shortest paths (KSP). As an alternative to KSP, we propose an innovative trap avoidance (TA) heuristic that requires much less running time than KSP (and ILP) and yet can effectively avoid almost all the avoidable traps as an ILP-based approach. We also propose an efficient shared SRLG protection scheme based on TA that can achieve a bandwidth efficiency that is nearly as high as other schemes based on ILP or KSP.Keywords
This publication has 19 references indexed in Scilit:
- Lightpath Re-optimization in mesh optical networksIEEE/ACM Transactions on Networking, 2005
- A new implementation of Yen?s ranking loopless paths algorithm4OR, 2003
- Optimal diverse routing in telecommunication fiber networks2002
- Addressing network survivability issues by finding the K-best paths through a trellis graph2002
- Successive survivable routing for node failures2002
- Auto-discovery of shared risk link groups2002
- Quantifying the benefit of wavelength add-drop in WDM rings with distance-independent and dependent trafficJournal of Lightwave Technology, 1999
- Comparison of k-shortest paths and maximum flow routing for network facility restorationIEEE Journal on Selected Areas in Communications, 1994
- Finding disjoint paths with different path‐costs: Complexity and algorithmsNetworks, 1992
- A quick method for finding shortest pairs of disjoint pathsNetworks, 1984