Over the last few years, the increase in bandwidth-intensive multicast applications such as HDTV, video conferencing, interactive distance learning, live auctions, and distributed games has driven an enormous increase in the volume of Internet traffic [1, 2]. Such explosive growth in traffic has led to an increase in the energy consumed by networks. Baliga et al. have estimated such consumption to be about 4% of the total energy consumed in broadband-enabled countries [3]. As a result, energy efficiency is now an important factor in network design and operation.

Wavelength-division multiplexing (WDM) has developed as a technology to support bandwidth-intensive multicast applications by establishing a lighttree to transmit data from one source node to multiple destination nodes. However, failure of a single fiber on the light-tree will disrupt the transmission of information to several destination nodes. Thus, multicast survivability is important in WDM networks. Several studies have proposed protection schemes to reduce network energy consumption [4-7]. In the proposed schemes, the devices used in the protection paths switch into sleep mode and promptly wake up when a failure occurs. For example, [4] found that a significant reduction in energy consumption could be achieved by using a provisioning solution that packed the working and protection paths into different fibers. However, the schemes proposed in such studies did not consider multicast traffic.

Various schemes have been proposed to protect against link failure in multicast networks, including tree-based [8], link-based, and segment-based protection [9]. Tree-based protection finds two link-disjoint light trees that start from the same source and end at the same destination nodes. Link-based and segment-based protection schemes respectively provide protection paths for each link and segment on the working tree. In [10], the authors proposed a multicast protection scheme through spanning paths (MPSP) to reduce the total bandwidth allocation. However, network energy consumption was not taken into account in the design of such multicast algorithms. Reference [11] proposed a green multicast grooming algorithm (GMG) based on dedicated spanning path protection. However, the authors did not consider the use of spare capacity that could be shared between different multicast connections.

The objective of this paper is to design a multicast algorithm for reducing energy consumption in survivable WDM networks while sharing spare capacity. In order to do this, we define two link cost functions, one for the working path and another for the protection path. The two link cost functions used in the routing procedure allow the proposed algorithm to pack the working and protection paths into different fibers to increase both the number of sleeping fibers and the amount of spare capacity that is shared. The proposed algorithm is then evaluated in terms of the number of sleeping fibers, energy consumption, and blocking probability.

The rest of this paper is organized as follows: Section 2 introduces conventional multicast algorithms. Section 3 details the proposed energy-efficient multicast algorithm (EEMA) for survivable WDM networks. In Section 4, the proposed algorithm is evaluated through a simulation, and the conclusions are given in Section 5.

Data can be transmitted in various ways on a network: by unicasting, broadcasting, anycasting, or multicasting. In multicasting, the same information is sent to a group of nodes, and upon the arrival of a multicast request, a light-tree is established to transmit the traffic. The light-tree is an extension of the concept of a light path, incorporating multicasting capabilities [12]. A light-tree for a multicast session can be derived from the Steiner tree problem, in which a minimum cost light-tree should be found, and since the Steiner tree problem is NP-complete [13], a number of heuristic algorithms have been proposed. These algorithms can be categorized into three groups: minimum path heuristics (MPH), spanning tree-based heuristics (STH), and metaheuristics. The MPH algorithm repeatedly includes the closest new destination node in the partially built light-tree until all destination nodes have joined the tree [14, 15]. The STH algorithm is a fast algorithm that first constructs a closure graph of the multicast nodes from the original graph by using the cost of the shortest path between each source or destination pair [14]. The closure graph is then used to obtain a minimum spanning tree. Then, the shortest paths from the original graph are used to replace the edges of this minimum spanning tree. Finally, the algorithm removes any cycles to obtain the multicast tree. Metaheuristics, such as simulated annealing [15], genetic algorithms [16], and Tabu search [17], have also been investigated to solve the Steiner tree problem. In this paper, an MPH heuristic algorithm is used to search for the working tree, because such an algorithm guarantees minimum cost paths.

