Received July 9, 2021, accepted July 29, 2021, date of publication August 2, 2021, date of current version August

16, 2021.
Digital Object Identifier 10.1109/ACCESS.2021.3101998

Routing, Modulation and Spectrum Assignment

Algorithm Using Multi-Path Routing and Best-Fit
LIDIA RUIZ , RAMÓN J. DURÁN BARROSO , IGNACIO DE MIGUEL , (Senior Member, IEEE),
NOEMÍ MERAYO , JUAN CARLOS AGUADO , AND EVARISTO J. ABRIL
Optical Communications Group, Universidad de Valladolid, 47002 Valladolid, Spain
Corresponding authors: Lidia Ruiz ([email protected]) and Ramón J. Durán Barroso ([email protected])
This work was supported in part by the Spanish Ministry of Economy and Competitiveness under Grant TEC2017-84423-C3-1-P and
Grant RED2018-102585-T, in part by the Fellowship Program of the Spanish Ministry of Industry, Trade and Tourism under Grant BES
2015-074514, in part by the INTERREG V-A España-Portugal (POCTEP) Program under Grant 0677_DISRUPTIVE_2_E, and in part by
the European Regional Development Fund and Consejería de Educación de la Junta de Castilla y León under Grant VA231P20.

ABSTRACT Elastic Optical Networks (EONs) are a promising optical technology to deal with the
ever-increasing traffic and the vast number of connected devices of the next generation of the Internet,
associated to paradigms like the Internet of Things (IoT), the Tactile Internet or the Industry 4.0, to name
just a few. In this kind of optical network, each optical circuit or lightpath is provisioned by means of
superchannels of variable bandwidth. In this manner, only the necessary bandwidth to accommodate the
demand is allocated, improving the spectrum usage. When establishing a connection, the EON control
layer determines the modulation format to be used and allocates a portion of the spectrum in a sequence
of fibers from the source to the destination node providing the user-demanded bandwidth. This is known
as the routing, modulation level and spectrum assignment (RMSA) problem. In this work, we firstly review
the most important contributions in that area, and then, we propose a novel RMSA algorithm, multi-path
best-fit (MP-BF), which uses a split spectrum multi-path strategy together with a spectrum assignment
technique (best-fit), and which jointly exploit the flexibility of EONs. A simulation study has been conducted
comparing the performance of EONs when using MP-BF with other proposals from the literature. The results
of this study show that, by using MP-BF, the network can increase its performance in terms of lightpath
request blocking ratio and supported traffic load, without affecting the energy per bit or the computation
time required to find a solution.

INDEX TERMS EON, RMSA, best-fit, split spectrum, multi-path, survey.

I. INTRODUCTION the capacity of the links. However, the wavelengths have an

Future Internet will have to deal with new applications from additional role, as they are also used for routing purposes,
many different verticals associated to machine-to-machine hence the name of this type of networks. WRONs are based
(M2M) and human-to-machine (H2M) services that cur- on the establishment of optical circuits, called lightpaths,
rent networks cannot satisfy. The key performance indica- between two network nodes that do not need to be adjacent in
tors (KPI) required for those applications, the ever-increasing the network topology. The establishment of these lightpaths
traffic, and the number of connected devices impose strin- implies the reservation of a wavelength over a sequence of
gent requirements to communication networks [1]. While fibers from the source to the destination node (path or route).
most of the fronthaul networks will be based on multi-radio Therefore, the control plane of those networks must solve the
access technologies (RAT), the backhaul will be built over routing and wavelength assignment (RWA) problem.
optical networks due to their high capacity, flexibility and WRONs use fixed ITU-T channels (typically, of 50 GHz
adaptability [2]. bandwidth) to set up lightpaths. To make a most efficient
Wavelength-routed optical networks (WRONs) use wave- use of the capacity of fibers, single line rate WRONs
length division multiplexing (WDM) techniques to increase migrated towards mixed line rate solutions in which mul-
tiple line rates coexist in the same network but still using
The associate editor coordinating the review of this manuscript and ITU-T fixed channels. Nevertheless, the use of techniques
approving it for publication was Yang Yue . like orthogonal frequency division multiplexing (OFDM)

This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see https://creativecommons.org/licenses/by/4.0/
VOLUME 9, 2021 111633
 L. Ruiz et al.: Routing, Modulation and Spectrum Assignment Algorithm Using Multi-Path Routing and Best-Fit

or Nyquist-WDM [3], [4], in conjunction with the devel- is, we studied the advantages of employing gridless spectrum
opment of devices like the bandwidth-variable transpon- and the introduction of the sub-lightpath approach. Results
der (BVT) and the bandwidth-variable optical cross-connect from that study show that incrementing the flexibility of the
(BV-OXC) [5] favored the appearance of flexible network network does not necessarily imply an improvement of the
architectures like spectrum-sliced elastic optical path net- performance of the network, unless using RSA techniques
work (SLICE) [6]. The main characteristic of these elastic specifically designed to exploit the flexibility of EONs.
optical networks (EONs) is the possibility of allocating a The contribution of this paper is twofold. We firstly present
variable portion of spectrum to each connection adjusted to a comprehensive review of RSA and RMSA methods. Then,
the actual traffic demand. Therefore, the traffic is transported and as the main contribution, we present a new RMSA algo-
in multiple low-rate subcarriers, providing sub-wavelength rithm for dynamic EONs, multi-path best-fit (MP-BF), which
granularity for low traffic requests, or superchannels to trans- combines the use of a split spectrum multi-path strategy with
port high-rate demands, making more efficient use of the a spectrum assignment technique called best-fit [20], [21].
spectrum. Previous studies on the use of best-fit had only considered
In EONs, the RWA problem becomes the routing and single-path routing strategies, and had concluded that its
spectrum assignment (RSA) problem [7]. Therefore, to set performance was similar to that of the well-known first-fit
up a new lightpath, the control layer must assign a portion of technique [20], [21]. However, in this article we demonstrate
spectrum (rather than a single wavelength) along a sequence that when best-fit is combined with a multi-path strategy,
of fibers from the source to the destination node (route) its full potential is realized. Thus, by means of a simulation
that satisfies the user request. To avoid interference between study, we show that MP-BF outperforms other techniques in
lightpaths, a guard-band between contiguous channels is typ- terms of connection blocking ratio and supported traffic load,
ically introduced. There are several studies in the literature without increasing the network energy consumption or the
that address the RSA problem, either considering the spec- computation time.
trum as a continuous block that can be assigned in slices The rest of the paper is structured as follows. In Section II,
(gridless) [8]–[10], or dividing the spectrum in narrow fre- a survey of the main proposals to solve the RSA/RMSA
quency slots (FSs) of fixed width and allocating enough problems is presented. Section III describes the RMSA algo-
consecutive slots to a request to satisfy the demanded traffic rithm proposed in this paper, MP-BF. Section IV reports the
along the fibers that compose the allocated route (flexgrid) performance comparison of MP-BF with other proposals in
[5], [11], [12]. terms of different metrics. Lastly, Section V summarizes the
On the other hand, to avoid request blocking due to the lack main conclusions of the paper.
of enough consecutive spectrum to support the demanded
traffic, split spectrum techniques can be applied [13]–[15]. II. RELATED WORK
These techniques allow providing the total requested capacity A. STATIC RSA AND RMSA
through multiple connections of smaller capacity (which will In static EONs, where the traffic demands are known in
be referred to as sub-lightpaths from now on) and routing advance, the RSA problem consists in allocating a route
them either through the same path (single-path approach) or (i.e., a sequence of fibers from the source to the destination
different paths (multi-path approach). node) and a portion of spectrum that satisfies the bandwidth
As most EONs are equipped with multi-rate/multi-format requirements of all the demands. That problem can be solved
transceivers, the RSA problem can be extended to incorpo- using mathematical formulations or by means of heuristics,
rate the selection of the modulation format, turning into the some of them based on artificial intelligence techniques.
routing, modulation level and spectrum assignment (RMSA) There are several proposals which use mathematical for-
problem. This kind of algorithm selects the most efficient mulations to solve the RSA/RMSA problem (Table 1). For
modulation scheme, in terms of spectral efficiency, that can instance, Klinkowsky and Walkowiak [12] proposed an inte-
be used in a route with acceptable quality of transmission ger linear programming (ILP) formulation that solves the
(QoT). More efficient modulation formats reduce the symbol RSA problem minimizing the number of occupied FSs.
rate while maintaining the transmission rate, hence requiring Christodoulopoulos et al. proposed in [3] and [4] various ILPs
less spectrum to satisfy the traffic demand [16]. The perfor- to jointly and separately address the RSA and the RMSA
mance of the modulation formats is impacted by inter-symbol problems. In [3], authors proposed an ILP formulation that
interference, inter-channel interference, attenuation, noise jointly solves the routing and the spectrum allocation sub-
and other factors, hence limiting the optical reach of the problems to minimize the starting FS index and the number of
transmitted signal [16], [17]. For this reason, higher-order utilized slots. Moreover, [3] also includes two ILPs to solve
modulation formats can be applied to shorter paths compared first the routing (with the objective of minimizing the cost of
to lower-order modulation formats. This is also known as routing, computed as the sum of occupied FS along the links
distance-adaptive spectrum allocation [16], [18]. that compose the route), and then the spectrum allocation
In [19], we evaluated the use of a well-known RWA problem (minimizing the maximum used FS). The method is
method, k-shortest paths and first-fit, to solve the dynamic extended in [4] to solve the RMSA problem. The joint RMSA
RSA problem considering different levels of flexibility, that ILP formulation pre-calculates k-shortest paths between each

111634 VOLUME 9, 2021

L. Ruiz et al.: Routing, Modulation and Spectrum Assignment Algorithm Using Multi-Path Routing and Best-Fit

pair of source-destination nodes and selects the route and TABLE 1. Mathematical formulations that solve the static RSA and RMSA
problems.
portion of spectrum that minimizes the routing cost and the
starting FS index, considering that the number of required
slots will vary according to the selected modulation format,
since each modulation scheme has a different maximum
length with an acceptable QoT. Furthermore, the paper also
solves the separate RMSA by means of an ILP that selects the
route and modulation scheme that minimizes the sum of the
capacity that the request would occupy in all the links along
the route and solving the spectrum assignment following
the same procedure proposed in the joint RMSA algorithm.
Wang et al. [22] proposed an ILP formulation that solves the
problem with the aim of minimizing the maximum subcarrier
index occupied and the total allocated subcarriers over the
fibers of the network. Cai et al. [23] solved the joint RSA
problem through an ILP formulation that minimizes the maxi-
mum FS index employed in the network. Miyagawa et al. [24]
proposed two ILP models for intra-data center static EONs,
aimed at minimizing the number of utilized FSs and maxi-
mizing the served traffic requests under a given number of
FSs, respectively. Gong et al. [25] presented two ILP formu-
lations to solve the RMSA problem with multicast traffic, one
optimizing the requests jointly and the other one optimizing
each request separately, with the objective of minimizing the
maximum employed FS index. Goscien et al. [26] proposed
two ILP algorithms to solve the joint RMSA problem min-
imizing the cost and power consumption, and the spectral
utilization, respectively. Finally, Zhao et al. [27] solved the
joint RMSA problem by means of an ILP formulation that
minimizes the maximum index of the allocated FS consid-
ering non-linear impairments. Behera et al. [28] addressed
the bit loading problem, i.e., the independent modulation of
each FS so that each one is loaded with a different num-
ber of bits per subcarrier. Authors proposed a mixed inte-
ger linear programming (MILP) formulation to solve the
routing, bit loading and spectrum allocation (RBLSA) that
selects the route, the spectrum and the modulation level
for each allocated FS that minimizes the sum of high-
est indexed FSs so that the signal-to-interference-plus-noise
ratio (SINR) is satisfied. These proposals are summarized
in Table 1.
RSA/RMSA problems have been shown to be NP-Hard [4], maximum subcarrier index. The first one sorts the requests
[7], [29]. To overcome this issue, some works have pro- in decreasing order of demanded FSs and, for each request,
posed heuristics for solving those problems. Klinkowsky and allocates the shortest path and the set of available FSs with
Walkowiak [12] included in their study a heuristic which the lowest index. The second heuristic first precomputes
solves the problem minimizing the maximum FS index occu- k-shortest paths for each pair of source-destination nodes,
pied in the network. The proposal processes each demand in checks which of the calculated paths minimizes the maximum
decreasing order of demanded FSs, examines all the candi- fiber load and allocates that path and the lowest-indexed set
date paths for each demand and selects the one that presents of available FSs. Christodoulopoulos et al. [4] accompanied
a set of free FSs that satisfy the demand and whose initial FS their ILP formulation with a heuristic in which the candidate
index is the smallest between all the initial FS indexes of the paths between each pair source-destination are computed, and
candidate paths. Cai et al. [23] proposed a greedy algorithm a greedy algorithm is applied to select the path containing the
that allocates to each traffic demand the shortest path in set of free FSs with the lowest starting index. Gong et al. [25]
number of hops that contains the set of free FSs with the proposed a genetic algorithm that solves the joint RMSA
lowest index that satisfies the traffic demand. Wang et al. [22] problem minimizing the maximum index of the allocated
proposed two heuristics with the objective of minimizing the subcarriers. Goscien et al. [26] devised a greedy algorithm

