QoS-driven multicast routing in sparse-splitting optical networks

This paper investigates the quality-of-service (QoS)-driven multicast routing problem in a sparse-splitting optical network. The main objective is to minimize the total cost of wavelength channels utilized by the light-tree while satisfying required QoS parameters. In this paper, both the optical-layer constraints (e.g., optical signal power) and application-layer requirements (e.g., end-to-end delay and inter-destination delay variation) are considered as the QoS parameters. First, integer linear programming (ILP) formulations to solve the optimal multicast routing problem with the given QoS parameters are presented. Solving the ILP formulations for large-scale networks can easily overwhelm the capabilities of state-of-the-art computing facilities, and hence, a heuristic algorithm is proposed to construct a feasible light-tree that satisfies the required QoS parameters in large-scale networks. Simulation results demonstrate the performance of the proposed heuristic algorithm in terms of the cost of utilized wavelength channels.     

Group-based spectrum assignment in dynamic flex-grid optical networks

Traditional wavelength switched optical network employing wavelength-division-multiplexing (WDM) technology, allocates constant spectrum band to different kinds of services, which lacks flexibility in spectrum provisioning and thus reduces the resource utilization efficiency. Flex-grid technology, which introduces a finer spectrum granularity and allocates spectrum to different services flexibly according to their required bandwidth, is considered a promising candidate solution to improve the resource utilization efficiency of an optical network. However, since multiple contiguous spectrum granularities are usually assigned to a single service in such flex-grid optical network, the spectrum continuity and contiguity constraints should always be guaranteed, which may induce spectrum fragmentation. With the accumulation of spectrum fragmentation, available spectrum resources decrease, and this will greatly worsen the performance of the whole network, especially in networking. Therefore, spectrum fragmentation is considered a serious problem in flex-grid optical networks and many schemes have been proposed to solve it. These existing schemes, known as defragmentation, can reduce spectrum fragmentation either by rerouting the lightpath or by reallocating the spectrum for a service, which re-optimizes the spectrum resources. However, in the rerouting or reallocation procedure, existing traffic may be disrupted or extra resources, such as alternative spectrum or expensive spectrum convertors, are needed. None of these schemes can solve spectrum fragmentation with both no disrupted traffic and extra resources. It is because all these schemes utilize remedial methods to solve fragmentation problem and either disrupted traffic or extra resources are the cost when they cope with the defragmented spectrum. Different from all the above schemes, we propose a precautionary method to solve fragmentation problem in this paper. By introducing group-based spectrum assignment algorithm into flex-grid optical networks, spectrum resources are sorted into groups and each spectrum group only accommodates one specific kind of services. Since released spectrum can always be reused by the services of the same kind, spectrum fragmentation is prevented from its generation. Simulation results demonstrate that the proposed algorithm induces no spectrum fragmentations and is suitable to accommodate high-speed services.     

Differential evolution optimization applied to the routing and spectrum allocation problem in flexgrid optical networks

Flexible optical network (FON) architectures are considered a very promising solution where spectrum resources are allocated within flexible frequency grids. Routing and spectrum allocation (RSA) in FON is an NP-complete problem. So far, this problem has been optimally solved for small instances with integer linear programming and has been suboptimally solved for more realistic instances by heuristic strategies. In this paper, we introduce the application of differential evolution (DE) to the off-line RSA problem in flexible optical networks. To the best of our knowledge, our work is the first application of a DE algorithm to the RSA problem. We develop two DE permutation-based algorithms named DE general approach (DE-GC) and DE relative position index (DE-RPI). Comparative studies show that in many cases, DE outperforms many other well-known evolutionary computational approaches. Furthermore, the method typically requires few control parameters. An illustrative example of the application of the DE-based algorithms is presented, and then, different heuristics are compared against the DE-RSA algorithms. Algorithms are evaluated in different test bench optical networks, such as the NSFnet and the European optical network, and for networks up to 40 nodes, such as the USA and Japan networks. Moreover, the DE-based algorithms save up to 37 % of spectrum utilization for the NSFnet and 13 and 15 % for the USA and Japan networks, respectively.     

