TY - JOUR
T1 - Finding multiple routing paths in wide-area WDM networks
AU - Liang, Weifa
AU - Shen, Xiaojun
PY - 2005/5/2
Y1 - 2005/5/2
N2 - 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.
AB - 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.
KW - Combinatorial optimization
KW - WDM opticla networks robust routing
UR - http://www.scopus.com/inward/record.url?scp=17644419620&partnerID=8YFLogxK
U2 - 10.1016/j.comcom.2005.01.009
DO - 10.1016/j.comcom.2005.01.009
M3 - Article
SN - 0140-3664
VL - 28
SP - 811
EP - 818
JO - Computer Communications
JF - Computer Communications
IS - 7
ER -