多域光网络中基于优先级的波长路由分配算法

本文提出一种在多域光网络中基于优先级的路由波长分配算法.算法设计旨在解决复杂网络拓扑下,多任务请求路由波长分配问题.本文首先根据复杂网络拓扑情况与任务请求状况,完成多域的划分,对跨域任务的最短路由进行路由分裂;其次依据域内与域间优先级设定策略,完成多任务请求优先级设定;按照优先级顺序,采用模糊优化波长分配算法完成波长分配.仿真结果表明本算法在处理复杂网络拓扑、多任务路由波长分配问题上效果明显,有效的降低了网络请求阻塞率,提高了光网络资源利用率.     

基于蚁群系统的分布式RWA算法研究

针对波分复用(WDM)光网络中动态选路和波长分配(RWA)问题，提出了一种基于蚁群算法的分布式动态RWA方法。将蚁群算法与分层图模型结合，实现了RWA的并行计算。仿真结果表明，与现有最短路径法相比，该算法能有效地降低光路阻塞率，促进波长资源的合理分配，同时分布式的计算方式也降低了现代频繁变化的大型光网络的通信开销。     

Multiple-Constraint-Aware RWA Algorithms Based on a Comprehensive Evaluation Model： Use in Wavelength-Switched Optical Networks

Because of explosive growth in Internet traffic and high complexity of heterogeneous networks,improving the routing and wavelength assignment (RWA) algorithm in underlying optical networks has become very important.Where there are multiple links between different the node pairs,a traditional wavelength-assignment algorithm may be invalid for a wavelength-switched optical networks (WSON) that has directional blocking constraints.Also,impairments in network nodes and subsequent degradation of optical signals may cause modulation failure in the optical network.In this paper,we propose an RWA algorithm based on a novel evaluation model for a WSON that has multiple constraints.The algorithm includes comprehensive evaluation model (CEM) and directional blocking constraint RWA based on CEM (DB-RWA).Diverse constraints are abstracted into various constraint conditions in order to better assign routing and wavelength.We propose using the novel CEM to optimize routing according to an assessed value of constraints on transmission performance.This eliminates the effects of physical transmission impairments in a WSON.DB-RWA based on CEM abstracts directional blocking conditions in multiple links between network nodes into directional blocking constraints.It also satisfies rigorous network specifications and provides flexibility,scalability,and first-fit rate for the backbone,especially in multiple links between WSON nodes.     

Ant Colony Optimization for Dynamic RWA in WDM Networks with Partial Wavelength Conversion

Dynamic routing and wavelength assignment (RWA), which supports request arrivals and lightpath terminations at random times, is needed for rapidly changing traffic demands in wavelength division multiplexed, (WDM) networks. In this paper, a new distributed heuristic algorithm based on ant colony optimization for dynamic RWA is put forward. We consider the combination of route selection and wavelength assignment as a whole using a multilayer-graph model. Therefore, an extended multilayer-graph model for WDM networks with limited wavelength conversion is presented. Compared with other RWA methods, the Ant Colony heuristic algorithm can achieve better global network optimization and can reduce communication overhead cost of the networks. Simulation showed that a lower blocking probability and a more rational wavelength resource assignment can be achieved.     

一种稀疏分光配置约束下的WDM网络多播RWA算法

在波长路由WDM网络中,波长路由和波长分配是RWA算法提高光网络阻塞性能的两个重要阶段和关键技术。文章针对现有的稀疏分光配置约束下的光网络多播RWA算法复杂度高、代价高的问题,提出了一种新的稀疏分光器配置的RWA多播算法。该算法摒弃传统RWA算法在波长路由阶段就考虑稀疏分光约束能力的惯性思维,论文首次提出在波长分配阶段,才通过多播长转换器实现满足稀疏分光约束条件的分光能力传递。仿真结果表明,所提算法在平均代价和所需波长数目方面都获得了较优的性能。     

Wavelength converter placement under different RWA algorithms in wavelength-routed all-optical networks

