TY - JOUR

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

AU - Dahshan, Mostafa

PY - 2013/7/1

Y1 - 2013/7/1

N2 - 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 + n 2 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.

AB - 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 + n 2 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.

KW - Disjoint paths

KW - Network survivability

KW - Optical switched networks

KW - Optimization algorithms

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

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

M3 - Article

AN - SCOPUS:84864989273

SN - 1683-3198

VL - 10

SP - 365

EP - 372

JO - International Arab Journal of Information Technology

JF - International Arab Journal of Information Technology

IS - 4

ER -