Scalable dimensioning of optical transport networks for grid excess load handling

Grids consist of the aggregation of numerous dispersed computational and storage resources, able to satisfy even the most demanding computing jobs. An important aspect of Grid deployment is the allocation and activation of installed network capacity, needed to transfer data and jobs to and from remote resources. Due to the data-intensive nature of Grid jobs, it is expected that optical transport networks will play an important role in Grid deployment. As Grids possibly consist of high numbers of resources, and users, solving the network dimensioning problem (i.e. determining the number of wavelength channels per fiber and wavelength granularity required) using straightforward Integer Linear Programs (ILP) does not scale well with increasing number of jobs. Therefore, we propose the use of Divisible Load Theory (DLT) when modeling the OCS (with wavelength translation) dimensioning problem in this context. We compare this approach to both an exact ILP and heuristic (derived from the exact ILP) approach as a function of the job arrival process, network related parameters and the Grid job scheduling strategy on the Grid. Results show the convergence of the DLT-based and the exact ILP approach, which indicates that the DLT-based approach is of practical use in cases where the exact ILP-based problem becomes intractable. We study an excess load scenario and evaluate the network cost for varying wavelength granularity, fiber/wavelength cost models, network topology and traffic demand asymmetry under multiple Grid scheduling strategies. Results indicate the suitability of our DLT-based approach as an Optical Transport Network dimensioning tool to be used by network operators.     

Design of programmable logic device based on electro-optic effect of lithium-niobate-based Mach–Zehnder interferometers

Elastic optical network (EON) technology is considered as a very promising candidate for future high-speed networks due to its intrinsic flexibility and high efficiency in allocating the optical spectrum resources. The key issue that has to be addressed in EON is the routing and spectrum allocation (RSA) problem. RSA is NP-hard problem that has to be solved in an efficient manner. It is a highly challenging task particularly in the case of large problem instances. In this paper, we applied the bee colony optimization (BCO) metaheuristic approach to solve the RSA problem in EON with static traffic demands. The objective of the proposed BCO–RSA algorithm is to minimize both the network spectrum utilization and the average path length criterions. The results of numerous experimental studies show that our BCO–RSA algorithm performs superior compared to some benchmark greedy heuristics as well as to differential evolution (DE) metaheuristic algorithm recently proposed in the literature. The algorithm is evaluated in different realistic size optical networks, such as the NSFnet, two European optical networks (EON-19 and EON-28) and the USA network topology. Simulation results demonstrate that considerable spectrum savings could be achieved with our BCO–RSA algorithm compared to other considered approaches. In addition, we analyzed the efficiency of the BCO–RSA algorithm and compare it with the competitive DE approach according to the required CPU time and the convergence speed.     

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.     

Shared Risk Link Group (SRLG)-Diverse Path Provisioning Under Hybrid Service Level Agreements in Wavelength-Routed Optical Mesh Networks

The static provisioning problem in wavelength-routed optical networks has been studied for many years. However, service providers are still facing the challenges arising from the special requirements for provisioning services at the optical layer. In this paper, we incorporate some realistic constraints into the static provisioning problem, and formulate it under different network resource availability conditions. We consider three classes of shared risk link group (SRLG)-diverse path protection schemes: dedicated, shared, and unprotected. We associate with each connection request a lightpath length constraint and a revenue value. When the network resources are not sufficient to accommodate all the connection requests, the static provisioning problem is formulated as a revenue maximization problem, whose objective is maximizing the total revenue value. When the network has sufficient resources, the problem becomes a capacity minimization problem with the objective of minimizing the number of used wavelength-links. We provide integer linear programming (ILP) formulations for these problems. Because solving these ILP problems is extremely time consuming, we propose a tabu search heuristic to solve these problems within a reasonable amount of time. We also develop a rerouting optimization heuristic, which is based on previous work. Experimental results are presented to compare the solutions obtained by the tabu search heuristic and the rerouting optimization heuristic. For both problems, the tabu search heuristic outperforms the rerouting optimization heuristic.     

