Considering Linear and Nonlinear Impairments in Planning WDM Networks

Abstract

In this chapter we study the planning (offline) problem in WDM networks. In such networks, the signal quality of transmission (QoT) degrades due to physical-layer impairments, making necessary the use of regeneration at some intermediate nodes for certain lengthy lightpaths. Because of physical effects, routing choices made for one lightpath affect and are affected by the choices made for the other lightpaths. This interference among the lightpaths is particularly difficult to formulate in a planning algorithm, since in this version of the problem, we start without any established connections, and the utilization of lightpaths is the variable of the problem. We present a way to formulate inter-lightpath interference as additional constraints on the routing and wavelength assignment (RWA) problem. We initially present algorithms to solve the problem of planning a transparent all-optical WDM network, that is, a WDM network without regeneration capability. Then, we turn our attention to translucent WDM optical networks and present a series of algorithms that choose the regeneration sites and the number of regenerators required on these sites, solving the regenerator placement and the RWA problem for a given set of requested connections.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

In a wavelength division multiplexed (WDM) network, each fiber link carries high-rate data on several different wavelengths, thus creating multiple channels within a single fiber. The most common architecture utilized for establishing communication in WDM optical networks is wavelength routing, where optical pulse trains are transmitted through lightpaths, that is, all-optical WDM channels that may span multiple consecutive fibers [1–3]. Since the lightpaths are the basic switched entities of a wavelength-routed WDM network, their effective establishment and usage is crucial. Thus, it is important to find efficient algorithms to select the routes for the requested connections and to assign wavelengths on each of the links along these routes, so as to serve the traffic and optimize a certain performance metric. This is known as the routing and wavelength assignment (RWA) problem. The constraints are that paths that share common links are not assigned the same wavelength (distinct wavelength assignment). Also a lightpath, in the absence of wavelength converters, must be assigned a common wavelength on all the links it traverses (wavelength continuity constraint).

The RWA problem is usually considered under two alternative traffic models. When the set of connection requests is known in advance (e.g., given in the form of a traffic matrix), the problem is referred to as offline or static RWA and is encountered in the planning phase of a WDM network, while when the connection requests arrive at random times, over an infinite time horizon, and are served on a one-by-one basis, the problem is referred to as online or dynamic RWA and is encountered in the operation phase. In this chapter we will focus on offline RWA, which is known to be a NP-hard problem [4]. Offline RWA is generally considered more difficult than online RWA, since it aims at jointly optimizing the lightpaths used by the connections, in the same way that the multicommodity flow problem is more difficult than the shortest path problem in general networks.

Optical core networks in the past were mainly point-to-point (opaque) networks, with signal regeneration taking place at each intermediate node via optical–electronic–optical (OEO) conversion. As the size of opaque networks increased, network designers had to consider more electronic-terminating and switching equipment, increasing capital costs (CAPEX), heat dissipation, power consumption, physical space requirements, and operation and maintenance costs (OPEX). The current trend clearly shows an evolution towards more transparent networks that use fewer OEO transponders (Fig. 5.1). In such WDM networks, where lightpaths are not regenerated at each hop but remain in the optical domain for more than one link, physical limitations of fibers and optical components affect the quality of transmission (QoT) of the lightpaths. We will refer to such phenomena as physical-layer impairments (PLIs). Because of PLIs, signal quality may degrade to the extent that the bit error rate (BER) at the receiver is so high that signal detection is infeasible. For the remaining of this chapter, we will refer to such a phenomenon as physical-layer blocking, as opposed to the network-layer blocking that arises from the unavailability of an adequate number of wavelengths.

Fig. 5.1

Evolution of optical networks

At present, and in the foreseeable future, the only satisfactory method to overcome these impairments is regeneration through OEO conversion (re-amplifying, reshaping, and retiming of optical pulses—referred to as 3R regeneration). The network cost of an opaque network could be reduced by employing regenerators only at specific nodes instead of all the nodes. When regenerators are available, a lengthy end-to-end connection that needs regeneration at some intermediate node(s) is set up in a multi-segment manner so that it is served by two or more consecutive lightpath segments. The regenerator at the end of each lightpath segment serves as a “refueling station” that restores signal quality. This type of optical networks, where some lightpaths are routed transparently, while others have to go through a sequence of 3R regenerators, is referred to as a translucent optical networks. The ultimate goal is the development of an all-optical transparent network, where the data signal remains in the optical domain for the entire path [5]. Since this may not be feasible for large-sized network, translucent networks seem a more appropriate solution at present and in the near future.

Clearly, PLIs limit the set of paths that can be used for routing. This interdependence between the physical and the network layers makes the RWA problem in the presence of impairments a cross-layer optimization problem. To address this problem, a number of approaches are emerging, usually referred to as impairment-aware (IA)-RWA algorithms. An important distinction is how the IA-RWA algorithms define the interaction between the network layer and the physical layer and if they jointly optimize the solutions over these two layers. Because of interference-related impairments, routing decisions made for one lightpath affect and are affected by the decisions made for other lightpaths. This interdependence is particularly difficult to formulate in offline IA-RWA where there are no already established connections and the utilization of the lightpaths are the variables of the problem. It is because of this difficulty that the majority of offline IA-RWA algorithms proposed to date do not handle interference-related impairments. In this chapter, we present offline IA-RWA algorithms for transparent and translucent networks that account for interference physical effects and jointly optimize the solution over the network and the physical layers.

In this chapter we will present an algorithm for solving the “impairment-unaware” (IU)-RWA problem (i.e., without considering physical impairments) that uses path-related variables and is based on a linear programming (LP)-relaxation formulation [6, 7]. To obtain good integrality performance, the presented formulation uses a piecewise linear cost function and a random perturbation technique. If, even with these techniques, the returned solution is not integer, we use iterative fixing and rounding techniques to obtain an integer solution.

The IU-RWA algorithm is next extended so as to also handle physical-layer impairments in a transparent WDM network, that is, a network that does not employ regeneration at any intermediate node. We present the Sigma-Bound IA-RWA algorithm that considers directly the physical impairments and performs a cross-layer optimization between the network and the physical layers [7]. For each candidate lightpath inserted in the formulation, we calculate a noise variance bound based on the impairments that do not depend on the interference among lightpaths. We use this bound and noise variance parameters to define appropriate constraints that limit the total interference noise accumulated on the lightpath. If the selected lightpaths satisfy these constraints, they have, by definition, acceptable quality of transmission. Our goal is to provide practical IA-RWA algorithms that can be used in real network and traffic scenarios. So, although the formulation presented can be solved optimally by ILP methods for small problems, we focus on LP relaxation combined with appropriate techniques for obtaining integer solutions that scale well and can give near-optimal solutions to problems of large sizes, within acceptable time.

We then turn our attention to translucent WDM networks. In such networks apart from the RWA problem, there is also the additional problem of choosing the connections that have to be served using regenerators and the sequence of regenerators these connections should use. We present a solution based on decomposition: we formulate the problem of regenerator placement as a virtual topology design problem and address it using various algorithms, ranging from integer linear programming (ILP) formulations to simple greedy heuristics [8]. Once the sequence of regenerators to be used by the nontransparent connections has been determined, we transform the initial traffic matrix by replacing nontransparent connection requests with a sequence of transparent connection requests that terminate and begin at the specified 3R intermediate nodes. Using the transformed matrix, we then apply the transparent Sigma-Bound IA-RWA algorithm, outlined above, to route the traffic. We also present simulation results to evaluate the efficiency and applicability of the presented algorithms under realistic scenarios.

The rest of this chapter is organized as follows. In Sect. 2 we overview previous work on RWA and IA-RWA. In Sect. 3, we discuss ways in which PLIs can be incorporated in the RWA problem. In Sect. 4 we give our IU-RWA formulation. We then extend it and present in Sect. 5 the Sigma-Bound IA-RWA algorithm for transparent networks. In Sect. 6, we present a number of algorithms for planning translucent networks, as opposed to transparent networks of Sect. 5. Simulation results are given in Sect. 7. Our conclusions follow in Sect. 8.

2 Previous Work

Routing and wavelength assignment (RWA) has been extensively studied in the literature. The offline version of RWA is known to be a NP-complete problem [4]. To make computations tractable, a common approach is to decouple the RWA into its constituent routing (R) and wavelength assignment (WA) subproblems by first finding routes for all requested connections and then searching for an appropriate wavelength assignment [1, 9]. Note that both subproblems are NP-hard: routing a set of requested connections corresponds to a multicommodity flow problem, while wavelength assignment corresponds to a graph coloring problem. Various efficient heuristics have been developed for each subproblem, which may be combined and produce solutions for the joint RWA problem. However, such decomposition suffers from the drawback that the optimal solution of the (joint) RWA problem might not be included in the solutions provided for the two subproblems.

RWA integer linear programming (ILP) formulations were initially proposed in [10] and [11]. Since the associated ILPs are hard to solve, the corresponding relaxed linear programs (LP) have been used to get bounds on the optimal value. A review on various offline and online RWA algorithms can be found in [9]. A few newer and more sophisticated RWA algorithms are presented in [6, 12, 13]. The LP-relaxation formulation proposed in [12] and in [6] is able to produce exact RWA solutions in many cases, despite the absence of integrality constraints. This is the approach that we adopt and extend in our formulations.

