Finding multiple routing paths in wide-area WDM networks

Date

2005

Authors

Liang, Weifa
Shen, Xiaojun

Journal Title

Journal ISSN

Volume Title

Publisher

Elsevier

Abstract

In this paper a multiple routing path problem in wide area Wavelength Division Multiplexing (WDM) networks is considered, which is to find K edge-disjoint lightpaths/semilightpaths from a source to a destination, if they exist, such that they meet some specified optimization objective. Two versions of the problem are studied. One is to minimize the total cost of the K paths, and the other is to minimize the cost of the maximum cost one among the K paths. An efficient algorithm for the first version is proposed, which takes O(kK(kn+m+nlog(kn))) time and delivers an exact solution, where n, m, and k are the number of nodes, links and wavelengths in the network, respectively. The second version of the problem is shown to be NP-hard, instead an approximation algorithm is devised which delivers a solution within K times of the optimum, where K≥2.

Description

Keywords

Keywords: Algorithms; Approximation theory; Combinatorial mathematics; Optimization; Problem solving; Robustness (control systems); Routers; Theorem proving; Wide area networks; Approximation algorithms; Combinatorial optimization; Multiple routing paths; WDM optic Combinatorial optimization; WDM opticla networks robust routing

Citation

Source

Computer Communications

Type

Journal article

Book Title

Entity type

Access Statement

License Rights

DOI

10.1016/j.comcom.2005.01.009

Restricted until

2037-12-31