Resource provisioning for survivable WDM networks under a sliding scheduled traffic model

Resource allocation in WDM networks, under both the static and dynamic traffic models have been widely investigated. However, in recent years there has been a growing number of applications with periodic bandwidth demands. Resources for such applications can be scheduled in advance, leading to a more efficient utilization of available network capacity. The setup and teardown times of the scheduled demands may be fixed, or may be allowed to slide within a larger window. A number of optimal integer linear program (ILP) solutions for the first problem (fixed setup/teardown times) have been presented in the literature. In this paper we present two new ILP formulations for the more general sliding scheduled traffic model, where the setup and teardown times may vary within a specified range. We first consider wavelength convertible networks and then extend our model to networks without wavelength conversion. Our ILP formulations jointly optimize the problem of scheduling the demands (in time) and allocating resources for the scheduled lightpaths. The fixed window model can be treated as a special case of our formulations. Our formulations are able to generate optimal solutions for practical sized networks. For larger networks, we have proposed a fast two-step optimization process. The first step schedules the demands optimally in time, so that the amount of overlap is minimized. The second step uses a connection holding time aware heuristic to perform routing and wavelength assignment for the scheduled demands.     

Comparison of ILP formulations for the RWA problem

We present a review of the integer linear programming (ILP) formulations that have been proposed for the routing and wavelength assignment problem in WDM optical networks assuming asymmetrical traffic. We show that all formulations proposed under asymmetrical traffic assumptions, both link and path formulations, are equivalent in terms of the upper bound value provided by the optimal solution of their linear programming relaxation, although their number of variables and constraints widely differ. We propose improvements for some of the formulations that result in further reductions in the number of variables and constraints.Under the objective of minimizing the blocking rate, we propose an experimental comparison of the best lower and upper bounds that are available. We then discuss the easiness of exact ILP solution depending on the formulations. We observe that LP relaxation bounds often provide solutions with a value very close to the optimal ILP one. We solve exactly for the first time several RWA (Routing and Wavelength Assignment) realistic instances, including those proposed by Krishnaswamy and Sivarajan [R. Krishnaswamy, K. Sivarajan, Algorithms for routing and wavelength assignment based on solutions of LP-relaxation, IEEE Communications Letters 5 (10) (2001) 435–437], with a proof of the optimality.     

WDM Network Design by ILP Models Based on Flow Aggregation

Planning and optimization of WDM networks has raised much interest among the research community in the last years. Integer linear programming (ILP) is the most used exact method to perform this task and many studies have been published concerning this issue. Unfortunately, many works have shown that, even for small networks, the ILP formulations can easily overwhelm the capabilities of today state-of-the-art computing facilities. So in this paper we focus our attention on ILP model computational efficiency in order to provide a more effective tool in view of direct planning or other benchmarking applications. Our formulation exploits flow aggregation and consists in a new ILP formulation that allows us to reach optimal solutions with less computational effort compared to other ILP approaches. This formulation applies to multifiber mesh networks with or without wavelength conversion. After presenting the formulation we discuss the results obtained in the optimization of case-study networks.     

Exact performance analytical model for spectrum allocation in flexible grid optical networks

Dynamic flexible grid optical networks have gained much attention because of the advantages of high spectrum efficiency and flexibility, while the performance analysis will be more complex compared with fixed grid optical networks. An analytical Markov model is first presented in the paper, which can exactly describe the stochastic characteristics of the spectrum allocation in flexible grid optical networks considering both random-fit and first-fit resource assignment policies. We focus on the effect of spectrum contiguous constraint which has not been systematically studied in respect of mathematical modeling, and three major properties of the model are presented and analyzed. The model can expose key performance features and act as the foundation of modeling the Routing and Spectrum Assignment (RSA) problem with diverse topologies. Two heuristic algorithms are also proposed to make it more tractable. Finally, several key parameters, such as blocking probability, resource utilization rate and fragmentation rate are presented and computed, and the corresponding Monte Carlo simulation results match closely with analytical results, which prove the correctness of this mathematical model.     

