Improved Lightpath (Wavelength) Routing in Large WDM Networks
-
Altmetric Citations
Description
We address the problem of efficient circuit switching in wide area networks. The solution provided is based on finding optimal routes for lightpaths and semilightpaths. A lightpath is a fully optical transmission path, while a semilightpath is a transmission path constructed by chaining several lightpaths together, using wavelength conversion at their junctions. The problem thus is to find an optimal lightpath/semilightpath in the network in terms of the cost of wavelength conversion and the...[Show more]
dc.contributor.author | Liang, Weifa | |
---|---|---|
dc.contributor.author | Shen, Xiaojun | |
dc.date.accessioned | 2015-12-13T23:21:06Z | |
dc.date.available | 2015-12-13T23:21:06Z | |
dc.identifier.issn | 0090-6778 | |
dc.identifier.uri | http://hdl.handle.net/1885/91024 | |
dc.description.abstract | We address the problem of efficient circuit switching in wide area networks. The solution provided is based on finding optimal routes for lightpaths and semilightpaths. A lightpath is a fully optical transmission path, while a semilightpath is a transmission path constructed by chaining several lightpaths together, using wavelength conversion at their junctions. The problem thus is to find an optimal lightpath/semilightpath in the network in terms of the cost of wavelength conversion and the cost of using the wavelengths on links. In this paper, we first present an efficient algorithm for the problem which runs in time O(k2n + km + kn log(kn)), where n and m are the number of nodes and links in the network, and k is the number of wavelengths. We then analyze that the proposed algorithm requires O(d2nk02 + mk0 log n) time for a restricted version of the problem in which the number of available wavelengths for each link is bounded by k0 and k0 = o(n), where d is the maximum in-degree or out-degree of the network. It is surprising to have found that the time complexity for this case is independent of k. It must be mentioned that our algorithm can be implemented efficiently in the distributed computing environment. The distributed version requires O(kn) time and O(km) messages. Compared with a previous O(k2n + kn2) time algorithm, our algorithm has the following advantages. 1) We take into account the physical topology of the network which makes our algorithm outperform the previous algorithm. In particular, when k is small [e.g., k = O(log n)] and m = O(n), our algorithm runs in time O(n log2 n), while the previous algorithm runs in time O(n2 log n). 2) Since our algorithm has high locality, it can be implemented on the network distributively. | |
dc.publisher | Institute of Electrical and Electronics Engineers (IEEE Inc) | |
dc.source | IEEE Transactions on Communications | |
dc.subject | Keywords: Algorithms; Computational complexity; Distributed computer systems; Fiber optic networks; Graph theory; Light transmission; Matrix algebra; Optical links; Routers; Wide area networks; Lightpath wavelength routing; Optical transmission path; Semilightpaths | |
dc.title | Improved Lightpath (Wavelength) Routing in Large WDM Networks | |
dc.type | Journal article | |
local.description.notes | Imported from ARIES | |
local.description.refereed | Yes | |
local.identifier.citationvolume | 48 | |
dc.date.issued | 2000 | |
local.identifier.absfor | 100503 - Computer Communications Networks | |
local.identifier.ariespublication | MigratedxPub21529 | |
local.type.status | Published Version | |
local.contributor.affiliation | Liang, Weifa, College of Engineering and Computer Science, ANU | |
local.contributor.affiliation | Shen, Xiaojun, University of Missouri | |
local.bibliographicCitation.startpage | 1571 | |
local.bibliographicCitation.lastpage | 1579 | |
local.identifier.doi | 10.1109/26.870024 | |
dc.date.updated | 2015-12-12T09:05:31Z | |
local.identifier.scopusID | 2-s2.0-0034267190 | |
Collections | ANU Research Publications |
Download
Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.
Updated: 17 November 2022/ Responsible Officer: University Librarian/ Page Contact: Library Systems & Web Coordinator