|
Shortest Node-Disjoint Path Using Dual-Network Topology in Optical Switched Networks |
|
|
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
|
