One-to-many multicast restoration based on dynamic core-based selection algorithm in WDM mesh networks

This paper proposes a novel dynamic core-based selection (DCS) algorithm for the multicast restoration in WDM mesh networks. The core-based fault tolerance scheme provides a flexible way to control a number of core nodes with less control overheads for searching the routing path, wavelength assignment (RWA), and restoration paths when fault occurs in the one-to-many multicast domain. Compared with the source-based scheme, core-based schemes are easier to maintain, and specifically scalable in large-scale topologies. In the core-based fault tolerance scheme, k-tuple domination nodes are selected to form a minimum sized vertex subset such that each vertex in the graph is dominated by at least k vertices, where the k is defined as two in this paper. The proposed DCS algorithm is defined as each node in multicast tree session must be directly connected to at least one core node in multicast tree session and also has to be directly connected to at least one core node out of multicast tree session. The primary aim of this work is to provide the scalable and fast local survivability based on the information from core nodes. Simulation results show that the proposed algorithm outperforms the Dual Tree and MRLR algorithms in terms of total hop counts needed for all recovery paths and blocking probability for different network topologies.     

Wavelength assignment for multicast in all-optical WDM networks with splitting constraints

Multicast is an important application in all-optical WDM networks. The wavelength assignment problem for WDM multicast is to assign a set of wavelengths to the links of a given multicast tree. In an all-optical WDM network without wavelength conversions, wavelength assignment is the key to guarantee the quality of service and to reduce communication costs. In this paper, we study wavelength assignment for WDM multicast with two criteria, to cover the maximum number of destinations, and to minimize the wavelength costs. The computational complexity of the problem is studied. Three heuristic algorithms are proposed and the worst-case approximation ratios for some heuristic algorithms are given. We also derive a lower bound of the minimum total wavelength cost and an upper bound of the maximum number of reached destinations. The efficiency of the proposed heuristic algorithms and the effectiveness of the derived bounds are verified by the simulation results.     

Minimizing the Number of Multicast Transmissions in Single-Hop WDM Networks

The problem of minimizing the number of transmissions for a multicast transmission under the condition that the packet delay is minimum in single-hop wavelength division multiplexing (WDM) networks is studied in this paper. This problem is proved to be NP-complete. A heuristic multicast scheduling algorithm is proposed for this problem. Extensive simulations are performed to compare the performance of the proposed heuristic algorithm with two other multicast scheduling algorithms, namely, the greedy and no-partition scheduling algorithms. The greedy algorithm schedules as many destination nodes as possible in the earliest data slot. The no-partition algorithm schedules the destination nodes of a multicast packet to receive the packet in the same data slot without partitioning the multicast transmission into multiple unicast or multicast transmissions. Our simulation results show that (i) an algorithm which partitions a multicast transmission into multiple unicast or multicast transmissions may not always produce lower mean packet delay than the no-partition algorithm when the number of data channels in the system is limited and (ii) the proposed heuristic algorithm always produces lower mean packet delay than the greedy and the no-partition algorithms because this algorithm not only partitions a multicast transmission into multiple unicast or multicast transmissions to keep the packet delay low but also reduces the number of transmissions to conserve resources.     

Multicast routing and wavelength assignment with delay constraint in WDM networks with sparse wavelength conversions

With the developments in multimedia and other real-time group applications, the question of how to establish multicast trees satisfying Quality-of-Service (QoS) requirements is becoming a very important problem. In this paper, multicast routing and wavelength assignment with delay constraint (MCRWA-DC) in wavelength division multiplexing (WDM) networks with sparse wavelength conversions is studied. We propose a colored multigraph model for the temporarily available wavelengths. Based on this colored multigraph model, two heuristic algorithms are proposed to solve the MCRWA-DC problem. The proposed algorithms have the following advantages:(1) finish multicast routing and wavelength assignment in one step; (2) the total cost of the multicast tree is low; (3) the delay from the source node to any multicast destination node is bounded; and (4) locally minimize the number of wavelength conversions and the number of different wavelengths used to satisfy a multicast request. Simulation results show that the proposed algorithms work well and achieve satisfactory blocking probability.     

Hypo-Steiner heuristic for multicast routing in all-optical WDM mesh networks

