Broadcast Routing with Minimum Wavelength Conversion in WDM Optical Networks |
| |
Authors: | Email author" target="_blank">Lu?RuanEmail author Weili?Wu |
| |
Institution: | (1) Department of Computer Science, Iowa State University, Ames, IA 50011, USA;(2) Department of Computer Science, University of Texas at Dallas, Richardson, TX 75083, USA |
| |
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 ln n for < 1 unless NP DTIME(nO(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 |
本文献已被 SpringerLink 等数据库收录! |
|