To improve network reliability, a protection tree is established to transmit traffic when a link failure occurs. Several approaches have been proposed in the literature [8-11] to improve network reliability. In [8], the authors propose a multicast tree-based protection scheme that protects a working tree by deriving a link-disjoint protection multicast tree. Two trees are said to be link-disjoint if they do not have any links in common. When a link failure occurs, the destination nodes that are affected reconfigure their switches so that data can be received from the protection tree. The drawback of using this scheme is that in many cases, it is difficult to find two link-disjoint light-trees. In [9], the authors investigated the use of link-based and segment-based protection schemes. A segment is defined as the sequence of edges from the source or from any splitting node, to a leaf node or a splitting node on the working tree. In [10], the authors proposed a spanning path-based protection scheme. A spanning path is a path from a leaf node to any other leaf node in the working tree; this scheme can reduce resource allocation, compared to link-based or segment-based protection. The protection schemes are divided into dedicated protection and shared protection schemes. In a dedicated protection scheme, a spare resource is specifically allocated for a particular working path. In a shared protection scheme, network resources along a protection path are reserved for multiple working paths when considering a single link failure. This implies that a shared protection scheme has higher capacity efficiency than a dedicated protection scheme.

Capacity-sharing schemes for multicast networks can be classified into three categories: self-sharing intrarequest sharing, and interrequest sharing [10]. Self-sharing schemes involve sharing capacity between the working and protection paths of the same multicast. In Fig. 1, the multicast is (0, {5, 3}), where node 0 is the source node. The working-tree is {0-1-2-3, 0-5} and the protection paths are {0-1-5, 0-5-4-3}. The links (0-1) and (0-5) can be shared. An intrarequest sharing scheme shares link capacity among the protection paths of the same multicast connection. In Fig. 2, the multicast request is {0, {5, 3}}. The protection paths for working-paths (0-1-5) and (0-1-2-3) are (0-5) and (0-5-4-3), respectively. The capacity on link 0-5 can be shared by the two protection paths. Interrequest sharing is capacity sharing among protection paths of different multicast connections. In Fig. 3, there are two multicast connections: {0, {5, 3}} and {3, {0, 4}}. The capacity of links 0-5 and 5-4 can be shared by two multicast connections.

In [10], the authors proposed a multicast protection scheme through spanning paths (MPSP). The key idea of MPSP is focused on minimizing the total bandwidth allocation by identifying a protection path for each spanning path to appropriately select the parts of these protection paths that form a protection tree. In this case, the scheme proposed by the authors considered self-sharing, intrarequest sharing, and interrequest sharing. However, this algorithm did not consider the energy consumed by the network.

In [11], the authors proposed a green multicast grooming algorithm based on spanning path dedicated protection (GMG) that considered the energy consumption of the network. This scheme dynamically adjusts the link cost to search for working and protection paths to decrease energy consumption. However, this method does not share spare capacity among the different multicast connections.

In this paper, a multicast request is accepted if both a working and a protection tree are available. The energy-efficient routing and resource allocation problem for a multicast in a survivable WDM network is formulated as follows. The given network is denoted as G (N, L), where N is the node set and L is the link set. R_i, (s_i, D_i, b_i, Δt_i) denotes the i^th multicast request with required bandwidth b_i from the source node s_i to the destination node set D_i with a request holding time of Δt_i . The energy consumption of a router port, a transceiver, and an amplifier are denoted as E_r, E_t and E_a respectively. The remaining notations are defined as follows.

l(∈ L): a link of network G : holding time of ∂th wavelength on link l hlholding time of the fiber on link l if the state of ∂th wavelength on link l is P or U; otherwise, . xlxl = 0 if the state of the fiber on link l is P or U; otherwise, xl = 1. Al: The number of amplifiers on link l WTi: Working tree for multicast request Ri PTi: Protection tree for multicast request Ri : The jth spanning path on WTi : Protection path for , where and are link-disjoint : Residual capacity on link l : Sharable spare capacity on link l Sl: Sl = 1 if link l has sharable spare capacity; otherwise, Sl = 0. α: Weight factor : Relative link cost of l to search for the working tree : Relative link cost of l to search for the protection path ACl: Absolute link cost of l , where ACl is the physical length of link l ε: Small value to encourage spare capacity sharing wl, pl, ml, ul: Binary variables {0, 1}, ul = 0 if the state of link l is U; otherwise, ul = 1.

This paper assumes that a link is in one of four states: dedicated working path (w), dedicated protection path (p), mixed working and protection path (m), or unused (u). The energy consumed by devices in a p or u state can be neglected, because devices used exclusively in protection paths are switched into sleep mode in survivable optical WDM networks. The total energy required by the network is consumed by three of its parts: the transceiver, router port, and amplifier. The number of amplifiers on a specific link l is A_l = [d_l / d₀] + 2, where d_l is the length of fiber link l , d₀ is the distance between two adjacent amplifiers, and the number 2 indicates there are two amplifiers allocated at the ends of a fiber link. Therefore, the energy consumed by the network (E) can be defined as Eq. (1).

