论文部分内容阅读
研究全光WDM网络中多播请求的路由与波长分配问题.给定网络拓扑和一组多播通信请求,要求对其进行路由和波长分配,满足波长连续性和波长无冲突约束,使得所用的波长总数最少.就几类特殊网络进行了研究.首先对二分树网络进行了研究,此时问题是多项式时间可求解的.其次对树网络进行了讨论,证明了即使是星网络,问题也不存在近似比小于m1/2-ρ(0<ρ<1)1的近似算法,除非NP=ZPP,这里m是星图的边数.随后给出了近似比为的近似算法,此结果对一般图也成立.最后考虑了环网和树环网,给出了近似比为3.6和2△的近似算法,这里△是图的最大度.
The problem of routing and wavelength allocation for multicast requests in all-optical WDM networks is studied.With a given network topology and a set of multicast communication requests, routing and wavelength assignment are required to satisfy the requirements of wavelength continuity and wavelength-free collisions, The number of wavelengths is the least.The research on several special networks is carried out.Firstly, the binary tree network is studied, in which case the polynomial time can solve the problem.Secondly, the tree network is discussed to prove that even the star network, the problem is not There is an approximate algorithm with an approximate ratio of less than m1 / 2-ρ (0 <ρ <1) 1 unless NP = ZPP, where m is the number of edges of the star graph, followed by an approximation algorithm with an approximate ratio of Finally, we consider the ring network and tree ring network, and give approximate algorithms with approximate ratios of 3.6 and 2 △, where Δ is the maximum of the graph.