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.     

Avoidance of multicast incapable branching nodes for multicast routing in WDM networks

In this article we study the multicast routing problem in all-optical WDM networks under the spare light splitting constraint. To implement a multicast session, several light-trees may have to be used due to the limited fanouts of network nodes. Although many multicast routing algorithms have been proposed in order to reduce the total number of wavelength channels used (total cost) for a multicast session, the maximum number of wavelengths required in one fiber link (link stress) and the end-to-end delay are two parameters which are not always taken into consideration. It is known that the shortest path tree (SPT) results in the optimal end-to-end delay, but it can not be employed directly for multicast routing in sparse light splitting WDM networks. Hence, we propose a novel wavelength routing algorithm which tries to avoid the multicast incapable branching nodes (MIBs, branching nodes without splitting capability) in the shortest-path-based multicast tree to diminish the link stress. Good parts of the shortest-path-tree are retained by the algorithm to reduce the end-to-end delay. The algorithm consists of tree steps: (1) a DijkstraPro algorithm with priority assignment and node adoption is introduced to produce a SPT with up to 38% fewer MIB nodes in the NSF topology and 46% fewer MIB nodes in the USA Longhaul topology, (2) critical articulation and deepest branch heuristics are used to process the MIB nodes, (3) a distance-based light-tree reconnection algorithm is proposed to create the multicast light-trees. Extensive simulations demonstrate the algorithm’s efficiency in terms of link stress and end-to-end delay.     

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).     

Performance analysis of multicast routing and wavelength assignment protocol with dynamic traffic grooming in WDM networks

The need for on‐demand provisioning of wavelength‐routed channels with service‐differentiated offerings within the transport layer has become more essential because of the recent emergence of high bit rate Internet protocol (IP) network applications. Diverse optical transport network architectures have been proposed to achieve the above requirements. This approach is determined by fundamental advances in wavelength division multiplexing (WDM) technologies. Because of the availability of ultra long‐reach transport and all‐optical switching, the deployment of all‐optical networks has been made possible. The concurrent transmission of multiple streams of data with the assistance of special properties of fiber optics is called WDM. The WDM network provides the capability of transferring huge amounts of data at high speeds by the users over large distances. There are several network applications that require the support of QoS multicast, such as multimedia conferencing systems, video‐on‐demand systems, real‐time control systems, etc. In a WDM network, the route decision and wavelength assignment of lightpath connections are based mainly on the routing and wavelength assignment (RWA). The multicast RWA's task is to maximize the number of multicast groups admitted or minimize the call‐blocking probability. The dynamic traffic‐grooming problem in wavelength‐routed networks is generally a two‐layered routing problem in which traffic connections are routed over lightpaths in the virtual topology layer and lightpaths are routed over physical links in the physical topology layer. In this paper, a multicast RWA protocol for capacity improvement in WDM networks is designed. In the wavelength assignment technique, paths from the source node to each of the destination nodes and the potential paths are divided into fragments by the junction nodes and these junction nodes have the wavelength conversion capability. By using the concept of fragmentation and grouping, the proposed scheme can be generally applied for the wavelength assignment of multicast in WDM networks. An optimized dynamic traffic grooming algorithm is also developed to address the traffic grooming problem in mesh networks in the multicast scenario for maximizing the resource utilization and minimizing the blocking probability. Copyright © 2011 John Wiley & Sons, Ltd.     

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.     

Dynamic wavelength assignment for multicast in all-optical WDM networks to maximize the network capacity

We study the problem of wavelength assignment for multicast in order to maximize the network capacity in all-optical wavelength-division multiplexing networks. The motivation behind this work is to minimize the call blocking probability by maximizing the remaining network capacity after each wavelength assignment. While all previous studies on the same objective concentrate only on the unicast case, we study the problem for the multicast case. For a general multicast tree, we prove that the multicast wavelength assignment problem of maximizing the network capacity is NP-hard and propose two efficient greedy algorithms. We also study the same problem for a special network topology, a bidirectional ring network, which is practically the most important topology for optical networks. For bidirectional ring networks, a special multicast tree with at most two leaf nodes is constructed. Polynomial time algorithms for multicast wavelength assignment to maximize the network capacity exist under such a special multicast tree with regard to different splitting capabilities. Our work is the first effort to study the multicast wavelength assignment problem under the objective of maximizing network capacity.     

