MULTICAST IN LARGE WDM NETWORKS

WEIFA LIANG^{∗} AND HONG SHEN^{†}

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 in 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(k^{2}n + km + kn log(kn) + (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.

Key words. optical networks, optimal multicast trees, algorithm design and analysis, graph theory, routing algorithms

1. Introduction. Multicast communication involves the transport of information between a single sender (source) and multiple receivers (destinations). A special case of multicast is broadcast where the set of receivers consists of all other nodes except the source. Multicast applications include video conferencing, entertainment distribution, tele-classrooms, distributed data processing, and so on. With growing demand for these services and the availability of high bandwidths, future networks such as WDM networks must be equipped to handle multicast communication in an efficient manner. The most popular solutions to multicast routing involve some kinds of tree constructions. Algorithms for constructing multicast trees have been developed in traditional undirected networks [10, 11, 1, 9, 16, 7]. Some of these algorithms have multiple optimization objectives for the tree such as the average delay [10], the maximum delay [11], the delay variation-bounded [16], etc. There are also some algorithms dealing with the dynamic version of the problem by taking into account adding and/or deleting a node from the tree [1]. It must be mentioned that there is a big difference between the traditional networks and the WDM networks on the multicast issue. This difference reflects in their optimization objectives. For example, in traditional networks we usually focus on minimizing the total of bandwidth spent and the maximum transfer delay of messages, etc, while in WDM networks the available wavelengths are crucial resources, and the cost for wavelength conversion at some nodes (switching from one wavelength to another wavelength) is an important factor.

The optimal multicast tree problem in an WDM network can be defined as follows. Given a source and a set S of destinations in the network such that every node in S is reachable from the source, the objective is to find a multicast tree rooted at the source including all the nodes in S such that the cost sum of links and nodes in the tree is minimized, in terms of the following cost measurement: 1) the cost for traversing a link on some wavelength, and 2) the cost for wavelength conversion when the path has to switch to a different wavelength at some intermediate nodes. Note that this cost measurement was defined by Chlamtac et al [3] for finding an optimal lightpath/semilightpath between a pair of nodes in the network. Clearly the problem is more complicated than its counterpart in traditional networks. Since the problem is NP-hard, it is unlikely that there is a polynomial algorithm for finding an exact solution for it unless P=NP. Instead, we shall look for an approximation solution for it. We devise an approximation algorithm for the problem which runs in time O(k^{2}n + km + kn log(kn) + (kn)^{1/ϵ}|S|), and delivers a solution within O(|S|^{ϵ}) of the optimal for any fixed 0 < ϵ ≤ 1, by reducing the problem to a directed Steiner tree problem on a directed auxiliary graph. Also, a distributed version of the proposed algorithm is given, which has O(km)

∗ Department of Computer Science, Australian National University, Canberra, ACT 0200, Australia,

(wliang@cs.anu.edu.au).

†School of Computing and Information Technology, Griffith University, Nathan, QLD 4111, Australia,

(hong@cit.gu.edu.au).

communication complexity and O(kn) time complexity where m is the number of links and k is the number of wavelengths in the network.

The rest of this paper is arranged as follows. In Section 2 we introduce the network model and define the optimal multicast tree problem. In Section 3 we first show the NP-hardness of the problem by a simple reduction, we then give our approximation algorithm by reducing the problem to a directed Steiner tree problem on an auxiliary graph, which we later show such a reduction is correct. Also, a distributed algorithm is presented in this section. In Section 4, we implement the proposed algorithms and verify their applicability through experimental simulation. We conclude our discussions in Section 5.

2. Network Model and Problem Statement. The optical network is modeled by a directed graph G = (V, E), where V and E are the set of nodes (vertices) and the set of directed links (edges) in the network. Denote by n = |V | and m = |E|. Let d_{in}(G, v) and d_{out}(G, v) be the in-degree and the out-degree of v in G. Denote d_{in} = max{d_{in}(G, v) | v ∈ V }, d_{out} = max{d_{out}(G, v) | v ∈ V }, and d = max{d_{in}, d_{out}}. It is well known that ∑_{v∈V} d_{in}(G, v) = ∑_{v∈V} d_{out}(G, v) = m. Clearly, m ≤ dn. Note that the directed version of an undirected network can be modeled by replacing an undirected link with two oppositely directed links.