In sparse light splitting all-optical WDM networks, the more destinations a light-tree can accommodate, the fewer light-trees and wavelengths a multicast session will require. In this article, a Hypo-Steiner light-tree algorithm (HSLT) is proposed to construct a HSLT light-tree to include as many destinations as possible. The upper bound cost of the light-trees built by HSLT is given as N(N − 1)/2, where N is the number of nodes in the network. The analytical model proves that, under the same condition, more destinations could be held in a HSLT than a Member-Only (Zhang et al., J. Lightware Technol, 18(12), 1917–1927 2000.) light-tree. Extensive simulations not only validate the proof but also show that the proposed heuristic outperforms the existing multicast routing algorithms by a large margin in terms of link stress, throughput, and efficiency of wavelength usage.     

Multicast wavelength assignment with sparse wavelength converters to maximize the network capacity using ILP formulation in WDM mesh networks

In general, multicast routing and wavelength assignment (MC-RWA) can be subdivided in routing and wavelength assignment issues in wavelength-division multiplexing (WDM) mesh networks. Previous studies on WDM multicast have mainly focused on WDM multicast routing. The multicast wavelength assignment problem is studied in this paper. A unicast routing path can be established by a lightpath in an all-optical network. However, in the multicasting case, a multicast routing tree can be established by a single light-tree or several lightpaths, or a combination of several light-trees and lightpaths. We propose a wavelength assignment algorithm for finding an optimal combination of lightpaths and light-trees to construct a newly required multicast session. First of all, two cost functions are given to evaluate the establishing cost for each feasible wavelength, and then find a set of wavelengths that covers all destinations with the minimal cost using Integer Linear Programming (ILP) formulation. We focus on maximizing the total number of users served in a multicast session and the network capacity. The simulation results show that the proposed algorithm can improve system resource utilization and reduce the blocking probability compared with the First-Fit algorithm.This research was partially supported by the Grant of National Science Council, R.O.C. (NSC 94-2745-E-155-007-URD).     

Algorithms for precomputing constrained widest paths and multicast trees

We consider the problem of precomputing constrained widest paths and multicast trees in a communication network. Precomputing and storing of the relevant information minimizes the computational overhead required to determine an optimal path when a new connection request arrives. We evaluate algorithms that precompute paths with maximal bandwidth (widest paths), which in addition satisfy given end-to-end delay constraints. We analyze and compare both the worst case and average case performance of the algorithms. We also show how the precomputed paths can be used to provide computationally efficient solutions to the constrained widest multicast tree problem. In this problem, a multicast tree with maximal bandwidth (widest multicast tree) is sought, which in addition satisfies given end-to-end delay constraints for each path on the tree from the source to a multicast destination.     

Efficient routing and wavelength assignment for multicast in WDMnetworks

The next generation multimedia applications such as video conferencing and HDTV have raised tremendous challenges on the network design, both in bandwidth and service. As wavelength-division-multiplexing (WDM) networks have emerged as a promising candidate for future networks with large bandwidth, supporting efficient multicast in WDM networks becomes eminent. Different from the IP layer, the cost of multicast at the WDM layer involves not only bandwidth (wavelength) cost, but also wavelength conversion cost and light splitting cost. It is well known that the optimal multicast problem in WDM networks is NP-hard. In this paper, we develop an efficient approximation algorithm consisting of two separate but integrated steps: multicast routing and wavelength assignment. We prove that the problem of optimal wavelength assignment on a multicast tree is not NP-hard; in fact, an optimal wavelength assignment algorithm with complexity of O(NW) is presented. Simulation results have revealed that the optimal wavelength assignment beats greedy algorithms by a large margin in networks using many wavelengths on each link such as dense wavelength-division-multiplexing (DWDM) networks. Our proposed heuristic multicast routing algorithm takes into account both the cost of using wavelength on links and the cost of wavelength conversion. The resulting multicast tree is derived from the optimal lightpaths used for unicast     

光组播路由代价与波长使用量的联合优化方法

为解决光组播路由中组播中路由代价和波长资源消耗单一化造成的组播路树路由的代价过高问题,在分光节点约束条件下,提出了光组播路由代价与波长使用量联合优化的长路优先(LPF)方法和短路优先(SPF)方法。算法通过检查最小光组播树是否存在节点分光约束的问题,根据设置的波长使用代价控制因子,使LPF或SPF的路由代价和波长使用量最小。LPF方法首先选择组播树最长路径或新波长通道重路由受分光约束的目的节点,SPF方法先选择组播树中最短路径或新波长通道重路由受分光约束的目的节点,仿真结果表明,本文提出的两种联合优化方法都能实现路由代价较低和波长需求较少的目的。     

