loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
2002 International Conference on Parallel Processing Workshops (ICPPW'02)
Finding Multiple Routing Paths in Wide-Area WDM Networks
Vancouver, B.C., Canada
August 18-August 21
ISBN: 0-7695-1680-7
Weifa Liang, Australian National University
Xiaojun Shen, University of Missouri - Kansas City
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 light-paths/semilightpaths 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.
Citation:
Weifa Liang, Xiaojun Shen, "Finding Multiple Routing Paths in Wide-Area WDM Networks," icppw, pp.199, 2002 International Conference on Parallel Processing Workshops (ICPPW'02), 2002
Usage of this product signifies your acceptance of the Terms of Use.