Wavelength conversion in shortest-path all-optical networks

Abstract

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 aplacement 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 alinear-time algorithm for finding an optimal placement of converters in undirected triangle-free networks, and show that the problem remains N P-hard in bidirected triangle-free planar networks.