Routing algorithm for multicast under multi-tree model in optical networks

摘要

To establish a multicast connection in a wavelength routed optical network, two steps are needed under the multi-tree model. One is to construct a set of light-trees rooted at the source node such that in each of them at most a specified number of destination nodes are allowed to receive the data and every destination node must be designated in one of them to receive the data. The other is to assign a wavelength to each of the produced light-trees in such a way that two light-trees must be assigned two distinct wavelengths if they use a common link. In this paper we mainly study how to construct a multicast routing of minimal cost under the multi-tree model in optical networks, where the routing cost is total costs of the produced light-trees. We propose a 4-approximation algorithm for this NP-hard problem.