Priority-based minimum interference path multicast: routing algorithm in optical virtual private network

While the “Virtual Private Network (VPN) over Internet” is cost-effective and flexible, it suffers from the difficulty of providing adequate transmission capacity for high bandwidth services. Hence a Dense Wavelength Division Multiplexing (DWDM) based “Optical VPN (OVPN)” technology has been regarded as a good alternative for realizing the future VPN services. To improve the transparency and data rate of OVPN, it is critical to consider the problem of Routing and Wavelength Assignment (RWA) for transmission capacity utilization. This paper proposes a Priority-based Minimum Interference Path Multicast Routing (PMIPMR) algorithm, a new routing algorithm which finds alternative routes based on node priorities and Virtual Source (VS) nodes that has both splitting and wavelength conversion, and then chooses a path that does not interfere with potential future multicast session requests when congestions occur in the network. The PMIPMR algorithm reduces blocking rate significantly and increases the wavelength utilization by avoiding congestion in future multicast session requests. We measured the performance of the proposed algorithm in terms of blocking rate and the resource utilization. The simulation results demonstrate that the PMIPMR algorithm is superior to the previous multicast routing algorithms using the Capability-based-Connection algorithm based on Capability-based-Priority and Spawn-from-VS methods.     

Virtual Source Based Multicast Routing in WDM Optical Networks

Wavelength-division multiplexed (WDM) networks using wavelength-routing are considered to be potential candidates for the next generation wide-area backbone networks. Multicasting is the ability to transmit information from a single source node to multiple destination nodes and is becoming an important requirement in high-speed networks. As WDM technology matures and multicast applications become increasingly popular, supporting multicast routing at the WDM layer becomes an important and yet a challenging topic. This paper concerns with the problem of optical multicast routing in WDM networks. A few nodes in the network may have wavelength conversion and/or splitting capabilities. In this paper, a new multicast tree construction algorithm is proposed. This algorithm is based on a concept called virtual source. A virtual source is a node having both the splitting and wavelength conversion capabilities. By exploiting the presence of virtual source nodes, the proposed algorithm achieves improved performance. To further improve the performance, the algorithm assigns priorities to nodes based on their capabilities. The effectiveness of the proposed algorithm is verified through extensive simulation experiments.     

Performance assessment of multicast node placement for multicast routing in WDM networks with sparse light splitting

This article examines all-optical multicast routing for wavelength-routed optical networks with sparse Multicast Capable (MC) nodes in two phases. The first phase is MC node placement and use of a simple and straightforward Maximum Path Count First (MPCF) algorithm to obtain candidates for MC nodes. The second phase is multicast routing with MC-based schemes that minimizes the number of wavelength channels with minimum transmission delay as required by a given multicast session, in that a light-tree is first constructed to connect MC nodes in a multicast group by using two algorithms, namely, the Pre-computing Minimum Cost (PMC) tree algorithm and the Pre-computing Shortest Path (PSP) tree algorithm. System performance of the proposed MPCF MC node placement algorithm is compared with that of the Normalized Cuts (NC) MC node placement algorithm for both PMC and PSP multicast routing. Furthermore, simulation results compare PMC and PSP multicast routing based on MPCF and NC node placement with Re-route-to-Source (RTS), Re-route-to-Any (RTA), Member-First (MF), and Member-Only (MO) multicast routing based on a light forest for a given multicast session in terms of average number of wavelengths needed, average blocking probability, and mean maximum transmission delay.

MINIMIZING INTERMEDIATE MULTICAST ROUTING FOR DYNAMIC MULTI-HOP AD HOC NETWORKS