When a multicast request arrives, a working tree WT_i and its corresponding protection tree PT_i, which is a set of protection paths, must be computed. To decrease energy consumption, the working and protection paths should be allocated to different fibers to increase the number of fibers in sleep mode. The working paths should be packed into fibers with more working paths, and the protection paths should be packed into fibers with more protection paths. To achieve this, two link-cost functions are defined to calculate the dynamic link-costs and to find the working and the protection paths.

Before the working tree is computed, the link-costs in the network are adjusted according to Eq. (2). If the residual capacity of a link is less than the required bandwidth, the link-cost will be set to infinity. If the link has enough residual capacity, we define the link-cost to be adaptively adjusted according to the link-state. In Eq. (2), the cost of the link with a state p increases α times, while the cost of the link with a state of w decreases α times. Therefore, we define the link cost function for a new working path so as to increase the cost of candidate links under state p and decrease the cost of the candidate links under state w. The purpose of this function is to pack the working paths into the links with more working paths to save energy.

Before the protection path is computed for a specific spanning path , the cost of the links on the spanning path is set to infinity, to satisfy the link-disjoint constraint. Then the link- costs are adjusted according to Eq. (3), and if the summation of sharable and residual capacities on a link is less than the required bandwidth, the link-cost is set to infinity to avoid selection. To increase the spare capacity that is shared, Eq. (3) sets a very small value of ε(ε = 0.01) for links with sharable capacity. If the link does not have sharable capacity, the link-cost is dynamically adjusted according to its link state. In Eq. (3), the cost of a link in state w increases α times, while the cost of a link in state p decreases α times. The purpose of this function is to pack the protection paths into the links with more protection paths to use resource efficiently and reduce energy consumption.

This section uses the flowchart shown in Fig. 4 to introduce the details of the EEMA algorithm. The EEMA (Energy-Efficient Multicasting Algorithm) generates an auxiliary graph to search for the working and protection trees. If a new request arrives, the EEMA uses the FINDROUTE function to compute the working and protection trees. If a route for the multicast request is successfully found, the EEMA allocates resources to each link on the working and protection trees and updates the auxiliary graph. Here resource allocation includes both wavelength and bandwidth allocation, and the request is blocked if the EEMA cannot find a working tree or a protection tree for the multicast request.

3.3.1. Multicast Routing

This subsection explains how to select working and protection trees for a dynamic multicast request, with the objectives of reducing energy consumption and improving sharing of spare capacity. The routing procedure for the EEMA shows “FINDROUTE” in Fig. 5. When the multicast request arrives, the EEMA adjusts the link-cost according to Eq. (2) and computes a working tree WT_i , using an MPH algorithm [10]. Then, the EEMA divides the working tree into several spanning-paths, adjusts the link-cost according to Eq. (3), and uses Dijkstra’s algorithm to compute a protection path for each spanning-path. Then, a minimum-cost protection tree is constructed using the Minimum-Cost Spanning Tree algorithm.

Figure 6 shows an example illustrating the routing procedure for the EEMA. Figure 6(a) shows the physical topology in which a multicast R₁(0, {2,3}) has been established. The auxiliary graph (AG) has nodes and links that correspond to the nodes and links in the physical graph G, and AG is generated to search for the working and protection trees. Each link in AG has a link- state and a link-cost, as shown in Fig. 6(b). Assuming that the multicast request R₂(0, {3,4}) arrives and needs to be established, the first step is to find a working-tree. The link- costs are adjusted according to Eq. (2). The result is shown in Fig. 6(c), where the weighting factor α is 8 and the working tree is {(0-3), (3-4)}, as shown in Fig. 6(d). The second step is to derive a set of spanning paths where θ is the node degree and N_θ = 1 is the set of nodes on the working tree with node degree 1. Each node pair in N_θ = 1 is considered as a spanning path. In this example, N_θ = 1 = {0, 4} and the spanning path is 0-3-4. The third step is to compute a protection- tree, formed by a set of protection paths. Here, the basic idea is to compute a protection path for each spanning path, deleting the ones that overlap, to form a minimum cost protection tree. Before searching for the protection path, the link costs in AG are adjusted and the cost of the link in the corresponding spanning path is set to infinity to satisfy the link-disjoint constraint, such as 0-3 and 3-4. Figure 6 shows the procedure for computing link cost and deciding the route of the second source and destination pair, after establishing the route of the first source and destination pair. The cost of a link in state u is initialized to 1 and the cost of a link in state p is changed to 0.125, according to Eq. (3). Finally, the EEMA decides on the least-cost path as a protection path, as shown in Fig. 6(f).

