GC'12 Workshop: Flexible Optical Networks

A Naturally-Inspired Algorithm for Routing,

Wavelength Assignment, and Spectrum Allocation
in Flexible Grid WDM Networks
Ankitkumar N. Patel1 , Philip N. Ji1 , Jason P. Jue2 , and Ting Wang1
1
NEC Laboratories America, Inc., Princeton, NJ 08540
2
The University of Texas at Dallas, Richardson, TX 75080
Email: apatel@[Link], pji@[Link], jjue@[Link], ting@[Link],
Abstract—Flexible grid networks enable elastic bandwidth In flexible grid networks, the constraint of fixed spectrum
transmission with higher spectral efficiency. In this paper, we allocation to channels is relaxed and variable amount of
address the Routing, Wavelength assignment, and Spectrum Al- spectral spacing can be allocated. Such systems are referred
location (RWSA) problem in flexible grid networks with the goal
of maximizing spectral efficiency. We design a novel algorithm to as Spectrum sLICed elastic optical (SLICE) networks [3]
using a hybrid application of naturally-inspired procedures such or Flexible optical WDM (FWDM) networks [4]. Line rates
as genetic evolution and simulated annealing. The performance of any granularity can be supported by allocating optimum
of the proposed sequential meta-heuristic algorithm is evaluated amount of spectrum based on a network condition such as an
with existing solutions and a lower bound. Simulation results availability of network resources, physical layer impairments,
demonstrate that the proposed algorithm outperforms the ex-
isting solutions and performs very close to the lower bound. and a channel condition such as the required bandwidth, oper-
Furthermore, the algorithm converges to the optimization in a ating modulation formats. Furthermore, the assigned spectrum
limited number of evolution and annealing iterations. can be dynamically adapted to support time-varying traffic
demands. Such functionalities can be offered by rate-adaptive
I. I NTRODUCTION transponders [5] and spectrum-variable ROADM nodes [6].
Optical networking technologies have dramatically evolved Flexible grid networks can reduce the gap between end-to-
to support the exponential growth of emerging multimedia end traffic demands and offered channel capacity, and thus,
services. Simple on-off modulation scheme that is used for offers scalable, flexible, and transparent transmission system
10 Gb/s transmission is being replaced by more sophisticated leading to higher spectral and energy efficiencies [4]. However,
advanced modulation schemes to support 40 Gb/s, 100 Gb/s, such systems impose new control and management challenges
and even higher line rates. To mitigate chromatic dispersion due to the flexibility in spectrum assignment. One such
and polarization mode dispersion, digital coherent detection challenge is how to establish lightpaths. While establishing
schemes have been investigated, which extend optical reach a lightpath in flexible grid networks, challenges such as how
and enable high bit-rate transparent-transport architectures. to route these lightpaths over the physical network, how to
Additionally, to densely pack more WDM channels, 100 GHz assign wavelengths to lightpaths, and how to allocate spectrum
of spectral grid was reduced to 50 GHz. However, the spectral to lightpaths need to be addressed by the control plane. We
utilization of current fixed-grid WDM systems is still not refer to this problem as the routing, wavelength assignment,
optimized to support traffic with heterogeneous granularity. and spectrum allocation (RWSA) problem in flexible grid
An assignment of an entire wavelength to sub-wavelength networks [4]. While establishing lightpaths, the control plane
granularity traffic results in a stranded channel leading to must observe additional spectral continuity and spectral con-
inefficient channel capacity utilization. On the other hand, an flict constraints in flexible grid networks in addition to the
assignment of multiple channels to support super-wavelength conventional wavelength continuity constraint as in fixed grid
granularity traffic requires an allocation of guard bands to networks, and thus, the conventional routing and wavelength
avoid inter-channel interference, and the spectrum allocated to assignment solutions for establishing lightpaths are no longer
such guard bands can no longer be used for data transmission. applicable to the RWSA problem in flexible grid networks.
Furthermore, following the recent commercialization of 100 Recently, several numerical and algorithmic solutions are
Gb/s transmission systems over 50 GHz of fixed grid, network investigated for the RWSA problem. In [4] and [7], node-
operators are now focusing on supporting 400 Gb/s and 1 Tb/s link based mathematical formulations are proposed for the
line rates. Unfortunately, the spectral requirements of 400 Gb/s RWSA problem using an Integer Linear Programming. To
(75 GHz [1])and 1 Tb/s (150 GHz [2]) line rates are beyond 50 reduce the computation time, in [7], [8], [9], and [10], path-
GHz, and such higher linerates may not be supported within link based formulations are proposed for the same problem;
currently standardized fixed grid networks. On the other hand, however, these formulations may not result optimal solutions
if the fixed grid is readjusted to support higher line rates, then if a limited number of paths is considered. In [3], a heuristic is
spectrum utilization of lower line rates, such as 10 Gb/s (25 proposed using the fixed-alternate routing and first-fit spectrum
GHz), may not be optimized. Thus, no single fixed channel allocation procedures, which considers different modulation
grid can optimize spectral efficiency of WDM networks. formats based on the transmission-reach of lightpaths. In [8],