VOLUME 9, 2021 111635

 L. Ruiz et al.: Routing, Modulation and Spectrum Assignment Algorithm Using Multi-Path Routing and Best-Fit

that sorts requests in decreasing order of demanded traffic, TABLE 2. Heuristics that solve the static RSA and RMSA problems.
computes the k-shortest paths between source and destination
and allocates to each demand the feasible path that mini-
mizes the cost. The proposal also includes a tabu search that
optimizes the solutions obtained with the greedy algorithm
by either changing the path, the modulation format or the
server when traffic is anycast. Zhao et al. [27] also presented
a heuristic that calculates k-shortest paths between each pair
of source-destination nodes, sorts the requests according to
a given criterion and, for each path, modulation format and
set of available FSs, computes the cost of each link in the
path, assigning the one with the lowest cost. Behera et al. [28]
proposed a heuristic that sorts the requests according to a
certain criterion and solves the RBSA for each request. For
that aim, it creates the set of candidate routes computing
k-shortest paths and checks each available FS and modulation
format to verify if there are enough consecutive available
FSs that meet the traffic and the SINR requirements. The
algorithm allocates the path with the lowest sum of highest
FS indexes in the links. Lastly, Yu et al. [30] proposed a
heuristic that computes k-shortest paths, sorts the requests
utilizing different policies and assigns the first available por-
tion of spectrum that satisfies the demand. These heuristics
are summarized in Table 2.

B. DYNAMIC RSA AND RMSA

The former studies addressed the RSA and RMSA problems
in static EONs. However, a next step in the evolution of EONs
is the establishment and release of lightpaths on demand.
That scenario is known as the dynamic scenario and, in it,
the network control layer must provision user demands with At each loop, the algorithm checks the nodes at one hop
a route and a portion of spectrum that fulfill the user request of each leave. If there are enough available spectrum in
in a short period of time, as they have to be established in the connected link, they are added to the decision tree and
real time. Mathematical formulations are not particularly suit- the algorithm repeats the procedure with the following hop
able to dynamic EONs due to the huge computing time that in the path, until arriving at the destination node. Finally,
they require. For this reason, it is common to find proposals the algorithm selects the path with enough free FSs and mini-
based on heuristics and meta-heuristics to solve the dynamic mum routing cost. Authors also proposed a modified version
RSA/RMSA problems. of Dijkstra’s shortest path that computes the shortest path
The problems can be solved jointly or separately. For between the source and destination node and the aggregated
example, Wan et al. [9] solved the RMSA problem using two available spectrum along the path. In this manner, the algo-
strategies for modulation format selection: fixed or adaptive rithm verifies if the same consecutive FSs are available in all
modulation. In the first one, the modulation level is selected the links composing the path and if they satisfy the traffic
at the beginning of the procedure and remains fixed until the demand, including the required guard-band. Salani et al. [31]
RSA problem is solved. In the second strategy, the algorithm proposed an ILP formulation to solve the joint RSA problem
selects the most efficient modulation level and tries to solve minimizing the number of transceivers and the occupied spec-
the RSA problem. If no feasible path is found, the algorithm trum. The formulation is extended to include multiple mod-
selects the second most efficient level and tries again. The ulations by adding reach constraints. Furthermore, the ILP
procedure is repeated until a path is found or until all the is enhanced with machine learning techniques to include
modulation schemes are checked. Furthermore, the authors a QoT estimation in the solution. Leiva et al. [32] solved
propose two heuristics to solve the RSA problem. The first the RSA problem by means of a dynamic graph coloring
heuristic builds a decision tree containing all candidate paths algorithm. The algorithm checks each FS in the spectrum and
with enough available spectrum. The algorithm examines builds sub-graphs that include the links with enough available
each path, taking as the root the source node and taking as the spectrum to satisfy the demand, assuming that the first FS
leaves the adjacent nodes connected with links with sufficient in the set is the FS being checked. Once all the sub-graphs
spectrum to satisfy the demand, including the guard-band. are built, the algorithm looks for the shortest path in terms of

111636 VOLUME 9, 2021

L. Ruiz et al.: Routing, Modulation and Spectrum Assignment Algorithm Using Multi-Path Routing and Best-Fit

number of hops and assigns the path and the available FSs. to solve the RSA problem. Solutions implementing least con-
Velinska et al. [33] adapted the genetic algorithm that solves gested routing (LCR) can also be found in literature. In this
the RWA problem proposed by Bisbal et al. [34] to solve the case, the algorithm selects the path with more FSs available
RMSA problem. The algorithm creates an initial population among a set of predetermined routes between the source
of random routes that connect the source and destination and destination nodes. This method is presented in [2] and
node of the request, applies classical genetic operations like employed in [7]. Moreover, Sambo et al. [40] used a varia-
crossover and mutation and calculates the number of FSs tion called least congested routing conditioned to modulation
required to satisfy the demanded traffic (that depends on the format, that calculates the congestion according to the best
modulation format that can be applied to the route) and the performing modulation scheme in terms of QoT and spectral
number of hops. The algorithm returns the best-found route efficiency that can be employed in the path. Yuan et al. [41]
in terms of number of allocated FSs and hops after a number proposed an RMSA algorithm that uses FAR to precompute
of iterations. Alyatama [35] presented an RSA algorithm that the list of candidate paths and then selects the route and
checks all the possible routes between the source and desti- the consecutive FSs that minimize the available spectrum
nation nodes and calculates the relative cost of carrying the resource reduction both in the candidate path and in the routes
requested traffic along the route, computed as the difference with shared links.
in the lost revenues when a connection is accepted or not. Lastly, the spectrum assignment subproblem can be solved
This relative cost is calculated for all the available sets of using techniques like the following ones:
FSs in the route. At the end of the process, the algorithm (1) First-fit (FF): This scheme indexes the FSs and main-
returns the route and the starting FS index that minimizes the tains updated information on the available and occupied FSs.
relative cost. Then, it searches for a set of contiguous FSs that satisfies the
The dynamic RSA/RMSA problem can also be solved by traffic demand, in ascending index order, hence allocating the
separately addressing the routing, the modulation, and the first set of FSs that are available. This tactic is employed in
spectrum allocation. The routing problem can be addressed [18], [36], [38], [42], [43] and [44].
using analogous algorithms to those employed to solve (2) Last-fit (LF): This technique works in a similar manner
the RWA problem. Hence, well-known techniques like to FF but attempting at allocating the highest indexed FSs to
fixed routing (FR) and fixed alternate routing (FAR) can a connection [2].
be used. FR has a single pre-calculated route for each (3) Random-fit (RF): The algorithm randomly selects the
source-destination pair of nodes, which is always used. spectrum slices among a list of available FSs, so that the FSs
In contrast, FAR has several pre-calculated routes for each are the same in all the links conforming the first found path
source-destination pair of nodes and, upon a lightpath request and satisfy the demanded traffic [43].
arrival, each path is checked until finding one with enough (4) Lowest starting slot (LSS): This method aims at allo-
idle spectrum. These techniques are employed in [36], where cating the first set of available FSs that satisfy the traffic
authors also proposed a k-distance adaptive path selec- demand in any path. Hence, the algorithm checks all the
tion algorithm that pre-computes the candidate paths and candidate paths between the source and destination nodes and
required spectrum when the most efficient modulation for- the available slots in increasing index order. Finally, it assigns
mat (depending on the path) is employed, and selects the the path with the lowest-indexed slots [4].
path using either FR or FAR. Jinno et al. [18] also used a (5) Exact-fit (EF): The algorithm starts to check all the
FAR approach to solve the RMSA problem and studied the sets of contiguous FSs in increasing index order and allocates
advantages of selecting the modulation format in terms of the set that exactly matches the requested traffic. If no set
spectrum resource utilization. Ahmed et al. [37] proposed fulfills this requirement, the policy allocates FSs using the
an RMSA algorithm for coexisting fixed/flexgrid networks, FF technique [43].
which computes k-shortest paths and selects the one with the (6) First-last-fit (FLF): This technique partitions incom-
highest spectral efficiency, i.e., the one that requires the least ing requests and, depending on the partition, aims at allo-
bandwidth to serve the requested traffic. Calderón et al. [38] cating the available FS either with the lowest or the highest
proposed a bit error rate (BER)-adaptive RMSA algorithm index [45]. Li and Li [46] use this technique in their RSA
that computes k-shortest paths and finds the route, the modu- proposal, which aims at minimizing the utilized spectrum
lation level and the portion of spectrum that meets the traffic resources and the distance between the candidate FS and a
requirements with the lowest BER. If the algorithm cannot certain boundary.
find a route, set of FSs and a modulation scheme, it splits (7) First-last-exact-fit (FLEF): This spectrum allocation
the route in two segments introducing a regenerating device, technique [47] classifies connections into non-disjoint and
and aims at finding a portion of spectrum and a modula- disjoint path requests. The requests with disjoint paths are
tion level at each segment independently, so that the BER solved using First-Exact Fit (FEF), which tries to allocate the
threshold is met. Alyatama et al. [39] employed adaptive first set of FSs that exactly adapt to the demanded traffic,
routing (AR), in which the routes are calculated according or the lowest indexed FSs that satisfies the demand, if not
to the network state at the connection request arrival time, exact fit is found. On the other hand, the connections with

VOLUME 9, 2021 111637

 L. Ruiz et al.: Routing, Modulation and Spectrum Assignment Algorithm Using Multi-Path Routing and Best-Fit

