Converter placement supporting broadcast in WDM optical networks

Given a WDM optical network with wavelength channels on its fiber links, we consider the problem of finding the minimum set of network nodes such that , with wavelength converters at these nodes, broadcast can be supported in the network. We call this problem the Converter Placement problem. We model a given network using a graph G with colors on its edges and give a mathem atical formulation for the problem based on the graph model. Two related pr oblems, Color-Covering and Vertex Color-Covering, are given and analyzed. B oth of them are shown to have a polynomial-time approximation with performa nce ratio In n + 1 and Inn is the best possible performance ratio unless NP subset of DTIME(n(polylogn)), where n is the number of vertices in G. Usin g these results, we show that the Converter Placement problem has a polynom ial-time approximation with performance ratio 2(ln n + 1) and (1)/(2)ln n i s the best possible performance ratio unless NP subset of DTIME(n(polylogn) ). We present an approximation algorithm to solve the Converter Placement p roblem and study the performance of the algorithm on randomly generated net work topologies.