Suppose that a set Λ = {λ_{1}, λ_{2}, …, λ_{k}} of wavelengths is available for the wide area WDM network G. By the definition of Chlamtac et al [3], the cost structure of using the resources in the network is represented as follows. For each link e and wavelength λ_{i} a nonnegative weight w(e, λ_{i}) is given, representing the “cost” of using wavelength λ_{i} on link e. If λ_{i} is not available on the link, then the weight is infinite. The “cost” of wavelength conversion c_{v}(λ_{p}, λ_{q}) is the cost of wavelength conversion at node v from wavelength λ_{p} to wavelength λ_{q}. For some given v, p and q, if the conversion at v is not available, then c_{v}(λ_{p}, λ_{q}) is infinite. If the two wavelengths are equal (i.e., p = q), then c_{v}(λ_{p}, λ_{p}) = 0. The above defined wavelength conversion costs accommodate the general case where the conversion cost depends on the nodes and the wavelengths involved.

Let s ∈ V be a source and S ⊂ V be a set of destinations. Assume that every v ∈ S be reachable from s, associated with each link e ∈ E a set Λ(e) (⊆ Λ) of available wavelengths has been given, so has the wavelength conversion function at each node v ∈ V. A multicast tree rooted at s in G is a tree such that every node in S is reachable from s. Clearly such a tree is a directed tree in which the in-degree of every node is one except the root node whose in-degree is zero. Let T be such a multicast tree. Assume that p(v) is the parent of v in T if v ≠ s, otherwise p(s) = ∅. For convenience, let w(⟨∅, s⟩, λ) = 0 for any λ ∈ Λ. Then the cost, C(T), of T is defined as follows.

(2.1)  C(T) = ∑_{v∈T} w(⟨p(v), v⟩, λ(v)) + ∑_{v∈T −{s}} c_{p(v)}(λ(p(v)), λ(v))

where λ(v) represents the wavelength used on link ⟨p(v), v⟩ for broadcasting and c_{p(v)}(λ(p(v)), λ(v)) represents the cost of wavelength conversion from λ(p(v)) to λ(v) at node p(v).

The optimal multicast tree problem then is to find a multicast tree T in the network with minimizing C(T) in Equation 2.1. Note that, for this problem, not only do we need to find such an optimal multicast tree, but also do we need to assign a wavelength λ ∈ Λ(⟨p(v), v⟩) for each link ⟨p(v), v⟩ and to set the wavelength conversion switches at non-leaf nodes if necessary.

Clearly, the optimal semilightpath problem defined by Chlamtac et al [3] is a special case of our problem where S = {t}.

As remarked by Chlamtac et al in [3], it is not forbidden in general for a semilightpath to visit a node more than once, on different wavelengths. It is expected, however, that in practical cases the cost structure will exclude such cases from being optimal, but we do not have to exclude them a priori. The case where the same link is traversed on the same wavelength more than once is automatically excluded from the potential optimal solutions, since it can be shortened by a shortcut. Therefore, the optimal multicast tree found may be a pseudo-tree, in which cycles may exist. But in practice by adjusting the ”cost structure”, this situation can be avoided.

3. The Optimal Multicast Tree Problem. In this section we first show the NP-hardness of the problem by a simple reduction. We then give an approximation algorithm for it by constructing an auxiliary graph and showing that the directed Steiner tree on the auxiliary graph corresponds to a solution of our problem. We finally propose a distributed algorithm for the problem.

3.1. NP hardness. Before we proceed, we introduce the (directed) Steiner tree definition. Let G(V, E) be an undirected weighted graph with a given subset S of V, a tree in G that includes all nodes in S is called a Steiner tree of G if the weighted sum of all the links in the tree is minimized. When G is a directed weighted graph, a tree rooted at a node s including all the nodes in S is called a directed Steiner tree of G if the weighted sum of the links in the tree is minimized and every node in S is reachable from s. We start by the following simple lemma.