Recently, RWA algorithms that consider the impact of physical-layer impairments have been the subject of intense research, referred to in this chapter as IA-RWA. Most of these studies consider the online (dynamic) version of the problem [14–19]. Among these online algorithms, there are approaches that consider the quality of transmission (QoT) problem separately from the RWA problem by first solving the RWA problem and then considering PLI effects through the evaluation of the feasibility of the selected lightpaths in a separate module [14–16]. This approach may not yield a solution of acceptable quality, and iterations are usually performed to improve physical-layer blocking performance. Other online approaches incorporate PLIs into the cost function of the optimization problem and also consider the interference among the lightpaths [17–19].

In the dynamic traffic case, where connections are served one by one, the employed algorithm must examine the feasibility of a lightpath that is about to be established. This can be done by calculating (through appropriate models) or measuring (through performance monitors) the interference caused by the already established lightpaths to the candidate lightpath. However, this cannot be done in the static RWA case, where there are no existing connections, and the utilization of lightpaths are the variables of the problem. For this reason, the majority of offline RWA algorithms proposed to date do not consider inter-lightpath interference. In [20], the authors solve the offline impairment-unaware (IU)-RWA problem and then evaluate the feasibility of the chosen lightpaths in a post-processing phase. For requests whose lightpaths do not have acceptable transmission quality, new solutions are found by excluding the ones previously considered. An offline impairment-aware (IA)-RWA algorithm that assigns Q-factor costs to links before solving the problem is proposed in [21]. However, the proposed algorithm does not account for the actual interference among lightpaths and assumes a worst-case interference scenario. In [22], the authors include the optical power in the RWA formulation so as to ensure that the power level at the beginning of each optical amplifier and at the end of each fiber is above a certain threshold.

All the work discussed in the preceding paragraphs refers to the case of transparent networks. The RWA problem for translucent optical networks has also been addressed before by dividing a large-scale optical network into several islands of transparency or optically transparent domains. Within the same island, a lightpath can transparently reach any other node without intermediate signal regeneration. For communication across islands, 3R regeneration is performed at nodes at the island boundaries [23]. An alternative approach, which is the one taken in this chapter, is called sparse placement of regenerators, where some selected nodes in the network are used for regeneration and there is no explicit notion of transparent domains. The majority of RWA algorithms proposed so far for translucent networks assume a dynamic traffic scenario, that is, they address the online version of the problem. [24] presents a two-dimensional Dijkstra RWA algorithm for translucent optical network that takes into account the placement of regenerators and a constraint on the maximum transparent distance. When the length of a lightpath exceeds the maximum transparent distance bound, the lightpath is blocked. A different approach for dynamic resource allocation and routing is considered in [25] and [26], where spare transceivers (transmitter–receiver pairs connected back-to-back) at the nodes are used to regenerate signals. In this kind of network, every node with a spare transceiver is a potential regenerator. A Max-spare algorithm for selecting the regeneration nodes for a lightpath is proposed in [27] and compared to a greedy algorithm used in conjunction with a wavelength-weighted and a length-weighted RWA algorithm. In [28], two online RWA algorithms for translucent networks with sparse regenerator placement are presented that assume either worst-case physical transmission penalties corresponding to a fully loaded system or that take into account the current network status and the actual number of active channels.

The work in [29] formulates the problem of maximizing the number of connections served, under a constraint on the maximum transparent length, as a mixed-integer linear program (MILP). Since MILP does not scale a heuristic algorithm to establish connections is also proposed. A heuristic for placing the fewest regenerator nodes to reach a given blocking probability for dynamic traffic, based on the ranked frequency of shortest routes, is given in [30]. In [31] the authors address the problem of translucent network design by proposing several regenerator placement algorithms based on different knowledge of future network traffic patterns. A QoT-based heuristic algorithm for IA-RWA in translucent networks is presented in [32]. In the first phase of that algorithm, a random search heuristic RWA algorithm is used, and in the second phase, regeneration placement is performed after estimating the BER of the lightpaths obtained in the first phase.

In the following sections we present a series of offline IA-RWA algorithms that solve the planning problem of heterogeneous transparent and translucent WDM networks. The algorithms presented take into account not only impairments that depend on the chosen lightpath but also impairments that depend on the interference among lightpaths as additional constraints on RWA, so as to perform a cross-layer optimization of the solution over the physical and the network layers.

3 Considering Physical-Layer Impairments in RWA

In transparent and translucent WDM networks, the signal quality of transmission (QoT) degrades due to the nonideal physical layer [2, 3]. Several criteria can be used to evaluate the signal quality of a lightpath. Among a number of measurable optical transmission quality attributes, such as optical power, optical signal-to-noise ratio (OSNR), chromatic dispersion (CD), and polarization mode dispersion (PMD), the Q-factor seems to be more suitable as a metric to be integrated in an RWA algorithm because of its immediate relation to the bit error rate (BER). In this chapter we look only at on–off keying (OOK) modulation, but similar expressions can be derived for higher-order modulations. The Q-factor is the electrical signal-to-noise ratio at the input of the decision circuit in the receiver’s terminal. Assuming Gaussian-shaped noise, the Q-factor of a lightpath (p, w), that is, wavelength w on path p, is given by

