Genetic algorithm for finding minimal cost light-forest of multicast routing on WDM networks

Wavelength division multiplexing (WDM) is an important technique to make use of the large amount of bandwidth in optical fibers to meet the bandwidth requirements of applications. Multicast is the transmission of information from one source to multiple destinations simultaneously. Given a multicast request in a WDM network, the goal is to find a set of light-trees, the assigned wavelengths of light-trees, and construct a light-forest. In this paper, the Minimal cost multicast routing problem (MCMRP) on WDM networks with Tap-and-continue nodes is defined and studied. A new cost model which consists of thewavelength usage and communication cost is defined. The objective is to minimize the sum of the cost of used wavelengths and the communication cost of the light-forest. Specifically, the formulation for the WDM multicast routing problem is given. Because the MCMRP is NP-hard, two genetic algorithms (GAs) are proposed to solve this problem. In the proposed GAs, a path-oriented encoding chromosome is used to represent the routing paths. These routing paths are used to construct source-based light-forests to represent a feasible solution to the multicast request. Moreover, to speed up the convergence of GAs, a Farthest-first greedy heuristic algorithm is proposed and used to generate one of the initial chromosomes. Simulation results demonstrate that the proposed GAs can run efficiently.     

波分复用光传输网中波长路由算法的研究进展

光纤正迅速成为主干通信网的标准传介媒质．随着光学器件的发展，使得信号在传输过程中，除了在源、汇节点需要光电转换外，中间节点可保持光传输，这种通信网络叫光传送网．光传送网中的波分复用技术是将整个光纤的带宽分成多个信道，不同的信道可使用不同的波长来同时进行信息传输，从而增加了整个网络的带宽．在光传送网中，实现一个通信请求需要建立一条通信路径，并为该通信路径所经过的每条链上分配一个波长，即所谓波长路由．该文详细介绍了波分复用光传送网中波长路由算法的研究进展，内容包括波长分配算法、网络的信元阻塞率分析、容错和QoS波长路由、多播波长路由、最小化ADM数路由以及基于光或光电连接的并行机模型等．     

WDM全光网络中优化组播路由的遗传算法

在WDM网络中，路由和波长分配是紧密联系在一起的，即在建立光连接的过程中，不但需要确定路由，还要为该路由分配合适的波长资源。该文给出了一种遗传算法以解决在给定一组时延受限的组播请求的情况下，如何为这些组播请求建立合适的组播路由树，从而使得该组组播树所占用的波长数最小的问题。通过使用一种合适的二维染色体编码表示，并设计适合问题的交叉和变异操作，从而算法可以有效地搜索假设空间，实验模拟结果表明了该算法具有快速有效的特点。     

Efficient and scalable provisioning of always-on multicast streaming services

There is a growing need for large-scale distribution of realtime multicast data such as Internet TV channels and scientific and financial data. Internet Service Providers (ISPs) face an urgent challenge in supporting these services; they need to design multicast routing paths that are reliable, cost-effective, and scalable. To meet the realtime constraint, the routing paths need to be robust against a single IP router or link failure, as well as multiple such failures due to sharing fiber spans (SRLGs). Several algorithms have been proposed to solve this problem in the past. However, they are not suitable for today’s large networks, because either they do not find a feasible solution at all or if they do, they take a significant amount of time to arrive at high-quality solutions.In this paper, we present a new Integer Linear Programming (ILP) model for designing a cost-effective and robust multicast infrastructure. Our ILP model is extremely efficient and can be extended to produce quality-guaranteed network paths. We develop two heuristic algorithms for solving the ILP. Our algorithms can guarantee to find high-quality, feasible solutions even for very large networks. We evaluate the proposed algorithms using topologies of four operational backbones and demonstrate their scalability. We also compare the capital expenditure of the resulting multicast designs with existing approaches. The evaluation not only confirms the efficacy of our algorithms, but also shows that they outperform existing schemes significantly.     

Nonblocking WDM multicast switching networks

