Skip navigation
Skip navigation

Finding multiple routing paths in wide-area WDM networks

Liang, Weifa; Shen, Xiaojun

Description

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...[Show more]

dc.contributor.authorLiang, Weifa
dc.contributor.authorShen, Xiaojun
dc.date.accessioned2015-12-13T22:52:07Z
dc.identifier.issn0140-3664
dc.identifier.urihttp://hdl.handle.net/1885/81413
dc.description.abstractIn 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.
dc.publisherElsevier
dc.sourceComputer Communications
dc.subjectKeywords: Algorithms; Approximation theory; Combinatorial mathematics; Optimization; Problem solving; Robustness (control systems); Routers; Theorem proving; Wide area networks; Approximation algorithms; Combinatorial optimization; Multiple routing paths; WDM optic Combinatorial optimization; WDM opticla networks robust routing
dc.titleFinding multiple routing paths in wide-area WDM networks
dc.typeJournal article
local.description.notesImported from ARIES
local.description.refereedYes
local.identifier.citationvolume28
dc.date.issued2005
local.identifier.absfor080799 - Library and Information Studies not elsewhere classified
local.identifier.ariespublicationMigratedxPub9708
local.type.statusPublished Version
local.contributor.affiliationLiang, Weifa, College of Engineering and Computer Science, ANU
local.contributor.affiliationShen, Xiaojun, University of Missouri
local.description.embargo2037-12-31
local.bibliographicCitation.issue7
local.bibliographicCitation.startpage811
local.bibliographicCitation.lastpage818
local.identifier.doi10.1016/j.comcom.2005.01.009
dc.date.updated2015-12-11T10:49:11Z
local.identifier.scopusID2-s2.0-17644419620
CollectionsANU Research Publications

Download

File Description SizeFormat Image
01_Liang_Finding_multiple_routing_paths_2005.pdf251.52 kBAdobe PDF    Request a copy


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator