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.