Lemma 3.1. Given a directed weighted graph G = (V, E), and a set S ⊂ V of nodes and a source s, assume that every node in S is reachable from s, finding a directed Steiner tree is NP-complete.

Proof. It is well known that the Steiner tree problem on undirected graphs is NP-complete [8]. The approach is to reduce a Steiner tree problem on an undirected graph to a directed Steiner tree problem on its corresponding directed graph. Let G be an undirected graph. Construct a directed version G′′ of G by replacing every undirected edge of G into two oppositely directed links, and assign the directed links with the weight of the undirected edge. Then, the Steiner tree of G by given S and s can be found as follows. Find a directed Steiner tree in G′′ rooted at s including all nodes in S. Let T′ be the resulting tree. Clearly, the undirected version of T′ is a Steiner tree of G. The above reduction is polynomial, so, the lemma then follows.

Consider a special case of the optimal multicast tree problem on the network G where there is only one common wavelength λ associated with each link, i.e., Λ(e) = {λ} for each link e ∈ E. It is clear that the problem now is the directed Steiner tree problem on G with edge weight w(e, λ) for every link e ∈ E. By Lemma 3.1 the directed Steiner tree problem is NP-complete, so, the optimal multicast problem on G is NP-complete. Therefore, we have

Lemma 3.2. Given a directed network G = (V, E) with a set S ⊂ V of nodes and a source s and every node in S is reachable from s, assume that a set Λ(e) (⊆ Λ) of available wavelengths associated with each directed link e ∈ E has been given, so has the wavelength conversion function at each node v ∈ V. Finding an optimal multicast tree on G is NP-complete.

¿From Lemma 3.2, we know that it is unlikely to have an exact solution for the problem in polynomial time unless P=NP. Instead, we will focus on giving approximation algorithms for it. The basic idea behind our algorithm is to reduce the problem on G to a directed Steiner tree problem on an auxiliary directed graph GC which will be defined below. As a result, any feasible solution for the directed Steiner tree problem on GC corresponds to a feasible solution with the same degree accuracy for the optimal multicast tree problem on G.

3.2. Data structures. In [13], Liang et al presented an improved algorithm for finding an optimal semilightpath in WDM networks by introducing new data structures. Following the same spirit, here we devise new data structures for the optimal multicast tree problem.

Given the network G = (V, E), let E_{in}(G, v) and E_{out}(G, v) be the set of incoming links and the set of outgoing links of v in G respectively.

Firstly, we construct a directed multigraph G_{M} = (V_{M}, E_{M}) as follows. V_{M} = V, and for each directed link e = ⟨u, v⟩ ∈ E there are |Λ(e)| parallel directed links in E_{M} from u to v if Λ(e) ≠ ∅. Each such a link is associated with a distinct wavelength λ ∈ Λ(e), and the link is assigned weight w(e, λ). Thus, G_{M} has |V_{M}| = |V | = n nodes and m_{1} = |E_{M}| = ∑_{e∈E} |Λ(e)| directed links. Obviously m_{1} ≤ km, where k (= |Λ|) is the number of wavelengths in the network. Also, it is obvious that |E_{in}(G_{M}, v)| + |E_{out}(G_{M}, v)| = ∑_{e∈E_{in}(G,v)∪E_{out}(G,v)} |Λ(e)| ≤ k(d_{in}(G, v) + d_{out}(G, v)) ≤ 2kd for each node v ∈ V_{M}.

Let Λ_{in}(G_{M}, v) = ⋃_{e∈E_{in}(G_{M} ,v)} Λ(e) and Λ_{out}(G_{M}, v) = ⋃_{e∈E_{out}(G_{M} ,v)} Λ(e) be the set of wavelengths on the incoming links and the set of wavelengths on the outgoing links of v respectively.

