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. © 2005 Elsevier B.V. All rights reserved.
| Original language | English |
|---|---|
| Pages (from-to) | 811-818 |
| Journal | Computer Communications |
| Volume | 28 |
| Issue number | 7 |
| DOIs | |
| Publication status | Published - 2 May 2005 |
| Externally published | Yes |
Bibliographical note
Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].Research Keywords
- Combinatorial optimization
- WDM opticla networks robust routing
Fingerprint
Dive into the research topics of 'Finding multiple routing paths in wide-area WDM networks'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver