Approximation Algorithms for Multicast Routing and Wavelength Assignment in Multi-hop Optical WDM Networks

摘要：

Existing research has demonstrated that effective Routing and Wavelength Assignment (RWA) algorithm and wavelength conversion are two primary vehicles for improving the networks performance. In this paper, we consider the multicast routing and wavelength assignment problem(MC-RWA) in multi-hop optical WDM networks, where requests arrives one by one. Specially, we first analyze this problem under the objective of minimizing maximum hops, an efficient MC-RWA algorithm was proposed in this case. But for minimizing the total number of wavelength conversions, the problem turns out to be NP-hard, hence we propose an efficient approximation MC-RWA algorithm. At last, combine the the two objectives, we propose a bi-factor approximation algorithm to minimize the total wavelength conversions and the maximum hops in the system simultaneously.

关键词： WDM network multicast routing and wavelength assignment approximation algorithm

作者: Tlanping Shuai Wenbao Ai

作者单位: School of Sciences Beijing University of Posts and Telecommunications Beijing, China

会议类型: 国际会议

会议名称: The Fourth International Joint Conference on Computational Science and Optimization(第四届计算科学与优化国际大会 CSO 2011)

会议地点: 昆明、丽江

会议语种:英文

页码: 1291-1295

在线出版日期: 2011-04-15（万方平台首次上网日期，不代表论文的发表时间）