On the resource efficiency of virtual concatenation in SDH/SONET mesh transport networks bearing protected scheduled connections

Virtual concatenation (VCAT) is a Synchronous Digital Hierarchy (SDH)/Synchronous Optical Network (SONET) network functionality recently standardized by the International Telecommunication Union Telecommunication Standardization Sector (ITU-T). VCAT provides the flexibility required to efficiently allocate network resources to Ethernet, Fiber Channel (FC), Enterprise System Connection (ESCON), and other important data traffic signals. In this article, we assess the resources' gain provided by VCAT with respect to contiguous concatenation (CCAT) in SDH/SONET mesh transport networks bearing protected scheduled connection demands (SCDs). As explained later, an SCD is a connection demand for which the set-up and tear-down dates are known in advance. We define mathematical models to quantify the add/drop and transmission resources required to instantiate a set of protected SCDs in VCAT- and CCAT-capable networks. Quantification of transmission resources requires a routing and slot assignment (RSA) problem to be solved. We formulate the RSA problem in VCAT- and CCAT-capable networks as two different combinatorial optimization problems: RSA in VCAT-capable networks (RSAv) and RSA in CCAT-capable networks (RSAc), respectively. Protection of the SCDs is considered in the formulations using a shared backup path protection (SBPP) technique. We propose a simulated annealing (SA)-based meta-heuristic algorithm to compute approximate solutions to these problems (i.e., solutions whose cost approximates the cost of the optimal ones). The gain in transmission resources and the cost structure of add/drop resources making VCAT-capable networks more economical are analyzed for different traffic scenarios.     

Resource Planning for Dynamic Traffic Grooming in WDM Optical Networks

Dynamic traffic grooming in wavelength division multiplexing (WDM) optical networks refers to consolidating dynamically arriving subwavelength connections onto lightpaths. Most studies on dynamic traffic grooming focused on designing effective algorithms to achieve better performance (typically blocking probability) with given resources such as wavelengths and transponders. In this paper, we study the reverse problem: given the blocking requirement in dynamic traffic grooming, how to determine the resources needed to meet this requirement. We call it resource planning for dynamic traffic grooming. It is raised in a situation that after the initial deployment of optical networks, service providers often need to upgrade resources to accommodate increasing traffic demands. We formulate it as an ILP problem, and developed heuristics to solve this problem for large networks. Numerical results show that the heuristics can achieve good performance, and network resources increase slowly when requiring lower client call blocking probability.     

Optimal regenerator assignment and resource allocation strategies for translucent optical networks

Physical layer impairments in wavelength-routed networks limit the maximum distance, a signal can travel in the optical domain, without significant distortion. Therefore, signal regeneration is required at some intermediate nodes for long-haul lightpaths. In translucent WDM networks, sparsely located regenerators at certain nodes can be used to offset the impact of physical layer impairments. The routing and wavelength assignment (RWA) techniques in such translucent networks need to take into consideration the availability of regenerators and the maximum optical reach of the transparent lightpaths (without any regeneration). Although there has been significant research interest in RWA algorithms for translucent networks, much of the research has focused on dynamic RWA techniques. Only a handful of recent papers have considered the static (offline) case, and they typically propose heuristic algorithms to solve this complex design problem for practical networks. In this paper, we propose a generalized integer linear program (ILP) based formulation for static regenerator assignment and RWA in translucent WDM optical networks, with sparse regenerator placement. To the best of our knowledge, such a formulation that optimally allocates resources for a set of lightpaths for translucent networks, given the physical network, the locations of the regenerators, and the maximum optical reach has not been considered before. The proposed formulation is important for two reasons. First, it can serve as a benchmark for evaluating different heuristic approaches that may be developedin the future. Second, we show that using a novel node representation technique, it is possible to drastically reduce the number of integer variables. This means that unlike existing ILP formulations, our approach can actually be used to generate optimal solutions for practical networks, with hundreds of lightpath demands.     

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.     

