Link disjoint paths using auxiliary graph transformation in WDM networks

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.