A Survey on OFDM-Based Elastic Core Optical Networking <s> b) Heuristic Algorithms for Static and Dynamic RSA <s> Let G be a directed graph containing n vertices, one of which is a distinguished source s, and m edges, each with a non-negative cost. We consider the problem of finding, for each possible sink vertex v, a pair of edge-disjoint paths from s to v of minimum total edge cost. Suurballe has given an O(n2 logn)-time algorithm for this problem. We give an implementation of Suurballe's algorithm that runs in O(m log(1+ m/n)n) time and O(m) space. Our algorithm builds an implicit representation of the n pairs of paths; given this representation, the time necessary to explicitly construct the pair of paths for any given sink is O(1) per edge on the paths. <s> BIB001 </s> A Survey on OFDM-Based Elastic Core Optical Networking <s> b) Heuristic Algorithms for Static and Dynamic RSA <s> Orthogonal Frequency Division Multiplexing (OFDM) has been recently proposed as a modulation technique for optical networks, due to its good spectral efficiency and impairment tolerance. Optical OFDM is much more flexible compared to traditional WDM systems, enabling elastic bandwidth transmissions. We consider the planning problem of an OFDM-based optical network where we are given a traffic matrix that includes the requested transmission rates of the connections to be served. Connections are provisioned for their requested rate by elastically allocating spectrum using a variable number of OFDM subcarriers. We introduce the Routing and Spectrum Allocation (RSA) problem, as opposed to the typical Routing and Wavelength Assignment (RWA) problem of traditional WDM networks, and present various algorithms to solve the RSA. We start by presenting an optimal ILP RSA algorithm that minimizes the spectrum used to serve the traffic matrix, and also present a decomposition method that breaks RSA into two substituent subproblems, namely, (i) routing and (ii) spectrum allocation (R+SA) and solves them sequentially. We also propose a heuristic algorithm that serves connections one-by-one and use it to solve the planning problem by sequentially serving all traffic matrix connections. To feed the sequential algorithm, two ordering policies are proposed; a simulated annealing meta-heuristic is also used to obtain even better orderings. Our results indicate that the proposed sequential heuristic with appropriate ordering yields close to optimal solutions in low running times. <s> BIB002 </s> A Survey on OFDM-Based Elastic Core Optical Networking <s> b) Heuristic Algorithms for Static and Dynamic RSA <s> We consider the Routing and Spectrum Allocation (RSA) problem in an OFDM-based optical network with elastic bandwidth allocation. We asses the spectrum utilization gains of this flexible architecture compared to a traditional fixed-grid rigid-bandwidth WDM network. <s> BIB003 </s> A Survey on OFDM-Based Elastic Core Optical Networking <s> b) Heuristic Algorithms for Static and Dynamic RSA <s> We propose optical path routing and frequency slot assignment algorithms that suit elastic optical paths and the distance adaptive modulation scheme. The algorithms are proven to yield high spectrum efficiency for the distant-adaptive frequency allocation scheme. <s> BIB004 </s> A Survey on OFDM-Based Elastic Core Optical Networking <s> b) Heuristic Algorithms for Static and Dynamic RSA <s> We propose a spectrally-efficient super-wavelength-path routing in SLICE by selecting a set of subcarrier numbers and modulation levels according to path distances. We demonstrate 420 Gb/s path routing using short-reach 14-subcarrier 8-APSK and long-reach 21-subcarrier QPSK. <s> BIB005 </s> A Survey on OFDM-Based Elastic Core Optical Networking <s> b) Heuristic Algorithms for Static and Dynamic RSA <s> We present a concept of spectrally-efficient optical networking with distance-adaptive spectral allocation by adjusting the number of modulation levels. We demonstrate it by routing 40 Gb/s optical paths using short-reach, narrow-spectrum 16APSK and long-reach QPSK. <s> BIB006 </s> A Survey on OFDM-Based Elastic Core Optical Networking <s> b) Heuristic Algorithms for Static and Dynamic RSA <s> We propose a dynamic routing and frequency slot assignment algorithm for SLICE networks that employ distance adaptive modulation. We verify that the spectrum utilization penalty that stems from non-uniform bandwidth allocation is marginal. <s> BIB007 </s> A Survey on OFDM-Based Elastic Core Optical Networking <s> b) Heuristic Algorithms for Static and Dynamic RSA <s> We propose dynamic routing and spectrum assignment algorithms for bitrate-flexible lightpaths in OFDM-based optical networks. The novel algorithms enable dynamic spectrum assignment with more efficient resource utilization and less traffic blockings. <s> BIB008 </s> A Survey on OFDM-Based Elastic Core Optical Networking <s> b) Heuristic Algorithms for Static and Dynamic RSA <s> We propose an efficient survivable FWDM network design algorithm for the first time. Survivable FWDM networks are efficient in terms of spectral utilization, power consumption, and cost compared to the conventional survivable fixed grid networks. <s> BIB009 </s> A Survey on OFDM-Based Elastic Core Optical Networking <s> b) Heuristic Algorithms for Static and Dynamic RSA <s> Orthogonal Frequency Division Multiplexing (OFDM) has recently been proposed as a modulation technique for optical networks, because of its good spectral efficiency, flexibility, and tolerance to impairments. We consider the planning problem of an OFDM optical network, where we are given a traffic matrix that includes the requested transmission rates of the connections to be served. Connections are provisioned for their requested rate by elastically allocating spectrum using a variable number of OFDM subcarriers and choosing an appropriate modulation level, taking into account the transmission distance. We introduce the Routing, Modulation Level and Spectrum Allocation (RMLSA) problem, as opposed to the typical Routing and Wavelength Assignment (RWA) problem of traditional WDM networks, prove that is also NP-complete and present various algorithms to solve it. We start by presenting an optimal ILP RMLSA algorithm that minimizes the spectrum used to serve the traffic matrix, and also present a decomposition method that breaks RMLSA into its two substituent subproblems, namely 1) routing and modulation level and 2) spectrum allocation (RML+SA), and solves them sequentially. We also propose a heuristic algorithm that serves connections one-by-one and use it to solve the planning problem by sequentially serving all the connections in the traffic matrix. In the sequential algorithm, we investigate two policies for defining the order in which connections are considered. We also use a simulated annealing meta-heuristic to obtain even better orderings. We examine the performance of the proposed algorithms through simulation experiments and evaluate the spectrum utilization benefits that can be obtained by utilizing OFDM elastic bandwidth allocation, when compared to a traditional WDM network. <s> BIB010 </s> A Survey on OFDM-Based Elastic Core Optical Networking <s> b) Heuristic Algorithms for Static and Dynamic RSA <s> We compare fixed-grid network architectures with variable-spacing OFDM based solutions. We show that capacity gains can reach up to 50% but are strongly affected by physical and topological constraints of transparent networks and traffic statistics. <s> BIB011
To solve the RSA problem efficiently, several heuristic algorithms have been proposed to serve each connection request sequentially in static or dynamic scenarios. The heuristic algorithms can be designed as one-step or two-step approaches. • Two-step approach: The RSA problem can be partitioned into routing and spectrum assignment sub-problems and solved sequentially. Regarding routing, pre-calculated k shortest paths are used in BIB002 [105], and load balanced routing which determines the routing by balancing the load within the network to potentially minimize the spectrum usage in the network is used in  . It was shown that shortestpath routing outperforms load-balanced routing in regard to minimizing the total spectrum resources used in the network, while load-balanced routing achieves better performance with the objective to minimize used spectrum index in the network  . After routing, spectrum allocation can be done using one of the following policies: -First-Fit BIB007 : In this scheme, all spectrum slots are numbered. With pre-calculated k shortest paths, from the shortest route to the longest one among the candidates, this algorithm searches for the necessary consecutive slots in ascending order of the spectrum slot index, and selects the first found route and slots to the connection request. This algorithm is similar to the first-fit policy for wavelength assignment in WDM networks  . -Lowest Starting Slot BIB002 : For each candidate route, this algorithm searches for the first consecutive slots feasible for the new request in ascending order of the slot index, and selects the path with the lowest starting slot among the set of candidate paths. This algorithm supports void filling, in the sense that voids of size greater than the requested slots can be utilized. The first-fit policy is quick and simple, while the lowest starting slot allocation might have better spectrum utilization because of its void-filling capability. To deal with the static request matrix during the network planning stage, the ordering in which the aforementioned single demand heuristic algorithms serve the traffic matrix is of key importance, as different orderings may result in different spectrum utilization. Several ordering policies are proposed in BIB002 : i) Most-subcarriers-first ordering, which orders the connection demands in decreasing order of their requested bandwidth, and serves the connection with the highest bandwidth first; ii) Longest-path-first ordering, which orders connection demands in descending order of the number of links their shortest paths use, and serves the connection that has the longest path first; iii) simulated annealing (SA) meta-heuristic, which finds a near-optimum ordering based on Policies i) and ii) to provide good spectrum allocation solutions. Simulation results indicate that the above heuristics combined using the SA meta-heuristic for ordering can give close-to-optimal solutions in low running times (order of tens of seconds) compared to ILP computation time BIB002 . • One-step approach: Two different algorithms using a one-step approach were proposed in BIB008 , namely Modified Dijkstra's Shortest Path (MSP) and Spectrum-Constraint Path Vector Searching (SCPVS). The two algorithms find the route and the available contiguous spectrum simultaneously. MSP is implemented by checking the available spectrum in the Dijkstra's shortest-path algorithm, and SCPVS builds a path-vector tree with spectrum constraint to search the global optimal route. Finally, simulation results show that the elastic optical network outperforms the fixed-grid WDM network by less spectrum utilization in the static scenario BIB003 and lower blocking probability in the dynamic traffic scenario BIB007 [105]. c) RSA for Survivable Networks When setting up optical paths in an optical network, it is often desirable to set up a link-disjoint or node-disjoint protection path at the same time. An algorithm that provides routing and spectrum allocation for dedicated protection in an elastic optical network with the same spectrum range allocated to both working and protection paths was proposed BIB009 . Starting at each spectrum slot, an auxiliary graph G (N, A) is established, in which N represents a set of auxiliary nodes and A represents a set of auxiliary links. If there are a number of consecutive available slots that can accommodate the requested connection, an auxiliary link is established on the graph. After constructing the auxiliary graph, two linkdisjoint routes can be found using Suurballe's algorithm BIB001 . By increasing the starting time slot and repeating the above procedure, a number of feasible solutions can be found for each request. The solution with minimum total route length of the working and protection paths is finally selected. A RSA algorithm that deals with dedicated or shared protection in ring networks is provided in BIB004 . d) Distance-Adaptive RSA In traditional WDM networks, all of the optical paths are assigned the same spectrum width, regardless of the transmission distance of each path, thus leading to an inefficient utilization of the spectrum. The distance-adaptive spectrum allocation concept can be introduced to the OFDM-based elastic optical network, based on adaptive modulation and bitrate/bandwidth variable transponders (as described in Section III-D and IV-C1) to further improve the spectrum efficiency, by adapting a low-level modulation format with wider spectrum for longer distance paths and a high-level modulation format with narrower spectrum to shorter distance paths using different modulation formats  . For example, for the same data rate, 16-QAM carries twice the number of bits per symbol of QPSK, and consequently requires half the spectrum bandwidth (as shown in Fig. 19(a) ), while its OSNR tolerance is lower than QPSK, meaning a shorter distance reach. The distanceadaptive spectrum allocation scheme enables spectrum efficiency (SE) improvement, as the assigned spectral bandwidth can be saved for shorter paths by increasing the number of modulated bits per symbol. The distance-adaptive RSA problem is an extension of RSA, with additional requirements to select an appropriate modulation format and spectrum width according to the transmission distance. The distance that a subcarrier with a specific modulation format can reach is determined based on the transport parameters of an optical path, including the transmission distance (OSNR degradation), the number of hops (WXCs that are traversed), and the optical filter shape. Fig. 19(b) gives an illustration of the spectral width of different modulation formats vs. optical path reach (number of hops). CD and PMD which can be compensated by the DSP are not considered, and non-linear effects are not taken into account for simplicity. Experimental demonstrations of the distanceadaptive spectrum allocation scheme were carried out, using single-carrier and multi-carrier transmission technologies BIB005 BIB006 . A distance-adaptive RSA heuristic algorithm was first proposed in  , using pre-calculated k-shortest path routing and Lowest Starting Slot spectrum allocation scheme. Given the function of transmission distance (number of hops) vs. modulation format, the modulation format and the spectrum Fig. 19 . Distance-adaptive spectrum allocation  : a) Modulated spectrum of QPSK and 16-QAM (with the same data rate); b) Reach vs. allocated spectrum width for different modulation scheme (the spectrum bandwidth listed in the figure includes the necessary guard band). DP-QPSK (Dual Polarization-Quadrature Phase-Shift Keying) signal uses two spectrum widths 45GHz and 57 GHz because, for a path with more hops, a wider guard band is allocated because of the imperfect WSS filter shape, which has been discussed in Section IV-C) width for each subcarrier can be chosen in the spectrum allocation stage. The combined RSA ILP described in Section IV-D2a was extended to give an optimum solution to the distance-adaptive RSA. Additional constraints are added to the ILP formulation, including the reach of each candidate route with the highest modulation level, and the spectrum width needed to be allocated to that route based on the modulation level. A sequential distance-adaptive RSA ILP was proposed in BIB010 , decomposing the problem into the routing and modulationlevel-selection ILP, and the subsequent spectrum assignment ILP. Efficient heuristic algorithms were also investigated, incorporating similar spectrum-allocation policies such as Lowest Starting Slot and Void Filling, as described earlier BIB010 . It has been verified that, with the distance-adaptive spectrum allocation, the allocated spectrum resource reduced by 9-60% compared with non-distance-adaptive elastic optical network (spectrum saving depends on the network topology, traffic pattern, and distance vs. spectrum width of different modulation formats) BIB004 BIB007 . Moreover, the actual spectral gains of the elastic optical network also depend on the guard-band values, transparent/opaque routing constraints, etc., as described in BIB011 .