Worst-case analysis of dynamic wavelength allocation in opticalnetworks

This paper proposes algorithms for allocating wavelengths to connections (lightpaths) in optical wavelength division multiplexed networks, predominantly for ring topologies. A worst-case model is considered, where no blocking of lightpaths is allowed, and there are no assumptions made on the traffic arrival and holding times. The traffic is characterized only by its load L, which is the maximum number of lightpaths that can be present on any link, assuming no blocking. A dynamic traffic model is considered where requests to set up lightpaths arrive over time and, must be accommodated without rerouting existing lightpaths, and lightpaths may be terminated over time as well. For networks without wavelength conversion, we show that at least 0.5Llog ₂N wavelengths are required by any dynamic algorithm for rings of N nodes and present an algorithm that uses at most Llog₂ N+L wavelengths for rings and 2(L-1)log₂N for trees. We also study the worst-case behavior of the well-known first-fit algorithm, and show that it requires at most 2.52Llog₂N+5L wavelengths (small variants of these constants are proven as well). When limited wavelength conversion is allowed, we first show how to use expanders to insure no blocking in arbitrary topologies. Then, we present conversion patterns for rings with conversion degree d=2, which require Llog₂L+4L or 2Llog₂log₂L+4L wavelengths, thereby eliminating the dependence (that exists without wavelength conversion) between the number of wavelengths and N. We also consider different traffic models where lightpath setup requests arrive over time, but once set up, lightpaths are never taken down. For this model, the number of wavelengths needed is shown to be only max{0,L-d}+L for a conversion degree of d     

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.     

光因特网中动态综合考虑的资源分配算法

该文研究了光因特网络中的动态资源分配问题，提出了基于分层图模型的路由选择和波长分配算法。对于动态变化的业务到达请求，如果在已有的基于IP级的逻辑拓扑上不能有效建立，则需要为该请求按算法分配资源，即解决路由选择和波长分配问题。由于该文算法将IP层和光层综合进行考虑，所以能大大提高资源利用的有效性，取得较好的阻塞性能。仿真结果表明，该算法既能选择比较短的路由，又能使网络取得较低的阻塞率。     

Rerouting technique with dynamic traffic in WDM optical networks

In this paper, we have proposed an efficient wavelength rerouting algorithm for dynamic provisioning of lightpath. In wavelength division multiplexed (WDM) networks rerouting of lightpath can be used to improve throughput and to reduce blocking probability. We have proposed a shortest path wavelength rerouting (SPWRR) algorithm for dynamic traffic in WDM optical networks. The results have shown that SPWRR algorithm can improve blocking performance of the network. In this paper, low complexity algorithm has been developed which is used for the calculation of blocking probability of network. The proposed algorithm has also been applied on the realistic network such as NSFnet for calculation and optimization of blocking probability of the network.     

Dynamic lightpath establishment considering four-wave mixing in multifiber WDM networks

This paper proposes a dynamic lightpath establishment scheme considering four-wave mixing (FWM) in multifiber wavelength-division multiplexed (WDM) all-optical networks. The FWM is one of the most important physical impairments to be resolved in WDM networks because the FWM induces nonlinear inter-channel crosstalk and decays the performance of WDM networks. In WDM networks, data are transmitted via lightpaths. When the effect of FWM crosstalk is large, it is highly possible that data transmission fails even if lightpaths are correctly established. The proposed scheme aims to avoid not only the blocking of lightpath establishment but also the accumulation of FWM crosstalk by means of ingenious selection of routes, wavelengths, and fibers for lightpath establishment. In the proposed scheme, a route and a wavelength are selected for each lightpath based on wavelength availability and wavelength placement of established lightpaths. Furthermore, fibers on the route are selected based on estimated FWM power. In this paper, we show the effectiveness of the proposed scheme through simulation experiments.     

Optimal nonuniform wavebanding in WDM mesh networks

