Wavelength Conversion in Shortest-Path All-Optical Networks

摘要

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 finding an optimal placement of converters is MAX SNP-hard in both undirected and directed networks. 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.