A Minimizing Intermediate Multicast Routing protocol （MIMR） is proposed for dynamic multi-hop ad hoc networks. In MIMR, multicast sessions are created and released only by source nodes. In each multicast session process, the source node keeps a list of intermediate nodes and destinations, which is encapsulated into the packet header when the source node sends a multicast packet. Nodes receiving multicast packets decide to accept or forward the packet according to the list. Depending on topology matrix maintained by unicast routing, the shortest virtual hierarchy routing tree is constructed by improved Dijkstra algorithm. MIMR can achieve the minimum number of intermediate nodes, which are computed through the tree. No control packet is transmitted in the process of multicast session. Load of the network is largely decreased. Experimental result shows that MIMR is flexible and robust for dynamic ad hoc networks.     

A multicast dynamic wavelength assignment algorithm based on matching degree

The wavelength assignment with multiple multicast requests in fixed routing WDM network is studied. A new multicast dynamic wavelength assignment algorithm is presented based on matching degree. First, the wavelength matching degree between available wavelengths and multicast routing trees is introduced into the algorithm. Then, the wave.length assignment is translated into the maximum weight matching in bipartite graph, and this matching problem is solved by using an extended Kuhn-Munkres algorithm. The simulation results prove that the overall optimal wavelength assignment scheme is obtained in polynomial time. At the same time, the proposed algorithm can reduce the connecting blocking probability and＂ improve the system resource utilization.     

A novel efficient multicast routing algorithm in sparse splitting optical networks

The advances in wavelength-division multiplexing (WDM) technology are expected to facilitate bandwidth-intensive multicast applications through light splitting. Due to complexity and cost constraints, light splitting (or optical multicast) nodes are sparsely configured in a practical WDM network. In this article, we investigate the multicast routing problem under the sparse light-splitting constraint. An efficient sparse splitting constrained multicast routing algorithm called Multicast Capable Node First Heuristic (MCNFH) is proposed. The key idea of MCNFH is to include the shortest path, that includes most of the multicast capable nodes, for configuring the multicast tree. Simulations and comparisons are used to demonstrate the performance of MCNFH. Simulation results and analysis show that MCNFH builds multicast trees with the least wavelength channel cost and with the smallest number of wavelengths used per link. In addition, MCNFH requires only one transmitter at the source node.     

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.     

基于多条件约束的ASON动态组播路由算法

在将自动交换光网络(ASON)建模成着色多重图的基础上采用综合成本策略,设计了一种新的最小综合成本路径计算算法,并结合组播成员的动态变化特性提出一种满足多条件约束的动态组播路由(DMRMC)算法,使组播路由和波长分配在同一过程内完成,且尽可能使组播树的综合总成本最小,同时局部优化波长转换次数、分光次数和不同波长的使用数量。仿真实验表明,本文算法有效可行,与采用单成本策略的组播算法相比,其取得了更低的综合成本和更好的连接阻塞性能。     

WDM疏导网络中一种新的多播业务路由算法

研究了波分复用(WDM)网状网中动态多播业务量疏导,提出一种新的辅助疏导模型,其可以描述当前网络资源状况和节点分光特点,并动态更新.进而提出一种有效的多播业务量疏导启发式算法(MGA),将业务的多播选路和波长分配同时完成.仿真表明,该算法在波长连续性限制、网络波长和节点收发器数目有限的情况下,具有较低网络阻塞率.     

Dynamic lightpath provisioning in optical WDM mesh networks with asymmetric nodes

The wavelength selective switch-based reconfigurable optical add/drop multiplexers is a promising switching equipment for future reconfigurable wavelength-division multiplexing (WDM) mesh networks. However, its asymmetric switching property complicates the optimal routing and wavelength assignment problem. In an asymmetric switching scenario, using the classic Dijkstra’s algorithm can lead to invalid paths traversing unconnected ports of an asymmetric node. To solve this problem, we propose both link-state (LS) and distance vector (DV) schemes for dynamic lightpath provisioning in optical WDM mesh networks with asymmetric nodes. The proposed LS schemes include the asymmetric switching-aware (ASA) Dijkstra’s algorithm, the $K$ -shortest path-based algorithm, and the entire path searching (EPS) algorithm. Simulation results show that the ASA-Dijkstra’s algorithm will bring notable improvement of the blocking performance with low computational complexity, while the EPS algorithm has much higher complexity and is not suitable to be employed in large-scale networks. On the other hand, our proposed DV solution, i.e., the information diffusion-based routing (IDBR), can achieve the lowest blocking probability with the lowest computational complexity. Moreover, IDBR does not require the distribution of local asymmetric switching information like the LS schemes, thus having a high level of topology confidentiality.     