non-disjoint paths are solved using Last-exact Fit (LEF), that TABLE 3. Proposals to solve the dynamic RSA/RMSA problems.
performs analogously to FEF but starting the search at the
highest-indexed FSs.
(8) Reusable spectrum allocation first (RSAF): This
technique classifies slots into two categories: slots that have
been allocated to previous connections (and released once
the connection is torn down) and slots that have never
been allocated to a connection. When a connection arrives,
the algorithm tries to allocate slots from the previously allo-
cated slots list using FF. If not enough previously used slots
are available, it allocates slots that have never been assigned,
also using FF. This strategy is employed in [37].
(9) Best-fit (BF): This method is a variation of EF.
It checks a candidate route between a source and a destination
node to find the sets of available FSs and sorts them according
to their size, instead of in increasing index order like EF.
The algorithm examines each set and allocates the one that
exactly fits the demanded traffic, like EF. However, if no
exact match is found, it allocates the set with the smallest
size that satisfies that demand [20], [21]. Although BF was
designed with the characteristics of the RSA problem in mind
(i.e., it is not a straightforward adaptation of an RWA tech-
nique), the results in both [20] and [21] show that it achieves
similar performance to FF when combined with single-path
routing. However, in this paper we will demonstrate that its
performance improves significantly when combined with a
multi-path strategy (which we will discuss later), resulting in
the proposed MP-BF algorithm.
(10) Multiple of n (Multi-n): Used in [40], the algorithm
selects the required n FS so that the selected lowest-indexed
FS is a multiple of n and the following n-1 FS are available.
All the techniques reviewed above to solve the
RSA/RMSA problem in dynamic EONs are summarized
in Table 3.

C. TRAFFIC GROOMING, FRAGMENTATION AND SPLIT

SPECTRUM TECHNIQUES
There are issues related to EONs as traffic grooming, frag-
mentation and split spectrum techniques that have an impact
on the performance of RSA and RMSA algorithms. We will
briefly introduce these aspects and describe their effects on
the performance of RSA and RMSA algorithms.

1) TRAFFIC GROOMING
This operation aggregates low-speed connection requests
into a higher capacity traffic flow to improve spectrum uti-
lization. Traditionally employed in WRONs, it was intro- optical-electrical-optical (O/E/O) conversions and switching
duced in EONs for two reasons: (i) it makes a better use requirements at the intermediate nodes, increasing energy
of transponder capacity, given the limitations in slicing of consumption [49], [50], [51]. Moreover, researchers devel-
early bandwidth-variable transponders (BVT) [7], and (ii) it oped the sliceable BVT (S-BVT), a device that over-
improves the use of the spectrum since establishing less comes the limitations of BVTs by supporting different
connections implies the use of less guard-bands between modulation schemes, bit rate, transmission distances and
channels [7]. sliceability [7], [49], [52]. These devices allow to partially
Traffic grooming can be performed electrically through perform traffic grooming at the optical layer, aggregating dif-
the use of electrical subcarrier multiplexing and switch- ferent low-capacity connections into one BVT and switching
ing [48], [49]. However, this approach requires additional them as an optical tunnel or group of optical paths. Again,

111638 VOLUME 9, 2021

L. Ruiz et al.: Routing, Modulation and Spectrum Assignment Algorithm Using Multi-Path Routing and Best-Fit

in order to separate different optical connections inside a be defragmented. The traffic then shifts from the old to the
network, a guard-band should be added [49], [50], [53]. new connection and the original one is torn down.
Finally, traffic grooming can also be performed at the Furthermore, fragmentation can be managed through the
optical layer. Zhang et al. [50] presented an ILP formulation RSA algorithms. Dávalos et al. [61] proposed an algorithm
and a heuristic to plan the optical grooming minimizing based on ant colony optimization and a genetic algorithm to
either the consumed spectrum or the employed transponders solve the RSA problem. The algorithms decide the best set
in static and dynamic scenarios. Khodashenas et al. [54] of lightpaths to be proactively rerouted, with the objective of
proposed a heuristic to solve the RSA problem with traffic reducing the request blockage. Moura et al. [62] proposed
grooming that minimizes the used transmitters in the network. a heuristic to solve the RSA problem using a multigraph,
Zhu et al. [55] proposed a grooming algorithm based on i.e., a graph where vertices can have multiple edges. In this
deep reinforcement learning that extracts the state of the case, the vertices are the optical cross connects (OXC) of the
network and takes actions to decide where to groom a given network and there are as many edges connecting the OXCs
IoT service with the goal of optimizing energy consumption. as FSs in the spectrum of each link. Authors, then, calculate
Hosseini et al. [56] proposed a heuristic to groom incoming the number of FSs required to satisfy the connection request
traffic requests to existing lightpaths with remaining hold- and propose a heuristic that uses the graph to select the
ing times close to the holding time required by the request, single path and portion of spectrum to be allocated that min-
or establish a new lightpath aiming at efficiently using the imizes the overall power consumption and bandwidth block-
spectrum and BVT resources. The proposals are summarized ing. Waldman et al. [63] proposed a deadlock-avoidance
in Table 4. technique that reduces fragmentation by assigning network
resources only if the allocated link is fully utilized after
TABLE 4. Proposals on traffic grooming in EONs.
reserving resources, or if the remaining resources can accom-
modate another connection. Qiu et al. [64] presented a spec-
trum consumption model that takes into consideration the
occupied spectrum, the fragmented spectrum, and their hold-
ing times. They proposed an ILP formulation that minimizes
the spectrum consumption obtained with this model, with the
objective of minimizing the bandwidth blocking. They also
devised a heuristic to solve the RSA problem in dynamic sce-
narios adapting the model to the characteristics of dynamic
traffic. This heuristic calculates the k-shortest paths and, for
each candidate path, finds the set of available FSs, calculates
the spectrum consumption including the fragmented FSs, and
allocates the path and portion of spectrum that minimizes
2) FRAGMENTATION this consumption. Yuan et al. [65] proposed an RSA to
The fulfillment of the continuity and contiguity constraints, minimize the blocking ratio by modeling the fragmentation
together with the allocation and deallocation of FSs to con- through the concept of contiguity reduction, which measures
nection requests, may cause fragmentation [57], i.e., the the reduction in the adjacency degree of available frequency
appearance of isolated idle FSs, almost unusable for the estab- slots, when a new connection is established. The algorithm
lishment of new connections, thereby increasing blocking computes the shortest path between the source and destina-
events. tion nodes, checks the blocks of available FSs in increasing
Fragmentation can be addressed through an operation size order, computes the path and link contiguity reduction
called defragmentation. This approach periodically recon- and selects the available FSs that minimize the fragmen-
figures the existing connections and allocated spectrum. tation in terms of path contiguity reduction and using the
In consequence, the misuse of spectrum resources and band- lowest link fragmentation in case of tie. Adhikari et al. [66]
width blocking are reduced [5], [7], [57]. There are different addressed the spectral and the spatial fragmentation problem
defragmentation techniques like the hop-tuning, the make- using an spectrum allocation algorithm. They proposed an
before-brake and the push-and-pull approaches [5], [7]. The RSA algorithm that computes the k-shortest paths between
hop-tuning strategy [58] moves the assigned slots to a con- source and destination nodes, and then selects those that
nection to other available slots, while keeping the route. meet a certain BER threshold. Once the candidate path set
The push-and-pull technique [59] changes the allocated slots is built, the algorithm checks, for each route, each set of
by increasing the assigned resources, pushing the central available FSs and selects the route and the FSs that mini-
frequency as close as possible to the side of the adja- mize the spectral fragmentation. If two candidates present
cent connection and reducing the allocated resources to the same minimum value of spectral fragmentation, the algo-
the original number of assigned FSs. Finally, the make- rithm selects the one with the lowest spatial fragmentation.
before-break approach [60] provisions a new connection Liu et al. [67] also addressed the time and spectrum fragmen-
between the source and destination nodes of the lightpath to tation problem by proposing an RMSA algorithm for advance

VOLUME 9, 2021 111639

 L. Ruiz et al.: Routing, Modulation and Spectrum Assignment Algorithm Using Multi-Path Routing and Best-Fit

reservation requests. The algorithm relies on pre-computed k- the available resources, sorts the pre-calculated set of paths
shortest hop paths and k-shortest distance paths between each according to different strategies and checks each path to
source-destination pair of nodes. When a request arrives at the find available resources, allocating the FSs using the first-fit
network, it dynamically calculates the routing weight of those algorithm. Authors in [69] presented a heuristic to solve the
paths as the occupied spectrum resources, and then selects RMSA problem considering a bi-dimensional resource model
candidate paths according to their increasing order of routing that contains the spectrum availability in the time domain.
weight. Next, for each candidate path, the algorithm com- The algorithm initially tries to allocate each request in a
putes the available spectrum resources and selects the route single connection using FF as the spectrum assignment tech-
that minimizes the spectrum fragmentation, measured as the nique. If there are blocked connections, the algorithm tries
fragmentation in the selected route and in those routes with to allocate them by splitting the traffic of each demand into
shared links. These algorithms are summarized in Table 5. three sub-lightpaths routed through the same path. Finally,
if there are requests that could not be allocated, the algo-
TABLE 5. Proposals to address the fragmentation problem using routing rithm tries to route them through different paths. When the
and spectrum allocation algorithms.
connections are provisioned using the multi-path technique,
the heuristic selects the paths and FSs that minimize the
fragmentation, calculated as the difference between the time
and spectrum fragmentation before and after the resource
reservation.
Yousefi et al. [70] proposed different heuristics to solve
the RMSA problem applying the multi-path approach. If the
request cannot be provisioned in a single connection solved
using the k-shortest paths and first-fit, the algorithm splits
the request into two different sub-lightpaths independently
provisioned. The set of candidate paths are calculated using
the k-shortest paths and checked according to some criteria
like the external fragmentation or fragmentation measure
metric proposed by the authors, while the algorithm assigns
the first set of available FSs that satisfy the traffic demand.
In our work in [19], the classic RWA methods k-shortest paths
and first-fit were adapted to be solve the RSA problem con-
sidering either flexgrid or gridless spectrum and single-path
and multi-path routing. Our study shows that traditional RWA
techniques are not able to fully exploit the flexibility of
EONs. Pagès et al. [15] proposed a heuristic to solve the RSA
problem combining a single-path approach and a flexible
spectrum allocation strategy. The algorithm computes the k-
shortest paths between the source and destination node, sorts
the sets of available FSs in decreasing size order and, for
3) SPLIT SPECTRUM TECHNIQUES each feasible path, starts allocating the sets of FSs in order
The elastic features of EONs allow providing the total until all the traffic is served. A guard-band is added after each
requested capacity through multiple connections of smaller sub-lightpath to avoid interference between adjacent connec-
capacity (sub-lightpaths) that can be routed through the same tions. Therefore, a request is blocked if no candidate path can
or different paths. If the same path is used for all sub- satisfy the demanded traffic plus the required guard-bands or
lightpaths, it is known as single-path routing, while if dif- if the traffic is split in more sub-lightpaths than the allowed.
ferent paths can be used for each sub-lightpath, the term The same authors presented in [71] a heuristic to solve the
multi-path routing is employed. RMSA problem. The technique employs a greedy approach to
Zhu et al. [68] proposed two heuristics to solve the RMSA build the set of candidate paths to serve the request and sorts
problem, which combine multi-path routing together with the it according to a quality criterion that includes the number
FF spectrum assignment technique. One of the algorithms of allowed modulation formats in the path and the number
calculates the k-shortest paths at the connection arrival time, of FSs required to serve the request utilizing each of the
taking into account current network status, and then checks feasible modulation formats. Once the candidate path set is
each path in ascending weighted length order and allocates built, the algorithm checks each one and the availability of
the first available FSs. The other algorithm pre-calculates spectral gaps in decreasing size order to favor the allocation
a set of fixed candidate paths using k-shortest paths. Then, of a demand in fewer parts (i.e., reducing the number of
when a connection request arrives, the algorithm updates required sub-lightpaths). If the algorithm cannot serve the

111640 VOLUME 9, 2021

L. Ruiz et al.: Routing, Modulation and Spectrum Assignment Algorithm Using Multi-Path Routing and Best-Fit