Grouping together a set of consecutive wavelengths in a WDM network and switching them together as a single waveband could achieve savings in switching costs of an optical cross-connect. This technique is known as waveband switching. While previous work has focused on either uniform band sizes or nonuniform band sizes considering a single node or ring networks, in this paper we focus on optimizing the number of wavebands and their sizes for mesh topologies. We formulate a problem of optimizing the number of wavebands in a mesh network for a given set of lightpaths. The objective of the band minimization problem is to minimize the number of nonuniform wavebands in the network while satisfying the traffic requests. We formulate an integer linear program and propose efficient heuristics. Simulation results are presented to demonstrate the effectiveness of the proposed approaches under static traffic case. Our results show that the number of switching elements can be reduced by a large amount using waveband switching compared to wavelength switching. We also apply the proposed waveband strategy to the dynamic stochastic traffic case and evaluate the network performance in terms of blocking probability through numerical simulations.     

Path protection WDM networks with impaired-transmission

In wavelength division multiplexing (WDM) networks, failures may imply severe loss of data due to the high transmission rates, leading to the need for employment of protective mechanisms. Transparency and switching in all-optical networks cause physical impairment, which can significantly degrade signal quality. If the signal quality along a path is below acceptable values, this path cannot be used for incoming requests in the establishment of lightpaths. Therefore, quality must be checked by the routing and wavelength assignment algorithm. The present article introduces two novel algorithms for shared path protection in WDM networks that take into consideration the Polarization Mode Dispersion, Amplifier Spontaneous Emission, and homowavelength cross-talk physical impairments during path selection. The efficiency of these algorithms is compared to that of their impairment-unaware counterparts.     

Survivable lightpath provisioning in WDM mesh networks under shared path protection and signal quality constraints

This paper addresses the problem of survivable lightpath provisioning in wavelength-division-multiplexing (WDM) mesh networks, taking into consideration optical-layer protection and some realistic optical signal quality constraints. The investigated networks use sparsely placed optical-electrical-optical (O/E/O) modules for regeneration and wavelength conversion. Given a fixed network topology with a number of sparsely placed O/E/O modules and a set of connection requests, a pair of link-disjoint lightpaths is established for each connection. Due to physical impairments and wavelength continuity, both the working and protection lightpaths need to be regenerated at some intermediate nodes to overcome signal quality degradation and wavelength contention. In the present paper, resource-efficient provisioning solutions are achieved with the objective of maximizing resource sharing. The authors propose a resource-sharing scheme that supports three kinds of resource-sharing scenarios, including a conventional wavelength-link sharing scenario, which shares wavelength links between protection lightpaths, and two new scenarios, which share O/E/O modules between protection lightpaths and between working and protection lightpaths. An integer linear programming (ILP)-based solution approach is used to find optimal solutions. The authors also propose a local optimization heuristic approach and a tabu search heuristic approach to solve this problem for real-world, large mesh networks. Numerical results show that our solution approaches work well under a variety of network settings and achieves a high level of resource-sharing rates (over 60% for O/E/O modules and over 30% for wavelength links), which translate into great savings in network costs.     

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.     

Lightpath Rerouting Algorithm to enhance blocking performance in all-optical WDM network without wavelength conversion

In this paper, we have proposed an efficient wavelength rerouting algorithm for dynamic provisioning of lightpath. In wavelength-division multiplexed (WDM) networks rerouting of lightpath can be used to improve throughput and to reduce blocking probability. We have proposed a Lightpath Rerouting Algorithm (LRRA) for dynamic traffic in WDM optical networks. The results have shown that LRRA can improve blocking performance of the network. In this paper, low complexity algorithm has been developed which is used for the calculation of blocking probability of network. The proposed algorithm has also been applied on the realistic network such as NSFnet for calculation and optimization of blocking probability of the network. The results have also shown that the proposed algorithm can be implemented to huge networks for good blocking performance of the network.     

Quality-of-Service Based Protection in MPLS Control WDM Mesh Networks

