Shortest Node-Disjoint Path Using Dual-Network Topology in Optical Switched Networks

Mostafa Dahshan
College of Computer and Information Sciences, King Saud University, Saudi Arabia

 

Abstract: This paper presents a new method for finding shortest node-disjoint paths in optical-switched networks with no wavelength conversion. The proposed method is based on a modified version of Dijkstra algorithm that works on an expanded so-called dual-network topology with n×n- nodes and 2×m×n links, where n is the number of nodes and m is the number of links in the original network. Despite the larger network size, the execution time of the algorithm is in polynomial order (mn + n2 log n). Considering that the problem is NP-complete, the presented algorithm takes much less time than using ILP, which takes exponential time. Yet, it is able to find all available disjoint paths obtainable by ILP.

Keywords: Disjoint paths, optical switched networks, network survivability, optimization algorithms.

 

Received March 17, 2011; accepted May 24, 2011

  

Full Text