Offline Impairment-Aware Routing and Wavelength Assignment Algorithms in Translucent WDM Optical Networks

Physical impairments in optical fiber transmission necessitate the use of regeneration at certain intermediate nodes, at least for certain lengthy lightpaths. We design and implement impairment-aware algorithms for routing and wavelength assignment (IA-RWA) in translucent optical networks. We focus on the offline version of the problem, where we are given a network topology, the number of available wavelengths and a traffic matrix. The proposed algorithm selects the 3R regeneration sites and the number of regenerators that need to be deployed on these sites, solving the regenerator placement problem for the given set of requested connections. The problem can be also posed in a slightly different setting, where a (sparse) placement of regenerators in the network is given as input and the algorithm selects which of the available regenerators to use, solving the regenerator assignment problem. We formulate the problem of regenerator placement and regenerator assignment, as a virtual topology design problem, and address it using various algorithms, ranging from a series of integer linear programming (ILP) formulations to simple greedy heuristic algorithms. Once the sequence of regenerators to be used by the non-transparent connections has been determined, we transform the initial traffic matrix by replacing non-transparent connections with a sequence of transparent connections that terminate and begin at the specified 3R intermediate nodes. Using the transformed matrix we then apply an IA-RWA algorithm designed for transparent (as opposed to translucent) networks to route the traffic. Blocked connections are re-routed using any remaining regenerator(s) in the last phase of the algorithm.      

On the routing and wavelength assignment in multifiber WDM networks

This paper addresses the problem of routing and wavelength assignment (RWA) in multifiber WDM networks with limited resources. Given a traffic matrix, the number of fibers per link, and the number of wavelengths a fiber can support, we seek to maximize the carried traffic of connections. We formulate the problem as an integer linear program (ILP), and show that the lightpaths selected by this formulation can indeed be established by properly configuring the optical switches. An upper bound on the carried traffic can be computed by solving the linear programming (LP)-relaxation of the ILP formulation. It is shown that this bound can be also computed exactly, and in polynomial-time, by solving a significantly simplified LP which considers only one wavelength. The bound can, thus, easily scale to an arbitrarily large number of wavelengths. Furthermore, we demonstrate that any instance of the RWA problem is also an instance of the more general maximum coverage problem. This allows us to take a greedy algorithm for maximum coverage and obtain an algorithm which provides solutions for the RWA problem that are guaranteed to be within a factor of (1-(1/e)) of the optimal solution. Each iteration of the greedy algorithm selects a set of lightpaths that realizes, using one wavelength, the maximum number of connection requests not previously realized. Computational results confirm the high efficiency of our proposed algorithm.     

Regenerator Placement and Traffic Engineering with Restoration in GMPLS Networks

In this paper, we study regenerator placement and traffic engineering of restorable paths in generalized multiprotocol label switching (GMPLS) networks. Regenerators are necessary in optical networks in order to cope with transmission impairments. We study a network architecture where regenerators are placed only at selected nodes for decreasing cost of regeneration. We propose two heuristic algorithms for optimum placement of these regenerators. Performances of these algorithms in terms of required number of regenerators and computational complexity are evaluated. In this network architecture with sparse regeneration, off-line computation of working and restoration paths is studied for traffic engineering with path rerouting as the restoration scheme. We study two approaches for selecting working and restoration paths from a set of candidate paths and formulate each method as an integer linear programming (ILP) problem. A traffic uncertainty model is developed in order to compare these methods based on their robustness with respect to changing traffic patterns. Traffic engineering methods are compared based on number of additional demands resulting from traffic uncertainties that can be carried over the network. Proposed heuristic regenerator placement algorithms are also evaluated from a traffic engineering point of view.     

Optical network design with mixed line rates