Intelligent methods for automatic protection and restoration are critical in optical transport mesh networks. This paper discusses the problem of quality-of-service (QoS)-based protection in terms of the protection-switching time and availability for end-to-end lightpaths in a WDM mesh network. We analyze the backup lightpath-sharing problem in such networks and study the correlation of the working lightpaths and the impact of the correlation on the sharing of the backup lightpaths. We present a multi-protocol-label-switching (MPLS) control-based fully distributed algorithm to solve the protection problem. The proposed algorithm includes intelligent and automatic procedures to set up, take down, activate, restore, and manage backup lightpaths. It greatly reduces the required resources for protection by allowing the sharing of network resources by multiple backup lightpaths. At the same time, it guarantees, if possible, to satisfy the availability requirement even with resource sharing by taking the correlation of working lightpaths into consideration. A simple analysis of the proposed algorithm in terms of computation time and message complexity indicates that the implementation of the algorithm is practical. The illustrative studies that compare the performance of 1:1, unlimited sharing, and QoS-based backup sharing algorithms indicate that QoS-based sharing achieves comparable performance as unlimited sharing, which is much better than the 1:1 backup scheme in terms of connection blocking probability, average number of connections in the network for a given offered load, and network resource utilization.     

一种公平的多优先级WDM光网络波长分配算法

文章研究了波分复用(WDM)光网络中动态业务下的波长分配问题,在无波长转换器的条件下,提出了一种加入了公平性考虑的动态门限算法.该算法在支持多优先级的动态门限法的基础上,通过更新初始优先级减少了不同距离光路连接请求间的阻塞率差别,改善了公平性.计算机仿真结果说明了该算法的有效性.     

A novel switching architecture for ATM networks

It is known that the flexibility and capacity of asynchronous transfer mode (ATM) networks can meet the bandwidth requirements of multimedia applications. In ATM networks, switching is one of the major bottlenecks of end-to-end communication. We propose using a multiple partitionable circular bus network (MPCBN) as an ATM switch. Connection requests are first transformed into a graph where vertices and edges represent connection requests and conflicts among connection requests, respectively. We then use a graph traversal algorithm to select a maximal set of requests for execution in physically partitioned buses. An approach of using finite projective planes is then used to reduce the number of switch points from O(N²) to O(N √N), where N is the number of ports of a switch. A performance evaluation for both uniform and bursty data sources shows that the approach of using finite projective planes to reduce the number of switch points results in a small increase of cell loss probability     

Comprehensive performance modeling and analysis of multicasting in optical networks

Multicasting is becoming increasingly important in today's networks. In optical networks, optical splitters facilitate the multicasting of optical signals. By eliminating the transmission of redundant traffic over certain links, multicasting can improve network performance. However, in a wavelength-division multiplexed (WDM) optical network, the lack of wavelength conversion necessitates the establishment of a single multicast circuit (light-tree) on a single wavelength. On the other hand, establishing several unicast connections (lightpaths) to satisfy a multicast request, while requiring more capacity, is less constrained in terms of wavelength assignment. The objective of the paper is to evaluate the tradeoff between capacity and wavelength continuity in the context of optical multicasting. To this end, we develop accurate analytical models with moderate complexity for computing the blocking probability of multicast requests realized using light-trees, lightpaths, and combinations of light-trees and lightpaths. Numerical results indicate that a suitable combination of light-trees and lightpaths performs best when no wavelength conversion is present.     

Physical layer performance benchmarking of two metropolitan area network configurations

This paper investigates the problem of dynamic survivable lightpath provisioning against single-node/link failures in optical mesh networks employing wavelength-division multiplexing (WDM).We unify various forms of segment protection into generalized segment protection (GSP). In GSP, the working path of a lightpath is divided into multiple overlapping working segments, each of which is protected by a node-/link-disjoint backup segment. We design an efficient heuristic which, upon the arrival of a lightpath request, dynamically divides a judiciously selected working path into multiple overlapping working segments and computes a backup segment for each working segment while accommodating backup sharing. Compared to the widely considered shared-path protection scheme, GSP achieves much lower blocking probability and shorter protection-switching time for a small sacrifice in control and management overhead.On the basis of generalized segment protection, we present a new approach to provisioning lightpath requests according to their differentiated quality-of-protection (QoP) requirements. We focus on one of the most important QoP parameters—namely, protection-switching time—since lightpath requests may have differentiated protection-switching-time requirements. For example, lightpaths carrying voice traffic may require 50 ms protection-switching time while lightpaths carrying data traffic may have a wide range of protection-switching-time requirements. Numerical results show that our approach achieves significant performance gain which leads to a remarkable reduction in blocking probability.While our focus is on the optical WDM network, the basic ideas of our approaches can be applied to multi-protocol label switching (MPLS) networks with appropriate adjustments, e.g., differentiated bandwidth granularities.     