$$ Q(p,w)=\frac{{{I_{{{`}1{\prime}} }}(p,w)-{I_{{{`}0{'}} }}(p,w)}}{{{\sigma_{{{`}1{'}} }}(p,w)+{\sigma_{{{`}0{'}} }}(p,w)}}, $$

where I _‘1’ and I _‘0’ are the mean values of electrical voltage of signal 1 and 0, respectively, and σ _‘0’ and σ _‘1’ are their standard deviations, at the input of the decision circuit at the destination, which in this case is the end of path p. Figure 5.2 illustrates the relation between an eye diagram and the Q-factor. The higher the Q-factor, the smaller the BER is and the better the quality of the signal. Generally, a path has acceptable QoT when the Q-factor at the destination is higher than 15.5 dB. When forward error correction (FEC) is employed, a connection can be accepted with even smaller Q values.

Fig. 5.2

Eye diagram and Q-factor

Physical-layer impairments (PLIs) are usually categorized to linear and nonlinear, according to their dependence on the power. However, when considering IA-RWA, it is useful to categorize the PLIs into those that affect the same lightpath that generated them and those that are due the presence of other lightpaths, resulting in the following two classes for the most important PLIs:

• Class 1–impairments that affect the same lightpath: amplified spontaneous emission noise (ASE), polarization mode dispersion (PMD), chromatic dispersion (CD), filter concatenation (FC), self-phase modulation (SPM)

• Class 2–impairments that are generated by other lightpaths: crosstalk (XT) (intra-channel and interchannel crosstalk), cross-phase modulation (XPM), four-wave mixing (FWM)

We now discuss the ways in which PLIs can be incorporated in the RWA problem. PLIs of class 1 depend only on the selected lightpath and can be accounted for quite easily. We will assume that we are using a typical RWA algorithm that takes as input a set of candidate lightpaths and selects an appropriate subset of lightpaths to serve the connections. Then, for each candidate lightpath, we can pre-calculate the effects of the PLIs of class 1, using, for example, analytical models, and discard those that have unacceptable QoT performance. In this way, the RWA algorithm can be fed with candidate solutions that are acceptable at least for the impairments of class 1. PLIs of class 2 are more difficult to consider in offline algorithms since they make decisions taken for one lightpath effect and be affected by decisions taken for other lightpaths. An obvious simplification is to consider a “worst-case scenario,” by assuming that all wavelengths on all links are active, and calculating the worst-case interference on each lightpath. Lightpaths that do not have acceptable QoT under this worst-case assumption can be discarded before the RWA algorithm is executed, ensuring that the solution is feasible, irrespective of the final selection of lightpaths.

This worst-case approach does not optimize the problem for the given traffic but solves it as if the network was fully utilized, which will never happen. In practice, wavelength continuity limits the achievable network utilization, except for the degenerate case where all connections are between adjacent nodes. The worst-case assumption results in discarding many candidate lightpaths that are not really infeasible. The feasibility or not of these lightpaths depends on the lightpaths finally selected in the solution, which are not known before the RWA execution. By formulating the interference among lightpaths, we may be able to use these lightpaths, letting the algorithm choose the optimal among all feasible solutions.

In the following, we quantify through a realistic example the reduction in the routing solution space when PLIs are considered. We assume the Deutsche Telekom network topology (DTnet), shown in Fig. 5.3, with physical-layer parameters chosen to have realistic values. We have also used a quality of transmission evaluation module (Q-Tool) developed within the DICONET project [33] that uses analytical models to account for the most important PLIs (and in particular, the ones listed in the above classification). We assume an offline RWA algorithm that takes as input a set of candidate paths and selects a subset of them to satisfy the demands. In this example, we assume that all source–destination pairs require a connection of one wavelength for a total number of connection demands equal to 182. Initially, we calculate the k-shortest length paths for different values of the parameter k, and then we prune the set of candidate paths using the Q-Tool. In doing so, we either assume an empty network, discarding lightpaths that are infeasible due to impairments of class 1, or we assume a fully utilized network, discarding lightpaths that are infeasible due to impairments of class 1 and of class 2 under the worst-case interference scenario.

Fig. 5.3

Generic DT network topology, consisting of 14 nodes and 46 unidirectional links

In Table 5.1 we see the reduction in the routing solution space after considering the PLIs. As we increase the initial path population size, by increasing parameter k, the percentage of paths that are discarded increases. This was expected since the path length largely determines the physical-layer effects, and thus as we move from the shortest to more lengthy paths, an increasing percentage of these paths turns out to be infeasible. Eventually, beyond some value of k, all paths will turn out to be infeasible, and the population reported in columns (b) and (c) will stabilize. Table 5.1 shows that the path population obtained after eliminating candidate paths due to the impairments of class 1 (column (b)) is considerably larger than when we use the worst-case interference assumption for the impairments of class 2 (column (c)). An IA-RWA algorithm that accounts for the actual interference among lightpaths can use as input the paths that correspond to column (b), while an algorithm that assumes a worst-case interference scenario will use as input the paths of column (c). This reduction in the solution space unnecessarily restricts the choices of the algorithm and leads to a deterioration of its performance.

Table 5.1 The reduction in the solution space due to the PLIs of class 1 and 2 (under the worst-case interference assumption) for the case of the DTnet and the reference traffic matrix

Based on the above discussion, an IA-RWA algorithm that accounts for the actual inter-lightpath interference and performs a cross-layer optimization over the physical and the network layers will require fewer wavelengths to serve the given traffic than an IA-RWA algorithm that assumes a worst-case interference scenario. We will come back and quantify this performance difference later in this chapter. The reduction in the solution space due to the physical effects depends on the topology and the traffic profile. For example, in a small network that consists of short-length links, PLIs are negligible, and the difference between the population sizes corresponding to columns (a), (b), and (c) will be small, even for high values of k. Thus, the above discussion is valid when PLIs are significant enough, which is the case of interest in this chapter.

A frequently used argument in favor of the worst-case interference scenario is that a network configured using this assumption is more reliable, since future connections will not render the already established lightpaths infeasible. In current operational WDM networks, changes in the traffic matrix are usually slow and incremental. The increase of the average traffic between two end nodes is eventually going to require an additional wavelength, but the average traffic increase is small compared to the granularity of the wavelength, and the frequency of such incremental changes is low, of the order of a couple of new connections per year. For slowly changing traffic, an online IA-RWA algorithm is executed to adjust the previous solution to the new traffic demands, and/or an offline algorithm can be periodically re-executed after a certain time or a certain number of new established lightpaths to optimize the solution to the current traffic. It stands to reason that the establishment of new lightpaths under the worst-case interference assumption would continue making inefficient utilization of the available wavelengths, and the network will reach the point where it cannot serve more connections earlier than in the case where an IA-RWA that accounts for the actual inter-lightpath interference and performs a cross-layer optimization is used.

4 Impairment-Unaware RWA Algorithm

In this section we present an algorithm for solving the RWA problem without considering physical-layer impairments. In the subsequent section, we extend this algorithm in order to take into account physical-layer impairments and address the planning problem of transparent and translucent WDM networks.

The network is represented by a connected graph G = (V,E). V denotes the set of nodes, assumed not to be equipped with wavelength converters. E denotes the set of single-fiber links. Each fiber supports a common set C = {1,2,…,W} of distinct wavelengths. The static version of RWA assumes an a priori known traffic scenario given in the form of a nonnegative integer matrix Λ, called the traffic matrix. Then, Λ _sd denotes the number of requested wavelengths from source s to destination d. Note that there may be multiple lightpath requests for a given source–destination pair (s,d) and they can be routed over different paths.

The algorithm takes as input an RWA instance, that is, a network topology, a set of available wavelengths, and a traffic matrix. It returns the RWA solution, in the form of routed lightpaths and assigned wavelengths, and the blocking probability, in case the connections cannot all be served for the given set of wavelengths.

The “impairment-unaware” (IU)-RWA algorithm consists of four phases [6]. The first (preprocessing) phase computes a set of candidate paths to route the requested connections. RWA algorithms that do not use any set of predefined paths but allow routing over any feasible path (using multicommodity flow formulations) have also been proposed in the literature. These algorithms are bound to give at least as good solutions as the algorithms that use pre-calculated paths, such as the one proposed here, but use a much higher number of variables and constraints and do not scale well. In any case, the optimal solution can be also found with a RWA algorithm that uses pre-calculate paths, given a large enough set of paths. The second phase of the proposed algorithm utilizes Simplex to solve the LP that formulates the given RWA instance. If the solution returned by Simplex is not integer, the third phase uses iterative fixing and rounding techniques to obtain an integer solution. Non-integer solutions are not acceptable, since a connection is not allowed to bifurcate over alternative paths or wavelength channels. Finally, phase 4 handles the infeasible instances so that most (if all is not possible) requested connections are established.

Phase 1: In this phase, k candidate paths are calculated for each connection request using a variation of the k-shortest path algorithm: at each step, a shortest path is selected, and its link costs are increased (doubled in our experiments) so as to be avoided by the paths found in subsequent steps. Paths thus obtained tend to use different edges and be more representative of the path solution space. Other k-shortest path algorithms are also applicable. By selecting a sufficiently large value for k, the solution space is expected to contain an optimal RWA solution with large probability. After a set P _sd of candidate paths for each s–d pair is computed, the total set $P={\cup_{s-d }}{P_{sd }}$ is inserted to the next phase. The preprocessing phase clearly takes polynomial time.

Phase 2: Taking into account the network topology, the number of available wavelengths, the traffic matrix, and the set of paths identified in phase 1, phase 2 formulates the given RWA instance as a linear program (LP). The LP formulation used is presented in Sect. 4.1. This LP is solved using the Simplex algorithm that is generally considered efficient for the great majority of all possible inputs and has additional advantages, as we will see, for the problem at hand. If the instance is feasible and the solution is integer, the algorithm terminates by returning the optimal solution and zero blocking. If the instance is feasible but the solution is non-integer, we proceed to phase 3. If the instance is infeasible, meaning that it cannot be solved for the given number of wavelengths, we proceed to phase 4.

Phase 3: In case of a fractional (non-integer) solution, phase 3 involves iterative fixing and rounding methods, as presented in Sect. 4.3, in order to obtain an integer solution. The maximum number of such iterations is the number of connection requests, which is polynomial on the size of the input. Rounding can turn the problem infeasible, and then we proceed to phase 4. If we find a feasible solution, the algorithm terminates and outputs the RWA solution and zero blocking.

Phase 4: This phase is used when the LP instance is infeasible for the given number of wavelengths W. Infeasibility is overcome by progressively increasing the number of available wavelengths and re-executing phases 2 and 3 until a feasible solution is obtained. Then, at the end of phase 4, we have to select which connections should be blocked to reduce the number of wavelengths to the given W. The wavelengths removed are those occupied by the smallest number of lightpaths, so as to minimize blocking. The algorithm terminates and outputs the RWA solution, along with the blocking probability, which is in that case strictly greater than zero.

4.1 RWA LP Formulation

The proposed LP formulation aims at minimizing the maximum resource usage in terms of wavelengths used on network links. Let F _l  = f(w _l ) denote the flow cost function, an increasing function on the number of lightpaths w _l traversing link l (the used formula is presented in the next subsection). The LP objective is to minimize the sum of all F _l values. The following variables are used:

• x _pw : an indicator variable, equal to 1 if path p occupies wavelength w, that is, if lightpath (p,w) is activated, and equal to 0, otherwise

• F _l : the flow cost function value of link l

  $${\rm Minimize}\quad \sum\limits_l {{F_l}} $$

  subject to the following constraints:

• Distinct wavelength assignment constraints: $\sum\limits_{{\left\{ {p|l\in p} \right\}}} {x_{pw }} \leqslant 1,$ for all $l\in E$ and all $w\in C$

• Incoming traffic constraints: $\sum\limits_{{p\in {P_{sd }}}} {\sum\limits_w {{x_{pw }}} } ={\varLambda_{sd }}$ for all (s,d) pairs

• Flow cost function constraints: ${F_l}\geqslant f\left( {{w_l}} \right)=f\left( {\sum\limits_{{\left\{ {p|l\in p} \right\}}} {\sum\limits_w {{x_{pw }}} } } \right)$ for all $l\in E$

• The integrality constraints are relaxed to $0\leqslant {x_{pw }}\leqslant 1$ for all $p\in P$ and all $w\in C$

The wavelength continuity constraints are implicitly taken into account by the definition of the path-related variables. Note that using inequalities for the flow cost function constraints in the above formulation is equivalent to using equalities, since these constraints will hold as equalities at the optimal solution. Using inequalities is convenient for employing a piecewise linear cost function f, as will be presented in the next subsection. In Sect. 5, we will extend the above LP formulation so as to take into consideration the physical-layer impairments.

4.2 Flow Cost Function

The variable F _l expresses the cost of congestion on link l, for a specific selection of the routes, and is chosen to be an increasing function f(w _l ) of the number of lightpaths ${w_l}=\sum\nolimits_{{\left\{ {p|l\in p} \right\}}} {\sum\nolimits_w {x_{pw }} }$ crossing link l. F _l  = f(w _l ) is chosen to also be strictly convex (instead of, e.g., linear), implying a greater degree of “undesirability,” when a link becomes congested. This is because it is preferable for overall network performance to serve an additional unit of flow using several low-congested links than using a link that is close to saturation. In particular, we utilize the following flow cost function:

$$ {F_l}=f\left( {{w_l}} \right)=\frac{{{w_l}}}{{W+1-{w_l}}},\ 0\ \leqslant {w_l}\leqslant W. $$

The above (nonlinear) function is inserted to the LP formulation in the approximate form of a piecewise linear function, consisting of W consecutive linear parts. The piecewise linear approximation is constructed as follows: we begin with F _l (0) = 0, and iteratively set, for i = 1,2,…,W, F _l  ⁱ(w _l ) = a _i  ċ w _l  + β _i , i − 1≤ w _l  ≤i, where a _i  = F _l (i) − F _l (i − 1) and β _i  = (i − 1) ċ F _l (i) − i ċ F _l (i − 1). We insert in the LP formulation W linear constraints of the form

$$ {F_l}^i\left( {{w_l}} \right)={a_i}\cdot{w_l}+{\beta_i}\leqslant {F_l},i=1,2,\ldots,W, $$

defined by the corresponding a _i and β _i values. Since the LP objective is to minimize the cost $\sum\nolimits_l {{F_l}}$, for a specific value of w _l , one of these W linear cost functions, and in particular the one that yields the highest F _l (w _l ), is satisfied with equality at the optimal solution of the LP. All the remaining linear functions are deactivated, that is, they are satisfied as strict inequalities at the optimal solution (Fig. 5.4).

Fig. 5.4

The set of linear constraints inserted in the LP formulation. We use inequality constraints to limit our search in the colored area. Since the objective is to minimize the flow cost, we search for solutions only at its lower bounds, which identify the piecewise linear approximation of the flow cost function F _l  = f(w _l ) (black line)

This piecewise linear function is equal to the nonlinear function f(w _l ) at integer values (w _l  = 1,2,…,W) and greater than that at non-integer values. Inserting such a piecewise linear function to the LP results in the identification of integer optimal solutions by Simplex in most cases [12]. This is because the vertices of the polyhedron defined by the constraints tend to correspond to the corner points of the piecewise linear function and tend to consist of integer components. Since Simplex moves from vertex to vertex of that polyhedron [34], there is a higher probability of obtaining integer solutions than with other (e.g., interior point) methods. The results in Sect. 7.1 show that this is the case in most problem instances.

4.3 Random Perturbation Technique

Although the piecewise linear cost function presented above is designed so as to yield good integrality characteristics, there are still cases where some of the solution variables of the LP relaxation turn out to be non-integer. Recall that non-integer solutions for the flow variables are unacceptable. To increase the number of integer solutions obtained, we use the following random perturbation technique. In the general multicommodity flow problem, given an optimal fractional solution, a flow that is served by more than one path has equal sum of first derivatives of the costs of the links comprising these paths [35]. The reason is that if they were not equal, one could shift some small flow δ from one path to the other, reducing the total cost, which would mean that it is not an optimal solution. The objective function used in our RWA formulation sums the flow costs of all the links, and thus a request that is served by more than one lightpaths has equal sums of first derivatives over the links of these lightpaths. Note that the derivative of the cost on a specific link is given by the slope of the linear or piecewise linear flow cost function used. To make the situations where two lightpaths have equal first derivative lengths over the links that comprise them less probable, we multiply the slopes on each link with a random number that differs from 1.0 in the sixth decimal digit (see Fig. 5.5).

Fig. 5.5

Random perturbation mechanism. The first derivatives of the two variables x _pw and ${x_{{p^{\prime},{w}^{\prime}}}}$ are not equal on a specific link. Thus, the variable with the smaller derivative is selected (set to one), yielding an integer solution

4.4 Iterative Fixing and Rounding Techniques

If even with the piecewise linear cost function and the random perturbation technique presented above we do not obtain an integer solution, we continue by “fixing” and “rounding” the variables.

We start by fixing the variables; that is, we treat the variables that are integer as final and solve the reduced problem for the remaining ones. Fixing variables does not change the objective cost returned by the LP, so we move with each fixing from the previous solution to a solution with equal or more integers with the same cost. This is because when some variables are fixed and the RWA problem is reduced, Simplex uses different variables and constraints and starts from a different basic feasible solution (bfs) [34]. Thus, it ends with the same objective cost but with a solution that might consist of a different (and in particular greater or equal) number of integer variables. Since the objective cost does not change, if after successive fixings we reach an all-integer solution, we are sure that it is an optimal one. On the other hand, fixing variables is not guaranteed to return an integer optimal solution, if one exists, since the integer solution might consist of different integer values than the ones in the iterative fixing process. When we reach a point beyond which the process of fixing does not increase the integrality of the solution, we proceed to the rounding process. We round a single variable at a time, the one closest to 1, and continue solving the reduced LP problem. While fixing variables helps us move to solutions with more integer variables and the same objective cost, rounding makes us move to higher objective values and search for an integer solution there. Rounding is inevitable when there is no integer solution with the same objective cost as the LP relaxation of the RWA instance. However, if after rounding the objective cost changes, we are not sure anymore that we will end up with an optimal solution. The maximum number of fixing and rounding iterations performed is the number of requests and is polynomial on the problem size.

We will refer to the algorithm outlined above as an “impairment-unaware” (IU)-RWA algorithm, in the sense that it ignores physical-layer impairments. Using this RWA algorithm and pruning the candidate paths under the worst-case interference assumption in the preprocessing phase (see discussion in Sect. 3), we obtain an impairment-aware (IA)-RWA algorithm that we will refer to as worst-case WC-IA-RWA. Note that the only difference between the RWA and the WC-IA-RWA algorithm is the set of candidate lightpaths that they use as input.

5 Impairment-Aware RWA Algorithm for Transparent Networks

In this section we extend the preceding RWA algorithm so as to make it impairment-aware.

5.1 Direct and Indirect IA-RWA Algorithms

To account for the PLIs in a cross-layer approach, an algorithm has to incorporate impairment-related constraints at some point in its formulation. An important distinction is whether these impairment constraints address directly or indirectly the effects of the impairments. To give an example, polarization mode dispersion (PMD) is proportional to the square root of the length of the path, and also other impairments, such as amplified spontaneous emission (ASE) noise, are affected by the path length. An algorithm that chooses paths with small lengths is bound to exhibit lower PMD and ASE effects; such an algorithm would be treating impairments indirectly by bounding the length of the paths. However, when the network is heterogeneous, the length of a path can be misleading even for PMD, since a path with small length is not ensured to have acceptable QoT, as the impairment effects are not verified. On the other hand, an algorithm that includes constraints that bound directly the effects of PMD and ASE in its formulation, using, for example, analytical formulas, can be sure (to a certain degree, depending on the other effects that are accounted for) that a lightpath satisfying these constraints has acceptable QoT. A key difference between these two classes of algorithms is that indirect algorithms need a QoT evaluation tool in order to verify the feasibility of the chosen lightpaths, while direct algorithms do not require an evaluation module, assuming that all dominant impairments are accounted for.

5.2 Direct IA-RWA Formulation

We now describe a direct IA-RWA algorithm. For each candidate lightpath inserted in the RWA formulation, we calculate an upper bound on the interference noise variance it can tolerate after accounting for the impairments that do not depend on the utilization of the other lightpaths (impairments of class 1, Sect. 3). Then, we use this to bound the interfering noise variance caused by other lightpaths (impairments of class 2) by introducing appropriate constraints in the RWA formulation.

5.2.1 Calculating the Noise Variance Bound of a Lightpath

We start from the Q-factor definition presented in Sect. 3. In the approach adapted here [21, 36], I _‘1’,p (w) depends on the transmitter’s power, the gains and losses over path p, and the “eye impairments”: self-phase modulation (SPM), chromatic dispersion (CD), polarization mode dispersion (PMD), and filter concatenation (FC). The remaining impairments are considered as noise or noise-like. For the noise impairments and bits 1 and 0, we have

$$ \sigma_{{`}1'}^2\left( {p,w} \right)=\sigma_{{\mathrm{ ASE},{`}1'}}^2\left( {p,w} \right)+\sigma_{{\mathrm{ XT},{`}1'}}^2\left( {p,w} \right)+\sigma_{\mathrm{ XPM,{`}1'}}^2\left( {p,w} \right)+\sigma_{{\mathrm{ FWM},{`}1'}}^2\left( {p,w} \right),$$

$$ \sigma_{{{`}0{'}}}^2\left( {p,w} \right)=\sigma_{{\mathrm{ ASE},{{`}0{'}}}}^2\left( {p,w} \right)+\sigma_{{\mathrm{ XT},{{`}0{'}}}}^2\left( {p,w} \right)+\sigma_{{\mathrm{ FWM},{{`}0{'}}}}^2\left( {p,w} \right)\approx \sigma_{{\mathrm{ ASE},{{`}0{'}}}}^2\left( {p,w} \right), $$

where $\sigma_{\mathrm{ ASE}}^2,\sigma_{\mathrm{ XT}}^2,\sigma_{\mathrm{ XPM}}^2,\mathrm{ and}\sigma_{\mathrm{ FWM}}^2$ are the electrical noise variances due to amplifier spontaneous emission (ASE), intra-channel crosstalk (XT), cross-phase modulation (XPM), and four-wave mixing (FWM), respectively. Note that the noise variances $\sigma_{{\mathrm{ XT},{{`}0{'}}}}^2,\sigma_{{\mathrm{ FWM},{{`}0{'}}}}^2$ of bit 0 are low and negligible compared to $\sigma_{{\mathrm{ ASE},{{`}0{'}}}}^2$ and especially compared to the corresponding noise variances of bit 1. Also, note that XT, XPM, and FWM depend on the utilization of the other lightpaths (class 2 impairments). Let Q _min be the acceptable threshold for the QoT of a lightpath. Since we do not consider all the physical impairment and we also make various simplifying assumptions (such as not considering XT and FWM for bit 0), we will use a Q _min that is somewhat higher than the desired threshold. We have

$$ \begin{array}{ll} \frac{{{I_{{`1'} }}(p,w)}}{{{\sigma_{{`1'} }}(p,w)+{\sigma_{{`0'} }}(p,w)}}\geq {Q_{\min}}\Rightarrow \sigma_{{`1'}}^2(p,w)\leq {{\left( {\frac{{{I_{{`1'} }}(p,w)}}{{{Q_{\min} }}}-{\sigma_{{`0'} }}(p,w)} \right)}^2} \hfill \\ \quad\Rightarrow\sigma_{{\mathrm{ XT},{`1'}}}^2(p,w)+\sigma_{{\mathrm{ XPM},{`1'}}}^2(p,w)+{c_{\mathrm{ FWM}}}\leq \left( \frac{{{I_{{`}1'} }}(p,w)}{{{Q_{\min} }}}-{\sigma_{{\mathrm{ ASE},{`0'}}}}(p,w) \right)^2\\ \quad\quad -\sigma_{{\mathrm{ ASE},{`1'}}}^2(p,w) \hfill \\ \quad\Rightarrow \sigma_{{\mathrm{ XT},{`1'}}}^2(p,w)+\sigma_{{\mathrm{ XPM},{`1'}}}^2(p,w)+{c_{\mathrm{ FWM}}}\leq \sigma_{\max}^2(p,w), \hfill \\ \mathrm{ where}\sigma_{\max}^2(p,w)\mathop{=}\limits^{\mathrm{ def}}{{\left( {\frac{{{I_{{`1'} }}(p,w)}}{{{Q_{\min} }}}-{\sigma_{{\mathrm{ ASE},{`0'}}}}(p,w)} \right)}^2}-\sigma_{{\mathrm{ ASE},{`1'}}}^2(p,w) \end{array} $$

assuming that FWM contributes a constant c _FWM (c _FWM is small relative to the other effects and could be chosen as the worst-case FWM contribution, when all wavelengths are used). Thus, for a lightpath (p,w), this inequality gives a bound $\sigma_{\max}^2\left( {p,w} \right)$, calculated based on the impairments that do not depend on the interference among lightpaths (class 1 impairments), which constrains the total interference noise variances of the impairments that depend on the other lightpaths (class 2 impairments).

5.2.2 Defining the Noise Interference Constraints

We assume that for each link l and the optical cross connect (OXC) switch n it ends at, we know the following noise variance parameters:

• G _l (in dB): the power loss/gain of the link/OXC due to fiber attenuation, power leakage, and amplifiers’ gains

• $s_{{1-\mathrm{ XPM},{{`}1{'}},l}}^{2},{s_{{2-\mathrm{ XPM}},{{`}1{'}},l}}^2$: the noise variance due to XPM for bit 1 from an active adjacent and second channel, respectively