Sparse wavelength conversion and appropriate routing and wavelength assignment (RWA) algorithms are the two key factors in improving the blocking performance in wavelength-routed all-optical networks. It has been shown that the optimal placement of a limited number of wavelength converters in an arbitrary mesh network is an NP-complete problem. There have been various heuristic algorithms proposed in the literature, in which most of them assume that a static routing and random-wavelength assignment RWA algorithm is employed. However, the existing work shows that fixed-alternate routing and dynamic routing RWA algorithms can achieve much better blocking performance. Our study further demonstrates that the wavelength converter placement and RWA algorithms are closely related in the sense that a well-designed wavelength converter placement mechanism for a particular RWA algorithm might not work well with a different RWA algorithm. Therefore, the wavelength converter placement and the RWA have to be considered jointly. The objective of this paper is to investigate the wavelength converter placement problem under the fixed-alternate routing (FAR) algorithm and least-loaded routing (LLR) algorithm. Under the FAR algorithm, we propose a heuristic algorithm called minimum blocking probability first for wavelength converter placement. Under the LLR algorithm, we propose another heuristic algorithm called weighted maximum segment length. The objective of the converter placement algorithms is to minimize the overall blocking probability. Extensive simulation studies have been carried out over three typical mesh networks, including the 14-node NSFNET, 19-node EON, and 38-node CTNET. We observe that the proposed algorithms not only outperform existing wavelength converter placement algorithms by a large margin, but they also can achieve almost the same performance compared with full wavelength conversion under the same RWA algorithm.     

An Ant-Based Approach for Dynamic RWA in Optical WDM Networks

In this paper, we propose a new ant-based algorithm for the dynamic routing and wavelength assignment (RWA) problem in optical WDM networks under the wavelength continuity constraint. Unlike conventional approaches, which usually require centralized global network information, our new RWA algorithm constructs the routing solution in a distributed manner by means of cooperative ants. To facilitate the ants’ foraging task, we adopt in our algorithm a probabilistic routing table structure for route selection. The new algorithm is highly adaptive in that it always keeps a suitable number of ants in the network to cooperatively explore the network states and continuously update the routing tables, so that the route for a connection request can be determined promptly by the current states of routing tables with only a small setup delay. Some new schemes for path scoring and path searching are also proposed to enhance the performance of our ant-based algorithm. Extensive simulation results upon three typical network topologies indicate that the proposed algorithm has a very good adaptability to traffic variations and it outperforms both the fixed routing algorithm and the promising fixed–alternate routing algorithm in terms of blocking probability. The ability to guarantee both a low blocking probability and a small setup delay makes the new ant-based routing algorithm very attractive for both the optical circuit switching networks and future optical burst switching networks     

基于改进蚁群算法的卫星光网络波长分配方法

路由与波长分配是下一代光网络的需要解决的核心问题之一。本文采用智能蚁群算法,研究了卫星光网络的路由与波长分配问题,为通信请求寻找最优的数据传输光路径。基于请求区域受限策略(Restricted Request Area,RRA)和链路波长负载平衡策略,建立了考虑传输延迟和波长连续性约束的双主星分布式星群节点结构光网络系统模型。利用智能蚁群路由和波长分配(Smart Ant Colony Routing AndWavelength Assignment,SAC-RWA)算法求解系统模型,以找到具有稀疏波长转换的卫星光网络中最小成本波长路径。所提出的算法允许单个蚂蚁同时完成路由和波长分配,仿真结果表明,RRA能够明显改进卫星光网络的性能,以略微增加拥塞率的代价显著降低了计算复杂度。     

Dynamic Routing and Wavelength Assignment in Survivable WDM Networks

Dense wavelength division multiplexing (DWDM) networks are very attractive candidates for next generation optical Internet and intelligent long-haul core networks. In this paper we consider DWDM networks with wavelength routing switches enabling the dynamic establishment of lightpaths between each pair of nodes. The dynamic routing and wavelength assignment (RWA) problem is studied in multifiber networks, assuming both protection strategies: dedicated and shared. We solve the two subproblems of RWA simultaneously, in a combined way using joint methods for the wavelength selection (WS) and wavelength routing (WR) tasks. For the WS problem in contrast to existing strategies we propose a new, network state based selection method, which tries to route the demand on each wavelength, and selects the best one according to different network metrics (such as available channels, wavelengths per fiber and network load). For the WR problem we propose several weight functions for using in routing algorithms (Dijkstra or Suurballe), adapting dynamically to the load of the links and to the length of the path. The combination of different wavelength selection and routing (WS&WR) methods enables wide configuration opportunities of our proposed algorithm allowing good adaptation to any network state. We also propose the extension of the RWA algorithm for dedicated and shared protection and a new method for applying shared protection in dynamic WDM environment. The detailed analysis of the strategies demonstrate that our RWA algorithm provides significantly better performance than previous methods in terms of blocking probability whether with or without protection methods.     

一种新型的动态路由和波长分配算法