traffic demand or if the connection needs to be split into more This restriction is known as the spectrum continuity con-
parts than those allowed, the request is blocked. straint. When there are not enough idle resources to satisfy
One disadvantage of multi-path routing techniques is that the request, the demand is rejected. Otherwise, the connection
the different sub-lightpaths experience different end-to-end is established [11]. The goodness of the RMSA methods is
delays. Some works have addressed this drawback by set- usually measured in terms of different indicators: blocking
ting constraints on the maximum differential delay between ratio (i.e., the ratio of rejected user demands), the carried
paths [72], [73], and have analyzed the impact on buffering traffic, the consumed energy or the computing time required
costs required to solve that problem [74]. to find a solution.
All these proposals, which implement split spectrum tech- The RMSA method proposed in this paper is called
niques are summarized in Table 6. multi-path best-fit (MP-BF), and it combines the multi-path
routing technique, using FAR, with the best-fit algorithm
TABLE 6. Proposals using split spectrum techniques. [20], [21]. In contrast to the algorithms in [20], [21], where
only single-path is allowed, MP-BF improves the network
performance by allowing the split of the required capacity
into multiple sub-lightpaths if a single route with enough
idle spectrum is not available. The different sub-lightpaths
can be routed through the same path or through a different
route, but the sum of their capacity must satisfy the one
requested by the user. Moreover, [20], [21] are RSA meth-
ods but MP-BF solves the RMSA problem and thus, it also
selects the modulation format. In particular, MP-BF uses the
most efficient modulation format that ensures the fulfillment
of QoT requirements. Note that each sub-lightpath can use
different modulation formats and, consequently, can have
different spectral efficiencies. That feature is also considered
by MF-BF. Similarly to other studies on this topic [71],
the issue of the differential delay among parts is left out of
the scope of this study. The use of multi-path routing implies
that the wasted spectrum in guard-bands increases with the
number of sub-lightpaths created for each connection, given
that each sub-lightpath requires the addition of a guard-band.
Despite that, the flexibility given by the multi-path routing
when combined with the BF technique takes MP-BF to beat
the performance of those methods as it will be demonstrated
later.
The pseudocode of MP-BF is shown in Algorithm 1.
Initially, a set of candidate routes for each pair of nodes
using the k-shortest paths (in terms of hops) is pre-computed.
In this paper, we propose a RMSA algorithm for dynamic Then, when a new lightpath establishment request between
EONs called multi-path best-fit (MP-BF). Our proposal uses the source node s and the destination node d arrives, MP-BF
the k-shortest paths technique and allows to use the multi- sets the value of the pending capacity to be assigned to
path routing strategy to solve the routing problem and the the requested capacity (line 2) and retrieves the set of
best-fit technique (BF) for the spectrum assignment, and we k-shortest paths for that s-d pair, sorted in increasing length
demonstrate that it outperforms other RMSA methods. order (line 4). Next, MP-BF searches in each path portions of
idle spectrum to establish the request (lines 5-25). Note that
III. NOVEL RMSA ALGORITHM: MULTI-PATH BEST-FIT the MP-BF stops as soon as it finds a solution (either using
(MP-BF) a single lightpath or several sub-lightpaths) that provides the
A. ALGORITHM DESCRIPTION requested capacity.
The dynamic RMSA problem is solved in a dynamic EON MP-BF uses the most efficient modulation format for each
when a user connection request arrives at the network. In that path taking into account its physical length (in kilometers),
moment, the network must determine the modulation for- as done in [4], [18], [71] (line 6). When checking the available
mat, the route, i.e., the sequence of fibers from the source spectrum in a candidate route, MP-BF obtains the set of
to the destination node, and a portion of spectrum to sat- contiguous idle FSs in all the fibers of the path to ensure the
isfy the requested bandwidth. If the network is not equipped spectrum continuity constraint (line 7). We assume that the
with waveband/wavelength converters, the reserved portion guard-band is included in the last slot of the assigned set of
of spectrum along the fibers of the route must be the same. contiguous FSs. Therefore, we can obtain the capacity of the

VOLUME 9, 2021 111641

 L. Ruiz et al.: Routing, Modulation and Spectrum Assignment Algorithm Using Multi-Path Routing and Best-Fit

Algorithm 1 : MP-BF describe that procedure. In contrast, if there are several sets
1: procedure MP-BF(source, destination, that provide equal or more capacity than the pending one,
requestedCapacity) MP-BF selects the one that has the closest capacity to the
2: pendingCapacity ← requestedCapacity pending capacity (lines 14-16). This is because the sets of
3: selectedSetsOfFS ← ∅ contiguous FSs were sorted in increasing order of capacity.
4: paths ← retrieveKShortestPaths(source, In case of tie, MP-BF uses LF with the tied sets of contiguous
destination) FSs. It is worth noting that the size of the selected set is
5: for path in paths do reduced to only use the required number of FSs to provide
6: modulation ← selectBestModulation(path) the pending capacity (line 15). That number is computed in
7: # Groups of contiguous idle FSs in the path a similar way as described before (i.e., taking into account
setList ← getSetsOfContiguousFS(path) the guard-band bandwidth, the bandwidth of the slots and the
8: for set in setList do spectral efficiency). Then, MP-BF uses the sets that have been
9: set.capacity ← computeCapacity(set, selected along the iterative procedure to establish optical con-
modulation) nections (one sub-lightpath per selected set) and the process
10: end for finishes (lines 17-18).
11: setList ← sort(setList, by =capacity, If all the sets of contiguous FSs in the path have less capac-
order=increasing) ity than the pending one (line 14 is not fulfilled), the demand
12: whilesetList 6 = ∅ do cannot be served with a single set of FSs; thus, MP-BF splits
13: for set in setList do the demand. First, it selects the set with the highest capacity
14: if set.capacity ≥ pendingCapacity then to be later used to establish a sub-lightpath and deletes it
15: # Use only the required spectrum (slots) from the list of (available) sets (lines 21-22). Since part of
of that set the pending capacity will be provided by that sub-lightpath,
set ← reduceSize(set, pendingCapacity) the pending capacity is updated by subtracting the capacity
16: selectedSetsOfFS ← selectedSetsOfFS of that set of FSs (line 23). The process continues with a new
∪ set iteration of the ‘while’ loop (line 12), looking for a set of
17: establishSubLightpaths(selectedSetsOfFS) contiguous FSs in the path that best fits the pending traffic,
18: go to end procedure or splitting again the demand until the requested capacity is
19: end if served, or all sets of contiguous FSs in the path are checked
20: end for and assigned.
21: # Extract the last set of FSs of the list If all the sets of contiguous, available FSs of the can-
highestCapacitySet ← pop(setList) didate path have been checked and assigned, and there is
22: selectedSetsOfFS ← selectedSetsOfFS ∪ still pending capacity to be satisfied, MP-BF continues with
highestCapacitySet the next path following the same procedure as described
23: pendingCapacity ← pendingCapacity - above. If MP-BF tries all the pre-computed paths but there
highestCapacitySet.capacity still is pending capacity to accommodate, the request is
24: end while blocked (line 26). Note that a connection is only established
25: end for if the network can fully satisfy the requested bandwidth
26: blockConnection() (line 17). The algorithm does not impose any limitation in
27: end procedure the number of splits, neither in the same route nor in different
routes.
Fig. 1 illustrates how MP-BF works in a sample scenario.
set, i.e., the rate at which the traffic can be transported over Let us assume a connection request from A to C arrives at
this group of available FSs, by subtracting the guard-band the control plane of the 6-node network shown in the figure.
bandwidth from the sum of the bandwidth of all the consec- The shortest path between those nodes goes through A→B
utive available slots in this set and multiplying the resulting and B→C links. The current spectrum utilization of those
value by the spectral efficiency of the selected modulation links and of the path (the combination of both link spectrum
format for that path (lines 8-10). The channels are then sorted utilizations) is also shown in Fig. 1. Let us assume that the
in increasing capacity order (line 11). size of guard-bands in this scenario is one slot.
Here, an iterative process with the available set of con- In the first example, the A to C connection request demands
tiguous FSs in the path begins, and it continues until the a capacity equal to one slot. Therefore, two consecutive
demand is served or until all the sets in the path are checked empty spectral slots are required (one to provide the requested
(lines 12-24). If no set of contiguous available FSs in the capacity, which will be represented in red in Fig. 1, and one
path has enough capacity to satisfy the pending one, the use for the guard-band, represented in green). MP-BF assigns
of several sets of contiguous FSs (and thus sub-lightpaths) the portion of spectrum that best fits the demand (as shown
will be required, hence splitting the demand. We will later in Fig. 1, E.g. 1). In contrast, if MP-FF had been used, the first

111642 VOLUME 9, 2021

L. Ruiz et al.: Routing, Modulation and Spectrum Assignment Algorithm Using Multi-Path Routing and Best-Fit

the O (1), O (S) and O (S · log (S)) complexities previously

mentioned. Therefore, the

total computational complexity of
MP-BF is O K S 2 + LS .

IV. PERFORMANCE EVALUATION OF MP-BF

A. SIMULATION SETTINGS
The performance of MP-BF has been compared with other
proposals from the literature by means of a simulation study.
For that aim, an EON simulator was implemented using
OMNeT++ [75]. The physical topology of the network used
in the simulation is the 14-node NSFNet [76], where each
link is composed of two unidirectional optical fibers, one for
each direction. All channels belong to the C-band and, there-
fore, the available bandwidth of each fiber is 4 THz. As in
most studies, flexgrid technology is considered using FSs
of 12.5 GHz, and assuming 10 GHz of guard-band between
contiguous lightpaths or sub-lightpaths. Nodes are assumed
to be equipped with transceivers able to use four modulation
FIGURE 1. Spectrum allocation when using MP-BF when 1 FS is schemes: BPSK, QPSK, 8-QAM and 16-QAM. The bits per
requested (E.g. 1) and 5 FSs are requested (E.g. 2). symbol, spectral efficiency, transmission rate per full slot, and
optical reach of each modulation format are shown in Table 7
[4], [77]. Like in most studies in the area, we have assumed
two empty slots would have been assigned, thus leaving one that blocking is only due to lack of spectrum and not to lack
idle (and unusable) slot in the spectrum. of transponders, unless otherwise stated.
In the second example, the request demands a capacity
equal to five slots. In this case, single path techniques cannot TABLE 7. Transmission rates and optical reach of the different
provide the required spectrum through the A→B→C path. modulation schemes.
Therefore, the lightpath should be either established in a
longer route with enough consecutive FSs or rejected. In con-
trast, MP-BF uses a multi-path technique. Thus, it will split
the request into two sub-lightpaths (including the required
guard-bands) and establish the request as shown in Fig. 1
(E.g. 2). If MP-FF had been used instead of MP-BF, three
sub-lightpaths (with three guard-bands) would have been
established to satisfy the request and, thus, it would have used
more spectrum than MP-BF. We also assume that connection requests arrive at the
network following a Poisson process with arrival rate, λ.
B. COMPLEXITY ANALYSIS The source and destination nodes for each request are ran-
The complexity analysis of MP-BF is derived from Algo- domly selected using a uniform distribution. Each connection
rithm 1. Let K be the number of candidate paths, S the total demands a capacity randomly generated using a uniform
number of FS in a link and L the number of links. Since the distribution between Cmin = 1 Gbps and Cmax = 300 Gbps,
candidate paths are pre-computed (as well as their best mod- therefore with average Cavg = (Cmax − C min ) /2. Finally, the
ulation format depending on their physical distance in km), holding time for each connection is generated by means of an
its complexity is not considered. There is a ‘‘for’’ loop (lines exponential distribution with mean equal to T = 60 s. Since
5-25) which repeats K times. That loop internally contains different connections demand different capacities, rather than
different operations. First, the precalculated best modulation using the classical traffic load in erlangs, computed as λT ,
format of the precalculated path is retrieved (O (1)), and the we use a normalized version of it. It is given by equation (1),
sets of contiguous FS in that path are searched (line 7), which which takes into account the average and maximum capacity
has a complexity O (LS). Then, the capacity of those sets is of the connections, as well as the number of nodes in the
computed in lines 8-9, which has complexity O (S), and they network, N .
are sorted in line 11, which has complexity O (S · log (S)). λT Cavg
load = · (1)
Next, the ‘‘while’’ loop (lines 12-24) assigns the spectrum N (N − 1) Cmax
using the BF policy. Since the ‘‘while’’ loop contains a ‘‘for’’
loop (lines 13-20) that checks all the channels in the channel B. COMPARISON ALGORITHMS
list and is completed in S steps in
the worst case, the com- Our proposal, MP-BF, has been compared with five other
plexity of the while loop is O S 2 , which dominates over algorithms, previously presented in Section 2, which have