Future telecommunication networks employing optical wavelength-division multiplexing (WDM) are expected to be increasingly heterogeneous and support a wide variety of traffic demands. Based on the nature of the demands, it may be convenient to set up lightpaths on these networks with different bit rates. Then, the network design cost could be reduced because low-bit-rate services will need less grooming (i.e., less multiplexing with other low-bit-rate services onto high-capacity wavelengths) while high-bit-rate services can be accommodated on a wavelength itself. Future optical networks may support mixed line rates (say over 10/40/100 Gbps). Since a lightpath may travel a long distance, for high bit rates, the effect of the physical impairments along a lightpath may become very significant (leading to high bit-error rate (BER)); and the signal’s maximum transmission range, which depends on the bit rate, will become limited.In this study, we propose a novel, cost-effective approach to design a mixed-line-rate (MLR) network with transmission-range (TR) constraint. By intelligent assignment of channel rates to lightpaths, based on their TR constraint, the need for signal regeneration can be minimized, and a “transparent” optical network can be designed to support all-optical end-to-end lightpaths. The design problem is formulated as an integer linear program (ILP). A heuristic algorithm is also proposed. Our results show that, with mixed line rates and maximum transmission range constraints, one can design a cost-effective network.     

Cost efficient traffic grooming and regenerator placement in impairment-aware optical WDM networks

In this paper, we address the problem of traffic grooming and regenerator placement in a WDM optical network in which lightpaths are hop-constrained by physical impairments. The efficient placement of regenerators and electronic grooming equipment at ROADM nodes for a given network topology is required such that all traffic demands can be supported with minimum cost. We present a detailed ROADM node architecture together with an associated cost model. We model the problem by Integer Linear Programming (ILPs) and propose an auxiliary-graph-based heuristic for jointly placing regenerators and electronic grooming equipment in the network. To evaluate the performance of the proposed heuristic, we also derive a lower bound on the network cost. The numerical results show that combining the grooming problem with the placement of regenerators reduces the network cost significantly compared to the cases in which traffic grooming and regenerator placement are handled separately. The performance of the proposed polynomial-time heuristic is very close to the lower bound and approaches the bound as the network load increases.     

Wavelength Assignment to Minimize the Number of SONET ADMs in WDM Rings*†

Optical wavelength division multiplexing (WDM) rings are being deployed to support SONET/SDH self-healing rings. In such systems, multiple SONET/SDH self-healing rings are realized over a single physical optical ring through wavelength division multiplexing. The cost of such a system is dominated by the SONET add/drop multiplexers (ADMs). To minimize the system cost, algorithms must be developed to assign wavelengths to lightpaths in the system so that the number of ADMs required is minimized. This problem of optimal wavelength assignment to minimize the number of SONET ADMs is known to be NP-hard. Existing heuristic algorithms for this problem include the assign first heuristic, the iterative matching heuristic and the iterative merging heuristic. In this paper, we develop an integer linear programming (ILP) formulation for this problem, propose a new wavelength assignment heuristic, and evaluate the existing and the newly proposed heuristic using the ILP formulation. We conclude that the performance of the newly proposed heuristic is very close to optimal.     

Distributed optical control plane for dynamic lightpath establishment in translucent optical networks based on reachability graph

In transparent optical networks, physical layer impairments (PLIs) incurred by non-ideal optical transmission media accumulate along an optical path, and the overall effect determines the optical feasibility of the lightpaths. In addition, transparent optical networks suffer from inefficient wavelength utilization, as a connection request may be rejected because of non-availability of a common wavelength on all the links along the chosen route. To increase optical reach, resource utilization, and average call acceptance ratio (and hence revenues), network operators are resort to translucent optical networks. In these networks a limited number of regenerators are placed at a selected set of nodes. In this scenario development of an optical control plane which is aware of PLIs, location and number of regenerators, is of paramount importance for on-demand lightpath provisioning. In this paper, we propose a novel approach of constructing a reachability graph of the physical network considering PLIs and regenerators. If there is no transparent path in the physical network, we route the connections with multiple transparent segments on the reachability graph. We propose efficient mechanisms and corresponding GMPLS protocol extensions for impairment and regenerator aware routing and wavelength assignment (IRA-RWA) in translucent optical networks. The simulation results suggest that our proposed approach together with LSP stitching signaling mechanism is feasible to implement and close to deployment.     

Accounting for Shared Regenerators in GMPLS-Controlled Translucent Optical Networks

