Multicast in Large WDM Networks

Abstract

We address the multicast issue in a wide area WDM network in which a source broadcasts its message to some sites in the network. This problem can be formalized as the following optimal multicast tree problem. Given a directed graph G = (V, E) with a source s and a set S of nodes, assume that every node is S (⊂ V) is reachable from s. Associated with every link e ∈ E, there is a set Λ(e) of available wavelengths on it, |V| = n and |E| = m, find a multicast tree rooted at s including all the nodes in S with minimizing the cost of the tree, in terms of the sum of the cost of wavelength conversion at nodes and the cost of using wavelengths on links in the tree. That is, not only do we need to find a directed tree rooted at s, but also do we need to assign a specific wavelength λ ∈ Λ(e) to every tree edge e and to set the switches at every node in the tree. Since this problem is NP-complete, it is unlikely that there is a polynomial algorithm to find an exact solution for it. Instead, we first present an approximation algorithm for the problem which runs in time O(k2n + km + kn log (kn)1/ε|S|), and delivers a solution within O(|S|ε) of the optimal, for any fixed 0 < ε ≤ 1. We then present a distributed version of the proposed algorithm. The communication and time complexities of the distributed algorithm are O(km) and O(kn) respectively, and the solution delivered is |S| times of the optimal, where k is the number of wavelengths in the network. Finally, we conduct some experiments to verify the applicability of the proposed algorithms. The experimental results matches our algorithmic claims.