Converter placement supporting broadcast in WDM optical networks

Citation
L. Ruan et al., Converter placement supporting broadcast in WDM optical networks, IEEE COMPUT, 50(7), 2001, pp. 750-758
Citations number
15
Categorie Soggetti
Computer Science & Engineering
Journal title
IEEE TRANSACTIONS ON COMPUTERS
ISSN journal
00189340 → ACNP
Volume
50
Issue
7
Year of publication
2001
Pages
750 - 758
Database
ISI
SICI code
0018-9340(200107)50:7<750:CPSBIW>2.0.ZU;2-#
Abstract
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.