978-1-4673-4941-3/12/$31.00 ©2012 IEEE 340

  &KDQQHOVSDFLQJIL[HG
*+] *+]
in terms of guard bands, leading to higher spectral efficiency.
« (2) Optimization of spectral efficiency while maintaining
Quality of Transmission (QoT): Spectral efficiency of the

*EV

*EV
*EV

*EV

*EV

*EV
*EV
D
network can be optimized with an application of spectrum-
)UHTXHQF\
)UHTXHQF\
efficient modulation formats that can meet the required end-
&HQWHUIUHTXHQF\,787IL[HGFKDQQHOJULGV )L[HG *ULG 1HWZRUN
to-end QoT. Furthermore, inter-channel spacing (guard bands)
needs to be optimized based on the number of switching nodes
&KDQQHOVSDFLQJIOH[LEOH
*+] *+] *+]
along the route and the modulation formats of neighboring
«
*EV
channels to overcome the cascaded filtering effects and inter-

*EV

*EV
channel nonlinear effects while maintaining certain level of
*EV

*EV

*EV

*EV
*EV

)UHTXHQF\
QoT at destination nodes. (3) Close mapping between client
)UHTXHQF\
and transport layer traffic: Channel establishment at the
&HQWHUIUHTXHQF\QRWIL[HGRQ,787IL[HGFKDQQHOJULGV ):'0 client layer traffic eliminates the necessity of opto-electronic
Fig. 1. Fixed Grid vs. Flexible Grid Networks
conversion during traffic aggregation of subwavelength layer
a similar Routing, Modulation Level, and Spectrum Allocation traffic and an allocation of guard bands to support super-
(RMLSA) algorithm is proposed. To improve spectral utiliza- wavelength layer traffic. Thus, higher energy and spectral
tion, the Maximize Common Large Segment (MCLS) heuristic efficiencies can be achieved.
is proposed in [11] that adaptively routes and allocates the There is a need for innovations in both the data plane and
spectrum such that consecutiveness of available spectrum is the control plane for the development of flexible grid networks.
maximized in order to improve provisionable path capacity of In the data plane, the key network elements are (1) rate-
networks. In [9], to minimize the maximum required spectrum variable transponders and (2) spectrum-variable ROADMs.
in networks, the Balanced Load Spectrum Allocation (BLSA) The rate-variable transponder can be realized by single-carrier
algorithm is designed that routes connections while balancing modulation schemes with switchable modulation stages and/or
load in a network. variable rate data multiplexer. Such technology can adjust
In this paper, we propose a novel algorithm, namely se- transmission rate and reach of the channel within the same
quential meta-heuristic, using a hybrid application of naturally- spectral width using different modulation formats. Alterna-
inspired procedures, such as Genetic Evolution and Simulated tively, the rate-variable transponder can also be realized using
Annealing. The performance of the proposed solution is eval- multicarrier modulation scheme with variable subcarrier as-
uated with existing solutions and a baseline algorithm that signment in which transmission rate and spectral assignment
adopts shortest path routing and first-fit spectrum allocation can be adapted for the same transmission reach. Multicarrier
procedures. To estimate the accuracy, the sequential meta- modulation scheme with switchable modulation stages leads
heuristic algorithm is also evaluated with a lower bound. to a more generalized architecture enabling adaptiveness in
The rest of the paper is organized as follow. In Section both spectral assignment and transmission reach along with
II, we provide an overview of flexible grid networks. Section transmission rate simultaneously at the price of higher cost.
III introduces the RWSA problem in flexible grid networks. The spectrum-variable ROADM node should be capable of
The Sequential meta-heuristic heuristic is proposed in Section switching channels with almost arbitrary size of channel
IV. The performance of the proposed solution is evaluated in spacing, which can be realized using several interconnected
Section VI, and finally, we conclude the study in Section VII. Flexible Wavelength Selective Switches (Flex-WSS). Flex-
WSS operates based on one of the several technologies, such
II. OVERVIEW OF F LEXIBLE G RID N ETWORKS as optical Micro Electro-Mechanical Systems (MEMS), Liquid
Unlike fixed channel spacing in conventional fixed grid Crystal on Silicon (LCoS), or silica Planer Lightwave Circuits
networks (as shown in Fig. 1(a)), in flexible grid networks, (PLCs).
channel spacing is variable as shown in Fig. 1(b). The major Flexibility in spectrum assignment leads to additional con-
drivers enabling such system are as follows. (1) Supporting trol and management plane challenges while establishing
higher line rates: After the recent standardization of 100 lightpaths, provisioning survivability, connection setup and
Gb/s transmission technologies, network operators are now teardown functionalities, and dissemination of network state
considering beyond 100 Gb/s transmission such as 400 Gb/s information. Unlike in fixed grid networks, a lightpath in
and 1 Tb/s. Using the state of the art technologies, it is not flexible grid networks needs to be assigned the same amount
feasible to transmit higher line rates within 50 GHz of spectral of spectrum on all links along the route (the spectral con-
width, and even if such technology can be realized, the trans- tinuity constraint), the assigned spectrum must be at the
mission reach needs to be sacrificed. Alternatively, long-reach same operating wavelength on each links (the wavelength
transmission of such higher line rates can be realized with continuity constraint), and the assigned spectrum must not
larger spectral widths using either single carrier modulation overlap with neighboring channels (the spectral conflict con-
schemes or low rate subcarriers in multicarrier modulation straint). Furthermore, an on-the-fly rate-adaptation of channels
schemes. Furthermore, supporting such higher line rates in to support time-varying traffic requires to upgrade existing
a single optical channel avoids over-provisioning of spectrum GMPLS protocol by either incorporating channel spacing

341
 &KURPRVRPH
*HQH
of the RWSA problem in flexible grid networks and the RWA
5 3 3 3
problem is NP-Complete [12], the RWSA problem is also
5 3 3 3
NP-Complete. Here, we propose the sequential meta-heuristic
5 3 3 3
algorithm that is described as follows.
5 3 3 3

5 3 3 3

$ 3RSXODWLRQJHQHUDWLRQ
3RSXODWLRQJHQHUDWLRQ

  
% &KURPRVRPHVHOHFWLRQIRUQH[WJHQHUDWLRQV
'HPDQGV 3RSXODWLRQ & &URVVRYHURIJHQHVDPRQJSDUHQWV
&URVVRYHURIJHQHVDPRQJSDUHQWV
Fig. 2. Genetic Encoding
' 0XWDWLRQRIJHQHV
0XWDWLRQRIJHQHV
and operating frequency related parameters or designing a
mechanism that allows to establish lambda channels at the ( 8SJUDGHSRSXODWLRQEDVHGRQILWQHVVIXQFWLRQ
8SJUDGHSRSXODWLRQEDVHGRQILWQHVVIXQFWLRQ
*HQHWLF
subcarrier granularity. Along with conventional network state 1R
6WRSSLQJFULWHULD
(YROXWLRQ
<HV
information, flexible grid networks are required to disseminate ) ,QLWLDOL]DWLRQRIFRQILJXUDWLRQDQGWHPSHUDWXUH
,QLWLDOL]DWLRQRIFRQILJXUDWLRQDQGWHPSHUDWXUH
additional spectral availability information. This information
* &RQILJXUDWLRQ*HQHUDWLRQ
may either be continuous or discrete in frequency domain
+ )LUVW)LW6SHFWUXP$OORFDWLRQ
and can be maintained either using a centralized approach
or a distributed approach. Spectral optimization increases in , (QHUJ\(YDOXDWLRQ( 1 

1R
proportion to the granularity at which spectrum is discretized; H ( 1 ±± ( & 7 !5DQG>@"
!5DQG>@" ( 1 ( & "
finer granularity of spectral discretization leads to higher 1R
<HV <HV
- &RQILJXUDWLRQ8SGDWH
spectral efficiency at the cost of significant overhead in dis-
. &RROLQJSURFHVV
semination of link state information. To reduce this overhead,
1R 6LPXODWHG
the Link Management protocol (LMP) and Open Shortest 6WRSSLQJFULWHULD
<HV $QQHDOLQJ
Path First-Traffic Engineering (OSPF-TE) protocol need to be 6WRS

updated such that abstract spectrum availability information Fig. 3. Flow Chart of Sequential Meta-Heuristic
can be handled without sacrificing network performance. Most
crucially, the control plane should support fixed and flexible IV. S EQUENTIAL M ETA -H EURISTIC A LGORITHM
grid functionalities in future optical networks consisting of The RWSA problem is divided into two subproblems; (1)
legacy fixed grid technologies and the state of the art flexible the routing subproblem, and (2) the wavelength assignment
grid technologies. and spectrum allocation subproblem. The sequential meta-
III. T HE ROUTING , WAVELENGTH A SSIGNMENT, AND heuristic addresses the routing subproblem using the genetic
S PECTRUM A LLOCATION P ROBLEM evolution procedure and the wavelength assignment and spec-
In the routing, wavelength assignment, and spectrum allo- trum allocation subproblem using the simulated annealing
cation problem, for a given network topology and a set of procedure sequentially as shown in Fig. 3.
offered line rates, the challenge is how to establish end-to-end To reduce the complexity of the problem, the spectrum is
transparent lightpaths for a given set of traffic demands such discretized in the frequency domain, and the smallest unit of
that the maximum required spectrum to support the traffic is a spectrum is referred to as a wavelength slot. The spectrum
minimized. The problem is formally defined as follows. is defined in terms of the number of consecutive wavelength
We are given a physical topology G(V, E), where V is slots, and the central wavelength slot is referred to as a
a set of ROADM nodes and E is a set of fiber edges. wavelength of a channel. The state information of wavelength
The network offers a set of line rates L. For example, slots is binary (state ‘1’ means a wavelength slot is available
L = {10 Gb/s, 40 Gb/s, 100 Gb/s, 400 Gb/s, 1 T b/s}. A and state ‘0’ means a wavelength slot is occupied), and is
line rate l ∈ L requires xl GHz of spectrum. We are given a set referred to as the spectral availability profile.
of traffic demands Λ in which a request is defined as R(s, d, l), We first introduce some terminologies to explain the meta-
where s is the source node, d is the destination node, and l ∈ L heuristic. In the genetic evolution procedure, a generic en-
is the requested line rate. We need to find lightpaths for a given coding is used to map a chromosome to a potential routing
set of demands, routing of these lightpaths over the physical solution of the routing subproblem. A set of routes for a
topology, wavelength assignment and spectrum allocation to given set of traffic demands represents a chromosome and an
these lightpaths such that the maximum required spectrum to individual route of a traffic demand within this set represents
support the given traffic is minimized. In this initial study, we a gene. Thus, each gene represents a feasible route Pij of a
ignore physical layer impairments and differential delay due to traffic demand i, where j indexes one of the feasible routes
traffic bi-furcation, and assume that up-to-date network state of a traffic demand i as shown in Fig. 2. A set of chromo-
information is maintained centrally. somes denotes the population and the number of chromosomes
Assuming that all line rates require the same amount of represents the population size. The fitness of a chromosome
spectrum, the problem is transferred into the routing and is defined as the maximum required spectrum on a fiber link
wavelength assignment (RWA) problem in fixed grid networks. in the network while ignoring the wavelength and spectral
Since the RWA problem in fixed grid networks is a special case continuity constraints, which can be mathematically expressed

342
 
as max(m,n)∈E {i|(m,n)∈P j } Qi , where Qi denotes the opti- to construct a new configuration. The new configuration is
i
mum required spectrum for a demand i. The genetic evolution selected with certain probability that depends on the energy
method of the sequential meta-heuristic performs the following (an optimization parameter; spectrum) difference between the
operations to optimize the routing of lightpaths for a given set current and new configurations and the global parameter T
of traffic demands. (called temperature). At higher temperature, probability of
• Step A: Population generation: For each demand, a route selecting a new or current configuration is random; however, as
is selected out of K potential shortest routes with some temperature decreases, the probability of selecting a configura-
distribution, and considered as the gene of a chromosome. tion with lower energy increases. Thus, at high temperature, a
Similarly, the number of chromosomes equivalent to the selection of a configuration with worse optimization parameter
given population size are generated. avoids the method being stuck at local optimization.
• Step B: Selection of chromosomes: Parent chromosomes Here, a configuration C of the procedure is defined as
are selected using the Roulette Wheel Selection method an order of demands in which the wavelength assignment
in which a chromosome is selected with a probability and spectrum allocation subproblem is addressed. The energy
that is proportional to the fitness of the chromosome. For function E(C) to be minimized represents the maximum
example, a chromosome i is selected with a probability required spectrum over a fiber link in observance of the
j=N
fi
, where fi denotes the fitness of chromosome i, wavelength continuity, spectral continuity, and spectral conflict
j=1 fj constraints. To minimize the energy function, we consider the
and N denotes the population size.
first-fit spectrum allocation procedure in which the spectrum
• Step C: Crossover of parent chromosomes: To bring
availability profile of a route obtained through the genetic
a diversity in the population, a crossover operation is
evolution procedure is determined by bitwise end operations
performed over the selected parent chromosomes. Chro-
of the spectrum availability profiles of all links along the route,
mosome segments (a group of genes) of parent chromo-
and finally, consecutive available wavelength slots equivalent
somes are exchanged at a crossover point that is randomly
to the spectrum required by the line rate are assigned at the
selected, and new children chromosomes are generated.
lowest available wavelength. This first-fit spectrum allocation
• Step D: Mutation: To further increase the population
procedure is performed in the order of demands defined in the
diversity, the children chromosomes are mutated. Based
configuration C. A temperature is defined as a global time-
on the given mutation ratio, a number of genes within
varying parameter T , and the annealing schedule controls how
each child chromosome is randomly selected. The route
the temperature varies over time.
of the selected gene is replaced with the given mutation
probability, and a new route is selected out of K potential • Step F: Configuration initialization: Initially, a configu-
shortest routes with some distribution. ration C is a sequence of traffic demands in a descending
• Step E: Population upgrade: Fitness of the children order of the requested line rates.
chromosomes are evaluated. If a child chromosome has • Step G: Configuration generation: A new configuration
lower fitness than the fitness of any existing chromosome, N is generated from the current configuration C by
then the child chromosome replaces the chromosome with swapping the order of two neighboring demands that are
the highest fitness to keep the population size constant. selected randomly.
The genetic evolution method iterates the same procedure • Step H: First-fit spectrum allocation: The wavelength
until variation in the best (minimum) fitness of the population assignment and spectrum allocation subproblem is ad-
in subsequent iterations remains negligible or the maximum dressed by the first-fit spectrum allocation procedure in
number of iterations has been reached. After completion of the the order of demands defined in the configuration N .
genetic evolution procedure, the chromosome with the lowest • Step I: Energy evaluation: Find the maximum required
fitness represents the routing solution of lightpaths for a given spectrum over a fiber in the network, which represents
set of traffic demands. the energy E(N ) of the new configuration N .
• Step J: Configuration update: If the energy of the new
Subsequently, the wavelength assignment and spectrum
configuration N decreases compared to that of the current
allocation subproblems are addressed through the simulated
configuration C, the current configuration is replaced by
annealing procedure. Simulated annealing is a probabilistic
the new configuration, otherwise the current configuration
iterative method designed based on a physical process of
is replaced by the new configuration with a probability
annealing a solid. To put the material in a low energy state, −(E(N )−E(C))

the material is first heated and later cooled in a controlled e T , where T is the current temperature.
manner. The heat causes atoms to displace from their initial • Step K: Cooling process: The temperature is decreased
positions and wander randomly in this high energy state. Slow at each iteration based on the annealing schedule Tn =
cooling helps atoms to find the configuration in the material α × Tn−1 , where 0.9 ≤ α ≤ 0.99.
such that internal energy is minimized. Thus, this process can This process is repeated until either the temperature T
be adopted in optimizing combinatorial problems. is reduced to 0 or maximum iterations per procedure is
In simulated annealing, initially, a configuration of the completed. Finally, the procedure selects a configuration C
solution is selected. The configuration is changed randomly with the minimum energy and the energy E(C) represents

343
 Fig. 4. Spectrum in 6-node Mesh Network Fig. 5. Route Selection Distribution for K=5 Fig. 6. Spectrum in the Torus Network

Fig. 7. Spectrum in the Ring Network Fig. 8. Route Selection vs. Uniform Distribu- Fig. 9. Spectrum vs. Alternate Routes
tions
the spectrum required to support the network traffic. assume that sufficient spectral resources are available to realize
a nonblocking system. In the simulation of the sequential
V. L OWER B OUND
meta-heuristic, we consider population size to be 5000, num-
To evaluate the quality of a solution, we develop a lower ber of alternate paths K to be 5, mutation ratio to be 0.5,
bound based on the concept of cut theory [13]. Let θ be a mutation probability to be 0.8, annealing parameter α to be
cut partitioning a network, λθ be a subset of traffic demands 0.98, temperature T to be 50, and number of iterations to be
crossing this cut, and Nθ be a number of edges crossing the 10000.
cut. Equal distribution of the total spectrum required by a set
Figure 4 demonstrates the spectral efficiency achieved in the
of demands λθ over Nθ links across the cut θ while ignoring
the wavelength continuity and spectral continuity constraints 6-node mesh network for various traffic load. MCLS offers
the worst spectral efficiency since this algorithm is designed
yields the minimum required spectrum over a fiber crossing
the cut. The same procedure is evaluated for all possible cuts with the goal of maximizing the number of provisionable
paths before the first connection blocking occurs. To meet
in the network and the maximum required spectrum over a
fiber represents a lower bound S to support the given traffic, this objective, MCLS may route connections over longer paths
and end up allocating more spectral resources eventually.
which can mathematically be expressed as follows.
The baseline algorithm performs very similar as MCLS at
 
R(s,d,l)∈λθ xl
lower load, and improves the spectral efficiency up to 4%
S = max (1) at higher load compared to MCLS. On the other hand, the
∀θ Nθ
RMLSA and BLSA algorithms perform very similar and
VI. S IMULATION R ESULTS improve spectral efficiency between 7% to 18% compared
We simulate the proposed algorithm on 6-node mesh [4], 9- to MCLS. On the other hand, the sequential meta-heuristic
node Torus, and 14-node ring network topologies and compare improves the performance between 22% to 34% compared to
the performance with the lower bound, the baseline algorithm, MCLS and the base-line algorithms and between 9% to 25%
and existing solutions, such as BLSA, MCLS, and RMLSA compared to the RMSLA and BLSA algorithms. Furthermore,
algorithms. The flexible grid network supports 10 Gb/s, 40 the performance of the proposed algorithm is very close to the
Gb/s, 100 Gb/s, 400 Gb/s, and 1 Tb/s line rates, and the lower bound, which verifies the accuracy of the solution. In
required spectral width is 25 GHz, 50 GHz, 50 GHz, 75GHz the proposed solution, genetic evolution intelligently selects
[1], and 150 GHz [2] respectively. Requests are uniformly potential routing solutions of lightpaths during the phase of
distributed in the network, and the requested line rate is population generation in which a potential route is selected
uniformly distributed among the offered set of linerates. We randomly out of K-alternate shortest routes. To reduce over-

344
provisioning of spectral resources, we consider the route se-
lection distribution as shown in Fig. 5 in which the probability
of selecting a longer route decreases as the capacity of a line
rate increases. Thus, connections with lower line rates may
take longer routes compared to that with higher line rates.
Genetic evolution iteratively finds routes of lightpaths such
that traffic load is evenly distributed over the network while
minimizing the total required spectrum on a fiber. On the other
hand, simulated annealing evaluates various ordering of traffic
demands according to which the wavelength assignment and
spectrum allocation subproblem is addressed with the goal of
minimizing the maximum required spectrum in a fiber. Thus,
the integration of the genetic evolution and simulated anneal-
Fig. 10. Spectrum Vs. Iterations
ing procedures optimizes the network performance compared
to existing solutions. configuration in simulated annealing lead to small convergence
The performance of various lightpath establishment algo- time in optimizing the fitness and energy functions.
rithms are evaluated with the proposed algorithm for the 9-
VII. C ONCLUSION
node torus and 14-node ring network topologies as shown
In this work, we address the RWSA problem and pro-
in Fig. 6 and Fig. 7 respectively. MCLS provisions exces-
pose the sequential meta-heuristic algorithm using a hybrid
sive spectral resources compared to all lightpath provisioning
application of the genetic evolution and simulated annealing
schemes for the same reason as mentioned above. The baseline
procedures. The performance of the proposed solution is eval-
algorithm occupies less spectrum compared to MCLS since
uated with the existing solutions, the baseline algorithm, and
shortest path routing occupies the least amount of total spectral
the lower bound. The proposed iterative algorithm improves
resources for connections; however, the network load is not
network performance compared to the existing solutions with
equally distributed due to its rigid routing nature, and thus,
smaller convergence time.
spectrum of bottleneck links is excessively utilized leading to
R EFERENCES
worse performance compared to other lightpath establishment [1] Y. Huang et al., “10 X 456 Gb/s DP-16QAM Transmission Over 8 X
schemes. The performance of BLSA degrades compared to 100 Km of ULAF Using Coherent Detection with 30 GHz of ANalog to
RMLSA as the network size and network connectivity in- Digital Converter,” Proc. of OECC, PDP, 2010.
[2] S. Gringeri et al., “Flexible Architectures for Optical Transport Nodes
crease. To balance the load in the network, BLSA routes and Networks,” IEEE Communication Mag., vol. 48, pp. 40-50, 2010.
connections over the least loaded fibers. Such routing scheme [3] M. Jinno et al., “Distance-Adaptive Spectrum Resource Alocation in
may consider longer routes and end up allocating excessive Spectrum-Sliced Elastic Optical Path Network,” IEEE Communication
Mag., vol. 48(8), pp. 138-145, 2010.
spectral resources. Sequential meta-heuristic outperforms ex- [4] A. N. Patel et al., “Routing, Wavelength Assignment, and Spectrum
isting lightpath establishment schemes in a Torus network, and Allocation in Transparent Flexible Optical WDM (FWDM) Networks,”
performs very similar to RMLSA in the 14-node ring network Proc. of Photonics in Switching, no. PDPWG2, Jul 2010.
[5] G. Gho et al., “Rate-Adaptive Modulation and Coding for Optical Fiber
due to its limited network connectivity. Transmission Systems,” Journal of Lightwave Tech., vol. 30(12), pp.
The performance of the proposed algorithm considering the 1818-1828, 2012.
route selection distribution (shown in Fig. 5) is evaluated with [6] P. Ji et al., “Spectrum-Variable Colorless, Directionless, and Contention-
less Multi-Degree ROADM Node,” Proc. of SPIE 7959, no. 79590H,
the uniform distribution (All K alternate routes are equiprob- 2011.
able irrespective of the requested line rate) in Fig. 8 for 9- [7] L. Velasco et al., “Modeling the Routing and Spectrum Allocation Prob-
node Torus network. The route selection distribution brings lem for Flexgrid Optical Networks,” Photonic Network Communications,
DOI 10.1007/s11107-012-0378-7, 2012.
consistent improvement in spectral efficiency compared to the [8] K. Christodoulopoulos et al., “Routing and Spectrum Allocation in
uniform distribution as traffic load increases. We also observe OFDM-Based Optical Networks with Elastic Bandwidth Allocation,”
similar performance behavior for different network topologies. Proc. of GLOBECOM, pp. 1-6, Dec. 2010.
[9] Y. Wang et al., “A Study of the Routing and Spectrum Allocation in
We also evaluate the impact of K on the optimization for Spectrum-Sliced Elastic Optical Path Networks,” Proc. of INFOCOM,
the same network at low (load=7), moderate (load = 21), pp. 1503-1511, Apr. 2011.
and high (load = 35) load as shown in Fig. 9. At low load, [10] M. Klinkowski et al., “A Routing and Spectrum Assignment Problem in
Optical OFDM Networks,” Proc. of European Teletraffic Seminar (ETS),
the optimization improves with K; however, at moderate and Feb. 2011.
higher load, the performance deteriorates beyond certain value [11] Y. Sone et al., “Routing and Spectrum Assignment Algorithm Maximizes
of K. The probability of selecting a longer route as a potential Spectrum Utilization in Optical Networks,” Proc. of ECOC, Sep. 2011.
[12] I. Chlamtac et al., “Lightpath Communications: An Approach to High
solution increases with the value of K, which may affect Bandwidth Optical WAN’s,” Transaction on Communications, vol. 40(7),
network performance by over-provisioning network resources. pp. 1171-1182, 1992.
The evolution of the fitness and energy functions in the [13] S. Baroni et al., “Wavelength Requirement in Arbitrary Connected
Wavelength-Routed Optical Networks,” Journal of Lightwave Tech., vol.
sequential meta-heuristic is demonstrated in Fig. 10 for the 15, pp. 242-251, 1997.
9-node Torus network when the traffic load is 35. Intelligent
selections of the population in genetic evolution and an initial

345