With ever increasing demands on bandwidth from emerging bandwidth-intensive applications, such as video conferencing, E-commerce, and video-on-demand services, there has been an acute need for very high bandwidth transport network facilities. Optical networks are a promising candidate for this type of applications. At the same time, many bandwidth-intensive applications require multicast services for efficiency purposes. Multicast has been extensively studied in the parallel processing and electronic networking community and has started to receive attention in the optical network community recently. In particular, as WDM (wavelength division multiplexing) networks emerge, supporting WDM multicast becomes increasingly attractive. In this paper, we consider efficient designs of multicast-capable WDM switching networks, which are significantly different and, hence, require nontrivial extensions from their electronic counterparts. We first discuss various multicast models in WDM networks and analyze the nonblocking multicast capacity and network cost under these models. We then propose two methods to construct nonblocking multistage WDM networks to reduce the network cost     

Efficient heuristic algorithms for light-path routing and wavelength assignment in WDM networks under dynamically varying loads

This paper presents heuristic algorithms that may be used for light-path routing and wavelength assignment in optical WDM networks under dynamically varying traffic conditions. We consider both the situations where the wavelength continuity constraint is enforced or not enforced along a light-path. The performance of these algorithms has been studied through simulations. We also compare their performance with that of a simpler system that uses fixed shortest-path routing. Our proposed algorithms provide lower blocking probabilities and are simple enough to be applied for real time network control and management. The heuristic algorithms are computationally simple and efficient to implement and provide good wavelength utilisation leading to efficient usage of the network's resources.     

A theory of deadlock-free adaptive multicast routing in wormholenetworks

A theory for the design of deadlock-free adaptive routing algorithms for wormhole networks, proposed by the author (1991, 1993), supplies sufficient conditions for an adaptive routing algorithm to be deadlock-free, even when there are cyclic dependencies between channels. Also, two design methodologies were proposed. Multicast communication refers to the delivery of the same message from one source node to an arbitrary number of destination nodes. A tree-like routing scheme is not suitable for hardware-supported multicast in wormhole networks because it produces many headers for each message, drastically increasing the probability of a message being blocked. A path-based multicast routing model was proposed by Lin and Ni (1991) for multicomputers with 2D-mesh and hypercube topologies. In this model, messages are not replicated at intermediate nodes. This paper develops the theoretical background for the design of deadlock-free adaptive multicast routing algorithms. This theory is valid for wormhole networks using the path-based routing model. It is also valid when messages with a single destination and multiple destinations are mixed together. The new channel dependencies produced by messages with several destinations are studied. Also, two theorems are proposed, developing conditions to verify that an adaptive multicast routing algorithm is deadlock-free, even when there are cyclic dependencies between channels. As an example, the multicast routing algorithms of Lin and Ni are extended, so that they can take advantage of the alternative paths offered by the network     

Routing of multicast audio/video streams in reconfigurable WDM optical networks

Due to its low attenuation, fiber has become the medium of choice for point-to-point links. Using Wavelength-Division Multiplexing (WDM), many independent channels can be created in the same fiber. A network node equipped with a tunable optical transmitter can select any of these channels for sending data. An optical interconnection combines the signal from the various transmitters in the network, and makes it available to the optical receivers, which may also be tunable. By properly tuning transmitters and/or receivers, point-to-point links can be dynamically created and destroyed. Therefore, in a WDM network, the routing algorithm has an additional degree of freedom compared to traditional networks: it can modify the netowrk topology to create the routes. In this paper, we consider the problem of routing multicast audio/video streams in WDM networks and propose heuristic algorithms to solve it. The performance of these heuristics is evaluated in a number of scenarios, with a realistic traffic model, and from the evaluation we derive guidelines for usage of the proposed algorithms.This work was supported in part by NASA under grant NAG2-842, by the National Science Foundation under grant NCR-9016032 and by Pacific Bell. Ciro Noronha was supported by a graduate scholarship from FAPESP from Sept/89 to Aug/93 under grant 89/1658.     

Multicast communication in wormhole-routed 2D torus networks with hamiltonian cycle model

In this paper, we propose an efficient multipath multicast routing algorithm in wormhole-routed 2D torus networks. We first introduce a hamiltonian cycle model for exploiting the feature of torus networks. Based on this model, we find a hamiltonian cycle in torus networks. Then, an efficient multipath multicast routing algorithm with hamiltonian cycle model (mulitpath-HCM) is presented. The proposed multipath multicast routing algorithm utilizes communication channels more uniformly in order to reduce the path length of the routing messages, making the multicasting more efficient. Simulation results show that the multicast latency of the proposed multipath-HCM routing algorithm is superior to that of fixed and dual-path routing algorithms.     

WDM网络中实时组播的分布式路由与波长分配算法

