Fulltext

Wavelength Conversion in All-Optical Networks with Shortest-Path Routing

Erlebach, Thomas ; Stefanakos, Stamatis

In: Algorithmica, 2005, vol. 43, no. 1-2, p. 43-61

Add to personal list
    Title
    • Wavelength Conversion in All-Optical Networks with Shortest-Path Routing
    Author
    • Erlebach, Thomas. Department of Computer Science, University of Leicester, Leicester LE1 7RH, England
    • Stefanakos, Stamatis. Computer Engineering and Networks Laboratory (TIK), ETH Zurich, CH-8092 Zurich, Switzerland
    Document Type
    • Postprint
    OAI-PMH Identifier
    • oai:doc.rero.ch:320622
    Summary
    We consider all-optical networks with shortest-path routing that use wavelength-division multiplexing and employ wavelength conversion at specific nodes in order to maximize their capacity usage. We present efficient algorithms for deciding whether a placement of wavelength converters allows the network to run at maximum capacity, and for finding an optimal wavelength assignment when such a placement of converters is known. Our algorithms apply to both undirected and directed networks. Furthermore, we show that the problem of designing such networks, i.e., finding an optimal placement of converters, is MAX SNP-hard in both the undirected and the directed case. Finally, we give a linear-time algorithm for finding an optimal placement of converters in undirected triangle-free networks, and show that the problem remains NP-hard in bidirected triangle-free planar networks