Algorithms for Multicast Routing and Wavelength Assignment inAll-Optical Networks under Some Special Topologies
几种特殊结构全光网中多播路由的波长分配算法

We consider the multiple multicast routing and wavelength assignment problem in all optical WDM network. Given a network topology and a set of multicast request, we must set up a route for each requests and assign a wavelength such that two requests share one common link must assign different wavelength, the objective is to minimize the total number of wavelengths used. We focus on some special network topologies. We prove that the problem can be solved inpolynomial time when the network topology is a binary tree. We also show that for star network, there does not exist a $m^{\frac{1}{2}-\rho}$-approximation algorithm for any given $o<\rho< \frac{1}{2}$ unless $NP=ZPP$, where $m$ is the number of edges in the star network. We then propose a $(\sqrt{m}+1)\big(\log{\frac{r}{\sqrt{m}+1}}+1\big)-$approximation algorithms for star network, where\ $r$ is the number of requests. The result can be applied to general network. In the end, we propose a 3.6-approximation algorithm for ring network and $2\Delta-$approximation algorithm for wavelength assignment in trees of rings, where $\Delta$ is a maximum degree of trees of rings.