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     

A Lagrangean relaxation-based approach for routing and wavelength assignment in multigranularity optical WDM networks

Optical wavelength-division multiplexed (WDM) networks often include optical cross-connects with multigranularity switching capability, such as switching on a single lambda, a waveband, or an entire fiber basis. In addition, it has been shown that routing and wavelength assignment (RWA) in an arbitrary mesh WDM network is an NP-complete problem. In this paper, we propose an efficient approximation approach, called Lagrangean relaxation with heuristics (LRH), aimed to resolve RWA in multigranularity WDM networks particularly with lambda and fiber switches. The task is first formulated as a combinatorial optimization problem in which the bottleneck link utilization is to be minimized. The LRH approach performs constraint relaxation and derives a lower-bound solution index according to a set of Lagrangean multipliers generated through subgradient-based iterations. In parallel, using the generated Lagrangean multipliers, the LRH approach employs a new heuristic algorithm to arrive at a near-optimal upper-bound solution. With lower and upper bounds, we conduct a performance study on LRH with respect to accuracy and convergence speed under different parameter settings. We further draw comparisons between LRH and an existing practical approach via experiments over randomly generated and several well-known large sized networks. Numerical results demonstrate that LRH outperforms the existing approach in both accuracy and computational time complexity, particularly for larger sized networks.     

A scalable design of multigranularity optical cross-connects for the next-generation optical Internet

This paper proposes a scalable design for next-generation optical cross-connects (OXCs). We present a novel strategy for dimensioning the switching capability as a long term planning. Switching fabrics in OXCs have to be expanded according to traffic growth, which may incur a scalability problem due to the exponentially increasing cost in manufacturing and maintenance. The proposed scheme expands the switching capacity of OXCs with waveband- and fiber-switching components (or, equivalently, expands the network capacity with waveband- and fiber-switching tiers). To minimize the number of extra fibers for waveband- and fiber-switching tiers required to satisfy a given traffic matrix, we formulate the problem of routing and wavelength assignment (RWA) with tunnel allocation (RWAT) into a constraint programming (CP) process. The CP is simplified as two integer linear programming (ILP) processes that are performed sequentially. Experiments are conducted on four examples to compare the throughput and the number of switching points when different switching architectures are adopted under different traffic increase. The benefits of our approach are demonstrated. Finally, we conclude that the proposed optimization scheme can dimension the networks with expandability and scalability to the growing traffic demand.     

智能光网络中的路由和波长分配问题

随着下一代智能光网络概念的提出，应用于传统光网络的路由和波长分配方法面临着许多新的挑战。本以自动交换光网络为代表，分析了智能光网络中不同类型连接的特点和实现路由和波长分配的控制软件模块，并着重从路由模式、多粒度分层选路、路由和波长分配算法、信令路由协议等几个方面出发，对智能光网络中的路由和波长分配问题进行了深入的探讨。同时提出了相应的解决方案。     

光网络选路和波长分配研究

文章在叙述了光网络中选路和波长分配(RWA)要解决的基本问题后,对有关方面的近年研究作了综述,主要包括:虚拓扑重构、业务量疏导的RWA、多播RWA、抗毁网络的RWA.抗毁问题涉及WDM网络的抗毁选路、区分可靠性、网状网的快速恢复、多故障下的抗毁.     

A novel distributed control protocol in dynamic wavelength-routed optical networks

Path selection has long been one of the most important issues in the network design and management, which is also referred to as routing and wavelength assignment in the optical network domain. In this article we investigate the RWA problem for dynamic wavelength-routed mesh networks in a fully distributed controlled environment. We present a novel routing and signaling protocol called Asynchronous Criticality Avoidance (ACA), which is devised to reduce the mutual interference between lightpaths launched by different source-destination pairs to improve network performance in terms of blocking probability. With the fixed alternate routing architecture, the ACA protocol dynamically marks a set of wavelength channels as critical if the occupancy of the channels causes a bottleneck between an S-D pair with a width equal to or narrower than a predefined threshold. To support a distributed control environment, a suite of signaling processes is devised to realize the criticality avoidance mechanism, with which a two-stage routing and wavelength assignment (or criticality avoidance routing) is performed. The ACA protocol has been shown by simulations to be capable of better performance than existing schemes.     