Dynamic group multicast routing with bandwidth reservations

Multicasting refers to the transmission of data from a source node to multiple destination nodes in a network. Group multicasting is a generalization of multicasting whereby every member of a group is allowed to multicast messages to other members that belong to the same group. The routing problem in this case involves the construction of a set of low cost multicast trees with bandwidth requirements, one for each member of the group for multicasting messages to other members of the group. In this paper, we examine this routing problem with an additional requirement that member nodes are allowed to join and leave the multicasting group anytime during a session. We call this problem, the dynamic group multicast routing problem (DGMRP). In this paper, we proposed three heuristic algorithms to generate a set of low cost multicast trees with dynamic group membership. Results from our empirical study shows that the one of the proposed algorithms, called Maximum bandwidth bottleneck path selection algorithm (MBBPS), achieves better utilization of bandwidth resources as compared with the other two algorithms which are based on a greedy approach. In addition MBBPS performs better in terms of cost when the bandwidth is not sufficient in the network. Copyright © 2002 John Wiley & Sons, Ltd.     

Link-State-Based Algorithms for Dynamic Routing in All-Optical Networks with Ring Topologies

The increased usage of large bandwidth in optical networks raises the problems of efficient routing to allow these networks to deliver fast data transmission with low blocking probabilities. Due to limited optical buffering in optical switches and constraints of high switching speeds, data transmitted over optical networks must be routed without waiting queues along a path from source to destination. Moreover, in optical networks deprived of wavelength converters, it is necessary for each established path to transfer data from source to destination by using only one wavelength. To solve this NP-hard problem, many algorithms have been proposed for dynamic optical routing like Fixed-Paths Least Congested (FPLC) routing or Least Loaded Path Routing (LLR). This paper proposes two heuristic algorithms based on former algorithms to improve network throughput and reduce blocking probabilities of data transmitted in all-optical networks with regard to connection costs. We also introduce new criteria to estimate network congestion and choose better routing paths. Experimental results in ring networks show that both new algorithms achieve promising performance.     

A heuristic algorithm for lightpath scheduling in next-generation WDM optical networks

We study the routing and wavelength assignment (RWA) problem of scheduled lightpath demands (SLDs) in all-optical wavelength division multiplexing networks with no wavelength conversion capability. We consider the deterministic lightpath scheduling problem in which the whole set of lightpath demands is completely known in advance. The objective is to maximize the number of established lightpaths for a given number of wavelengths. Since this problem has been shown to be NP complete, various heuristic algorithms have been developed to solve it suboptimally. In this paper, we propose a novel heuristic RWA algorithm for SLDs based on the bee colony optimization (BCO) metaheuristic. BCO is a newborn swarm intelligence metaheuristic approach recently proposed to solve complex combinatorial optimization problems. We compare the efficiency of the proposed algorithm with three simple greedy algorithms for the same problem. Numerical results obtained by numerous simulations performed on the widely used realistic European Optical Network topology indicate that the proposed algorithm produces better-quality solutions compared to those obtained by greedy algorithms. In addition, we compare the results of the BCO–RWA–SLD algorithm with four other heuristic/metaheuristic algorithms proposed in literature to solve the RWA problem in the case of permanent (static) traffic demands.     

Wavelength assignment with sparse wavelength conversion for optical multicast in WDM networks

This paper addresses the problem of multicast wavelength assignment for sparse wavelength conversion (MWA-SWC) in wavelength-routed wavelength-division-multiplexing (WDM) networks. It aims to optimally allocate the available wavelength for each link of the multicast tree, given a sparse wavelength conversion network and a multicast request. To our knowledge, little research work has been done to address this problem in literature.In this paper, we propose a new technique called MWA-SWC algorithm to solve the problem. The algorithm first maps the multicast tree from the sparse conversion case to the full conversion case by making use of a novel virtual link method to carry out the tree mapping. The method provides a forward mapping to generate an auxiliary tree as well as a reverse mapping to recover the original tree. Applying the auxiliary tree, we propose a dynamic programing algorithm for the wavelength assignment (WA) aiming to minimize the number of wavelength converters (NWC) required. Simulation results show that our new algorithm outperforms both random and greedy algorithms with regard to minimizing the NWC. Testing on various scenarios by varying the number of wavelength conversion nodes in the tree has confirmed the consistency of the performance. The primary use of the MWA-SWC algorithm is for static traffic. However, it can also serve as a baseline for dynamic heuristic algorithms. Typically, the MWA-SWC algorithm will provide great benefit when the number of available wavelengths on each link of the multicast tree is relatively large and the performance advantage is significant.     