In translucent optical networks, the usage of sparse opto-electronic regenerators permits to overcome optical signal quality degradations. In dynamic translucent optical networks, where lightpaths are established upon request, regenerators can be effectively time shared. However, the current generalized multiprotocol label switching (GMPLS) protocol suite does not consider how to dynamically reserve and release shared regenerators and how to distribute regenerator availability information to network nodes. In this paper, four Translucent Lightpath Dynamic Provisioning (TLDP) schemes are proposed to establish lightpaths in dynamic distributed translucent optical networks. TLDP schemes differently combine the utilization of specific open shortest path first-traffic engineering (OSPF-TE) or resource reservation protocol-traffic engineering (RSVP-TE) extensions and shared regenerator availability information. Simulation results show that TLDP scheme based on OSPF-TE extensions obtains lower lightpath setup time, but higher control plane load than TLDP schemes based on RSVP-TE extensions. Moreover, schemes based on RSVP-TE extensions or on OSPF-TE extensions obtain the same lowest blocking probability.      

Translucent network design from a CapEx/OpEx perspective

Translucent wdm network design has been widely investigated during the last 10 years. Translucent networks stand halfway between opaque and transparent networks improving the signal budget while reducing the network cost. On one hand, opaque networks provide satisfying quality from source to destination by the use of electrical reg regeneration (Re-amplifying, Re-shaping, and Re-timing) at each network node. In addition to their high cost inherent to numerous 3R regenerations, opaque networks are also constrained by the bit-rate dependence of electrical components. Transparent networks, on the other hand, do not include any electrical regeneration; therefore, the signal quality is degraded due to the accumulation of linear and non-linear effects along the signal’s route. Translucent networks include electrical regeneration at some network nodes. Among the different possible strategies for translucent network design, sparse regeneration inserts regenerators whenever needed to help establish connection requests. In this context the objective of translucent network design is to judiciously choose the regeneration sites in order to guarantee a certain quality of transmission while minimizing the network cost. In this paper, we propose to solve the translucent network design problem by introducing a heuristic for routing, wavelength assignment, and regenerator placement. This heuristic, called COR2P (Cross-Optimization for RWA and Regenerator Placement) aims not only to minimize the number of required regenerators, but also to minimize the number of regeneration sites. In this perspective, we introduce an original cost function that contributes to the optimization of CapEx/OpEx expenditures in translucent network design. In fact, the CapEx-to-OpEx ratio strongly depends on the pricing and management strategy of the carrier. In this respect, COR2P is designed in a way that its parameters can be adjusted according to carriers’ strategies. In order to discuss its different features, we compare COR2P performance with two other algorithms proposed in the literature for translucent network design.     

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.     

A practical approach for routing and wavelength assignment in largewavelength-routed optical networks

We consider large optical networks in which nodes employ wavelength-routing switches which enable the establishment of wavelength-division-multiplexed (WDM) channels, called lightpaths, between node pairs. We propose a practical approach to solve routing and wavelength assignment (RWA) of lightpaths in such networks. A large RWA problem is partitioned into several smaller subproblems, each of which may be solved independently and efficiently using well-known approximation techniques. A multicommodity flow formulation combined with randomized rounding is employed to calculate the routes for lightpaths. Wavelength assignments for lightpaths are performed based on graph-coloring techniques. Representative numerical examples indicate the accuracy of our algorithms     

考虑功率限制的WDM光网有效设计

提出了一种基于禁忌搜索技术的启发式算法有效波长与路由分配(RWA-TS-P)来解决考虑功率限制的WDM光网的优化设计。该算法建立在局部搜索贪婪算法RWA-greedy之上,引入了功率验证过程来保证建立光路的功率有效性。通过环网和网状网的设计实例验证了算法的性能。数值结果表明,该算法能够在保证网络中建立的所有光路功率有效性的前提下最优地配置网络资源,同时具有可以控制的计算复杂性。     

Challenges and requirements for introducing impairment-awareness into the management and control planes of ASON/GMPLS WDM networks

The absence of electrical regenerators in transparent WDM networks significantly contributes to reduce the overall network cost. In transparent WDM networks, a proper resource allocation requires that the presence of physical impairments in routing and wavelength assignment (RWA) and lightpath provisioning be taken into account. In this article a centralized, a hybrid centralized-distributed and two distributed approaches that integrate information about most relevant physical impairments in RWA and lightpath provisioning are presented and assessed. Both centralized and hybrid approaches perform a centralized path computation at the management-plane level, utilizing physical impairment information, while the lightpath provisioning is done by the management plane or the control plane, respectively. The distributed approaches fall entirely within the scope of the ASON/GMPLS control plane. For these two approaches, we provide functional requirements, architectural functional blocks, and protocol extensions for implementing either an impairment-aware real-time RWA, or a lightpath provisioning based on impairment-aware signaling     

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