本文讨论了WDM光网中，在动态业务流量和有限范围波长变换情况下的动态路由和波长分配（RWA）问题，基于Moone-Dijkstra算法，考虑到动态波长变换的可能和限制，提出了一种新型的、可实现动态最小代价路由和最佳虚波长通道的综合启发式算法（DMC－OVMP）。该算法对路由子问题和波长分配子问题既相互独立，又相互结合，优化了RWA，保证了网络信息传输的安全性。对中国教育和科研计算机网（CERNET）基于本算法进行了计算机仿真，实现了低的网络阻塞率。     

Dynamic circuit provisioning in all-optical WDM networks using lightpath switching

In this paper we investigate the problem of provisioning holding-time-aware (HTA) dynamic circuits in all-optical wavelength division multiplexed (WDM) networks. We employ a technique called lightpath switching (LPS) wherein the data transmission may begin on one lightpath and switch to a different lightpath at a later time. Lightpath switches are transparent to the user and are managed by the network. Allowing LPS creates a number of segments that can use independent lightpaths. We first compare the performance of traditional routing and wavelength (RWA) assignment to routing and wavelength assignment with LPS. We show that LPS can significantly reduce blocking compared to traditional RWA. We then address the problem of routing dynamic anycast HTA dynamic circuits. We propose two heuristics to solve the anycast RWA problem: anycast with continuous segment (ACS) and anycast with lightpath switching (ALPS). In ALPS we exercise LPS, and provision a connection request by searching for the best candidate destination node is such a way that the network resources are utilized efficiently. In ACS we do not allow a connection request to switch lightpaths. The lightpaths to each candidate destination node of a request are computed using traditional RWA algorithms. We first compare the performance of ACS to ALPS and observe that ALPS achieves better blocking than ACS. Furthermore, we also compare the performance of these two anycast RWA algorithms to the traditional unicast RWA algorithm. We show that the anycast RWA algorithms presented here significantly outperform the traditional unicast RWA algorithms.     

Routing and wavelength assignment in all-optical networks

Considers routing connections in a reconfigurable optical network using WDM. Each connection between a pair of nodes in the network is assigned a path through the network and a wavelength on that path, such that connections whose paths share a common link in the network are assigned different wavelengths. The authors derive an upper bound on the carried traffic of connections (or equivalently, a lower bound on the blocking probability) for any routing and wavelength assignment (RWA) algorithm in such a network. The bound scales with the number of wavelengths and is achieved asymptotically (when a large number of wavelengths is available) by a fixed RWA algorithm. The bound can be used as a metric against which the performance of different RWA algorithms can be compared for networks of moderate size. The authors illustrate this by comparing the performance of a simple shortest-path RWA (SP-RWA) algorithm via simulation relative to the bound. They also derive a similar bound for optical networks using dynamic wavelength converters, which are equivalent to circuit-switched telephone networks, and compare the two cases. Finally, they quantify the amount of wavelength reuse achievable in large networks using the SP-RWA via simulation as a function of the number of wavelengths, number of edges, and number of nodes for randomly constructed networks as well as de Bruijn networks. They also quantify the difference in wavelength reuse between two different optical node architectures     

Binary quadratic programming formulation for routing and wavelength assignment problem in all-optical WDM networks

Routing and wavelength assignment (RWA) is the most concern in wavelength routed optical networks. This paper proposes a novel binary quadratic programming (BQP) formulation for the static RWA problem in order to balance traffic load among a network links more fairly. Subsequently, a greedy heuristic algorithm namely variable-weight routing and wavelength assignment (VW-RWA) is proposed to solve the developed BQP problem. In this method, the weight of a link is proportional to the link congestion. Performance evaluation results for different practical network topologies show that our proposed algorithm can decrease the number of required wavelengths in the network, blocking rate and variance of used wavelengths in each link. Besides, it is shown that the number of required wavelengths to establish call requests for a given network topology can be reduced at lower cost compared to other heuristics.     

基于关键链路预测的动态路由和波长分配算法

 光网络中的路由和波长分配 （RWA）算法是NP难问题. 目前的解决方案大多是基于启发式算法或图论的,其计算复杂度往往随着网络规模的增加呈指数增长,而且链路阻塞概率建模也十分困难. 本文提出了一种基于“关键链路”预测机制的RWA算法,并综合考虑跳数和空闲波长数的因素,不仅通过链路层面,而且也从网络层面来解决RWA问题. 实验结果表明我们的算法可以实现很好的流量负载均衡和低的阻塞率,具有较小的计算复杂度.     

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.     