Lifetime optimization for reliable broadcast and multicast in wireless ad hoc networks

In this paper, we consider the reliable broadcast and multicast lifetime maximization problems in energy‐constrained wireless ad hoc networks, such as wireless sensor networks for environment monitoring and wireless ad hoc networks consisting of laptops or PDAs with limited battery capacities. In packet loss‐free networks, the optimal solution of lifetime maximization problem can be easily obtained by tree‐based algorithms. In unreliable networks, we formulate them as min–max tree problems and prove them NP‐complete by a reduction from a well‐known minimum degree spanning tree problem. A link quality‐aware heuristic algorithm called Maximum Lifetime Reliable Broadcast Tree (MLRBT) is proposed to build a broadcast tree that maximizes the network lifetime. The reliable multicast lifetime maximization problem can be solved as well by pruning the broadcast tree produced by the MLRBT algorithm. The time complexity analysis of both algorithms is also provided. Simulation results show that the proposed algorithms can significantly increase the network lifetime compared with the traditional algorithms under various distributions of error probability on lossy wireless links. Copyright © 2012 John Wiley & Sons, Ltd.     

QoS-driven multicast routing in sparse-splitting optical networks

This paper investigates the quality-of-service (QoS)-driven multicast routing problem in a sparse-splitting optical network. The main objective is to minimize the total cost of wavelength channels utilized by the light-tree while satisfying required QoS parameters. In this paper, both the optical-layer constraints (e.g., optical signal power) and application-layer requirements (e.g., end-to-end delay and inter-destination delay variation) are considered as the QoS parameters. First, integer linear programming (ILP) formulations to solve the optimal multicast routing problem with the given QoS parameters are presented. Solving the ILP formulations for large-scale networks can easily overwhelm the capabilities of state-of-the-art computing facilities, and hence, a heuristic algorithm is proposed to construct a feasible light-tree that satisfies the required QoS parameters in large-scale networks. Simulation results demonstrate the performance of the proposed heuristic algorithm in terms of the cost of utilized wavelength channels.     

A novel backup multiplexing scheme for surviving double-link failures in mesh optical networks without wavelength conversion capability

We consider the problem of recovery from any double-link failure by exploiting shared path protection in wavelength-division multiplexing (WDM) mesh networks. We for the first time discover the phenomenon of sharing contradiction, which results in the violation of 100% recovery guarantee. To completely eliminate the sharing contradiction, we introduce the so-called preference policy, which implies that one of two backup paths (BPs) for each connection is given priority over the other to recover the failed active path (AP). Based on this policy, we propose a backup-multiplexing scheme with 100% recovery guarantee. Further, we transform the problem of minimizing the total number of wavelength-links under the wavelength continuity constraint while recovering from any dual-link failure to integer linear programming (ILP) formulations. Additionally, we investigate three preference policies, i.e., the first backup path preference policy (FBPPP), the second backup path preference policy (SBPPP), and the optimal preference policy (OPP). The numerical results show that our proposed backup multiplexing scheme can reduce about 30% wavelength-link consumption, compared to dedicated protection. Also, the results show that the policy, which specifies that the shorter one of two backup paths is preferred, generally outperforms the policy, which specifies that the longer one of two backup paths is preferred. Furthermore, the results show that OPP has a better performance when two BPs for each connection are more comparable in their lengths.     

Layered-routing approach for solving multicast routing and wavelength assignment problem