VOLUME 9, 2021 111643

 L. Ruiz et al.: Routing, Modulation and Spectrum Assignment Algorithm Using Multi-Path Routing and Best-Fit

proven their efficiency to solve the RMSA problems: when FF or EF spectrum assignment techniques are used,
multi path-first fit (MP-FF) [68], [70], multi path-exact fit the advantages of multi-path routing do not outweigh the
(MP-EF), single path-first fit (SP-FF) [18], single path-exact disadvantages. In contrast, the BF technique is more efficient
fit (SP-EF) [43] and single path-best fit (SP-BF) [20], [21]. in this scenario (since it helps reducing the number of splits
MP-FF uses precalculated multi-path, k-shortest paths for needed to serve the demands, as it will be later demonstrated),
routing and FF for spectrum allocation. MP-EF also precal- thereby reducing the blocking ratio as shown in Fig. 2. How-
culates k-shortest paths but uses EF to assign the spectrum. ever, when the traffic load is high, the multi-path approach
The SP-FF method works like MP-EF but using single path does not compensate for the wasted bandwidth due to addi-
routing. Note that single path routing means that a connection tional guard-bands, even when using BF. Nevertheless, the
request cannot be split in different sub-lightpaths, in contrast blocking ratios for these high traffic loads are around 0.1,
to the MP methods. However, precalculated k-shortest paths and no network operator would be interested in operating the
are also used for route selection in SP-FF. SP-EF [43] works network with such poor performance. Therefore, if we focus
like SP-FF, but using EF as the spectrum assignment tech- on pragmatic scenarios, with a low blocking ratio (which
nique. Finally, SP-BF [20], [21] uses single path routing with corresponds to low to medium traffic loads), the combination
precalculated k-shortest paths, but using the BF technique of multipath routing with BF makes better use of the available
for spectrum allocation instead of FF. In all cases, the most spectrum to reduce the blocking ratio by more than one
efficient modulation format that ensures the fulfillment of order of magnitude, resulting in approximately 25% more
QoT requirements has been considered for each path. supported traffic compared to SP methods.
Unless otherwise stated, the six algorithms calculate
5 routes to determine the k-shortest paths (k = 5). Simulations
with other values of this parameter (k = 1, 3, 7) were also
analyzed leading to the same conclusions as the ones that will
be presented in the next subsections.

C. RESULTS
The six methods have been compared in terms of different
parameters: blocking ratio, energy consumption, and compu-
tation time. First of all, Fig. 2 shows the request blocking ratio
obtained when using the different methods. This parameter is
especially important for improving the perception of the final
users and it clearly affects the quality of experience (QoE)
and the operator reliability. For all the methods, the request
blocking ratio increases when the network load grows. As in
[20], [21], SP-BF obtains a similar request blocking ratio to
that achieved by SP-FF and SP-EF, in the same order of mag-
FIGURE 2. Request blocking ratio obtained by MP-BF, MP-EF,
nitude for all network loads. However, when comparing the MP-FF [68], [70], SP-BF [20], [21], SP-EF [43] and SP–FF [18] considering k
six methods, MP-BF clearly outperforms the other proposals. = 5 shortest paths.
For instance, for traffic loads around 0.4 the blocking ratio
for MP-BF is more than one order of magnitude lower than Next, Fig. 3 shows the request blocking ratio obtained
SP-based methods and more than three orders of magnitude with SP-FF and MP-BF (the best methods from the pre-
lower than MP-FF and MP-EF. This means that, if we set vious figure) for different values of k (1, 3 and 5). The
the maximum admissible request blocking ratio to 10−3 and figure shows that increasing the number of candidate paths
compare the performance of MP-BF with the SP methods reduces the request blocking ratio of both algorithms. How-
(which are the next best performing methods), when using ever, the reduction decreases as k increases. Comparing the
MP-BF, the network can support network loads of up to 0.5, performance of the two algorithms, the blocking ratio using
while it supports around 0.4 for SP methods (i.e., around 25% MP-BF is lower for all values of k.
more traffic with MP-BF). In order to check whether the improvement in performance
The use of multi-path routing has potential for establish- of MP-BF comes at a cost, we have evaluated three different
ing connections that otherwise would be blocked, by split- issues: the network energy consumption, the required num-
ting the demand in several sub-lightpaths, but this may lead ber of transponders and the computing time required by the
to higher spectrum fragmentation, and it also implies that different algorithms.
the wasted spectrum in guard-bands increases (given that Thus, we have first analyzed whether the increment in the
each sub-lightpath requires the addition of a guard-band). supported traffic translates into more energy consumption in
Therefore, these connections occupy more spectral resources, the network or not. As the dynamic EON in the study carries
which in turn negatively affect to future requests. Hence, there the traffic from the source to the destination node using
is a trade-off between these factors, and in some cases, like direct lightpaths (i.e., without Layer 2 and/or Layer 3 routing

111644 VOLUME 9, 2021

L. Ruiz et al.: Routing, Modulation and Spectrum Assignment Algorithm Using Multi-Path Routing and Best-Fit

loads except for traffic loads higher than 0.8 but, as we

have previously discussed, that is not a pragmatic scenario
as the blocking ratio is too high. Moreover, MP-BF outper-
forms MP-FF and MP-EF achieving an energy consumption
up to 36% lower than MP-EF and up to 33% lower than
MP-FF. Therefore, Fig. 2 and Fig. 4 show that the combi-
nation of multi-path routing with the BF approach for spec-
trum allocation significantly outperforms the combination
with FF.
Nevertheless, splitting the demanded traffic into several
sub-lightpaths, either routed over the same route or traveling
over different paths may lead to an increase of the complexity
of the network, since it may induce the utilization of more
transponders, as well as additional spectrum waste due to hav-
ing more guard-bands (one per sub-lightpath), as previously
FIGURE 3. Request blocking ratio obtained by of MP-BF and SP–FF [18] mentioned. In order to explore these issues in more detail,
for increasing values of k. we have first analyzed the average number of sub-lightpaths
required to serve the demand when using the multi-path
at intermediate nodes), only the energy consumption of the approaches.
optical layer has been considered. For that aim, the EON
energy model proposed by Lopez et al. [77] was imple-
mented in the EON simulator. It provides power consumption
models for transponders, optical cross connects (OXCs) and
optical amplifiers (in particular, erbium doped fiber ampli-
fiers, EDFAs), taking into account issues like modulation
formats, transmission rates, and the number of ports of the
OXCs. Using those models, the energy consumption per bit
when employing the six RMSA algorithms was computed.
Thus, Fig. 4 shows the energy efficiency in watt-hour per
bit (W·h/b) for different traffic loads and using the different
methods.

FIGURE 5. Average number of sub-connections required by MP-BF, MP-EF

and MP-FF [68], [70], considering k = 5 shortest paths.

As shown in Fig. 5, MP-FF and MP-EF split the traffic

demands into up to about 15 sub-connections for medium
traffic loads. In contrast, MP-BF uses fewer sub-connections
per request, splitting an average of up to 1.2 sub-lightpaths
for medium traffic loads. This behavior is due to the fact that
FF and EF assign the first available set of FSs (unless there is
a set of FSs that exactly matches the pending traffic, if EF is
used), hence leading to more splits compared to MP-BF and,
consequently, increasing the required guard-bands between
FIGURE 4. Energy efficiency of MP-BF, MP-EF, MP-FF [68], [70], connections. Contrarily, BF assigns either the smallest set of
SP-BF [20], [21], SP-EF [43] and SP–FF [18] considering k = 5 shortest available and contiguous FSs where the demand fits, or if
paths.
it does not fit in any set, it uses the largest available set of
FSs to partially serve the demand (line 21 in Algorithm 1),
As it can be seen in Fig. 4, the use of MP-BF, which thus reducing the number of required splits and the associated
is the most efficient method in terms of supported traffic number of guard-bands. In this manner, MP-BF makes a
(Fig. 2), does not translate in higher energy consumption better use of the spectrum and results in the reduction of the
in the network. The energy efficiency obtained using this request blocking ratio up to more than one order of magnitude
method is roughly equal to that of the SP methods for all compared to other techniques, as shown in Fig. 2, and in

VOLUME 9, 2021 111645

 L. Ruiz et al.: Routing, Modulation and Spectrum Assignment Algorithm Using Multi-Path Routing and Best-Fit

energy savings of up to 36% compared to other multi-path blocking ratio is slightly below 10−2 (around 8·10−3 ), while
techniques, as shown in Fig. 4. for MP-BF the blocking ratio is well below 10−3 (around
We now turn our attention to the impact on transpon- 4.5·10−4 ). Let us now consider that BVTs are used. When
ders. Split spectrum techniques involve generating multiple a low number of BVTs per node are used, the results in
optical flows (sub-lightpaths) starting from a single node. blocking ratio are similar for MP-BF and SP-FF (very slightly
From the transponder point of view, there are two main better for SP-FF, as shown in Fig. 6). However, the use of
approaches to support this, either using a different band- MP-BF provides the operator with an additional option to
width variable transponder (BVT) for each sub-lightpath upgrade the network to support traffic increases. For instance,
to be established or equipping each node with a sliceable let us assume that the aim is to operate the network so that the
bandwidth variable transponder (S-BVT). In the latter case, request blocking ratio is lower than 10−3 . As shown in Fig. 6,
a single transponder in each node is able to generate mul- when using 30 transponders with SP-FF or with MP-BF the
tiple sub-lightpaths, each using a different portion of the network can support a traffic load of around 0.4. If the traffic
optical spectrum, and which may be routed through different load increases to 0.5, the operator might opt for adding new
paths through the EON [52]. In summary, the use of split transponders per node (reaching 50 per node) together with
spectrum techniques involves using either a higher num- MP-BF to still have a blocking ratio below 10−3 . In contrast,
ber of transponders or a more complex architecture of the if SP-FF were used, the blocking ratio would exceed that
transponders. value (it would be around 8·10−3 ), and adding transponders
In order to analyze the impact of transponders in perfor- would not reduce the blocking ratio, so that the operator could
mance, Fig. 6 shows the blocking ratio of MP-BF and SP-FF, only opt for adding spectral resources (even if that were less
as a function of the maximum number of sub-lightpaths that cost effective). Thus MP-BF provides more flexibility to the
can start at a node. If the first approach is used (one BVT per operator when trading off the costs required to upgrade the
sub-lightpath), that number represents the number of BVTs network (increasing transponders or spectral resources) to
per node. If the second approach is used (a single S-BVT support higher future traffic loads.
per node), that number represents the maximum number of The complexity analysis of MP-BF has been shown in
sub-lightpaths that can be generated by the architecture of the Section III.B. The five baseline algorithms to which our pro-
S-BVTs employed in the network. posal is compared have an analogous structure, i.e., a ‘‘for’’
loop that is completed in a maximum of K cycles, a ‘‘for’’
loop to compute the available channels that is completed in
LS steps and a ‘‘while’’ loop with a ‘‘for’’ loop inside to
assign the available spectrum having the same worst-case sce-
nario. Therefore,


