Shortest node-disjoint path using dual-network topology in optical switched networks

Abstract EN

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.