Design of Translucent Optical Networks: Partitioning and Restoration

We discuss the problem of designing translucent optical networks composed of restorable, transparent subnetworks interconnected via transponders. We develop an integer linear programming (ILP) formulation for partitioning an optical network topology into subnetworks, where the subnetworks are determined subject to the constraints that each subnetwork satisfies size limitations, and it is two-connected. A greedy heuristic partitioning algorithm is proposed for planar network topologies. We use section restoration for translucent networks where failed connections are rerouted within the subnetwork which contains the failed link. The network design problem of determining working and restoration capacities with section restoration is formulated as an ILP problem. Numerical results show that fiber costs with section restoration are close to those with path restoration for mesh topologies used in this study. It is also shown that the number of transponders with the translucent network architecture is substantially reduced compared to opaque networks.     

Uniform waveband assignment in optical mesh networks

The cost of an optical network in wavelength division multiplexing (WDM) networks can be reduced using optical reconfigurable optical add/drop multiplexers (ROADMs), which allow traffic to pass through without the need for an expensive optical-electro-optical (O-E-O) conversion. Waveband switching (WBS) is another technique to reduce the network cost by grouping consecutive wavelengths and switching them together using a single port per waveband. WBS has attracted the attention of researchers for its efficiency in reducing switching complexity and therefore cost in WDM optical networks. In this paper, we consider the problem of switching wavelengths as non-overlapping uniform wavebands, per link, for mesh networks using the minimum number of wavebands. Given a fixed band size b _s , we give integer linear programming formulations and present a heuristic solution to minimize the number of ROADMs (number of wavebands) in mesh networks that support a given traffic pattern. We show that the number of ROADMs (or number of ports in band-switching cross-connects) can be reduced significantly in mesh networks with WBS compared to wavelength switching using either the ILP or the heuristic algorithm. We also examine the performance of our band assignment algorithms under dynamic traffic.     

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

Considering physical layer impairments in offline RWA

We consider the offline version of the routing and wavelength assignment problem in transparent all-optical networks. In such networks and in the absence of regenerators, the signal quality of a transmission degrades due to physical layer impairments. Certain physical effects cause choices for one lightpath to affect and be affected by the choices made for other lightpaths. This interference among lightpaths is particularly difficult to formulate in an offline algorithm, since in this version of the problem we start without any established connections, and the utilization of lightpaths are the variables of the problem. For this reason the majority of work performed in this field either neglects lightpath interactions or assumes a worst case interference scenario. In this article we present a way to formulate interlightpath interference as additional constraints on RWA and show how to incorporate these constraints in an IA-RWA algorithm that directly accounts for the most important physical layer impairments. The objective of the resulting cross-layer optimization problem is not only to serve the connection requests using the minimum number of wavelengths (network layer objective), but also to select lightpaths that have acceptable quality of transmission performance (physical layer objective).     

Resource efficient network design and traffic grooming strategy with guaranteed survivability

In WDM networks, path protection has emerged as a widely accepted technique for providing guaranteed survivability of network traffic. However, it requires allocating resources for backup lightpaths, which remain idle under normal fault-free conditions. In this paper, we introduce a new design strategy for survivable network design, which guarantees survivability of all ongoing connections that requires significantly fewer network resources than protection based techniques. In survivable routing, the goal is to find a Route and Wavelength Assignment (RWA) such that the logical topology remains connected for all single link failures. However, even if the logical topology remains connected after any single link fault, it may not have sufficient capacity to support all the requests for data communication, for all single fault scenarios. To address this deficiency, we have proposed two independent but related problem formulations. To handle our first formulation, we have presented an Integer Linear Program (ILP) that augments the concept of survivable routing by allowing rerouting of sub-wavelength traffic carried on each lightpath and finding an RWA that maximizes the amount of traffic that can be supported by the network in the presence of any single link failure. To handle our second formulation, we have proposed a new design approach that integrates the topology design and the RWA in such a way that the resulting logical topology is able to handle the entire set of traffic requests after any single link failure. For the second problem, we have first presented an ILP formulation for optimally designing a survivable logical topology, and then proposed a heuristic for larger networks. Experimental results demonstrate that this new approach is able to provide guaranteed bandwidth, and is much more efficient in terms of resource utilization, compared to both dedicated and shared path protection schemes.     

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.