Secondly, we construct a directed bipartite weighted graph G_{v} = (X_{v}, Y_{v}, E_{v}, ω_{1}) for every node v ∈ V_{M} as follows. For each wavelength λ ∈ Λ_{in}(G_{M}, v) there is a corresponding node x in X_{v}, and for each wavelength λ′ ∈ Λ_{out}(G_{M}, v) there is a corresponding node y in Y_{v}. There is a directed link e = ⟨x, y⟩ ∈ E_{v} from x ∈ X_{v} to y ∈ Y_{v} if one of the following conditions hold. (i) λ = λ′. The weight of e is assigned ω_{1}(e) = C_{v}(λ, λ) = 0; (ii) λ ≠ λ′ and the wavelength conversion from λ to λ′ at v is allowed. The weight of e is assigned ω_{1}(e) = C_{v}(λ, λ′). Note that the weights on the links in G_{v} represent the costs of wavelength conversion at node v.

Thirdly, we construct an auxiliary graph G′ = (V′, E′, ω_{2}) from G_{M} and G_{v} for all v ∈ V_{M}, which is also a directed weighted graph, as follows. V′ = ⋃_{v∈V_{M}} (X_{v} ∪ Y_{v}). Let ⟨u, v⟩ ∈ E_{M} be any directed link with wavelength λ. Assume that u′ ∈ Y_{u} and v′ ∈ X_{v} are the corresponding nodes of u and v in G_{u} and G_{v} respectively. Then, ⟨u′, v′⟩ ∈ E′ and the weight of this link is ω_{2}(⟨u′, v′⟩) = w(⟨u, v⟩, λ). Let E_{org} be the set of the links of G′ obtained from E_{M} by the above transformation, then |E_{org}| = |E_{M}| = ∑_{e∈E} |Λ(e)| ≤ km. ω_{2}(e) = ω_{1}(e) for every e ∈ ⋃_{v∈V} E_{v}. Define E′ = ⋃_{v∈V_{M}} E_{v} ∪ E_{org}.

Lemma 3.3. Let G′(V′, E′, ω_{2}) be the directed weighted graph defined as above, then |V′| = ∑_{v∈V_{M}} (|X_{v}|+|Y_{v}|) = ∑_{v∈V_{M}} (|Λ_{in}(G_{M}, v)|+|Λ_{out}(G_{M}, v)|) ≤ 2kn and |E′| = ⋃_{v∈V_{M}} |E_{v}|+|E_{org}| ≤ k^{2}n + m_{1} ≤ k^{2}n + km.

Lemma 3.4. Let G′(V′, E′, ω_{2}) be the directed weighted graph defined as above. Then G′ can be constructed in O(k^{2}n + km) time and space if G′ is represented by adjacency lists.

Finally, we construct an auxiliary directed, weighted graph GC = (V C, EC, ω_{3}) as follows. V C = ⋃_{v∈V} (X_{v} ∪Y_{v})∪{v′′ | v ∈ V −{s}}∪{s′} and EC = ⋃_{v∈V} E_{v} ∪E_{org} ∪⋃_{v∈V −{s}}{⟨u, v′′⟩ | u ∈ X_{v}} ∪ {⟨s′, u⟩ | u ∈ Y_{s}}, where v′′ means that v ∈ V could be a receiver in the final tree, and s′ means that s is the only source in the tree. ω_{3}(e) = ω_{2}(e) for every e ∈ ⋃_{v∈V} E_{v} ∪E_{org}. The links in {⟨u, v′′⟩ | u ∈ X_{v}} are assigned weight zeros, i.e., ω_{3}(⟨u, v′′⟩) = 0, and the links in {⟨s′, u⟩ | u ∈ Y_{s}} are assigned weight zeros, i.e., ω_{3}(⟨s′, u⟩) = 0. It is obvious that GC can be constructed in time O(k^{2}n + km).

3.3. An approximation algorithm. Assume that the auxiliary graph GC has been given, we now consider how to find an approximation solution for the optimal multicast tree problem.

Theorem 3.5. Let T be a directed Steiner tree of GC with the source s′ and the destination set S′ and T_{1} be an optimal multicast tree of G, then the cost w(T) of T is equal to the cost of T_{1}, i.e., w(T) = ∑_{⟨u,v⟩∈E(T)} ω_{3}(⟨u, v⟩) = C(T_{1}), where S′ = {v′′ | v ∈ S} and E(T) is the set of links in T.