Algorithms for routing and wavelength assignment based on solutionsof LP-relaxations

In this letter, we consider the problem of maximizing the number of lightpaths that may be established in a wavelength routed optical network (WRON), given a connection matrix, i.e., a static set of demands, and the number of wavelengths the fiber supports. The problem of establishing all the connections of the connection matrix using the fewest number of wavelengths has been investigated in Banerjee and Mukherjee (1996) and Baroni et al. (1998). We call the former problem max-RWA (problem of maximizing the number of lightpaths) and the latter problem min-RWA (minimizing the number of wavelengths). In this letter, we only consider WRONs with no wavelength conversion capabilities. We formulate the max-RWA problem when no wavelength conversion is allowed as an integer linear programme (ILP) which may be solved to obtain an optimum solution. We hope to solve the ILP exactly for small size networks (few nodes). For moderately large networks (tens of nodes) we develop algorithms based on solutions obtained by solving the LP-relaxation of the ILP formulation. Results obtained for networks such as NSFNET and EONNET are presented     

Routing and wavelength assignment based on genetic algorithm

In this letter, the routing and wavelength assignment problem in all optical networks is considered. We improve the Max-RWA model presented by R. M. Krishnaswamy and K. N. Sivarajan (see ibid., vol.5, p.435-7, Oct. 2001) by introducing limited-range wavelength conversions. Considering transmission performance, we propose a new optimization objective, which is to establish the maximum number of connections with the least number of wavelength converters. The modified Max-RWA problem is formulated as a integer linear programming (ILP) problem, and then solved using a genetic algorithm. The extended layered-graph approach is used to assign routes and wavelengths when necessary, thus reducing the complexity of the genetic algorithm. Numerical results obtained for NSFNET are presented     

Some studies on path protection in WDM networks

Path protection in WDM networks is one of the popular ways to design resilient WDM networks. Although complete ILP formulations for optimal design of WDM networks have been proposed in literature, the computational cost of actually solving such formulations make this approach impractical, even for moderate sized networks. This high computational cost arises mainly due to the large number of integer variables in the formulations, which increases the complexity exponentially. As a result, most practical solutions use heuristics, which do not provide any guarantees on the performance. In this article, we propose two novel ILP formulations, which drastically reduce the number of integer variables compared to existing ILPs. This leads to much more efficient formulations. We also present a simple heuristic that may be used for larger networks for which ILP formulations become computationally intractable.     

Survivability Approaches Using p-Cycles in WDM Mesh Networks Under Static Traffic

The major challenge in survivable mesh networks is the design of resource allocation algorithms that allocate network resources efficiently while at the same time are able to recover from a failure quickly. This issue is particularly more challenging in optical networks operating under wavelength continuity constraint, where the same wavelength must be assigned on all links in the selected path. This paper proposes two approaches to solve the survivable routing and wavelength assignment RWA problem under static traffic using p-cycles techniques. The first is a non-jointly approach, where the minimum backup capacity against any single span failure is set up first. Then the working lightpaths problem is solved by first generating the most likely candidate routes for each source and destination s-d pair. These candidate routes are then used to formulate the overall problem as an ILP problem. Alternatively, for a more optimum solution, the problem can be solved jointly, where the working routes and the backup p-cycles are jointly formulated as an ILP problem to minimize the total capacity required. Furthermore, only a subset of high merit cycles that are most likely able to protect the proposed working paths is used in the formulation. Reducing the number of candidate cycles in the final formulation plays a significant role in reducing the number of variables required to solve the problem. To reduce the number of candidate cycles in the formulation, a new metric called Route Sensitive Efficiency (RSE) - has been introduced to pre-select a reduced number of high merit cycle candidates. The RSE ranks each cycle based on the number of links of the primary candidate routes that it can protect. The two approaches were tested and their performances were compared.