Finding multiple routing paths in wide-area WDM networks

Weifa Liang*, Xiaojun Shen

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    1 Citation (Scopus)

    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.

    Original languageEnglish
    Pages (from-to)811-818
    Number of pages8
    JournalComputer Communications
    Volume28
    Issue number7
    DOIs
    Publication statusPublished - 2 May 2005

    Fingerprint

    Dive into the research topics of 'Finding multiple routing paths in wide-area WDM networks'. Together they form a unique fingerprint.

    Cite this