Multicast service protection algorithm based on elastic optical network

With the rapid growth of the network traffic,the elastic optical network (EON) has been proposed as a promising solution due to its high spectrum efficiency and flexible bandwidth provision.Meanwhile,multicast routing and spectrum allocation,and the survivability of the network become more challenging than that in the conventional optical network.The routing for multicast traffic and its protection algorithm in EON was investigated.An integer linear programming (ILP) formulation with the objective to minimize total spectrum consumption was presented.In addition,a heuristic algorithm called multicast sub-tree protection algorithm (MSPA) to achieve sufficient protection and satisfy resources savings was designed.The simulation results demonstrate that comparing with the traditional multicast routing and protection algorithm,MSPA performs well in improving the blocking probability and the spectrum utilization of the network.     

基于超图模型的多域ASON损伤感知组播路由算法

如何在缺乏全局信息的条件下构建安全可靠的组 播树,是智能光网络分域管理后引入的一个新问 题。针对此问题,通过建立新型的多域智能光网络超图模型,在考虑物理或攻击损伤的约束 条件下,利用 基于超路径的域间超树构建方法,结合K最短路径策略,提出了 一种基于超图模型的多域ASON损伤感知 组播路由算法,并进行了实例分析。本文算法在完成多域组播路由建立与波长分配的同时, 具有较低的时间复杂度。通过测量K值、组播规 模、波长数量及分配策略、域数量对网络平均连接阻塞率的影响,实验结果表明,本文算法 是有效的且取得了较好的阻塞性能,同时建议多域ASON组播规模大小应与域的数量保持一 定的比例均衡。     

Algorithms for multicast traffic grooming in WDM mesh networks

Several of the new applications in high-performance networks are of the multicast traffic type. Since such networks employ an optical network infrastructure, and since most of these applications require subwavelength bandwidth, several streams are usually groomed on the same wavelength. This article presents an account of recent advances in the design of optical networks for multicast traffic grooming in WDM mesh networks. The article addresses network design and session provisioning under both static and dynamic multicast traffic. Under static traffic conditions, the objective is to accommodate a given set of multicast traffic demands, while minimizing the implementation cost. Optimal and heuristic solution techniques for mesh network topologies are presented. Under dynamic traffic conditions, techniques for dynamic routing and session provisioning of multicast sessions whose objective is to minimize session blocking probabilities are explained. The article also presents a number of open research issues     

基于强化学习的光传送网路由波长优化

针对光传送网中动态业务的路由和波长问题,提出一种基于强化学习的深度路由波长分配算法DeepRWA。算法基于软件定义网络架构,通过强化学习灵活地调整控制光传送网,实现光网络路由波长分配策略优化。针对路由选择问题,结合链路上的波长使用情况,使用A3C算法选择合适的路由,使得阻塞率最小;针对波长分配问题,使用首次命中算法选择波长。考虑阻塞率、资源利用率、策略熵、价值损失、运行时间及收敛速度等多个指标,利用14节点NSFNET网络拓扑仿真实验。结果表明:当信道中包含18个波长时,与传统KSP-FF算法相比,所提出的路由波长分配算法的阻塞率降低了0.06,资源利用率提高了0.02,但运行时间有增加;在波长数超过45以后,与传统KSP-FF算法相比,所提算法保持阻塞率和资源利用率的同时,运行时间开始降低;当信道中包含波长数为58时,与传统KSP-FF算法相比,所提算法运行时间减少了0.07 ms。由此可见,提出的算法使路由选择和波长分配得到了优化。