Approximation Ratios of Multicast Light-trees in WDM Networks

All-optical multicast routing (AOMR) is implemented by the concept of light-tree in WDM networks. The cost-optimal multicast light-tree is NP-hard to compute, especially when taking sparse splitting into account. Thus many heuristic algorithms have been proposed. In this paper, the approximation ratios of two classical heuristic AOMR algorithms for sparse splitting WDM network are studied. Let K be the number of destinations in a multicast session, it is proved that Reroute-to-Source (R2S) algorithm achieves a tight approximation ratio equal to K in the non-equally-weighted WDM network while Member-Only (MO) algorithm approaches the optimal solution with a ratio inferior to (K2+3K)/4 for any WDM network. It is also found that if the WDM network G is unweighted, both the approximation ratios of R2S and MO are no bigger than the diameter of the network Diam(G). Simulation results illustrate that both R2S and MO obtain good performances in candidate WDM backbone NSF network, which are far from the worst cases.