Skip to main content
Article
Graph transformation approaches for diverse routing in shared risk resource group (SRRG) failures
Computer Networks
  • Pallab Datta, Los Alamos National Laboratory
  • Arun K. Somani, Iowa State University
Document Type
Article
Publication Version
Accepted Manuscript
Publication Date
8-22-2008
DOI
10.1016/j.comnet.2008.04.017
Abstract

Failure resilience is a desired feature of the Internet. Most traditional restoration architectures assume single failure assumption, which is not adequate in present day WDM optical networks.

Multiple link failure models, in the form of shared risk link groups (SRLG’s) and shared risk node groups (SRNG’s) are becoming critical in survivable optical network design. We classify both of these form of failures under a common scenario of shared risk resource groups (SRRG) failures. We develop graph transformation techniques for tolerating multiple failures arising out of shared resource group (SRRG) failures.

Diverse routing in such multi-failure scenario essentially necessitates finding out two paths between a source and a destination that are SRRG disjoint. The generalized diverse routing problem has been proved to be NP-Complete. The proposed transformation techniques however provides a polynomial time solution for certain restrictive failure sets. We study how restorability can be achieved for dependent or shared risk link failures and multiple node failures and prove the validity of our approach for different network scenarios. Our proposed technique is capable of improving the diverse route computation by around 20–30% as compared to approaches proposed in the literature.

Comments

This is a manuscript of an article published as Datta, Pallab, and Arun K. Somani. "Graph transformation approaches for diverse routing in shared risk resource group (SRRG) failures." Computer Networks 52, no. 12 (2008): 2381-2394. DOI: 10.1016/j.comnet.2008.04.017. Posted with permission.

Creative Commons License
Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International
Copyright Owner
Elsevier B.V.
Language
en
File Format
application/pdf
Citation Information
Pallab Datta and Arun K. Somani. "Graph transformation approaches for diverse routing in shared risk resource group (SRRG) failures" Computer Networks Vol. 52 Iss. 12 (2008) p. 2381 - 2394
Available at: http://works.bepress.com/arun-somani/39/