Proof. Let T_{1}(V_{1}, E_{1}) be an optimal multicast tree of G rooted at s that includes all the nodes in S. We construct a new graph T_{2}(V_{2}, E_{2}) from T_{1}, using the same transformation approach as that for G′ from G_{M}, as follows. Let v be a node of T_{1}, c(T_{1}, v) be the children set of v in T_{1} and p(T_{1}, v) be the parent of v in T_{1}. Then, |Λ_{in}(T_{1}, v)| = 1 and |Λ_{out}(T_{1}, v)| ≤ |c(T_{1}, v)|. Let Λ_{in}(T_{1}, v) = {λ(v)}, then there is a corresponding node in X_{v} of G′ driven from the link ⟨p(T_{1}, v), v⟩ and the wavelength λ(v). We use λ(v) to represent the node if there is no any confusion. We use Z_{v} to represent the corresponding node set of Λ_{out}(T_{1}, v) in G′. Clearly, Z_{v} ⊆ Y_{v}.

Define V_{2} = ⋃_{v∈T_{1}}({λ(v)} ∪ Z_{v}) and ⟨λ(v), u⟩ ∈ E_{2} for every u ∈ Z_{v} and assign the weight of this link c_{v}(λ(p(T_{1}, v)), λ(v)) if v ≠ s, which is switching cost. For every link ⟨u, v⟩ ∈ E_{1}, there is an edge ⟨λ(u), x_{v}⟩ ∈ E_{2} and the weight of this link is w(⟨p(T_{1}, v), v⟩, λ(v)) which is the cost using wavelength λ(v) on this link, where x_{v} is the corresponding node of v in Z_{v}. Obviously T_{2} is a forest of G′ in which every non-root node has in-degree one and every rooted node has in-degree zero. We now extend T_{2} in the following way. For every v ∈ T_{1}, if v ≠ s, we add a new node v′′ and a new link ⟨λ(v), v′′⟩ to T_{2}, and assign this link weight zero; otherwise, we add a new node s′ and new links ⟨s′, u⟩ to T_{2} for all u ∈ Z_{s} and assign these new links weight zeros. Let T_{3} be the augmented graph of T_{2}. Now T_{3} is a directed tree of GC which includes all nodes in S′. Let w(T_{1}) be the cost of the optimal multicast tree of T_{1} of G. Then w(T_{2}) = w(T_{1}) by the definition. Since the new links added from T_{2} to T_{3} with weight zeros, w(T_{3}) = w(T_{2}). While T is a directed Steiner tree of GC rooted at s′ including all nodes of S′, w(T) ≤ w(T_{3}) = w(T_{2}) = w(T_{1}). Meanwhile, by the definition of T_{1}, w(T_{1}) ≤ w(T). Therefore, the theorem follows.

By Theorem 3.5, if a directed Steiner tree T of GC can be found, an exact solution for our problem then follows, because the transformation from T to the optimal multicast tree of G is straightforward. However, as shown in Lemma 3.1, finding T of GC is NP-complete. Instead, we focus on finding a polynomial approximation solution for the problem.

Let G(V, E) be a directed weighted graph with a source s and a destination set S (S ⊂ V), the objective is to find a directed approximation Steiner tree. There are several approximation algorithms for this problem [17, 15, 5], and among them, the most simple algorithm is based on the single source shortest path algorithm, which is presented as follows. Finding a shortest path P_{v} in G from s to v for each v ∈ S. Let P_{v_{1}}, P_{v_{2}},…, P_{v_{|S|}} be the sequence of the paths, sorted by their lengths in increasing order, where v_{i} ∈ S. Let T be an approximation Steiner tree. T = P_{v_{1}} and i = 1 initially. Repeat the following steps until all the paths are added to T: i = i + 1, add P_{v_{i}} to T, and remove those edges from P_{v_{i}} which introduce a cycle in T ∪ P_{v_{i}}. Obviously the solution obtained is within |S| times the optimum because the length of each shortest path is no more than the weighted sum of the links in the directed Steiner tree. Another sophisticated approach is described as follows. Construct a single source shortest path tree T′ rooted at s, then remove those leaves that are not in S until all the leaves in the resulting tree are in S. The final tree is an approximate directed Steiner tree of G. Clearly the time complexity for this latter approach is O(m + n log n) [6].