在WDM网络中,由于每条链路上可用波长是动态变化的,在考虑波长转换延迟时间的条件下,实现实时组播连接的路由与波长分配是十分困难的。该文提出了一种用于建立实时组播连接的分布式路由与波长分配算法。该算法将路由与波长分配统一进行,大大减少连接的建立时间。组播路由算法以Prim最小生成树算法和K-度宽度优先搜索方法为基础,生成一棵满足给定延迟时限的最小成本树。波长分配使用最少波长转换和负载平衡策略。     

有固定波长转换器的全光环网波长分配算法

采用波分复用技术的全光网是目前宽带网络研究的方向之一,波长分配是其中主要的算法问题,具有重要的理论和应用价值.研究了具有任意固定波长转换器的环形光网上的波长分配问题.首先,提出了两个对环网上的请求集合预处理的算法,这两个算法可以将请求集合分解成一些连续的循环序列;然后,采用置换群来描述具有固定波长转换器的光环网,基于这种数学表示,提出了对环网上的波长信道进行分解的算法;基于这些算法,进一步提出了一个波长分配算法,该算法对于环形光网上的任意固定转换模式都能给出一个较好的波长分配方案.     

Reliable and Energy-Efficient Routing for Static Wireless Ad Hoc Networks with Unreliable Links

Energy efficient routing and power control techniques in wireless ad hoc networks have drawn considerable research interests recently. In this paper, we address the problem of energy efficient reliable routing for wireless ad hoc networks in the presence of unreliable communication links or devices or lossy wireless link layers by integrating the power control techniques into the energy efficient routing. We consider both the case when the link layer implements a perfect reliability and the case when the reliability is implemented through the transport layer, e.g., TCP. We study the energy efficient unicast and multicast when the links are unreliable. Subsequently, we study how to perform power control (thus, controlling the reliability of each communication link) such that the unicast routings use the least power when the communication links are unreliable, while the power used by multicast is close to optimum. Extensive simulations have been conducted to study the power consumption, the end-to-end delay, and the network throughput of our proposed protocols compared with existing protocols.     

On the joint link dimensioning and routing metric assignment problem for reliable WDM networks

In this paper, we tackle the joint link dimensioning and routing metric assignment problem for reliable wavelength division multiplexing (WDM) networks. This design problem consists to find the number of wavelength channels on each link and the routing metrics (considering shortest-path routing) that ensure the routing of all virtual wavelength paths (VWPs) and the successful rerouting of the reliable VWPs for all failure scenarios of interest to the network planner. A mixed integer mathematical programming model is proposed for the problem. The model is adapted for the single link failure scenarios. Since the problem is NP-hard, we propose a tabu search algorithm to obtain good approximate solutions for real-size instances of the problem. Finally, a lower bound is proposed and numerical results are presented and analyzed.     

QoS multicast tree construction in IP/DWDM optical internet by bio-inspired algorithms

In this paper, two bio-inspired Quality of Service (QoS) multicast algorithms are proposed in IP over dense wavelength division multiplexing (DWDM) optical Internet. Given a QoS multicast request and the delay interval required by the application, both algorithms are able to find a flexible QoS-based cost suboptimal routing tree. They first construct the multicast trees based on ant colony optimization and artificial immune algorithm, respectively. Then a dedicated wavelength assignment algorithm is proposed to assign wavelengths to the trees aiming to minimize the delay of the wavelength conversion. In both algorithms, multicast routing and wavelength assignment are integrated into a single process. Therefore, they can find the multicast trees on which the least wavelength conversion delay is achieved. Load balance is also considered in both algorithms. Simulation results show that these two bio-inspired algorithms can construct high performance QoS routing trees for multicast applications in IP/DWDM optical Internet.     

一种综合IP层和WDM层资源的光网络动态路由优化模型及其性能研究

在分层图模型的基础上,本文提出一种以最小化全网光路总代价为优化目标的IP over WDM光网络动态路由优化模型,设计了一种针对该模型的在线综合路由算法——MCTLP（Minimizing the Cost of Total Lightpaths）,MCTLP通过综合考虑IP逻辑层带宽资源分配和WDM光物理层波长链路资源的占用以优化网络资源。与两种有代表性的IP over WDM光网络路由算法的性能仿真时比表明：MCTLP能够在IP逻辑层和WDM光物理层都使用较少的链路以承载IP业务流,接纳更多的IP业务连接请求,有效地降低网络阻塞率．     