3.3.2. Resource Allocation and Release

After the working and protection trees have been computed for the multicast request, the wavelength and bandwidth for both trees need to be allocated. To allocate resources for the working tree, the EEMA assigns a wavelength by using a first-fit scheme [17, 18] for each link of the tree, and then assigns the required b units of bandwidth as the working capacity. To allocate resources for the protection tree, EEMA assigns units of bandwidth for each link of the tree. The pseudo-code to calculate is shown in Fig. 7. The EEMA then checks whether the link has a sharable spare capacity. If the sharable spare capacity is larger than the required bandwidth, this link does not need any additional bandwidth. But the EEMA allocates units of bandwidth for protection capacity on the chosen wavelength if the sharable capacity is less than b.

Whenever a multicast connection drops from the network, the wavelength and bandwidth allocated to the working and protection trees need to be released. The procedure to release these resources is comprised of two parts: releasing the resources on the working tree, and releasing those on the protection tree. For the working tree, the EEMA simply releases the allocated bandwidth for each link. For the protection tree, the procedure is more complex: To release the resources on each link of the protection tree, a minimum needed-protection capacity MNC_l is calculated. Assume that l is the link of the protection tree PT that needs to be released, and that the protection capacity of PT is b units, carried by wavelength λ_k. MNC_l is calculated according to Eq. (4), where is the working capacity on link l′ protected by link l using wavelength λ_k. Let be the protection bandwidth reserved on link l using wavelength λ_k. If , the protection capacity on link l can maintain network survivability after releasing b units of capacity, and the EEMA releases b units of protection capacity as residual capacity. If , the protection capacity on link l cannot be released.

3.3.3. Failure Restoration Procedure

If a link failure occurs in the working tree, the multicast request is restored using the protection paths that were derived. This subsection uses an example to describe how to restore a failed multicast request. When a link failure occurs, the working tree is divided into two parts, M1 and M2. M1 stores the nodes that are not affected by the link failure, while M2 stores the nodes that are affected. A protection path is selected to connect M1 to M2.

Figure 8(a) shows an example where the working tree is (0, {2, 5}) and the protection tree is {0-5, 5-4-2}. If link 0-1 fails, the working tree is divided into M1 = {0} and M2 = {1, 5, 2}, and the working tree is reconfigured as shown in Fig. 8(b). Figures 8(c) and 8(d) illustrate how to restore the multicast request when a failure occurs on links 1-2 and 1-5 respectively.

The proposed algorithm and conventional algorithms were evaluated over an NSF network with 14 nodes and 21 links. This paper assumes that each node has full wavelength conversion and splitting capability, each link is comprised of only one fiber, and each fiber carries two bidirectional wavelength channels. The bandwidth for each wavelength is OC-48. The idle or the protection devices in network are switched into sleep mode, and their energy consumption is negligible. The energy consumption of the active devices is set according to [11], as shown in Table 1.

10,000 multicast demands are generated according to a Poisson distribution with average arrival rate λ. The holding time of each multicast follows a negative exponential distribution with mean 1/μ. For simplicity, μ is set to 1. Thus, the network load becomes λ Erlang. The required bandwidth for each multicast is fixed to OC-1.

The performance of the proposed algorithm is evaluated in terms of its blocking probability, average energy consumption (AEC), and protection bandwidth ratio (PBR), as defined below.

Blocking probability: the ratio of the number of multicast requests that are blocked to the number of all multicast requests that have arrived.

AEC: the ratio of the total network energy consumption (E) to the number of serving demands (N_s).

PBR: the ratio of the bandwidth reserved for the protection path P_b to the total allocated bandwidth, as shown in (6), where W_b is the bandwidth allocated for the working path. A smaller value of PBR can be seen to indicate a higher degree of resource sharing,