the complexity of those algorithms is also
O K S 2 + LS . However, this is the worst-case scenario,
and it could be reasonable to think that multi-path routing
and the use of BF approach could involve higher computing
time. For this reason, we have also analyzed the execu-
tion time of the algorithms. Fig. 7 shows the computational
times of the studied algorithms for different network loads.
MP-EF and MP-FF are the most computationally demanding
methods, as they split the demand in many low-bandwidth
sub-lightpaths. However, MP-BF presents the same compu-
tational time than SP-FF, SP-EF and SP-BF for low and
medium loads, since it efficiently splits the demands, showing
only up to 1.2 average splits per connection for medium
FIGURE 6. Request blocking ratio of MP-BF and SP-FF [18] as a function loads. Only for loads higher that 0.6 the computation time
of the maximum number of sub-lightpaths that can start at a node,
considering k = 5 shortest paths. for MP-BF significantly increases when compared with SP-
based algorithms, being up to 2.5 times higher than SP-EF,
We have considered different traffic loads (from 0.4 to 0.6) SP-FF and SP-BF for a load of 0.9, since it checks more sets
and the use of 5 shortest paths. For that simulation setup, of available FSs in different candidate paths until satisfying
the multipath technique brings advantages in terms of request the demanded traffic, if possible. Nevertheless, as previously
blocking ratio over the single path option when a node is able discussed, the network would not operate at those loads since
to be the source of around 30-40 sub-lightpaths. Therefore, the blocking ratio would be too high. In any case, the times
if S-BVT are used, and have potential to generate more required by the studied methods are below 200 ms (and below
than those sub-lightpaths, improvements on blocking proba- 20 ms for loads lower than 0.5), which is much less than the
bility higher than one order of magnitude can be achieved. time required to establish a lightpath.
For instance, if the S-BVT can be the source of 70 sub- Hence, MP-BF is the most efficient method. It achieves the
lightpaths, for SP-FF and a traffic load of 0.5, the request lowest blocking ratio, thus supporting a higher traffic load in

111646 VOLUME 9, 2021

L. Ruiz et al.: Routing, Modulation and Spectrum Assignment Algorithm Using Multi-Path Routing and Best-Fit

Future work includes extending the algorithm to support

constraints on the maximum differential delay between paths
and analyzing its performance and impact on fragmentation
of the spectrum in different topologies and service level
agreement schemes. The extension to a different environment
like space division multiplexing (SDM) elastic optical net-
works is also an interesting future research line.

REFERENCES
[1] A. Mayoral, R. Vilalta, R. Muñoz, R. Casellas, R. Martínez, and V. López,
‘‘Cascading of tenant SDN and cloud controllers for 5G network slicing
using transport API and openstack API,’’ in Proc. Opt. Fiber Commun.
Conf., Mar. 2017, pp. 1–3. [Online]. Available: https://www.osapublishing.
org/abstract.cfm?uri=OFC-2017-M2H.3
[2] B. Mukherjee, Optical WDM Networks. New York, NY, USA: Springer,
2006.
FIGURE 7. Computation times of MP-BF, MP-EF, MP-FF [68], [70], [3] K. Christodoulopoulos, I. Tomkos, and E. A. Varvarigos, ‘‘Routing and
SP-BF [20], [21], SP-EF [43] and SP–FF [18] considering k = 5 shortest spectrum allocation in OFDM-based optical networks with elastic band-
paths. width allocation,’’ in Proc. IEEE Global Telecommun. Conf. GLOBECOM,
Dec. 2010, pp. 1–6.
[4] K. Christodoulopoulos, I. Tomkos, and E. A. Varvarigos, ‘‘Elastic band-
the network (Fig. 2). This improvement in performance does width allocation in flexible OFDM-based optical networks,’’ J. Lightw.
not imply paying a cost in terms of energy efficiency in the Technol., vol. 29, no. 9, pp. 1354–1366, May 1, 2011, doi: 10.1109/
network (Fig. 4), nor in terms of computational time (Fig. 7). JLT.2011.2125777.
[5] I. Tomkos, S. Azodolmolky, J. Solé-Pareta, D. Careglio, and
This is because multi-path routing and best-fit techniques E. Palkopoulou, ‘‘A tutorial on the flexible optical networking paradigm:
complement each other really well, splitting the demand only State of the art, trends, and research challenges,’’ Proc. IEEE, vol. 102,
when it really brings advantages (Fig. 5), resulting in excel- no. 9, pp. 1317–1337, Sep. 2014, doi: 10.1109/JPROC.2014.2324652.
lent performance results. [6] M. Jinno, H. Takara, B. Kozicki, Y. Tsukishima, Y. Sone, and S. Matsuoka,
‘‘Spectrum-efficient and scalable elastic optical path network: Architec-
ture, benefits, and enabling technologies,’’ IEEE Commun. Mag., vol. 47,
V. CONCLUSION no. 11, pp. 66–73, Nov. 2009, doi: 10.1109/MCOM.2009.5307468.
In this paper, we have presented a comprehensive review of [7] B. C. Chatterjee, N. Sarma, and E. Oki, ‘‘Routing and spectrum allo-
cation in elastic optical networks: A tutorial,’’ IEEE Commun. Surveys
the main references in the area of RSA/RMSA problems, both Tuts., vol. 17, no. 3, pp. 1776–1800, 3rd Quart., 2015, doi: 10.1109/
in static and dynamic scenarios, for elastic optical networks. COMST.2015.2431731.
Then, we have proposed a new RMSA algorithm for dynamic [8] A. Klekamp and U. Gebhard, ‘‘Benefits for mixed-line-rate (MLR)
and elastic networks using flexible frequency grids,’’ in Proc. Eur.
scenarios called MP-BF. The novelty of the MP-BF algorithm Conf. Exhib. Opt. Commun., Sep. 2012, pp. 1–3. [Online]. Available:
relies on combining multi-path routing (which allows split- https://www.osapublishing.org/abstract.cfm?uri=ECEOC-2012-Mo.1.D.1
ting the demand and serving it by means of multiple sub- [9] X. Wan, N. Hua, and X. Zheng, ‘‘Dynamic routing and spectrum
assignment in spectrum-flexible transparent optical networks,’’ IEEE/OSA
lightpaths) with an efficient spectrum allocation technique, J. Opt. Commun. Netw., vol. 4, no. 8, pp. 603–613, Aug. 2012, doi:
best-fit (which assigns the set of available FSs that best fits 10.1364/JOCN.4.000603.
the traffic demand). Previous studies on the best-fit method [10] Y. Liu, N. Hua, X. Zheng, H. Zhang, and B. Zhou, ‘‘Discrete spectrum-scan
routing based on spectrum discretization in flexible optical networks,’’ in
had only analyzed its performance when combined with
Proc. Nat. Fiber Optic Eng. Conf., Mar. 2012, pp. 1–3.
single-path routing, and we have demonstrated that best-fit [11] R. J. Duran, I. Rodriguez, N. Fernandez, I. de Miguel, N. Merayo,
unveils its potential when combined with a split spectrum P. Fernandez, J. C. Aguado, T. Jimenez, R. M. Lorenzo, and E. J. Abril,
approach. ‘‘Performance comparison of methods to solve the routing and spectrum
allocation problem,’’ in Proc. 14th Int. Conf. Transparent Opt. Netw.
The performance of MP-BF has been compared with that (ICTON), Jul. 2012, pp. 1–4.
of five efficient RMSA algorithms proposed in the literature. [12] M. Klinkowski and K. Walkowiak, ‘‘Routing and spectrum assign-
The results of this comparison clearly show that the use of ment in spectrum sliced elastic optical path network,’’ IEEE Commun.
Lett., vol. 15, no. 8, pp. 884–886, Aug. 2011, doi: 10.1109/LCOMM.
MP-BF in an EON allows to decrease the blocking ratio more 2011.060811.110281.
than one order of magnitude without increasing the network [13] L. Ruan and N. Xiao, ‘‘Survivable multipath routing and spectrum allo-
energy consumption or the computation time. In particular, cation in OFDM-based flexible optical networks,’’ J. Opt. Commun.
Netw., vol. 5, no. 3, pp. 172–182, Mar. 2013, doi: 10.1364/JOCN.5.
MP-BF exploits the advantages of splitting the demands of 000172.
multi-path routing, but it reduces the average number of splits [14] X. Chen, Y. Zhong, and A. Jukan, ‘‘Multipath routing in elastic optical
needed when compared with other multi-path approaches. networks with distance-adaptive modulation formats,’’ in Proc. IEEE Int.
Conf. Commun. (ICC), Jun. 2013, pp. 3915–3920.
Therefore, EONs can carry 25% more traffic when MP-BF
[15] A. Pagès, J. Perelló, S. Spadaro, and G. Junyent, ‘‘Split spectrum-enabled
is used for solving the RMSA problem instead of using other route and spectrum assignment in elastic optical networks,’’ Opt. Switching
previous proposals from the literature. Moreover, the efficient Netw., vol. 13, pp. 148–157, Jul. 2014, doi: 10.1016/j.osn.2014.04.002.
splitting of the demands also translates into energy savings [16] B. Kozicki, H. Takara, Y. Sone, A. Watanabe, and M. Jinno, ‘‘Distance-
adaptive spectrum allocation in elastic optical path network (SLICE)
of up to 36% when compared with the other multi-path with bit per symbol adjustment,’’ in Proc. Opt. Fiber Commun. Conf.,
strategies. Mar. 2010, pp. 1–3.

VOLUME 9, 2021 111647

 L. Ruiz et al.: Routing, Modulation and Spectrum Assignment Algorithm Using Multi-Path Routing and Best-Fit

