基于模拟退火遗传算法求解路由和波长分配问题

静态的路由选择和波长分配(RWA)问题是波分复用（WDM）光网络中的一个重要问题，目前常用的处理方法是将RWA问题拆成选路子问题和波长分配子问题。静态RWA问题通常先按某种策略确定建立光路的顺序,然后用启发式的算法加以解决。提出通过模拟退火遗传算法对光路的建立顺序进行优化，然后用基于爬山算法的启发式算法可求解以波长数最小为优化目标的静态RWA问题。通过对ARPANet等5种实际光网络的仿真表明,该算法和文献[5]相比，所用的波长数更少，且大部分优化结果达到最优。     

有效的光传送网路由及波长分配算法

研究了光传送网路由及波长分配问题，对于虚波长网络以波长优化为目的，给出了两种启发式算法，并提出了波长数减一代价，作为对算法另一评判依据，通过对仿真结果的分析，来研究所提出算法的有效性。     

基于WDM传输网的动态路由算法

波分复用技术(WDM)作为一种公认的最佳光纤扩容技术已被广泛应用在国际和国内长途骨干网上。路由算法与波长分配(RWA)是WDM网中的重要技术之一,评价RWA算法的一个重要标准是网络阻塞率。采用合适的路由算法可以大大降低网络的阻塞率。该文采用一种结合了再生节点选择的动态RWA算法来解决WDM网中的波长路由问题,并通过光纤通道拓扑的优化算法来进一步优化。通过建模仿真,研究了NSFNET网络优化前后阻塞率的变化,仿真的结果证明采用该优化算法可以降低网络的阻塞率。     

SRLG分离的静态RWA保护算法

对于静态业务,传统RWA算法仅仅着眼于通过合理的选路和波长分配算法来建立相应的光路,使网络成本最小化。本文从提高网络生存性的角度出发,结合共享风险链路组的概念,讨论了抗毁WDM网络中的静态RWA保护设计算法。根据实现方式的不同将其分为两类:并行算法和分解算法,并分别进行了讨论。     

基于遗传算法的动态RWA问题的研究

针对WDM光传送网中的动态路由选择和波长分配(RWA)问题,提出了一种基于遗传算法的动态RWA方法。将遗传算法与相对容量影响(RCI)波长分配算法相结合,以实现对RWA算法的改进。仿真结果表明,与现有最短路径算法[1]相比,该算法能有效提高网络资源利用率,促进波长资源的合理分配。     

一种稀疏波长转换光网络中的波长分配算法

研究了具有波长转换功能的WDM光网络的分类以及已有的几种波长分配算法,分析了波长分配算法的一般流程。文中以波长变换次数最少做为所提出的波长分配算法的主要优化目标,根据WDM光网络中的节点是否具有波长转换的功能,结合等价光路由替换的思想,提出了在稀疏有限波长转换光网络中的一种启发式的波长分配算法。仿真实验表明,当光网络中的连接请求量较大时,该算法的阻塞率低于已有的一些波长分配算法,连接能力有了较大提高。     

多粒度光网络中动态路由与波长分配算法

通过分析多粒度光网络路由与波长分配的特点,针对WAPG算法的波长碎片问题,通过定义5种不同的逻辑链路权重,修改了WAPG算法的波长权重标注方法,达到减少波长碎片的目的。仿真结果表明,提出的修正算法有效地减少了多粒度光网络中的波长转换数,降低网络的阻塞概率,同时节省网络资源。     

基于OWns的WDM光网络仿真软件RwaOWns的开发

OWns是基于ns的WDM光网络仿真软件,被人们广泛用于光网络的研究.仿真软件RwaOWns扩充OWns以支持多种RWA算法,提供一个对多种RWA算法进行性能比较的平台,且有一个简便的RWA算法模块加入接口.给出了RwaOWns的总体结构和详细的设计,描述了如何编写新的RWA算法模块,最后给出了使用RwaOWns软件进行仿真的方法.     

一种稀疏波长转换光网络中的波长分配算法

研究了具有波长转换功能的WDM光网络的分类以及已有的几种波长分配算法，分析了波长分配算法的一般流程。文中以波长变换次数最少做为所提出的波长分配算法的主要优化目标，根据WDM光网络中的节点是否具有波长转换的功能，结合等价光路由替换的思想，提出了在稀疏有限波长转换光网络中的一种启发式的波长分配算法。仿真实验表明，当光网络中的连接请求量较大时，该算法的阻塞率低于已有的一些波长分配算法，连接能力有了较大提高。     

DWDM光网络中RWA问题的遗传求解方法

针对密集波分复用(dense wavelength-division multiplexing,DWDM)光网络通信中的动态路由与波长分配(routing and wavelength assignment,RWA)问题,提出了一种基于遗传算法的动态RWA方法.将遗传算法与分层图模型相结合,实现了RWA的方便计算.通过扩展适应值函数,能够有效地处理带时延约束的通信量请求.实验结果表明,与已有最短路径算法(Dijks-tra)相比,该算法能够提供多条候选路由方案,更适应较差环境下的网络通信.     

