Fen Zhou, Miklos Molnar, Bernard Cousin, and Chunming Qiao (2011)
Cost Bounds and Approximation Ratios of Multicast Light-trees in WDM Networks
Journal of Optical Communications and Networking 3(4):323-334.
The construction of light-trees is one of the principal
subproblems for all-optical multicast routing in sparse
splitting wavelength division multiplexing (WDM) networks.
Due to the light splitting constraint and the absence of
wavelength converters, several light-trees may be required
to establish a multicast session. However, the computation
of the cost-optimal multicast light-trees is NP-hard. In
this paper, first we study the cost bounds of the
light-trees built for a multicast session in unweighted WDM
networks. Then, partially based on this result, the
approximation ratios of some classical multicast light-tree
computation algorithms, i.e., the reroute-to-source (R2S)
and member-only (MO) algorithms, are derived in both
unweighted and non-equally-weighted WDM networks. Moreover,
integer linear programming formulations are introduced and
carried out to search the optimal light-trees for multicast
routing. The cost bounds and approximation ratios of the
R2S and MO algorithms in some candidate WDM backbone
networks are examined through simulations.