[17] J. Yuan, Z. Ren, R. Zhu, Q. Zhang, X. Li, and Y. Fu, ‘‘A RMSA algorithm [36] A. Agrawal, V. Bhatia, and S. Prakash, ‘‘Spectrum efficient distance-
for elastic optical network with a tradeoff between consumed resources adaptive paths for fixed and fixed-alternate routing in elastic optical net-
and distance to boundary,’’ Opt. Fiber Technol., vol. 46, pp. 238–247, works,’’ Opt. Fiber Technol., vol. 40, pp. 36–45, Jan. 2018, doi: 10.1016/
Dec. 2018, doi: 10.1016/j.yofte.2018.10.020. j.yofte.2017.11.001.
[18] M. Jinno, M. Jinno, B. Kozicki, H. Takara, A. Watanabe, Y. Sone, [37] T. Ahmed, S. Rahman, S. Ferdousi, M. Tornatore, A. Mitra,
T. Tanaka, and A. Hirano, ‘‘Distance-adaptive spectrum resource allo- B. C. Chatterjee, and B. Mukherjee, ‘‘Dynamic routing, spectrum,
cation in spectrum-sliced elastic optical path network [topics in optical and modulation-format allocation in mixed-grid optical networks,’’
communications],’’ IEEE Commun. Mag., vol. 48, no. 8, pp. 138–145, J. Opt. Commun. Netw., vol. 12, no. 5, pp. 79–88, 2020, doi: 10.1364/
Aug. 2010, doi: 10.1109/MCOM.2010.5534599. JOCN.378370.
[19] L. Ruiz, I. Gonzalez, R. J. Duran, I. D. Miguel, N. Merayo, J. C. Aguado, [38] F. I. Calderon, A. Lozada, D. Borquez-Paredes, R. Olivares, E. J. Davalos,
P. Fernandez, R. M. Lorenzo, and E. J. Abril, ‘‘Comparing differ- G. Saavedra, N. Jara, and A. Leiva, ‘‘BER-adaptive RMLSA algo-
ent types of flexibility when solving the RSA problem in EONs,’’ rithm for wide-area flexible optical networks,’’ IEEE Access, vol. 8,
in Proc. Int. Conf. Comput. Sci. Comput. Intell. (CSCI), Dec. 2017, pp. 128018–128031, 2020, doi: 10.1109/ACCESS.2020.3008883.
pp. 1356–1359. [39] A. Alyatama, I. Alrashed, and A. Alhusaini, ‘‘Adaptive routing and spec-
[20] R. A. Cortes, A. L. Lopez, F. A. Villalobos, S. F. Massmann, and trum allocation in elastic optical networks,’’ Opt. Switching Netw., vol. 24,
G. F. Castro, ‘‘Spectrum allocation algorithms for elastic DWDM net- pp. 12–20, Apr. 2017, doi: 10.1016/j.osn.2016.10.001.
works on dynamic operation,’’ IEEE Latin Amer. Trans., vol. 12, no. 6, [40] N. Sambo, F. Cugini, G. Bottari, P. Iovanna, and P. Castoldi, ‘‘Dis-
pp. 1012–1018, Sep. 2014, doi: 10.1109/TLA.2014.6893994. tributed setup in optical networks with flexible grid,’’ in Proc.
[21] F. S. Abkenar, A. Ghaffarpour Rahbar, and A. Ebrahimzadeh, ‘‘Best fit 37th Eur. Conf. Expo. Opt. Commun., Sep. 2011, pp. 1–3. [Online].
(BF): A new spectrum allocation mechanism in elastic optical networks Available: https://www.osapublishing.org/abstract.cfm?uri=ECOC-2011-
(EONs),’’ in Proc. 8th Int. Symp. Telecommun. (IST), Sep. 2016, pp. 24–29, We.10.P1.100
doi: 10.1109/istel.2016.7881775. [41] J. Yuan, R. Zhu, Y. Zhao, Q. Zhang, X. Li, D. Zhang, and A. Samuel,
[22] Y. Wang, X. Cao, and Q. Hu, ‘‘Routing and spectrum allocation in ‘‘A spectrum assignment algorithm in elastic optical network with min-
spectrum-sliced elastic optical path networks,’’ in Proc. IEEE Int. Conf. imum sum of weighted resource reductions in all associated paths,’’
Commun. (ICC), Jun. 2011, pp. 1–5. J. Lightw. Technol., vol. 37, no. 21, pp. 5583–5592, Nov. 1, 2019.
[23] A. Cai, G. Shen, L. Peng, and M. Zukerman, ‘‘Novel node-arc model and [42] T. Takagi, H. Hasegawa, K. Sato, Y. Sone, B. Kozicki, A. Hirano, and
multiiteration heuristics for static routing and spectrum assignment in elas- M. Jinno, ‘‘Dynamic routing and frequency slot assignment for elastic
tic optical networks,’’ J. Lightw. Technol., vol. 31, no. 21, pp. 3402–3413, optical path networks that adopt distance adaptive modulation,’’ in Proc.
Nov. 1, 2013, doi: 10.1109/JLT.2013.2282696. Opt. Fiber Commun. Conf./National Fiber Optic Eng. Conf., 2011, pp. 1–3.
[24] Y. Miyagawa, Y. Watanabe, M. Shigeno, K. Ishii, A. Takefusa, and [43] A. Rosa, C. Cavdar, S. Carvalho, J. Costa, and L. Wosinska, ‘‘Spectrum
A. Yoshise, ‘‘Bounds for two static optimization problems on routing allocation policy modeling for elastic optical networks,’’ in Proc. High
and spectrum allocation of anycasting,’’ Opt. Switching Netw., vol. 31, Capacity Opt. Netw. Emerg./Enabling Technol., Dec. 2012, pp. 242–246,
pp. 144–161, Jan. 2019, doi: 10.1016/j.osn.2018.10.008. doi: 10.1109/HONET.2012.6421472.
[25] L. Gong, X. Zhou, X. Liu, W. Zhao, W. Lu, and Z. Zhu, ‘‘Efficient resource [44] R. Wang and B. Mukherjee, ‘‘Spectrum management in heterogeneous
allocation for all-optical multicasting over spectrum-sliced elastic optical bandwidth optical networks,’’ Opt. Switching Netw., vol. 11, pp. 83–91,
networks,’’ J. Opt. Commun. Netw., vol. 5, no. 8, p. 836, Aug. 2013, doi: Jan. 2014, doi: 10.1016/j.osn.2013.09.003.
10.1364/JOCN.5.000836. [45] W. Fadini and E. Oki, ‘‘A subcarrier-slot partition scheme for wave-
[26] R. Gošcień, K. Walkowiak, and M. Klinkowski, ‘‘Tabu search algorithm length assignment in elastic optical networks,’’ in Proc. IEEE 15th Int.
for routing, modulation and spectrum allocation in elastic optical network Conf. High Perform. Switching Routing (HPSR), Jul. 2014, pp. 7–12, doi:
with anycast and unicast traffic,’’ Comput. Netw., vol. 79, pp. 148–165, 10.1109/HPSR.2014.6900874.
Mar. 2015, doi: 10.1016/j.comnet.2014.12.004. [46] L. Li and H.-J. Li, ‘‘Performance analysis of novel routing and spec-
[27] J. Zhao, H. Wymeersch, and E. Agrell, ‘‘Nonlinear impairment-aware trum allocation algorithm in elastic optical networks,’’ Optik, vol. 212,
static resource allocation in elastic optical networks,’’ J. Lightw. Tech- Jun. 2020, Art. no. 164688, doi: 10.1016/j.ijleo.2020.164688.
nol., vol. 33, no. 22, pp. 4554–4564, Nov. 15, 2015, doi: 10.1109/ [47] B. C. Chatterjee, W. Fadini, and E. Oki, ‘‘A spectrum allocation
JLT.2015.2474130. scheme based on first–last-exact fit policy for elastic optical networks,’’
[28] S. Behera, A. Deb, G. Das, and B. Mukherjee, ‘‘Impairment aware routing, J. Netw. Comput. Appl., vol. 68, pp. 164–172, Jun. 2016, doi: 10.1016/
bit loading, and spectrum allocation in elastic optical networks,’’ J. Lightw. j.jnca.2016.02.020.
Technol., vol. 37, no. 13, pp. 3009–3020, Jul. 1, 2019. [48] Y. Zhang, X. Zheng, Q. Li, N. Hua, Y. Li, and H. Zhang, ‘‘Traffic
[29] Y. Wang, X. Cao, and Y. Pan, ‘‘A study of the routing and spectrum grooming in spectrum-elastic optical path networks,’’ in Proc. Opt. Fiber
allocation in spectrum-sliced elastic optical path networks,’’ in Proc. IEEE Commun. Conf./Nat. Fiber Optic Eng. Conf., Mar. 2011, pp. 1–3, doi:
INFOCOM, Apr. 2011, pp. 1503–1511. 10.1364/OFC.2011.OTuI1.
[30] X. Yu, Y. Zhao, J. Zhang, B. Mukherjee, J. Zhang, and X. Wang, ‘‘Static [49] S. Miladić-Tešić, G. Marković, and V. Radojičić, ‘‘Traffic grooming tech-
routing and spectrum assignment in co-existing fixed/flex grid optical nique for elastic optical networks: A survey,’’ Optik, vol. 176, pp. 464–475,
networks,’’ in Proc. OFC, San Francisco, CA, USA, Mar. 2014, pp. 1–3, Jan. 2019, doi: 10.1016/j.ijleo.2018.09.068.
doi: 10.1364/OFC.2014.W2A.59. [50] G. Zhang, M. De Leenheer, and B. Mukherjee, ‘‘Optical traffic grooming in
[31] M. Salani, C. Rottondi, and M. Tornatore, ‘‘Routing and spectrum assign- OFDM-based elastic optical networks [Invited],’’ J. Opt. Commun. Netw.,
ment integrating machine-learning-based QoT estimation in elastic optical vol. 4, no. 11, p. B17, Nov. 2012, doi: 10.1364/JOCN.4.000B17.
networks,’’ in Proc. IEEE INFOCOM Conf. Comput. Commun., Apr. 2019, [51] K.-I. Sato, ‘‘Recent developments in and challenges of elastic opti-
pp. 1738–1746. cal path networking,’’ in Proc. 37th Eur. Conf. Expo. Opt. Com-
[32] A. Leiva, N. Pavez, A. Beghelli, and R. Olivares, ‘‘A joint RSA algorithm mun., Sep. 2011, pp. 1–3. [Online]. Available: https://www.osapublishing.
for dynamic flexible optical networking,’’ IEEE Latin Amer. Trans., vol. 13, org/abstract.cfm?uri=ECOC-2011-Mo.2.K.1
no. 11, pp. 3531–3537, Nov. 2015, doi: 10.1109/TLA.2015.7387926. [52] N. Sambo, P. Castoldi, A. D’Errico, E. Riccardi, A. Pagano,
[33] J. Velinska, I. Mishkovski, and M. Mirchev, ‘‘Routing, modulation and M. S. Moreolo, J. M. Fabrega, D. Rafique, A. Napoli, S. Frigerio, and
spectrum allocation in elastic optical networks,’’ in Proc. 26th Telecom- E. H. Salas, ‘‘Next generation sliceable bandwidth variable transponders,’’
mun. Forum (TELFOR), Nov. 2018, pp. 1–4. IEEE Commun. Mag., vol. 53, no. 2, pp. 163–171, Feb. 2015, doi:
[34] D. Bisbal, I. D. Miguel, F. González, J. Blas, J. C. Aguado, P. Fernández, 10.1109/MCOM.2015.7045405.
J. Durán, R. Durán, R. M. Lorenzo, E. J. Abril, and M. López, ‘‘Dynamic [53] O. Gerstel, ‘‘Flexible use of spectrum and photonic grooming,’’ in Integr.
routing and wavelength assignment in optical networks by means of Photon. Res., Silicon Nanophoton. Photon. Switching, OSA Tech. Dig.
genetic algorithms,’’ Photonic Netw. Commun., vol. 7, no. 1, pp. 43–58, (CD). Optical Society of America, 2010, Paper PMD3.
2004, doi: 10.1023/A:1027401202391. [54] P. S. Khodashenas, J. Comellas, S. Spadaro, and J. Perelló, ‘‘Dynamic
[35] A. Alyatama, ‘‘Relative cost routing and spectrum allocation in elastic source aggregation of subwavelength connections in elastic optical net-
optical networks,’’ J. Opt. Commun. Netw., vol. 12, no. 3, pp. 38–49, 2020, works,’’ Photonic Netw. Commun., vol. 26, nos. 2–3, pp. 131–139,
doi: 10.1364/JOCN.379585. Dec. 2013, doi: 10.1007/s11107-013-0415-1.

111648 VOLUME 9, 2021

L. Ruiz et al.: Routing, Modulation and Spectrum Assignment Algorithm Using Multi-Path Routing and Best-Fit