Joint routing and wavelength assignment in wavelength division multiplexing networks for permanent and reliable paths

In this paper, we tackle the routing and wavelength assignment problem for wavelength division multiplexing (WDM) networks containing permanent and reliable wavelength paths (WPs). It consists of finding the route and the wavelength of each WP for the normal state of the network and for the important failure scenarios. These scenarios might be the most probable failure scenarios or simply the failure scenarios of interest to the network planner (e.g., the single link failure scenarios). We propose a mathematical programming model for this problem. In order to find a solution within a reasonable amount of time, a simple heuristic algorithm is proposed. The results show that “good” solutions can be obtained with the proposed heuristic algorithm.     

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

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

Designing a fine‐grained parallel differential evolution with Pareto tournaments for solving an optical networking problem

The future of designing optical networks focuses on the wavelength division multiplexing technology. This technology divides the huge bandwidth of an optical fiber into different wavelengths, providing different available channels per link of optical fiber. However, when it is required to establish a set of demands, a problem comes up. This problem is known as routing and wavelength assignment problem. In this work, we have tackled the static routing and wavelength assignment problem by using multiobjective evolutionary computing. The algorithm applied is the differential evolution but modified with the Pareto tournaments concept for being adapted to the multiobjective context. By using OpenMP, an application programming interface that supports multiplatform shared memory multiprocessing programming, we have demonstrated that this algorithm is highly suitable to be parallelized. We have performed several experiments in multicore systems with two, four, and eight cores, obtaining 97.57% of mean efficiency. To ensure that our heuristic obtains relevant results, we have compared it with a parallel version of the standard fast nondominated sorting genetic algorithm. Finally, in order to show the goodness and effectiveness of the differential evolution with Pareto tournaments algorithm when dealing with this problem, we present diverse multiobjective comparisons with the nondominated sorting genetic algorithm and other approaches published in the literature. Copyright © 2013 John Wiley & Sons, Ltd.     

WDM网络中满足延迟和延迟差约束的分布式组播路由与波长分配算法

在WDM网络中,由于每条链路上可用波长是动态变化的,在考虑波长转换延迟时间的条件下,实现实时组播连接的路由与波长分配是十分困难的。论文提出了一种用于建立满足延迟时限和延迟差要求的实时组播连接的分布式路由与波长分配算法。该算法假定每个节点没有全局路由信息,只根据关联链路的信息进行路由选择,且将路由与波长分配统一进行。组播路由算法以Prim最小生成树算法为基础,生成一棵满足给定延迟时限的最小成本树。对不满足延迟时限的目的节点,通过增加回路边构造回路再消除长延迟路径的方式,加入到组播树中。对不满足延迟差的目的节点,采用重构Steiner树的方法,使其满足延迟差的要求。波长分配使用最少波长转换和负载平衡策略。     

LID Assignment in InfiniBand Networks

To realize a path in an InfiniBand network, an address, known as local identifier (LID) in the InfiniBand specification, must be assigned to the destination of the path and used in the forwarding tables of intermediate switches to direct the traffic following the path. Hence, routing in InfiniBand has two components: (1) computing all paths, and (2) assigning LIDs to destinations and using them in intermediate switches to realize the paths. We refer to the task of computing paths as path computation and the task of assigning LIDs as LID assignment. This paper focuses on the LID assignment component, whose major issue is to minimize the number of LIDs required to support a given set of paths. We prove that the problem of realizing a given set of paths with a minimum number of LIDs is NP-complete, develop an integer linear programming formulation for this problem, design a number of heuristics that are effective and efficient in practical cases, and evaluate the performance of the heuristics through simulation. The experimental results indicate that the performance of our best performing heuristic is very close to optimal.     

A multiobjective approach based on artificial bee colony for the static routing and wavelength assignment problem

Nowadays, the most promising technology for designing optical networks is the wavelength division multiplexing. This technique divides the huge bandwidth of an optical fiber link into different wavelengths, providing different available channels per link. However, a problem comes up when it is necessary to interconnect a set of traffic demands. This problem is known as routing and wavelength assignment problem, and due to its complexity (NP-hard problem) it is very suitable for being solved using evolutionary computation. The selected heuristics is the artificial bee colony algorithm, an heuristics based on the behavior of honeybee foraging for nectar. Therefore, we have applied multiobjective optimization to solve the static routing and wavelength assignment problem, and adapted this algorithm to the multiobjective context. New results have been obtained that significantly improve those published in previous researches.     

一种光因特网中的一体化QoS组播路由算法

讨论了IP/DWDM光因特网中的一体化多约束QoS组播路由和波长分配算法。给定一个QoS组播请求,包括带宽需求、组播端到端延迟上界和延迟抖动上界,提出了一种算法,它能够找到一棵同时满足上述三个约束的组播树。提出的算法基于一种类似于波长图的逻辑拓扑来构造组播树。逻辑拓扑上的路径同时指出路由和该路由上的可用波长。通过这种方式,算法将路由和波长分配集成在一起一体化考虑。最后,阐述了算法的正确性。