Recently Charikar et al [5] presented an efficient approximation algorithm for the directed Steiner tree problem. Their algorithm runs in time O(max{m+n log n, |S|n^{i}}), and delivers a solution which is (3i)^{i}|S|^{1/i} of the optimal where i ≥ 1 is a fixed integer. In other words, their algorithm runs in time O(m+n log n+n^{1/ϵ}|S|), and delivers a solution which is O(|S|^{ϵ}) optimal for any fixed 0 < ϵ ≤ 1. In summary, we have

Lemma 3.6. Let G(V, E) be a directed weighted graph with a source s and a destination set S (S ⊂ V), |V | = n and |E| = m, There is a simple algorithm for the directed Steiner tree problem which runs in O(m + n log n) time and delivers a solution within |S| times the optimum. There is also an efficient algorithm for this problem which runs in time O(|S|n^{1/ϵ}), and delivers a solution which is O(|S|^{ϵ}) of the optimal for any fixed 0 < ϵ < 1.

Following the above discussions, we have

Theorem 3.7. Given a directed network G = (V, E) with a given source s and a destination set S, assume that each link e of G has been assigned a set Λ(e) ⊆ Λ of available wavelengths, and a wavelength conversion function at each node has been given. There is an approximation algorithm for the optimal multicast tree problem which runs in time O(k^{2}n + km + kn log(kn)), and delivers a solution within |S| the optimal. There is another approximation algorithm for this problem which runs in time O(k^{2}n + km + (kn)^{1/ϵ}|S|), and delivers a solution within O(|S|^{ϵ}) of the optimal for any fixed 0 < ϵ < 1.

Proof. The construction of GC and the assignment of links in GC can be done in time O(k^{2}n + km) clearly. GC contains O(kn) nodes. Then, finding an approximate directed Steiner tree T in GC rooted at s′ including all nodes in S′ = {v′′ | v ∈ S} by the above simple algorithm and the algorithm due to Charikar et al [5]. T can be found either in time O(k^{2}n + km + kn log(kn)) with a cost of |S| optimal, or in time O((kn)^{1/ϵ}|S|) with the cost of O(|S|^{ϵ}) the optimal for any fixed 0 < ϵ < 1. Therefore, the theorem follows.

3.4. A distributed algorithm. Usually an optical network can be decomposed into two separate networks in functionality. One is called data network which is used to transfer large volume of data such as image data and databases etc, by its optical fibers. The other is called control network which is used for high level protocol controls such as finding an approximate optimal multicast tree and setting appropriate optical switches for every node in the tree. Because the size of the message used for these controls is usually not large, people make use of the electric network to implement high level protocol controls. Since we are dealing with a large wide area network, in practice it is not realistic to design a centralized algorithm to find an approximate optimal multicast tree for the network. Instead, a distributed algorithm seems more appropriate. In the following a distributed algorithm for the problem is proposed.

