Converter placement supporting broadcast in WDM optical networks

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

20 Scopus Citations
View graph of relations

Author(s)

  • Lu Ruan
  • Dingzhu Du
  • Xiaodong Hu
  • Deying Li
  • Zheng Sun

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)750-758
Journal / PublicationIEEE Transactions on Computers
Volume50
Issue number7
Publication statusPublished - Jul 2001

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 mathematical formulation for the problem based on the graph model. Two related, problems, Color-Covering and Vertex Color-Covering, are given and analyzed. Both of them are shown to have a polynomial-time approximation with performance ratio ln n + 1 and inn is the best possible performance ratio unless NP ⊂ DTIME(npoly log n), where n is the number of vertices in G. Using these results, we show that the Converter Placement problem has a polynomial-time approximation with performance ratio 2(ln n + 1) and 1/2 ln n is the best possible performance ratio unless NP ⊂ DTIME(npoly log n). We present an approximation algorithm to solve the Converter Placement problem and study the performance of the algorithm on randomly generated network topologies.

Research Area(s)

  • Color-Covering, Converter placement, Network optimization, Optical networks, Vertex Color-Covering, WDM

Citation Format(s)

Converter placement supporting broadcast in WDM optical networks. / Ruan, Lu; Du, Dingzhu; Hu, Xiaodong; Jia, Xiaohua; Li, Deying; Sun, Zheng.

In: IEEE Transactions on Computers, Vol. 50, No. 7, 07.2001, p. 750-758.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review