We have developed a new layered-routing approach to address the problem of all-optical multicast over wavelength-routed wavelength division multiplexing (WDM) networks. We model the WDM network as a collection of wavelength layers with sparse light- splitting (LS) and wavelength conversion (WC) capabilities. We apply the degree constraint technique to solve the problem. The approach is capable of completing multicast routing and wavelength assignment (MCRWA) in one step. We propose two generic frameworks to facilitate heuristic development. Any heuristic that is derived from either Prim’s or Kruskal’s algorithm can be easily imported to solve the MCRWA problem. One example is given for each framework to demonstrate heuristic development. Extensive simulations were carried out to measure the performance of heuristics developed from the frameworks. The results show that the STRIGENT scheme is suitable for hardware design and it is advisable to deploy light splitters and wavelength converters to the same node for better performance.     

Virtual topology transition sequence problem in WDM networks with FIPP p-cycles protection

In this article, for the given wavelength division multiplexing (WDM) network, the demand traffic matrix, the old and new survivable virtual topologies which are protected by the failure-independent path-protecting p-cycles (FIPP p-cycles) protection scheme, the virtual topology transition sequence (VTTS) problem is studied. The goal of this problem is to find an optimal sequence to transfer the old virtual topology into new one, and during the transiting process, the services are not disrupted. Moreover, each lightpath in the virtual topology is protected by the FIPP p-cycle and can survive against a single-link failure. In this article, a heuristic algorithm and a genetic algorithm are proposed to solve this problem. Simulations are also performed to evaluate the performance of proposed algorithms.     

Achieving resource reduction for protecting multicast sessions in WDM mesh networks

The advances in wavelength division multiplexing (WDM) technology are expected to facilitate bandwidth-intensive multicast application by establishing a light-tree, which regards the source node as the root, and involves all the destination nodes. The light-tree is sensitive to failures, e.g., a single fiber cut may disrupt the transmission of information to several destination nodes. Thus, it is imperative to protect multicast sessions. In this work, we investigate the problem of protecting dynamic multicast sessions in mesh WDM networks against single link failures. Our objectives are to minimize the usage of network resources in terms of wavelength links for provisioning survivable multicast session, and to reduce the multicast session blocking probability. We propose two efficient multicast session protecting algorithms, called Optimal Path Pair based Removing Residual Links (OPP-RRL) and Source Leaf Path based Avoiding Residual Links (SLP-ARL), which try to reduce the usage of network resource by removing or avoiding residual links in the topology consisting of light-tree and its backup paths. To evaluate the proposed algorithms, we apply Integer Linear Programming (ILP) to generate an optimal solution. We also compare the proposed algorithms with existing algorithms through simulation. Simulation results indicate that the two proposed algorithms have better performance than other existing algorithms in terms of wavelength links required and network blocking probability. Furthermore, the solutions generated by the two proposed algorithms are quite close to the solutions generated by ILP in terms of the number of wavelength links required, when the network size is small.     

Cost Effective Shared Path Protection for WDM Optical Mesh Networks with Partial Wavelength Conversion

In this paper, we study routing and wavelength assignment of connection requests in survivable WDM optical mesh networks employing shared path protection with partial wavelength conversion while 100% restorability is guaranteed against any single failures. We formulate the problem as a linear integer program under a static traffic model. The objective is to minimize the total cost of wavelength-links and wavelength converters used by working paths and protection paths of all connections. A weight factor is used which is defined as the cost ratio of a wavelength converter and a wavelength-link. Depending on the relative cost of bandwidth and wavelength conversion, the optimization objective allows a proper tradeoff between the two. The proposed algorithm, the shortest-widest-path-first (SWPF) algorithm, uses a modified Dijkstra's algorithm to find a working path and a protection path for each connection request in the wavelength graph transformed from the original network topology. When there are multiple candidate paths that have the same minimum total cost, the path along which the maximum number of converters used at each node is minimized is chosen by the SWPF algorithm. We have evaluated the effectiveness of the proposed algorithm via extensive simulation. The results indicate that the performance of the proposed algorithm is very close to that of the optimal solutions obtained by solving the ILP formulation and outperforms existing heuristic algorithms in terms of total number of converters used and the maximum number of converters required at each node in the network. The proposed algorithm also achieves slightly better performance in terms of total cost of wavelength-links and converters used by all connections. We also investigated shared path protection employing converter sharing. The results show that the technique can reduce not only the total number of converters used in the network but also the maximum number of converters required at each node, especially when a large number of converters are needed in the network. In this study, although the ILP formulation is based on static traffic, the proposed algorithm is also applicable to routing dynamic connection requests.