[55] R. Zhu, S. Li, P. Wang, M. Xu, and S. Yu, ‘‘Energy-efficient deep reinforced [74] Z. Zhang, S. Yin, S. Guo, Z. Lin, Y. Chen, and S. Huang, ‘‘Dynamic buffer-
traffic grooming in elastic optical networks for cloud–fog computing,’’ ing cost-saving multi-path routing under differential delay constraint in
IEEE Internet Things J., vol. 8, no. 15, pp. 12410–12421, Aug. 2021, doi: EONs,’’ in Proc. Asia Commun. Photon. Conf. (ACP), Oct. 2018, pp. 1–3,
10.1109/JIOT.2021.3063471. doi: 10.1109/ACP.2018.8596067.
[56] S. Hosseini, A. G. Rahbar, and M. Jafari-Beyrami, ‘‘Survivable time-aware [75] OMNeT++. Discrete Event Simulator. Accessed: Apr. 1, 2021. [Online].
traffic grooming in spatial division multiplexing elastic optical networks Available: https://omnetpp.org
with minimized crosstalk,’’ Comput. Electr. Eng., vol. 83, May 2020, [76] S. Ghose, R. Kumar, N. Banerjee, and R. Datta, ‘‘Multihop virtual topology
Art. no. 106579, doi: 10.1016/j.compeleceng.2020.106579. design in WDM optical networks for self-similar traffic,’’ Photonic Netw.
[57] B. C. Chatterjee, S. Ba, and E. Oki, ‘‘Fragmentation problems and man- Commun., vol. 10, no. 2, pp. 199–214, Sep. 2005, doi: 10.1007/s11107-
agement approaches in elastic optical networks: A survey,’’ IEEE Com- 005-2484-2.
mun. Surveys Tuts., vol. 20, no. 1, pp. 183–210, 1st Quart., 2018, doi: [77] J. López, Y. Ye, V. López, F. Jiménez, R. Duque, and P. M. Krummrich,
10.1109/COMST.2017.2769102. ‘‘On the energy efficiency of survivable optical transport networks with
[58] X. Wang, I. Kim, Q. Zhang, P. Palacharla, and M. Sekiya, ‘‘A hitless defrag- flexible-grid,’’ in Proc. Eur. Conf. Exhib. Opt. Commun., Sep. 2012,
mentation method for self-optimizing flexible grid optical networks,’’ in pp. 1–3. [Online]. Available: https://www.osapublishing.org/abstract.
Proc. Eur. Conf. Exhib. Opt. Commun., Sep. 2012, pp. 1–3. cfm?URI=ECEOC-2012-P5.05
[59] F. Cugini, F. Paolucci, G. Meloni, G. Berrettini, M. Secondini, F. Fresi,
N. Sambo, L. Poti, and P. Castoldi, ‘‘Push-pull defragmentation without
traffic disruption in flexible grid optical networks,’’ J. Lightw. Technol.,
vol. 31, no. 1, pp. 125–133, Jan. 1, 2013, doi: 10.1109/JLT.2012.2225600.
[60] T. Takagi, H. Hasegawa, K.-I. Sato, Y. Sone, A. Hirano, and M. Jinno, LIDIA RUIZ received the degree in telecommu-
‘‘Disruption minimized spectrum defragmentation in elastic optical nication engineering, the M.Res. degree in infor-
path networks that adopt distance adaptive modulation,’’ in Proc. mation and telecommunication technologies, and
37th Eur. Conf. Expo. Opt. Commun., Sep. 2011, pp. 1–3, doi: the Ph.D. degree from the University of Valladolid,
10.1364/ECOC.2011.Mo.2.K.3. Spain, in 2013, 2015, and 2020, respectively.
[61] E. J. Davalos, M. F. Romero, S. M. Galeano, D. A. Baez, A. Leiva, She has been a Visiting Researcher with the
and B. Baran, ‘‘Spectrum defragmentation in elastic optical net- Politecnico di Milano, Italy, and has worked as a
works: Two approaches with metaheuristics,’’ IEEE Access, vol. 7, IT Consultant. She is currently working as a Post-
pp. 119835–119843, 2019, doi: 10.1109/ACCESS.2019.2937032. doctoral Researcher. Her research interests include
[62] P. M. Moura, R. A. Scaraficci, and N. L. S. da Fonseca, ‘‘Algorithm for 5G, network function virtualization, virtual topol-
energy efficient routing, modulation and spectrum assignment,’’ in Proc. ogy design in WRON networks, and the design of RSA algorithms in flexible
IEEE Int. Conf. Commun. (ICC), Jun. 2015, pp. 5961–5966. optical networks.
[63] H. Waldman, R. C. Almeida, R. C. Bortoletto, and K. D. R. Assis, ‘‘Dead-
lock avoidance under incremental traffic in the elastic single link,’’ in Proc.
16th Int. Conf. Transparent Opt. Netw. (ICTON), Jul. 2014, pp. 1–4.
[64] Y. Qiu, Z. Fan, and C.-K. Chan, ‘‘Efficient routing and spectrum
assignment in elastic optical networks with time scheduled traffic,’’ RAMÓN J. DURÁN BARROSO received the
Opt. Fiber Technol., vol. 30, pp. 116–124, Jul. 2016, doi: 10.1016/ degree in telecommunication engineering and the
j.yofte.2016.04.011. Ph.D. degree from the University of Valladolid,
[65] J. Yuan, D. Zhang, Q. Zhang, X. Li, and Z. Ren, ‘‘A routing and spectrum Spain, in 2002 and 2008, respectively. He cur-
assignment algorithm in elastic optical network based on minimizing rently works as an Associate Professor with the
contiguity reduction,’’ Photonic Netw. Commun., vol. 38, no. 1, pp. 51–61, University of Valladolid. He is also the Coor-
Aug. 2019, doi: 10.1007/s11107-019-00851-1. dinator of the Spanish Research Thematic Net-
[66] D. Adhikari, D. Datta, and R. Datta, ‘‘Impact of BER in fragmentation- work ‘‘Go2Edge: Engineering Future Secure Edge
aware routing and spectrum assignment in elastic optical networks,’’ Computing Networks, Systems and Services’’
Comput. Netw., vol. 172, May 2020, Art. no. 107167, doi: 10.1016/j. composed of 15 entities and the H2020 IoTalentum
comnet.2020.107167. Project. He has authored more than 100 papers in international journals
[67] Y. Liu, R. He, S. Wang, and C. Yu, ‘‘Temporal and spectral 2D and conferences. His current research interests include the use of artificial
fragmentation-aware RMSA algorithm for advance reservation requests intelligence techniques for the design, optimization, and operation of future
in EONs,’’ IEEE Access, vol. 9, pp. 32845–32856, 2021, doi: 10.1109/
heterogeneous networks, multi-access edge computing, and network func-
ACCESS.2021.3060375.
tion virtualization.
[68] Z. Zhu, W. Lu, L. Zhang, and N. Ansari, ‘‘Dynamic service provisioning in
elastic optical networks with hybrid single-/multi-path routing,’’ J. Lightw.
Technol., vol. 31, pp. 15–22, Jan. 1, 2013, doi: 10.1109/JLT.2012.2227683.
[69] R. J. Zhu, Y. Zhao, H. Yang, X. Yu, J. Zhang, A. Yousefpour, N. Wang, and
J. P. Jue, ‘‘Dynamic time and spectrum fragmentation-aware service pro- IGNACIO DE MIGUEL (Senior Member, IEEE)
visioning in elastic optical networks with multi-path routing,’’ Opt. Fiber received the degree in telecommunication engi-
Technol., vol. 32, pp. 13–22, Dec. 2016, doi: 10.1016/j.yofte.2016.08.009. neering and the Ph.D. degree from the Universidad
[70] F. Yousefi, A. Ghaffarpour Rahbar, and M. Yaghubi-Namaad, de Valladolid (UVa), Spain, in 1997 and 2002,
‘‘Fragmentation-aware algorithms for multipath routing and spectrum respectively. Since 1997, he has worked as a Lec-
assignment in elastic optical networks,’’ Opt. Fiber Technol., vol. 53, turer at UVa, and is currently an Associate Pro-
Dec. 2019, Art. no. 102019, doi: 10.1016/j.yofte.2019.102019.
fessor. He is also the Coordinator of the master’s
[71] A. Pagès, J. Perelló, S. Spadaro, and J. Comellas, ‘‘Optimal route, spec-
degree in telecommunication engineering and the
trum, and modulation level assignment in split-spectrum-enabled dynamic
master’s degree in big data science at UVa. He has
elastic optical networks,’’ J. Opt. Commun. Netw., vol. 6, no. 2, p. 114,
Feb. 2014, doi: 10.1364/JOCN.6.000114. also been a Visiting Research Fellow at University
[72] W. Lu, X. Zhou, L. Gong, M. Zhang, and Z. Zhu, ‘‘Dynamic multi-path College London, U.K. His main research interests include the design, control
service provisioning under differential delay constraint in elastic optical and performance evaluation of optical networks, edge computing, and the
networks,’’ IEEE Commun. Lett., vol. 17, no. 1, pp. 158–161, Jan. 2013, application of artificial intelligence techniques in those environments. He has
doi: 10.1109/LCOMM.2012.120612.121343. been a member of the TPC of several international conferences, besides
[73] X. Chen, A. Jukan, and A. Gumaste, ‘‘Optimized parallel transmission being the Chair of the TPC and the Local Organizing Committee of NOC
in elastic optical networks to support high-speed Ethernet,’’ J. Lightw. 2009. He was a recipient of the Nortel Networks Prize to the Best Ph.D.
Technol., vol. 32, no. 2, pp. 228–238, Jan. 2014, doi: 10.1109/JLT. Thesis on Optical Internet in 2002, awarded by the Spanish Institute and the
2013.2291318. Association of Telecommunication Engineers (COIT/AEIT).

VOLUME 9, 2021 111649

 L. Ruiz et al.: Routing, Modulation and Spectrum Assignment Algorithm Using Multi-Path Routing and Best-Fit

NOEMÍ MERAYO received the degree in EVARISTO J. ABRIL received the degree in
telecommunication engineering from Valladolid telecommunication engineering and the Ph.D.
University, Spain, in February 2004, and the Ph.D. degree from the Universidad Politécnica de
degree from the Optical Communication Group, Madrid, Spain, in 1985 and 1987, respectively.
Universidad de Valladolid, in July 2009. Since From 1984 to 1986, he was a Research Assistant
2005, she has been working as a Lecturer with the with the Universidad Politécnica de Madrid and
Universidad de Valladolid. She has also been a Vis- became a Lecturer in 1987. Since 1995, he has
iting Research Fellow with the Optical Networks been a Full Professor with the Universidad de
Group, Science and Technology Research Institute Valladolid, Spain, where he founded the Opti-
(STRI), University of Hertfordshire, another at cal Communications Group. His research interests
the TOyBA Research Group, University of Zaragoza, and more recently include integrated optics, optical communication systems, and optical net-
at the Technical University of Munich (TUM). She is currently coordinating works. He has authored more than 100 papers in international journals and
the master’s degree in physics and technology of lasers at the University of conferences.
Valladolid and the University of Salamanca. Her research interests include
the design and performance evaluation of optical networks, especially pas-
sive optical networks and the application of artificial intelligence techniques.

JUAN CARLOS AGUADO received the degree

in telecommunication engineering and the Ph.D.
degree from the University of Valladolid, Spain,
in 1997 and 2005, respectively. Since 1998, he has
been working as a Junior Lecturer with the Uni-
versity of Valladolid, where he is currently an
Associate Professor. He has also been a Postdoc-
toral Researcher with the Group of Transmisiones
Ópticas de Banda Ancha (TOyBA), University of
Zaragoza. His current research interests include
design and performance evaluation of optical networks and the application
of artificial intelligence techniques.

111650 VOLUME 9, 2021