Traffic engineering in multigranularity heterogeneous optical WDM mesh networks through dynamic traffic grooming

In this article we investigate the problem of efficiently provisioning connections of different bandwidth granularities in a heterogeneous WDM mesh network through dynamic traffic grooming schemes under traffic engineering principles. Due to the huge amount of traffic a WDM backbone network can support and the large geographic area it can cover, constructing and upgrading such an optical WDM network can be costly. Hence, it is extremely important for network operators to apply traffic engineering strategies to cost-effectively support different bandwidth granularity services using only the appropriate amount of network resources. This requires an optical WDM network to have multigranularity switching capability, and such a network tends to be a multivendor heterogeneous network. However, WDM network heterogeneity increases the difficulty and challenge of efficient traffic provisioning. In this article we present different TE issues that need to be carefully considered in such an optical WDM network, and propose possible solutions and extensions for the generalized multiprotocol label switching optical network control plane. We extend an existing generic graph model to perform efficient traffic grooming and achieve different TE objectives through simple shortest path computation algorithms. We show that our approach is very practical and very suitable for traffic engineering in a heterogeneous multigranularity optical WDM mesh network.     

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     

Waveband Switching for Dynamic Traffic Demands in Multigranular Optical Networks

Waveband switching (WBS) in conjunction with multigranular optical cross-connect (MG-OXC) architectures can reduce the cost and complexity of OXCs. In this paper, we study the performance of different MG-OXC architectures under dynamic traffic. In the case with online incremental traffic, we compare two MG-OXC architectures in terms of the blocking probability of new lightpath requests and study the impact of port counts and traffic loads. We develop an online integer linear programming model (On-ILP), which minimizes the number of used ports and the request blocking probability, given a fixed number of wavelengths and MG-OXC architecture. The On-ILP optimizes the routing of new lightpaths so as to maximize lightpath grouping and reduce the port count given that existing traffic cannot be rearranged. We also propose a new efficient heuristic algorithm, called maximum overlap ratio (MOR) to satisfy incremental traffic and compare it with the On-ILP, first-fit, and random-fit algorithms. Our results and analysis indicate that using WBS with MG-OXCs can reduce the size (and, hence, the cost) of switching fabrics compared to using ordinary OXCs. Based on the results and observations in the incremental traffic case, we further study the performance of a particular MG-OXC architecture under fully dynamic or fluctuating traffic. Our simulations show that the proposed heuristic algorithm waveband assignment with path graph, which groups wavelengths to bands and uses wavelength converters efficiently under fluctuating traffic, significantly outperforms other heuristic algorithms.     

Adaptive subcarrier-distribution algorithm for routing and spectrum allocation in OFDM-based elastic optical networks

In this paper, we have proposed the adaptive subcarriers-distribution routing and spectrum allocation (ASD-RSA) algorithm, which is the first elastic optical network routing and spectrum allocation algorithm based on distributed subcarriers. It allocates lightpaths to request adaptively and proved to achieve much lower bandwidth blocking probability than traditional routing and spectrum allocation algorithms based on centralized subcarriers with integer linear programming and dynamic simulation methods. Additionally, the ASD-RSA algorithm performs the best with three alternate routing paths; this character will decrease the calculating amount of both alternate routing path searching and spectrum allocation immensely in large networks.     

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.     

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

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

多域光网络中的动态RWA算法研究

随着光网络规模的不断增大,下一代智能光网络将被划分为多个路由域进行分布式管理.由于在这种具有分布式特点的多域光网络中,每个路由域只了解本地子网内的拓扑和资源信息,因此以往光网络中已有的基于全网信息的动态RWA算法将不在有效.文章首先分析了多域光网络中的动态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.     

Prediction-based routing as RWA in multilayer traffic engineering

