几种特殊结构全光网中多播路由的波长分配算法

研究全光WDM网络中多播请求的路由与波长分配问题.给定网络拓扑和一组多播通信请求,要求对其进行路由和波长分配,满足波长连续性和波长无冲突约束,使得所用的波长总数最少.就几类特殊网络进行了研究.首先对二分树网络进行了研究,此时问题是多项式时间可求解的.其次对树网络进行了讨论,证明了即使是星网络,问题也不存在近似比小于m1/2-ρ(0＜ρ＜1))的近似算法,除非NP=ZPP,这里m是星图的边数.随后给出了近似比为(√m 1)(log r/√m 1 1)的近似算法,此结果对一般图也成立.最后考虑了环网和树环网,给出了近似比为3.6和2△的近似算法,这里△是图的最大度.

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.