The proposed approach is to embed the ideal network GC into the physical network G and use G to simulate GC. In doing so we first show that the construction of GC has high locality, which is explained as follows. In the original network G(V, E), we construct a bipartite weighted graph G′_{v}(X′_{v}, Y′_{v}, E′_{v}, ω_{3}) for every node v ∈ V as follows. Let us recall the construction of G_{v}(X_{v}, Y_{v}, E_{v}, ω_{1}) for every v ∈ V_{M} = V. Now we construct another bipartite graph G′_{v} = (X′_{v}, Y′_{v}, E′_{v}, ω_{3}). If v ≠ s, then X′_{v} = X_{v}, Y′_{v} = Y_{v} ∪{v′′}, and E′_{v} = E_{v} ∪{⟨u, v′′⟩ | u ∈ X_{v}}, all links in E′_{v} − E_{v} are assigned weight zeros, i.e., ω_{3}(e) = 0 for every e ∈ E′_{v} − E_{v}; and ω_{3}(e) = ω_{1}(e) for every e ∈ E_{v}. Otherwise X′_{s} = X_{s} ∪ {s′}, Y′_{s} = Y_{s}, E′_{s} = E_{s} ∪ {⟨s′′, u⟩ | u ∈ Y_{s}}, and ω_{3}(e) = 0 for every e ∈ E′_{s} − E_{s}. However, ω_{3}(e) = ω_{1}(e) for every e ∈ E_{s}. Then, the auxiliary directed weighted graph GC = (V C, EC) can be constructed as follows. V C = ⋃_{v∈V} (X′_{v} ∪ Y′_{v}) and EC = ⋃_{v∈V} E′_{v} ∪ E_{org}. Note that the links in E_{org} are simulated by the physical links in E of G. Each physical link e ∈ E of G serves as |Λ(e)| links of GC. As a result, GC is constructed and presented distributively, i.e., each node v of G holds the adjacency lists of the nodes of GC in G′_{v}. Then, the optimal multicast tree problem on G then becomes a directed Steiner tree problem on GC with a given source s′ and a destination set S′ = {v′′ | v ∈ S}. Now we use G to simulate GC, i.e., each node of G actually represents a subgraph of GC. The Steiner tree problem on undirected graphs has been well studied in the distributed computing environments, and there are many efficient distributed algorithms for it such as the algorithm by Kompella et al. [12]. However, these algorithms for undirected graphs are not appropriate for our case in which a directed Steiner tree is required. Here we make use of the distributed algorithm for finding a shortest path between a pair of nodes by Chandy and Misra [2], which runs in time O(n′) using O(m′) messages in a network H with n′ nodes and m′ links. Actually the result delivered by their algorithm is a single source shortest tree rooted at the source. Therefore we have

Theorem 3.8. Given a directed network G = (V, E) with a given source s and a destination set S, assume that each link e of G has been assigned with a set Λ(e) ⊆ Λ of available wavelengths, and every node has been given a wavelength conversion function. There is a distributed, approximation algorithm for finding the optimal multicast tree on G. The communication and time complexities of the algorithm are O(km) and O(kn) respectively, and the solution delivered is |S| times the optimum.

Proof. First we construct the directed weighted graph GC which takes O(1) time because the local computation is negligible in the distributed computing environment. Then we make use of the algorithm of Chandy and Misra [2] to find a single source shortest path tree T in GC rooted at s′. This step requires O(kn) time and O(km) messages since GC contains O(kn) nodes. Note that the links in ⋃_{v∈V} E_{v} are not taken into account because they are inside of nodes, so, O(k^{2}n) messages in this step are reduced. Finally we remove all leaves that are not in S′ = {v′′ | v ∈ S} from T. This step requires O(kn) time and O(kn) messages because T is a tree. Clearly the solution obtained is |S| times the optimum.

4. Implementation Issue. In this section we conduct experiment to verify the applicability of the proposed approximation algorithm. We start with a sparse connected graph G(V, E). Assume that the number of edges in G is no more than 3n and the number of nodes in it is n. There are 4 different wavelengths associated with each edge. The machine used is SUN Ultra SPARC with 248MHz CPU. The experimental results are presented below.

Figure 4.1 shows the three cases where ϵ = 0.25, ϵ = 0.5 and ϵ = 0.8. That is, the solution obtained is |S|^{ϵ} times of optimal. Assume that the number of nodes in S is ⌈n^{0.25}⌉.

Fig. 4.1. The approximation solution with |S| = ⌈n^{0.25}⌉.

Figure 4.2 considers the three cases where ϵ = 0.25, ϵ = 0.5 and ϵ = 0.8, and the number of nodes in S is ⌈n^{0.5}⌉.

Finally, Figure 4.3 considers the three cases where ϵ = 0.25, ϵ = 0.5 and ϵ = 0.8, and the number of nodes in S is ⌈n^{0.8}⌉.

¿From the experiments conducted above, we conclude that the time spent to find a solution is

Fig. 4.2. The approximation solution with |S| = ⌈n^{0.5}⌉.

