Research Article
Complexity of Converter Placement Supporting Broadcast in WDM Networks
@INPROCEEDINGS{10.1109/BROADNETS.2006.4374385, author={Rudra Dutta and Prashant Iyer and Carla D. Savage}, title={Complexity of Converter Placement Supporting Broadcast in WDM Networks}, proceedings={3rd International ICST Conference on Broadband Communications, Networks, and Systems}, publisher={IEEE}, proceedings_a={BROADNETS}, year={2006}, month={10}, keywords={NP-Completeness Optical networks WDM broadcast graph coloring network provisioning wavelength converter}, doi={10.1109/BROADNETS.2006.4374385} }- Rudra Dutta
Prashant Iyer
Carla D. Savage
Year: 2006
Complexity of Converter Placement Supporting Broadcast in WDM Networks
BROADNETS
IEEE
DOI: 10.1109/BROADNETS.2006.4374385
Abstract
Wavelength converters simplify the wavelength assignment problem in virtual topology design in optical networks and increase the utilization of the fiber bandwidth. However, converters are costly, and minimizing the number of converters needed to support a given level of functionality has been investigated in the literature in various contexts. In particular, previous work has addressed the problem of minimizing the number of converters needed to support broadcast over all network nodes with a given set of residual wavelengths on each link. In this paper, we show that previous work leaves the computational complexity of this question open. We go on to show that the problem is in fact NP-complete, but becomes tractable in the special case when the network graph is a tree. We also show that there are cases when the heuristics articulated in previous work fail to provide solutions, and provide some heuristic approaches to solve the general problem.