Algorithms for multicast connection under multi-path routing model

Given a source node and a set of destination nodes in a network, multicast routing problem is usually treated as Steiner tree problem. Unlike this well-known tree based routing model, multicast routing under multi-path model is to find a set of paths rooted at the source node such that in each path at most a fixed number of destination nodes can be designated to receive the data and every destination node must be designated in a path to receive the data. The cost of routing is the total costs of paths found. In this paper we study how to construct a multicast routing of minimal cost under multi-path model. We propose two approximation algorithms for this NP-complete problem with guaranteed performance ratios.     

Joint routing, scheduling, and power control for multichannel wireless sensor networks with physical interference

Reliability and real-time requirements bring new challenges to the energy-constrained wireless sensor networks, especially to the industrial wireless sensor networks. Meanwhile, the capacity of wireless sensor networks can be substantially increased by operating on multiple nonoverlapping channels. In this context, new routing, scheduling, and power control algorithms are required to achieve reliable and real-time communications and to fully utilize the increased bandwidth in multichannel wireless sensor networks. In this paper, we develop a distributed and online algorithm that jointly solves multipath routing, link scheduling, and power control problem, which can adapt automatically to the changes in the network topology and offered load. We particularly focus on finding the resource allocation that realizes trade-off among energy consumption, end-to-end delay, and network throughput for multichannel networks with physical interference model. Our algorithm jointly considers 1) delay and energy-aware power control for optimal transmission radius and rate with physical interference model, 2) throughput efficient multipath routing based on the given optimal transmission rate between the given source-destination pairs, and 3) reliable-aware and throughput efficient multichannel maximal link scheduling for time slots and channels based on the designated paths, and the new physical interference model that is updated by the optimal transmission radius. By proving and simulation, we show that our algorithm is provably efficient compared with the optimal centralized and offline algorithm and other comparable algorithms.     

A multipopulation parallel genetic simulated annealing-based QoS routing and wavelength assignment integration algorithm for multicast in optical networks

In this paper, we propose an integrated Quality of Service (QoS) routing algorithm for optical networks. Given a QoS multicast request and the delay interval specified by users, the proposed algorithm can find a flexible-QoS-based cost suboptimal routing tree. The algorithm first constructs the multicast tree based on the multipopulation parallel genetic simulated annealing algorithm, and then assigns wavelengths to the tree based on the wavelength graph. In the algorithm, routing and wavelength assignment are integrated into a single process. For routing, the objective is to find a cost suboptimal multicast tree. For wavelength assignment, the objective is to minimize the delay of the multicast tree, which is achieved by minimizing the number of wavelength conversion. Thus both the cost of multicast tree and the user QoS satisfaction degree can approach the optimal. Our algorithm also considers load balance. Simulation results show that the proposed algorithm is feasible and effective. We also discuss the practical realization mechanisms of the algorithm.     

Adaptive two-way uniform partition for multicast routing problem with separate paths in ad hoc networks

Finding a near-optimal routing solution for multicast requests is a challenge for supporting different multicast applications including video and group communications over wireless ad hoc networks. A heuristic partitioning algorithm for solving the multicast routing problem with separate paths in ad hoc networks is presented. We consider scheduling a set of multicast requests which may have a source node with multiple destinations respectively through a wireless network. Our heuristic method for partitioning arbitrary routing requests is both effective in finding a near-optimal solution, and efficient to solve large multicast requests. Our simulation shows that the average overall latency reduces up to 38%. We also find that the handling scales up well from 8 nodes to 64 nodes.     

全光双向网络中的波长转换

在许多光学路由中,对于给定一组通讯路的集合,必须对有公共边的路安排相同的波长.为了充分利用光学的带宽,目的是安排尽量少的波长数.但有时候也考虑使用波长转换器. 如果一个顶点安装转换器,任何经过这个顶点的路都可以改变其波长.因此在某些顶点安装波长转换器后可以将波长的数目减少到一个拥塞界,因此,Wilfong和Winkler定义了一个顶点集 S,在S上安装转换器后,任何路集都可以分配数目等于拥塞界的波长,这样的集合S被称为充分集.研究在双向网络中的最小充分集问题,并把他转化为最小顶点覆盖问题.对此问题给出几个算法.