Broadcast Routing with Minimum Wavelength Conversion in WDM Optical Networks

Authors: Ruan, Lu¹; Wu, Weili²

Source: Journal of Combinatorial Optimization, Volume 9, Number 2, March 2005 , pp. 223-235(13)

Publisher: Springer

Buy & download fulltext article:

Price: $47.00 plus tax (Refund Policy)

Abstract:

We consider dynamic routing of broadcast connections in WDM optical networks. Given the current network state, we want to find a minimum set of network nodes S such that a broadcast routing using only the nodes in S as wavelength conversion nodes can be found. This ensures that the average conversion delay from the source to all destinations is minimized. We refer to the problem as Broadcast Conversion Node Selection (BCNS) problem. We prove that BCNS has no polynomial-time approximation with performance ratio rho

ln n for

< 1 unless NP sub

DTIME(n^{O(log log n)}) where n is the number of vertices in the input graph. We present a greedy approximation algorithm for BCNS that achieves approximation ratio 2+ln n. Simulation results show that the algorithm performs very well in practice, obtaining optimal solutions in most of the cases.

Keywords: WDM; optical networks; wavelength conversion; broadcast routing

Document Type: Research article

DOI: http://dx.doi.org/10.1007/s10878-005-6859-1

Affiliations: 1: Department of Computer Science, Iowa State University, Ames, IA, 50011, USA, Email: ruan@cs.iastate.edu 2: Department of Computer Science, University of Texas at Dallas, Richardson, TX, 75083, USA, Email: weiliwu@utdallas.edu

Publication date: 2005-03-01