IP over WDM网中的综合选路算法

研究了IP over WDM网中,当节点不具备波长变换能力并且配备有限光收发器对时,如何利用综合选路(IR)算法为到达业务请求建立标签交换路径(LSP)。提出一种新颖的辅助图模型(AGM)表示网络的当前状态,基于AGM提出一种动态IR算法-最小光收发器对法(MTA)。MTA总是选择占用光收发器对最少的通路来建立LSP,仿真结果表明：与已有算法相比,MTA可以降低全网的阻塞率,从而提高业务通过率,并且有利于减少业务连接所经光／电变换的次数。     

Hybrid connection algorithm: A strategy for efficient restoration in WDM optical networks

In present communication, we propose a modified resource allocation strategy, namely, hybrid connection algorithm, for achieving efficient restoration in WDM optical networks. The main theme of the algorithm is that, while attempting connection establishment, a wavelength is reserved in advance for providing resources for backup lightpaths. The analysis and the comparison of the proposed strategy with other existing strategies has been undertaken using metrics such as, restoration efficiency, number of wavelength links used by primary and backup lightpaths, and the percent link utilization. The proposed strategy provides 100% restoration efficiency and much better performance than the existing techniques.     

An efficient algorithm for virtual-wavelength-path routing minimizing average number of hops

We present a novel heuristic algorithm for routing and wavelength assignment in virtual-wavelength-path (VWP) routed wavelength-division multiplexed optical networks. We are the first to take up the approach of both minimizing the network cost, as well as maximizing the resource utilization. Our algorithm not only minimizes the number of wavelengths required for supporting the given traffic demand on any given topology, but also aims to minimize the mean hop length of all the lightpaths which in turn maximizes the resource utilization. The algorithm initially assigns the minimum hop path to each route and then performs efficient rerouting to reduce the number of wavelengths required while also trying to minimize the average hop length. To further reduce the network cost, we also propose a wavelength assignment procedure for VWP routed networks which minimizes the number of wavelength converters required. Our algorithm has been tested on various topologies for different types of traffic demands and has been found to give solutions much better than previous standards for this problem.     

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

Wavelength routing with spare reconfiguration for all-optical WDM networks

This study presents a wavelength-routing scheme with spare reconfiguration (SR) to construct dependable all-optical wavelength-division-multiplexing (WDM) networks. Path protection using shared spare lightpaths is a general wavelength-routing method for reducing blocking probability while minimizing demand for spare resources. However, in a dynamic traffic environment, this method may still yield a poor performance because a wavelength on a link is very likely to be continuously held by a spare lightpath and to be unable to be assigned to the working lightpath of a new connection. This study develops a spare reconfiguration mechanism with wavelength reassignment (SR/spl I.bar/WR) and path reassignment (SR/spl I.bar/PR) to make the spare dynamic and thus further reduce the blocking probability. The proposed wavelength routing with SR proceeds in three stages and has polynomial time complexity. Extensive simulation experiments were conducted on the NSFNET and the K5 fully connected network to investigate the performance of the proposed wavelength routing with SR. Results of this study show that the proposed wavelength routing with SR can reduce the blocking probability compared with the general wavelength routing with just shared spare lightpaths by choosing a positive tuning cost. In addition, the improvement of the blocking performance is maximized when using SR/spl I.bar/WR followed by SR/spl I.bar/PR.