Multilayer traffic engineering (MLTE) allows coping with ever-increasing and varying traffic demands in IP-over-Optical multilayer networks. It utilizes cross-layer TE (Traffic Engineering) techniques to provision optical lightpath capacity to the IP/MPLS (Internet Protocol/ Multi-Protocol Label Switching) logical topology on-demand. Such provisioning however causes optical connection arrival rates that pose strong performance requirements to Routing and Wavelength Assignment (RWA) strategies. Collecting up-to-date network information for the RWA with rapidly changing network states can be quite difficult. Exposing optical layer state information to the IP layer in the overlay model, or transforming this optical layer information in a workable representation in an integrated control plane is similarly problematic. Prediction-Based Routing (PBR) has been proposed as a RWA mechanism for optical transport networks; it bases routing not on possibly inaccurate or outdated network state, but instead on previous connections set-up. In this article, we propose to implement PBR as the RWA mechanism in the optical layer of a multilayer network, and use the predictive capabilities of PBR to expose dynamic optical network information into the multilayer traffic engineering algorithm with minimal control plane overhead. Some simulations show the benefits of using the PBR in the optical layer for MLTE purposes.     

A dynamic and quasi-centralized RWA method for optical fast circuit switching networks employing route pre-prioritization

We propose a new dynamic RWA algorithm for optical fast circuit switching networks, agile optical networks that can accommodate changing broadband demands. The algorithm utilizes pre-computed prioritized route candidates that reflect statistical information such as traffic distribution characteristics to attain better load balancing. The route priority is periodically distributed over a network and RWA for each path connection demand is processed in a distributed manner. Numerical experiments demonstrate that the algorithm matches the performance of a centralized RWA algorithm that uses all the necessary information on a network.     

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.     

Sparse Regeneration in Translucent Wavelength-Routed Optical Networks: Architecture,Network Design and Wavelength Routing

In this paper we study an alternate network architecture, called translucent network, to the fully transparent and fully opaque network architectures. In a translucent wavelength-routed optical network, a technique called sparse regeneration is used to overcome the severe lightpath blocking due to signal quality degradation and wavelength contention in a fully transparent network while using much less regenerators than in a fully opaque network. In this paper, we present a node model and a network model that perform sparse regeneration. We address the problem of translucent network design by proposing several regenerator placement algorithms based on different knowledge of future network traffic patterns. We also address the problem of wavelength routing under sparse regeneration by incorporating two regenerator allocation strategies with heuristic wavelength routing algorithms. We compare the performance of different regenerator placement algorithms and wavelength routing schemes through simulation experiments. The benefit of sparse regeneration is quantitatively measured under different network settings.This work was supported by NSF grants (ANI-0074121 and EPS-0091900).Portions of this work have appeared in the Proceedings of the OSA Optical Fiber Communications (OFC 1999) Conference [6] and the Proceedings of the IEEE Global Telecommunications (GLOBECOM 2001) Conference [12].     

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

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

Analysis and design of resilient multifiber wavelength-routedoptical transport networks

Wavelength-routed optical networks (WRONs) are attracting significant attention for future high-capacity transport applications. This paper studies resilient multifiber WRONs, investigating the influence on the network performance of the maximum number of wavelengths per fiber W restoration strategies, node functionality, and physical topology. Fiber requirements are analyzed for numerous network topologies both without and with link failure restoration, considering different optical cross-connect (OXC) configurations and terminal functionalities. An integer linear program (ILP) formulation is presented for the exact solution of the routing and wavelength allocation (RWA) problem, with minimal total number of fibers, F_T (W). Lower bounds on F_T(W) are discussed, and heuristic algorithms proposed. Three restoration strategies are considered and compared in terms of capacity requirement. Different network topologies are analyzed, to evaluate the influence of physical connectivity and network size on the restoration capacity. Network evolution in terms of growth in traffic demand is investigated to study the importance of wavelength conversion within the OXC's as a function of network size and connectivity, traffic demand, and wavelength multiplicity W