An Algorithm with Better Approximation Ratio for Multicast Traffic in Unidirectional SONET/WDM Rings

作者：Yu Jiguo^*; Cui Suxia; Wang Guanghui

来源：3rd International Conference on Combinatorial Optimization and Applications, 2009-06-10 to 2009-06-12.

The goal for the problem of efficient grooming of given non-uniform multicast traffic demands on a unidirectional SONET/WDM ring is to try to minimize the network cost as given by (i) the number of wavelengths required per fiber and (ii) the number of electronic Add-Drop Multiplexers (ADMs) required in the ring. The problem with cost i) can be reduced to a corresponding traffic grooming problem for unicast traffic which can then be modeled as a standard circular-arc graph coloring problem. The ii) is a main research topic in recent studies. The problem is NP hard for both the cost functions. For the problem with fuction (ii), we present a algorithm with better approximation ratio, 3/2 (N/N-1 + 1). Additionally, we give a lower bound and upper bound for the number of ADMs.

• 出版日期2009
• 单位曲阜师范大学