GMPLS协议中的路由和波长分配技术

因特网工程工作组（IETF）制定的通用多协议标签交换协议（GMPLS）,作为光网络的控制平面协议,推动了光网络的智能化进程。路由和波长分配问题（RWA）是光网络智能化的核心问题之一。在介绍RWA算法和GMPLS协议的基础上,分析了不同RWA算法、不同RWA机制对网络信息的需求,描述了GMPLS协议为解决RWA问题所做的标准化工作,并分析了与RWA相关的网络信息分发格式。     

Routing and wavelength assignment strategies in optical networks

We consider the routing and wavelength assignment (RWA) problem on wavelength division multiplexing (WDM) networks without wavelength conversion. When the physical network and required connections are given, RWA is the problem to select a suitable path and wavelength among the many possible choices for each connection such that no two paths using the same wavelength pass through the same link. In WDM optical networks, there is need to maximize the number of connections established and to minimize the blocking probability using limited resources. This paper presents efficient RWA strategies, which minimizes the blocking probability. Simulation results show that the performance of the proposed strategies is much better than the existing strategy.     

Routing and Wavelength Assignment in Optical Networks Using Logical Link Representation and Efficient Bitwise Computation

In this paper, we propose and evaluate a new approach for implementing efficient routing and wavelength assignment (RWA) in wavelength division multiplexing (WDM) optical networks. In our method, the state of a fiber is given by the set of free wavelengths in this fiber and is efficiently represented as a compact bitmap. The state of a multiple-fiber link is also represented by a compact bitmap computed as the logical union of the individual bitmaps of the fibers in this link. Likewise, the state of a lightpath is represented by a similar bitmap computed as the logical intersection of the individual bitmaps of the links in this path. The count of the number of 1-valued bits in the bitmap of the route from source to destination is used as the primary reward function in route selection. A modified Dijkstra algorithm is developed for dynamic routing based on the bitmap representation. The algorithm uses bitwise logical operations and is quite efficient. A first-fit channel assignment algorithm is developed using a simple computation on the bitmap of the selected route. The resulting bitwise routing algorithm combines the benefits of least loaded routing algorithms and shortest path routing algorithms. Our extensive simulation tests have shown that the bitwise RWA approach has small storage overhead, is computationally fast, and reduces the network-wide blocking probability. The blocking performance of our RWA method compares very favorably with three routing methods: fixed alternate routing, shortest path using flooding, and Dijkstra’s algorithm using mathematical operations. Our simulation experiments have also evaluated the performance gain obtained when the network access stations are equipped with finite buffers to temporarily hold blocked connection requests.     

Dynamic routing and wavelength assignment in the presence of wavelength conversion for all-optical networks

Blocking probability has been one of the key performance indexes in the design of wavelength-routed all-optical WDM networks. Existing research has demonstrated that an effective Routing and Wavelength Assignment (RWA) algorithm and wavelength conversion are two primary vehicles for improving the blocking performance. However, these two issues have largely been investigated separately; in particular the existing RWA algorithms have seldom considered the presence of wavelength conversion. In this paper, we firstly demonstrate that the existing dynamic RWA algorithms do not work well in the presence of wavelength conversion as they usually only take into account the current traffic, and do not explicitly consider the route lengths. We then propose a weighted least-congestion routing and first-fit wavelength assignment (WLCR-FF) algorithm that considers both the current traffic load and the route lengths jointly. We further introduce an analytical model that can evaluate the blocking performance for WLCR algorithm. We carry out extensive numerical studies over typical topologies including ring, mesh-torus, and the 14-node NSFNET; and compare the performance of WLCR-FF with a wide variety of existing routing algorithms including static routing, fixed-alternate routing and least-loaded routing. The results conclusively demonstrate that the proposed WLCR-FF algorithm can achieve much better blocking performance in the presence of sparse or/and full wavelength conversion.     

ASON网络环境下面向业务的RWA问题研究

从下一代光网络的业务需求出发,研究了在自动交换光网络(ASON)架构下面向业务的路由与波长分配(RWA)问题,提出了适应光网络向业务网络演进环境下面向业务的RWA概念,并分别就选路和波长分配问题进行了初步的探讨;面向业务的网络环境要求能为业务提供区分服务,以提供区分服务为目的对基于优先级的RWA算法进行了研究,并提出了面向区分业务的RWA实现框图.