TY - GEN

T1 - Finding multiple routing paths in wide-area WDM networks

AU - Liang, Weifa

AU - Shen, Xiaojun

N1 - Publisher Copyright:
© 2002 IEEE.

PY - 2002

Y1 - 2002

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

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

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

U2 - 10.1109/ICPPW.2002.1039731

DO - 10.1109/ICPPW.2002.1039731

M3 - Conference contribution

T3 - Proceedings of the International Conference on Parallel Processing Workshops

SP - 199

EP - 206

BT - Proceedings - International Conference on Parallel Processing Workshops, ICPPW 2002

A2 - Olariu, Stephan

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - International Conference on Parallel Processing Workshops, ICPPW 2002

Y2 - 18 August 2002 through 21 August 2002

ER -