Multicasting and Broadcasting in Large WDM Networks

We address the issue of multicasting and broadcasting in wide area WDM networks in which a source broadcasts a message to all members in S (⊂ V). We formalize it as the optimal multicast tree problem which is defined as follows. Given a directed network G = (V, E) with a given source s and a set S of nodes |V| = n and |E| = m. Associated with every link e ∈ E, there is a set Λ (e) of available wavelengths on it. Assume that every node in S is reachable from s, the problem is to find a multicast tree rooted at s including all nodes in S such that the cost of the tree is the minimum in terms of the cost of wavelength conversion at nodes and the cost of using wavelengths on links. That is, not only do we need to find such a tree, but also we need to assign a specific wavelength λ ∈ Λ(e) to each directed tree edge e and to set the switches at every node in the tree. We show the problem is NP-complete, and hence it is unlikely that there is a polynomial algorithm for it. We further prove that there is no polynomial approximation algorithm which delivers a solution better than (1-ϵ') in n times the optimum unless there is an n^O(^{log log n}) time algorithm for NP-complete problems, for any fixed ϵ' with 0 < ϵ' < 1. We finally reduce the problem to a directed Steiner tree problem on an auxiliary directed graph. As results, any approximation solution for ,the directed Steiner tree problem gives an approximation solution for our problem with the same degree accuracy, i.e, there is an approximation algorithm for the problem which runs in time O(k²n + km + kn log(kn) + (kn)'^/εlSl), and delivers a solution within O(|S|^ε) the optimum for any fixed ε with 0 < ε < 1. Moreover, we also present a distributed algorithm for the problem. The communication and time complexities of the distributed algorithm are O(km) and O(kn) respectively, and the solution delivered is |S| times the optimum, where k is the number of wavelengths in the network.