Fig. 4.3. The approximation solution with |S| = ⌈n^{0.8}⌉.

proportional to the accuracy of the solution, i.e, more accurate solutions are required, more time for finding such a solution is needed.

5. Conclusion. In this paper we have formalized the optimal multicast tree problem in wide area WDM networks in terms of the sum of the cost of using wavelengths on links and the cost for doing wavelength conversion at nodes if necessary. We have also given an approximation algorithm and a distributed algorithm for it through a reduction which reduces the problem to a directed Steiner tree problem on an auxiliary directed weighted graph. As a result, any approximation solution for the directed Steiner tree problem gives an approximation solution with the same degree accuracy for our problem.

Acknowledgments. We thank the anonymous referees for their invaluable suggestions and comments which help us improve the paper’s quality and presentation. Partial contents of this paper also appeared in [14].

REFERENCES

[1] F. Bauer and A. Varma, ARIES: a rearrangeable inexpensive edge-based on-line Steiner algorithm, IEEE Journal on Selected Areas in Communications, 15 (1997), pp. 382–397.

[2] K. M. Chandy and J. Misra, Distributed computations on graphs: shortest path algorithms, Commun. ACM, 25 (1982),pp. 833–837.

[3] I. Chlamtac, A. Faragó, and T. Zhang, Lightpath (wavelength) routing in large WDM networks, IEEE Journal on Selected Areas in Communications, 14 (1996), pp. 909–913.

[4] I. Chlamtac, A. Ganz, and G. Karmi, Lightpath communications: a novel approach to high bandwidth optical WDN’s, IEEE Trans. Commun., 40 (1992).

[5] M. Charikar, C. Chekuri, A. Goel, and S. Guha, Approximation algorithms for directed Steiner tree problems, TR: CS-TN-97-56, Dept. of Computer Sci., Stanford University, March, 1997.

[6] T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA, [7] C. Diot, W. Dabbous, and J. Crowcroft, Multipoint communication: a survey of protocols, functions, and

mechanism, IEEE Journal on Selected Areas in Communications, 1997), pp. 277–290.

[8] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP–Completeness, W. H. Freeman, 1979.

[9] E. Gelenbe, A. Ghanwani, and V. Srinivasan, Improved neural heuristics for multicast routing, IEEE Journal on Selected Areas in Communications, 15 (1997), pp. 147–155.

[10] B. K. Kadaba and J. M. Jaffe, Routing to multiple destinations in computer networks, IEEE Trans. Commun., 31 (1983), PP. 343–351.

[11] V. P. Kompella, J. C. Pasquale, and G. C. Polyzos, Multicast routing for multimedia communication, IEEE/ACM Trans. Networking, 1 (1993), pp. 286–292.

[12] V. P. Kompella, J. C. Pasquale, and G. C. Polyzos, Two distributed algorithms for the constrained Steiner tree problem, Proc. 2nd Int’l. Conf. Comput., Commun. and Networks, San Diego, CA, 1993.

[13] W. Liang, G. Havas and X. Shen, Improved lightpath (wavelength) routing in large WDM networks, Proc. 18th Int’l. Conf. on Distributed Computing Systems, Amsterdam, IEEE Computer Society Press, 1998, pp. 516–523.

[14] W. Liang and H. Shen, Multicast broadcasting in large WDM networks, Proc. 12th Int’l Conf. on Parallel Processing Symposium, Orlando, IEEE Computer Society Press, 1998, pp. 365–369.

[15] S. Ramanatan, An algorithm for multicast tree generation in networks with asymmetric links, Proceedings of IEEE INFOCOM’96, 1996, pp. 337–344.

[16] G. N. Rouska and I. Baldine, Multicast routing with end-to-end delay and delay variation constraints, IEEE Journal on Selected Areas in Communications, 15 (1997), pp. 346–356.

[17] S. Voss, Worst-case performance of some heuristics for Steiner’s problem in directed graphs, Info. Proc. Lett., 48 (1993), pp. 99–105.

Edited by: Yi Pan Received: March 30th, 1999 Accepted: November 16th, 1999