The simulation model is implemented using OPNET Modeler 14.5 running on Windows 7 Professional with a 2.8 GHz CPU and 4 GB of RAM. OPNET has a three-tiered hierarchy that consists of a network domain, node domain, and process domain. The node model specifies an object in the network domain, and the process model specifies an object in the node domain. The OPNET simulation is event-driven; the simulation time advances when an event occurs. Events can be generated by BEGSIM/ENDSIM interrupts, self-interrupts, or packet arrivals. In OPNET, discrete events and continuous models are created using an object-oriented paradigm in Visual Basic, C, or Visual C++.

The EEMA is executed on a mesh network with 14 nodes and 21 links, as shown in Fig. 9. Two kinds of nodes can be seen in this figure: a control node (node 15), and 14 mesh nodes (nodes 1-14). The control node generates multicast requests and runs the EEMA algorithm. The process model for the control node in Fig. 10 includes five states: Init, Generate_req, Routing, Allocate_resource, and Release_resource. The function of each state is described as follows.

Init obtains the topology information, which includes the number of links, the link length, and the number of wavelengths per fiber.

Generate_req generates a multicast request, including its source, destination, and holding time.

Routing searches the working and protection trees for multicast requests, using the EEMA algorithm.

Allocate_resource allocates wavelength and bandwidth for each link on the working and protection trees.

Release_resource releases the wavelength and bandwidth of each link on the working and protection trees.

Figure 11 compares the average number of sleeping fibers for MPSP (Multicast Protection Scheme through Spanning paths), GMG (Green Multicast Grooming), and the EEMA (Energy-Efficient Multicasting Algorithm). The average number of sleeping fibers for the EEMA and GMG are higher than that for MPSP, because the EEMA and GMG gather more protection paths into sleeping fibers. The number of sleeping fibers for the EEMA is higher than that for GMG because the EEMA shares the spare capacity of the links among different multicast connections.

Figures 12-14 show the average energy consumption of the core router, transceiver, and amplifier, respectively. The AEC of the core router is 90% of the total energy consumption which implies that the core router is the main consumer of energy. The AEC of the core router, transceiver, and amplifier for EEMA are lower than those for MPSP and GMG. This is because the EEMA increases the number of sleeping fibers and switches the router ports, transceivers, and amplifiers on those fibers into sleep mode to reduce energy consumption.

Figure 15 presents the average energy consumption for MPSP, EEMA, and GMG. The AEC for the EEMA can be seen to be lower than those for MPSP and GMG at all times. The EEMA gathers the working and protection paths into different fibers to increase the number of sleeping fibers and the spare capacity that is shared. The EEMA can save up to 26% and 12% of energy, compared to MPSP and GMG, respectively, and the energy savings is larger under higher traffic load. This implies that the number of shared links for the EEMA increases under a heavy traffic load.

Figure 16 shows the average number of hops for MPSP, EEMA, and GMG. The average number of hops for the EEMA and GMG are higher than that for MPSP because the EEMA and GMG choose a route with more active fibers as the working path, and choose a route with more sleeping fibers as the protection path, while MPSP always chooses the shortest paths. Figure 17 clearly shows that the blocking probability for the EEMA is higher than that for MPSP, because the protection paths of EEMA are allocated to longer routes that use sleeping fibers, as shown in Fig. 16. Figure 17 shows that the blocking probability for the EEMA is lower than that for GMG. The EEMA considers interrequest sharing to increase resource utilization. As shown in Fig. 18, the PBR for the EEMA is lower than that for GMG, which indicates that the EEMA has a higher degree of capacity sharing. Figures 19 and 20 compare the AEC and blocking probability of the EEMA based on the weight factor. As the figures suggest, with an increase in weight factor, the AEC decreases, while the blocking probability increases. Since more protection paths are collected into sleeping fibers, more devices enter the sleep state.

In this paper, we have proposed an energy-efficient multicast algorithm (EEMA) to achieve efficient routing and bandwidth allocation in survivable WDM networks. The working and protection paths of a multicast request are selected using two link-cost functions, defined by taking into account energy consumption. The proposed link-cost functions allow EEMA to pack working and protection paths into different fibers and switches, so that more components enter sleep mode. The proposed algorithm was compared to the conventional multicast algorithms MPSP and GMG. The results showed that the EEMA increased both the number of sleeping fibers and the amount of spare capacity. These resulted in decreasing energy consumption. Compared to conventional MPSP and GMG, the EEMA saved up to 26% and 12% of the energy consumed, respectively.