TY - JOUR

T1 - Link Disjoint Paths Using Auxiliary Graph Transformation in WDM Networks

AU - Dahshan, Mostafa H.

PY - 2013/1/1

Y1 - 2013/1/1

N2 - This paper presents a new method for finding two link-disjoint paths in WDM networks under wavelength continuity and lowest cost constraints. Such a problem is considered to be an NP-complete problem, which is only solvable using Integer Linear Programming (ILP). The presented method is based on transforming the original network into an auxiliary network with n × n nodes and 2 mn links, where n is the number of nodes and m is the number of links in the original network, and then applying a modified version of Dijkstra's shortest path algorithm on that network. Despite the larger network size, the execution time of the algorithm is in polynomial order. Considering that the problem is NP-complete, the presented algorithm takes much less time than using ILP, which generally requires exponential time. Yet, it is able to find all available disjoint paths obtainable by ILP.

AB - This paper presents a new method for finding two link-disjoint paths in WDM networks under wavelength continuity and lowest cost constraints. Such a problem is considered to be an NP-complete problem, which is only solvable using Integer Linear Programming (ILP). The presented method is based on transforming the original network into an auxiliary network with n × n nodes and 2 mn links, where n is the number of nodes and m is the number of links in the original network, and then applying a modified version of Dijkstra's shortest path algorithm on that network. Despite the larger network size, the execution time of the algorithm is in polynomial order. Considering that the problem is NP-complete, the presented algorithm takes much less time than using ILP, which generally requires exponential time. Yet, it is able to find all available disjoint paths obtainable by ILP.

KW - Disjoint paths

KW - Network survivability

KW - Optimization algorithms

KW - WDM networks

UR - http://www.scopus.com/inward/record.url?scp=84880736540&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84880736540&partnerID=8YFLogxK

U2 - 10.1007/s13369-013-0568-3

DO - 10.1007/s13369-013-0568-3

M3 - Article

AN - SCOPUS:84880736540

VL - 38

SP - 2043

EP - 2054

JO - Arabian Journal for Science and Engineering

JF - Arabian Journal for Science and Engineering

SN - 2191-4281

IS - 8

ER -