loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
First International Conference on Broadband Networks (BROADNETS'04)
Survivable Virtual Topology Routing under Shared Risk Link Groups in WDM Networks
San Jose, California, USA
October 25-October 29
ISBN: 0-7695-2221-1
Ajay Todimala, University of Nebraska-Lincoln
Byrav Ramamurthy, University of Nebraska-Lincoln
Network survivability is one of the most important issues in the design of optical WDM networks. In this work we study the problem of survivable routing of a virtual topology on a physical topology with Shared Risk Link Groups (SRLG). The survivable virtual topology routing problem against single-link failures in the physical topology is proved to be NP-complete in [Survivable Lightpath Routing: A New Approach to the design of WDM-BasedNetworks]. We prove that survivable virtual topology routing problem against SRLG/node failures is also NP-complete. We present an improved integer linear programming (ILP) formulation (in comparison to [Survivable Lightpath Routing: A New Approach to the design of WDM-BasedNetworks]) for computing the survivable routing under SRLG/node failures. Using an ILP solver, we computed the survivable virtual topology routing against link and SRLG failures for small and medium sized networks efficiently. As even our improved ILP formulation becomes intractable for large networks, we present a congestion-based heuristic and a tabu search heuristic (which uses the congestion-based heuristic solution as the initial solution) for computing survivable routing of a virtual topology. Our experimental results show that tabu search heuristic coupled with the congestion based heuristic (used as initial solution) provides fast and near-optimal solutions.
Citation:
Ajay Todimala, Byrav Ramamurthy, "Survivable Virtual Topology Routing under Shared Risk Link Groups in WDM Networks," broadnets, pp.130-139, First International Conference on Broadband Networks (BROADNETS'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.