• $s_{{\mathrm{ XT},{{`}1{'}},n}}^2$: the intra-channel crosstalk (intra-XT) noise variance for bit 1, contributed to a lightpath that also crosses switch n and uses the same wavelength

Note that we assume that $s_{{1-\mathrm{ XPM},{{`}1{'}},l}}^2,s_{{2-\mathrm{ XPM},{{`}1{'}},l}}^2,s_{{\mathrm{ XT},{{`}1{'}},n}}^2$ are the same irrespectively of the wavelength w, but the algorithm can be extended to consider different parameters per wavelength. To obtain the above parameters, analytical models for the specific impairments can be used. For example, for NRZ modulation, we can use models described in [14] and [36].

For a path p that consists of links l = 1,2,…,m, we have

$$ \begin{array}{ll} \sigma_{{\mathrm{ XT},{`1'}}}^2(p,w)+\sigma_{{\mathrm{ XPM},{`1'}}}^2(p,w) \hfill \\ \quad=\sum\limits_{{\{l=1|n\mathrm{ end}\mathrm{ of}l\}}}^m \bigg( \bigg( {s_{{\mathrm{ XT},{`1'},n}}^2\cdot {n_{{\mathrm{ XT},n}}}(w)}+ {s_{{1-\mathrm{ XPM},{`1'},l}}^2\cdot {n_{{\mathrm{ adj},l}}}(w)} \end{array}$$

$$\begin{array}{llll}+ s_{{2-\mathrm{ XPM},{`1'},l}}^2\cdot {n_{{2-\mathrm{ adj},l}}}{(w)} ( ( \cdot \prod\limits_{i=l+1}^m {{10^{{\frac{{2 \cdot {G_l}}}{10 }}}}} ) )\end{array}$$

where n _XT,n (w) is the number of intra-XT generating sources on switch n and wavelength w, n _adj,l (w) and ${n_2}_{{-\mathrm{ adj},l}}(w)\in \left\{ {0,1,2} \right\}$ is the number of utilized adjacent and second-adjacent channels on link l and wavelength w, respectively.

Based on the above, we constrain the interference accumulated over the lightpaths:

$$ \begin{array}{l}{ \sum\limits_{{\{l\in p|n\mathrm{ end}\mathrm{ of}l\}}} {\left( {\overbrace{{s_{{\mathrm{ XT},n}}^2\cdot \sum\limits_{{\{p\prime|n\in p\prime\}}} {x_{p\prime,w}}}}^{\mathrm{ intra}\rm{-}\mathrm{ XT}}+\overbrace{{s_{{\mathrm{ XPM},l}}^2\cdot \left( {\sum\limits_{{\{p\prime|l\in p\prime\}}} {x_{p\prime,w-1 }+} x_{p\prime,w+1 }} \right)}}^{\mathrm{ adjacent}\ \mathrm{ channel}\ \mathrm{ XPM}}} \right.} +\ \left. {\overbrace{{s_{{2-\mathrm{ XPM},l}}^2\cdot \left( {\sum\limits_{{\{p\prime|l\in p\prime\}}} {x_{p\prime,w-2 }+} x_{p\prime,w+2 }} \right)}}^{\mathrm{ second}\ \mathrm{ adjacent}\ \mathrm{ channel}\ \mathrm{ XPM}} }\right) + {c_{\mathrm{ FWM}}}+M\cdot x_{pw } - {S_p}\leqslant\sigma_{\max}^2(p,w)+M, }\cr \mathrm{ for}\ \mathrm{ all}p\in P\mathrm{ and}\ \mathrm{ all}w\in C. \hfill \\ \end{array} $$

We use constant M (large integer) to activate/deactivate the constraints and carry the surplus variables S _p in the objective cost. Lightpaths satisfying these constraints have by definition (assuming that the models used for calculating the noise variance parameters and the Q-factor are accurate) acceptable quality of transmission. Although in the above constraint we assumed that the signal power is totally compensated at the end of each link and each OXC, this assumption is not restrictive, and the above constraints can be modified for nonzero power gains or losses. We will refer to the direct IA-RWA algorithm described above as Sigma-Bound or SB-IA-RWA algorithm.

6 Impairment-Aware RWA Algorithms for Translucent Networks

We now turn our attention to translucent WDM networks. We assume a network of known physical topology that supports a given number of wavelengths, and wavelength conversion is possible only through 3R regeneration. We assume static traffic, given in the form of a traffic matrix specifying the number of connection requests between any pair of nodes. Each connection requires transmission rate equal to that of one wavelength, but there may be multiple connection requests for a given source–destination pair. The proposed algorithm is given a specific RWA instance, described as above, and returns the solution, in the form of paths and wavelengths used, including decisions on whether a connection will be served transparently or using regenerators. For the latter connections, the algorithm also decides the sequence of regenerators to be used. In case a solution serving all connections cannot be found with the given number of wavelengths, the algorithm returns the corresponding blocking ratio.

The IA-RWA algorithms for translucent WDM networks consist of three phases. In phase 1, described in Sect. 6.1, the algorithm decides which connections cannot be served transparently. For these nontransparent connections, we formulate and solve a virtual topology design problem to decide the regeneration sites they should use. The virtual topology consists of the 3R sites with (virtual) links between any pair of transparently connected 3R sites. Each virtual link of the paths chosen in the virtual topology to serve a connection corresponds to a sub-connection (lightpath) in the physical topology (Fig. 5.6). Thus, a nontransparent connection uses multiple consecutive segments (lightpaths), defined by the intermediate 3R sites it is going to utilize. Based on these decisions, we transform the initial traffic matrix into a transparent traffic matrix, where nontransparent connection requests are replaced by a sequence of transparent sub-connection requests. In phase 2 of the algorithm, described in Sect. 6.2, we apply an impairment-aware (IA) RWA algorithm using as input the transformed transparent traffic matrix. The IA-RWA algorithm we used is the one proposed in Sect. 5, but other algorithms are also applicable. If some connections cannot be served while there are still regenerators not used in phase 1, in phase 3, described in Sect. 6.3, these physically blocked connections are reattempted through the remaining regenerators. Figure 5.7 provides an overview of the IA-RWA algorithm for heterogeneous translucent networks.

Fig. 5.6

The nontransparent connection request between source–destination pair (s,d) can be broken into four transparent sub-connection requests: s-R3, R3-R12, R12-R10, and R10-d. Each of the three sub-connection requests can be served using a different wavelength

Fig. 5.7

Flow chart of the proposed IA-RWA algorithm for translucent networks

6.1 Obtaining the Transparent Traffic Matrix (Phase 1)

Phase 1 of the algorithm aims at transforming the initial traffic matrix Λ into a transparent traffic matrix $\mathop{\Lambda}\limits^{\sim{} }$ that consists of connection requests that can be served without regenerators. To do so, we formulate in Sect. 6.1.1 a virtual topology problem that considers only nontransparent connection requests. Section 6.1.2 presents algorithms to solve this to obtain the intermediate regeneration sites. The traffic matrix is then transformed into a transparent traffic matrix, as described in Sect. 6.1.3.

We assume that 3R regenerators will be sparsely placed in the network, forming pools of regenerators at some nodes. We let $R\subseteq V$ be the set of nodes equipped with at least one 3R regenerator and r _n be the number of regenerators at node $n\in R$. In the version of the problem where the algorithm is free to select the regeneration sites and the number of regenerators to deploy (regenerator placement problem), we assume that R = V and that r _n is unbounded. In the version of the problem where the placement of regenerators is given (regenerator assignment problem), the set R and r _n are part of the input to the algorithm. The same problem can be given in the slightly different setting where, instead of the sparse regenerator placement, we are given the number of available transceivers at each node. Given the number of transceivers at a node, and subtracting the ones used by originating or terminating traffic (described in matrix Λ), we can find the number of spare transceivers at each node. These spare transceivers can be connected back-to-back so as to function as 3R regenerators, and thus, we can transform this problem to the typical regeneration assignment problem.

6.1.1 Constructing the Virtual Topology

In order to formulate the virtual topology problem, we first distinguish between transparent and nontransparent connection requests in the given traffic matrix. Specifically, for each source–destination pair (s,d), we examine if the QoT of at least one of its k-shortest length paths has acceptable performance, as indicated by its Q-factor, in an otherwise empty network. More formally, we let P _k (s,d) be the set of k-shortest length paths between nodes s and d. We will say that a source–destination pair (s,d) is transparently connected and will denote that by (s,d) $\in$ T, when the following holds:

$$ \left( {s,d} \right)\in T\,\mathrm{ iff}\ {Q_p}>{Q_{min} }+{Q_{\mathrm{ margin}}}\quad \rm{ for}\ \mathrm{ some}\ \mathrm{ path}\quad p\in {P_k}\left( {s,d} \right), $$

where Q _min is the Q-factor value that corresponds to the minimum transmission quality requirement and Q _margin is a safety margin. We use k-shortest paths instead of a single path in the above definition, since in a heterogeneous network, the shortest length path does not always yield the best QoT. The set of nontransparent connections that do not satisfy the above constraint are denoted by $\overline{T}$.

For a source–destination pair $\left( {s,d} \right)\in T$, at least one of its k-shortest paths has acceptable Q performance, and it is possible in principle to serve a connection between them without using regenerators. However, this possibility depends on the IA-RWA solution since the Q-factor values used in distinguishing between transparent and nontransparent connections are calculated for an empty network. When all connections are present, some of the assumed transparent lightpaths may be infeasible in reality due to interference. The IA-RWA algorithm applied in phase 2 aims at avoiding such problems by finding lightpaths that are feasible even when all impairments are taken into account.

Given the set T of transparently connected (s,d) pairs and the set R of nodes with regeneration capabilities, we define the virtual topology as the graph $\mathop{G}\limits^{\sim{} }=(R,\mathop{E}\limits^{\sim{} })$, where $\mathop{E}\limits^{\sim{} }=\left\{ {(u,v)|u\in R,v\in R,(u,v)\in T} \right\}$, denotes the set of virtual links between regeneration nodes that are transparently connected. Each virtual link corresponds to a transparent lightpath between two regeneration nodes, spanning one or several physical links. We also denote by R ^s and R ^d the set of regeneration sites the source s and the destination d are transparently connected to, respectively.

6.1.2 Choosing the Regenerators for the Nontransparent Connections

In this step of phase 1 we consider only the set $\overline{T}$ of source–destination pairs that are not transparently connected and that have to be routed through regenerators. Therefore, for a source–destination pair $\left( {s,d} \right)\in \overline{T}$, we have to choose the sequence of regeneration site(s) they are going to use. This is equivalent to finding a path from s to d in the virtual topology $\mathop{G}\limits^{\sim{}}\left( {s,d} \right)$, obtained by adding to graph $\mathop{G}\limits^{\sim{} }$ the source node s and the virtual links connecting it to the elements of R ^s and, also, the destination node d and the virtual links connecting it to the elements of R ^d. In the example of Fig. 5.8, we focus on six regenerator sites (assuming 12 regeneration sites as presented in Fig. 5.6) and present the virtual topology$\mathop{G}\limits^{\sim{}}\left( {s,d} \right)$for the source–destination pair (s,d). In order to select the virtual path from s to d (equivalently, the sequence of regenerators to be used), we investigated two classes of algorithms in the following two subsections:

Fig. 5.8

The virtual topology $\mathop{G}\limits^{\tilde{}}\left( {s,d} \right)$, assuming regeneration sites R2, R3, R4, R10, R11, and R12. Source s and destination d are transparently connected to sites R2 and R3 and R10 and R11, respectively

• (a) Greedy first-fit algorithms for routing in the virtual topology

We now present several greedy algorithms for routing nontransparent connections in the virtual topology. We denote by ${\Lambda^{\overline{T}}}$ the part of the traffic matrix Λ that corresponds to source–destination pairs in $\overline{T}$, that is,

$$ \Lambda_{sd}^{\overline{T}}={\Lambda_{sd }}\ \mathrm{ if}\ (s,d)\in \overline{T};\ \mathrm{ and}\Lambda_{sd}^{\overline{T}}=0,\mathrm{ otherwise}. $$

Nontransparent connection requests are treated by the greedy routing algorithms one by one. In particular, for each pair (s,d) for which $\Lambda_{sd}^{\overline{T}}\ne 0,$, we run Dijkstra’s shortest path algorithm on graph $\mathop{G}\limits^{\sim{}}\left( {s,d} \right)$ with appropriate link costs. The way the costs of the virtual links in $\mathop{G}\limits^{\sim{}}\left( {s,d} \right)$ are defined is important for the performance of the algorithms and is described next.

A nontransparent connection may be blocked due to the unavailability of free regenerators, or of free wavelengths, or due to significant physical impairments (including inter-lightpath interference). The latter factor is important for paths that are long or use many hops. Given the above considerations, we studied the following definitions for the cost of the virtual links in the virtual topology:

• 1. Virtual-hop (VH) shortest path algorithm: All the links of the virtual graph have cost equal to 1. The optimal virtual path is the one consisting of the fewest regenerators (virtual hops).

• 2. Physical-hop (PH) shortest path algorithm: The cost of a virtual link is set equal to the number of physical links (physical hops) it consists of. The optimal virtual path is the one that traverses the minimum number of physical nodes.

• 3. Physical-length (PL) shortest path algorithm: The cost of a virtual link is set equal to the sum of the lengths of the physical links that comprise it. Thus, the PL algorithm selects the virtual path that has the shortest physical length.

• 4. Adjusted-virtual-hop (AVH) shortest path algorithm. Since in the three algorithms described above, Dijkstra’s algorithm is executed for each nontransparent (s,d) pair separately and successively, many connections may try to use certain regeneration sites. To avoid this and also distribute the load more equitably among the regeneration sites, the AVH algorithms adjust the cost of using the regenerators. In our simulations, the cost of a virtual link l between virtual nodes i and j equipped with r _i and r _j regenerators, respectively, from which u _i and u _j regenerators have already been used by previous connections, is taken to be

  $$ {w_l}=\left[ {\frac{{{u_i}}}{{{r_i}}}+\frac{{{u_j}}}{{{r_j}}}} \right] \cdot \mathop{\max}\limits_{{n\in R}}\left( {{r_n}} \right). $$

• (b) ILP routing algorithm for routing in the virtual topology

We also developed an ILP formulation to solve the virtual topology problem presented above. The ILP algorithm selects the routes of the nontransparent connections by minimizing one of the following: (1) the maximum number of regenerators used among all nodes or (2) the total number of regenerators used in the network or (3) the number of regeneration sites. Due to space limitations, we do not present this algorithm here and refer the reader to [8] for details. The ILP developed can be solved for large-sized networks since the number of variables and constrains is small. When its solution is intractable (which may be the case for very large networks), the LP relaxation of the problem combined with piecewise linear link costs and iterative fixing and rounding, as presented in Sect. 4.4, can be used and also yield good solutions. In the simulation experiments we performed with realistic network and traffic input, we were always able to solve the corresponding ILP problems in a few seconds time.

6.1.3 Transforming the Traffic Matrix

Having found the sequence of regenerators to be used by nontransparent connections, the IA-RWA problem in the translucent network is transformed into a corresponding IA-RWA problem in a transparent network that has a different traffic matrix. In particular, after obtaining the solution to the virtual topology problem, which effectively breaks each nontransparent connection into multiple transparent segments, we transform appropriately the original traffic matrix, as follows. From the part of the initial traffic matrix that corresponds to the nontransparent connections, ${\Lambda^{\overline{T}}}$, we use the virtual paths chosen for the nontransparent connections to obtain the traffic matrix $\mathop{{{\Lambda^{\overline{T}}}}}\limits^{\sim{} }$ corresponding to these virtual paths. By adding this to the matrix ${\Lambda^T}=\Lambda -{\Lambda^{\overline{T}}}$ that represents the initial transparent connections, we obtain the transparent traffic matrix $\mathop{\Lambda}\limits^{\sim{} }={\Lambda^T}+\mathop{{{\Lambda^{\overline{T}}}}}\limits^{\sim{} }$ that if routed, will serve all requested (transparent and nontransparent) connections.

6.2 IA-RWA Using the Transformed Traffic Matrix (Phase 2)

Phase 2 of the algorithm takes as input the transparent traffic matrix $\mathop{\Lambda}\limits^{\sim{} }$, calculated in the previous phase, which only contains connections that can be served transparently, and applies an IA-RWA algorithm designed for transparent networks to route and assign wavelengths to these connections. Given the traffic matrix $\mathop{\Lambda}\limits^{\sim{} }$, the physical network topology G, the number of supported wavelengths W, and impairment-related parameters, the IA-RWA algorithm returns the RWA solution to the specific instance in the form of paths and wavelengths and the corresponding blocking probability. Blocking in phase 2 may occur for two reasons: (1) if the transformed traffic matrix $\mathop{\Lambda}\limits^{\sim{} }$ cannot be served with the available wavelengths, some connections will have to be dropped, or (2) the interference among lightpaths may make the QoT of some lightpaths (which are feasible in an empty network) unacceptable. Blockings of category (1) are avoided by appropriately placing the regenerators in the network. Blockings of category (2) are avoided by a well-designed IA-RWA algorithm that accounts for the interference among lightpaths. In any case, connections blocked in phase 2 are reattempted in phase 3 of the algorithm, as described in Sect. 6.3.

The IA-RWA algorithm presented in Sect. 5 was used in this phase, but other IA-RWA algorithms can also be used.

6.3 Rerouting the Blocked Connections (Phase 3)

In the final phase 3 of the algorithm, we try to reroute any connections blocked in phase 2. Given the solution of the IA-RWA algorithm of phase 2 and the set B of blocked (s,d) pairs, we want to serve the connections in B without altering previously accepted lightpaths. The set B of blocked connections refers to the initial traffic matrix Λ and not to the transformed traffic matrix $\mathop{\varLambda}\limits^{\sim{} }$. We formulate a new virtual topology problem similar to that of phase 1 (Sect. 6.1). The input is the set of remaining regenerators in the network and the set B of blocked connections. We re-execute the IA-RWA algorithm of phase 2 (Sect. 6.2), assuming that the lightpaths calculated in the previous solution are established (i.e., we set equal to 1 the corresponding variables). The output of this reduced IA-RWA problem will indicate if we can route the connections in B with acceptable transmission quality without affecting the other connections. The proposed algorithm is terminated at this point and outputs the routed lightpaths from phase 2 in addition to any new lightpaths that were rerouted in phase 3. Connections that have unacceptable Q performance, after phase 3, are blocked.

7 Simulation Results

To evaluate the performance of the proposed IA-RWA algorithms, we carried out a number of simulation experiments. We implemented all the algorithms in Matlab and used LINDO [37] to solve the corresponding LP and ILP problems. We start, in Sect. 7.1, by presenting results for the impairment-unaware IU-RWA algorithm (Sect. 4). We evaluate the integrality and optimality performance of the proposed LP-relaxation algorithm and the random perturbation technique by comparing it to a typical min–max RWA formulation. We then, in Sect. 7.2, turn our attention to the RWA problem in the presence of physical impairments. We initially consider a transparent WDM network and evaluate the performance of the proposed Sigma-Bound IA-RWA algorithm of Sect. 5. We then turn our attention to a translucent WDM network and evaluate the performance of the algorithms presented in Sect. 6.

The network topology used in our simulations for the impairment-unaware and the impairment-aware transparent RWA algorithms (Sects. 7.1 and 7.2.1) was the Deutsche Telekom network (DTnet), shown in Fig. 5.3, which is a candidate transparent network as identified by the DICONET project [33]. For the translucent network experiments (Sect. 7.2.2), we have used the GEANT-2 network topology, shown in Fig. 5.6. In both cases, the capacity of a wavelength was assumed equal to 10 Gbps.

7.1 Impairment-Unaware RWA Performance Results

In this section we evaluate the performance of the IU-RWA algorithm that is based on the LP-relaxation formulation of Sect. 4. To have a reference point, we also executed the same experiments using a typical min–max formulation (a formulation whose objective is to minimize the maximum number of wavelengths used), which was solved using the ILP branch-and-bound algorithm of [37]. Note that the maximum number of wavelengths used is the actual objective that we want to minimize. The piecewise linear cost function used in the proposed LP RWA algorithm (Sect. 4.2) tries to approximate the min–max objective, so as to exhibit a good integrality performance when the Simplex algorithm is used. Thus, the ILP-min–max algorithm sets the criterion in terms of optimality. We also used the same min–max formulation and solved its LP-relaxed version followed by iterative fixing and roundings. This LP-min–max algorithm sets a comparison criterion in terms of integrality and execution time since its difference to our proposed LP algorithm lies on the piecewise linear cost function that we utilize and the random perturbation technique. For all algorithms in this section, we have used k = 3.

In this set of experiments, we used the DTnet of Fig. 5.3. The results were averaged over 100 experiments obtained with different random traffic matrices of a given traffic load, defined as the ratio of the total number of connection requests over all possible source-destination pairs for loads ranging from 0.5 to 2 with 0.5 step. Figure 5.9a, b shows the number of RWA instances for which we are sure to have obtained an optimal solution and the average execution time of the algorithms. We observe that the LP-piecewise algorithm has superior overall performance than the other algorithms examined. It finds with high probability an optimal solution in low execution times. The random perturbation technique further improves the LP-piecewise algorithm by increasing its integrality performance and reducing its running time. The good optimality performance of the proposed algorithm is maintained irrespectively of the load.

Fig. 5.9

(a) Number of RWA instances that we are sure to obtain optimal solution and (b) corresponding average running times, as a function of load ρ

7.2 IA-RWA Performance Results

We now turn our attention to the case where physical-layer impairments are present. To evaluate the feasibility of the lightpaths in terms of QoT, we used a Q-factor estimator (Q-Tool) that relies on analytical models to account for the most important impairments (see section 3). The link model of the reference network is presented in Fig. 5.10. We assumed NRZ-OOK modulation format, 10 Gbps transmission rates, and 50 GHz channel spacing. The span length on each link was set to 100 km. Each link was assumed to consist exclusively of single-mode fibers (SMF) with dispersion parameter D = 17 ps/nm/km and attenuation parameter a = 0.25 dB/km. For the dispersion-compensating fibers (DCF), we used parameters a = 0.5 dB/km and D = −80 ps/nm/km. The launch power was 3 dBm/ch for every SMF span and −4 dBm/ch for the DCF modules. The Erbium Doped Fiber Amplifier’s (EDFA) noise figure was 6 dB with small variations (±0.5 dB), and each EDFA exactly compensates for the losses of the preceding fiber span. We assumed a switch architecture similar to [14] and a switch–crosstalk ratio X _sw  = 32 dBs with small variations per node (±1 dB). Regarding dispersion management, a pre-compensation module was used to achieve higher reach: initially the dispersion was set to −400 ps/nm/km, every span was under-compensated by a value of 30 ps/nm/km to alleviate nonlinear effects, and the accumulated dispersion at each switch input was fully compensated to zero using an appropriate post-compensation module at the end of the link. The acceptable Q-factor value was set to Q _min = 15.5 dB.

Fig. 5.10

Link model

7.2.1 Transparent Network Simulation Experiments

In this section we present performance results for the Sigma-Bound SB-IA-RWA algorithm of Sect. 5, obtained for the DTnet topology shown in Fig. 5.3.

When planning a WDM network (offline problem), we are usually looking for a zero-blocking solution. The direct SB-IA-RWA algorithm can find a zero-blocking solution given enough wavelengths, indicating that DTnet is in principle a transparent network, in the sense that it can serve all traffic without regenerators. Thus, in these experiments, we focus on zero-blocking solutions and examine the SB-IA-RWA performance by solving either (1) its LP-relaxation version using iterative fixings and roundings to obtain an integer solution or (2) the ILP version with a branch-and-bound method.

In Fig. 5.11a we report the number of wavelengths required for zero blocking averaged over 100 traffic matrices and loads between 0.5 and 1 with a step of 0.1. For the ILP version of the algorithm, we were able to track solutions for loads up to ρ = 0.7 in a time limit of 5 h per instance (for certain instances of larger load, we were not able to find an optimal solution within 5 h). We see that the number of wavelengths required by the LP-relaxation algorithm is quite close to that required by the optimum ILP. The optimality was lost only in two or three instances (from the 100 examined) for the traffic loads for which we were able to find optimal solutions. Regarding execution times (Fig. 5.11b), we see that the LP-relaxation version has superior performance and maintains the average running time within a few hundreds of seconds, while the ILP version cannot solve certain hard instances even at medium load. Note that as the load increases, more lightpaths are activated and the interfering sources among them increase, making the problem more complicated and difficult to solve.

Fig. 5.11

(a) Average number of wavelengths required to obtain zero blocking and (b) average execution time for the SB-IA-RWA algorithm, solved with the proposed LP-relaxation technique and ILP

We also performed experiments assuming the actual traffic matrix of DTnet, consisting of 381 connection requests (corresponding to load ρ ≈ 2.05) [33]. We compared the performance of three algorithms: (1) the IU-RWA algorithm that does not consider physical impairments at all, (2) the WC-IA-RWA algorithm that prunes the candidate paths based on the impairments of class 1 and of class 2 under the worst interference scenario (Sect. 4.4), and (3) the cross-layer SB-IA-RWA algorithm that takes into account the interference among lightpaths in its RWA formulation (Sect. 5). A key difference of these algorithms is the set of candidate paths they take as input. In particular, referring to Table 5.1, the IU-RWA algorithm takes as input the set of paths that correspond to column (a), the WC-IA-RWA algorithm the set of paths that correspond to column (c), and the proposed cross-layer SB-IA-RWA algorithm the set of paths that correspond to column (b). To make the comparison more fair, we used k = 3 for the IU-RWA and the proposed SB-IA-RWA algorithm and k = 4 for the WC-IA-RWA.

Figure 5.12a shows the number of wavelengths required to achieve zero (physical and network) blocking for the WC-IA-RWA and the SB-IA-RWA algorithms using the randomly generated traffic matrices. We do not graph the performance of IU-RWA since this algorithm was unable to obtain zero-blocking solutions due to physical blocking. We observe that SB-IA-RWA achieves zero blocking using fewer wavelengths than WC-IA-RWA. WC-IA-RWA algorithm is only affected by network-layer blocking, since all candidate paths that are fed to the algorithm have acceptable QoT performance. However, the set of candidate paths that WC-IA-RWA uses turns out to be inferior, resulting in a solution that consumes more wavelengths than SB-IA-RWA. Note that path population is not the only parameter affecting performance. Even more important is the distribution of the number of different candidate paths that are available for each source–destination pair. Since, in the case of WC-IA-RWA, some paths are unnecessarily discarded, the choices on the routes that can be used for certain connections are very restricted. In contrast, the cross-layer SB-IA-RWA has more options in selecting lightpaths of acceptable quality to serve the traffic.

Fig. 5.12

(a) Number of wavelengths required to reach zero blocking for various loads obtained using the random traffic generator and (b) blocking probability versus number of available wavelengths W per link for realistic traffic load

Figure 5.12b shows the average blocking probability versus the number of available wavelengths per link for all examined algorithms, assuming the realistic DTnet traffic matrix. The impairment-unaware IU-RWA algorithm has the highest blocking rate since it cannot avoid physical-layer blocking. The WC-IA-RWA algorithm exhibits only network-layer blocking, while SB-IA-RWA exhibits both physical and network blocking. The SB-IA-RWA algorithm outperforms the WC-IA-RWA algorithm in terms of rejected connections and is able to reach zero blocking using fewer wavelengths. In particular, the difference between these two algorithms is 4 wavelengths for this realistic traffic load, a difference which is substantial. The running time of IU-RWA and WC-IA-RWA for W = 36 was around 30 s. The corresponding running time for the SB-IA-RWA algorithm was about 15 min, which is still quite low, considering that this is a realistic experiment and we are considering a planning (offline) problem. Comparing the results of Fig. 5.12a to those of Fig. 5.12b, we can deduce that the improvements obtained by SB-IA-RWA are more pronounced for heavy traffic; since then, the number of interfering sources is higher and cross-layer optimization is more important.

Concluding, SB-IA-RWA was shown to exhibit superior performance. It is able to serve all traffic (zero blocking) given enough wavelengths, which is particularly important in practice for the planning problem (telecom operators do not like to reject connections). The number of variables and constraints it requires is rather small, and its execution time is acceptable, using the LP-relaxation and iterative fixing and rounding methods. We also performed a small number of experiments with networks that are even larger than DTnet (see the following section) and found that the SB-IA-RWA algorithm scales very well with network size.

7.2.2 Translucent Network Simulation Experiments

We now focus on the algorithms described for translucent WDM networks. The topology used in this set of simulations was the GEANT-2 network, shown in Fig. 5.6 [33]. All single-hop connections in GEANT-2 were able to be served transparently, but some multi-hop connections were not, making the use of regenerators necessary for some connections. We assume that all nodes can host regenerators; that is, the number of regeneration sites is not restricted. The algorithms were asked to solve the regeneration placement problem in order to decide the regeneration sites and the number of regenerators to deploy at each site. The traffic matrix used in our simulations corresponds to a realistic traffic load with 826 connection demands. The acceptable Q-factor limit was taken equal to Q _min = 15.5 dB and the transparency margin equal to Q _margin = 0.5 dB (Sect. 6.1.1). For the given topology, the described link models (Fig. 5.10), the given traffic matrix, and using k = 3 candidate paths for each source–destination pair, the set of nontransparent connections consists of 373 connections, which have to be routed through regenerators.

We evaluated the performance of the ILP virtual topology algorithms (Sect. 6.1.2) combined with VH and PH heuristics to pre-calculate their paths. Thus, the algorithms evaluated are VH-ILPsum, VH-ILPmax, VH-ILPsites, PH-ILPsum, PH-ILPmax, and PH-ILPsites. It is worth noting that we were able to obtain results for all these ILP algorithms with running times in the order of a few seconds.

In Fig. 5.13a we graph the blocking ratio as a function of the number of available wavelengths. From Fig. 5.13a, it is obvious that PH-based algorithms have better performance, since they have lower blocking probability and require fewer wavelengths to reach zero blocking. Among these algorithms, PH-ILPmax outperforms all the other examined algorithms, requiring the fewest number of wavelengths, in particular W = 100, to serve all the connections with zero blocking. This was expected, since the PH-ILPmax algorithm distributes the regenerators in the network so as to minimize the number of connections crossing a specific regeneration node, preventing regeneration nodes from becoming “bottlenecks.” In this way, PH-ILPmax distributes the load and ends up using fewer different wavelengths to achieve zero blocking.

Fig. 5.13

(a) Blocking ratio for realistic traffic load versus number of available wavelengths and (b) total number of regenerators, total number of regeneration sites, and total number of wavelengths in the network required to obtain blocking equal to zero

In Fig. 5.13b we graph (1) the total number of regenerators used in the network, (2) the number of regeneration sites, and (3) the number of wavelengths required to reach zero blocking. We can observe the difference between the VH- and PH-based algorithms. PH-based algorithms need a smaller number of wavelengths to reach zero blocking but utilize more regenerators and regeneration sites. On the other hand, VH-based algorithms need more wavelengths to reach zero blocking but have better regenerator utilization performance. For example, focusing on PH-ILPsum and VH-ILPsum, they both minimize the total number of regenerators used in the network. PH-ILPsum needs 115 wavelengths while VH-ILPsum needs 135 to reach zero blocking. To achieve this performance, PH-ILPsum needs 461 regenerators while VH-ILPsum needs 430. This difference can be explained by the fact that PH-based algorithms are fed with good candidate paths that have been calculated in the physical topology, while VH-based algorithms are fed with good candidate paths that have been calculated in the virtual topology. PH algorithm uses paths that minimize the number of physical hops utilized, which tends to give good wavelength utilization performance, since shorter physical-hop paths use less wavelengths than longer physical-hop paths. This is the reason shorter physical-hop paths are widely used in impairment-unaware RWA problems. On the other hand, these paths are not directly related to the virtual topology, and thus, the ILP algorithm that runs over the virtual topology cannot find a good solution that minimizes its objective. The VH-based algorithms use as input good virtual paths that are not related to the physical topology. So, although these paths yield good solutions to the regenerator placement problem that is performed over the virtual topology, they may be long physical-hop paths that waste wavelength resources. From Fig. 5.13b, we see that there is a trade-off between the number of wavelengths and the number of regenerators required to reach zero blocking. All examined algorithms provide good solutions depending on the objective they are set to minimize, and there is no single algorithm that outperforms the others with respect to all criteria. For example, if the cost of the regenerators is the dominant expense, one has to use VH-base algorithms and probably VH-ILPsum; if the objective is to minimize the number of wavelengths, PH-ILPmax seems to perform better.

8 Conclusions

We presented algorithms for planning transparent and translucent WDM networks in the presence of physical-layer impairments. We initially presented an algorithm for solving the (impairment-unaware) RWA problem, where physical impairments are not considered, based on an LP-relaxation formulation that provides integer optimal solutions for a large subset of RWA input instances, despite the absence of integrality constraints. We then extended the RWA formulation and proposed an impairment-aware (IA)-RWA algorithm for transparent WDM networks that models the physical-layer impairments as additional constraints in its formulation, performing a cross-layer optimization between the network and the physical layers. The proposed Sigma-Bound IA-RWA is a direct algorithm that constrains the interference among the lightpaths so as to obtain acceptable transmission quality as defined by the Q-factor. We also addressed the planning problem of translucent WDM networks, in which case the algorithm has to select the 3R regeneration sites and the number of regenerators that need to be deployed on these sites. We formulated regenerator placement as a virtual topology design problem and addressed it using various algorithms, ranging from ILPs to simple greedy heuristics. After determining the sequence of regenerators to be used by the nontransparent connections, we transform the initial traffic matrix to a transparent traffic matrix and then apply a transparent IA-RWA algorithm to serve it. Using realistic traffic scenarios, our results quantified the blocking improvements obtained by considering physical-layer impairments according to the actual utilization of the network as opposed to worst-case utilization based approaches.