第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
遗传算法的多目标优化问题.pdf
1028 J. OPT. COMMUN. NETW./VOL. 6, NO. 11/NOVEMBER 2014
Martinelli et al.
Genetic Approach for Optimizing
the Placement of All-Optical
Regenerators in WSON
Francesca Martinelli, Nicola Andriolli, Piero Castoldi, and Isabella Cerutti
Abstract—In wavelength switched optical networks
(WSONs), the placement of opto-electronic regenerators
has always been optimized to keep the cost and power con-
sumption contained, while ensuring the quality of trans-
mission (QoT) for the optical signals. Nowadays, with the
increase of the transmission rates and the spectral effi-
ciency of the modulation formats, optical signal regenera-
tion is still relevant for ensuring QoT. The progress in
integrated photonics makes possible the realization of inte-
grated optical regenerators that can replace the traditional
opto-electronic regenerators. All-optical regenerators en-
able a reduction of size and energy consumption. However,
differently from opto-electronic regenerators, recently fab-
ricated integrated optical regenerators neither perform
wavelength conversion nor regenerate multiple lightpaths
at the same wavelength. Thus, novel constraints and limi-
tations are introduced to the conventional regenerator
placement problem, which has been well studied in the past
for opto-electronic regenerators. This paper addresses the
all-optical regenerator placement
(ORP) problem in
WSONs with guaranteed QoT. A genetic algorithm (GA) is
proposed for optimizing the ORP while jointly solving the
routing and wavelength assignment problem. GA results
are compared with the optimal solutions found by solving
a binary linear programming (BLP) formulation. When
properly tuned, GA is able to quickly achieve the optimal
solutions found by the BLP solver. The performance analy-
sis indicates that the additional constraints have a negli-
gible impact on the overall number of regenerators,
compared to the case with opto-electronic regenerators.
Index Terms—All-optical networks; Assignment and
routing algorithms; Integrated optics devices; Network
optimization; Wavelength routing.
I. INTRODUCTION
I ntegrated photonics is progressing and now enables the
realization of photonic integrated circuits that perform
the same complex operations previously carried out by bulk
discrete optical devices or by electronic circuits. The un-
doubted advantage is the possibility to reduce the footprint
of the circuits.
Manuscript received April 7, 2014; revised September 11, 2014; accepted
September 18, 2014; published October 17, 2014 (Doc. ID 208070).
F. Martinelli was with CNIT, 56124 Pisa, Italy.
I. Cerutti (e-mail: i.cerutti@sssup.it), N. Andriolli, and P. Castoldi are
with the Scuola Superiore Sant’Anna, 56124 Pisa, Italy.
http://dx.doi.org/10.1364/JOCN.6.001028
A notable example of the achieved progress is given by
the photonic integrated circuits performing all-optical re-
generation presented in [1–3]. The manufactured all-
optical regenerator performs reamplification, reshaping,
and retiming (3R) regeneration of the optical signal in
the optical domain. Due to the photonic implementation,
the all-optical regenerator exhibits some limitations in the
regeneration capabilities with respect to the traditional
opto-electronic regenerators. The most relevant one is
the inability to offer wavelength conversion, which is an in-
herent capability of opto-electronic regenerators.
The conventional placement of opto-electronic regenera-
tors in wavelength switched optical networks (WSONs) has
always been optimized to keep the cost and power con-
sumption contained, while ensuring the quality of trans-
mission (QoT) for the optical connections, or lightpaths.
The regenerator placement problem (RP problem) consists
of selecting few strategic nodes in which regeneration can
be offered to the bypassing lightpaths, leading to a trans-
lucent design of the WSON. The RP problem has been well
studied in the past [4–23] and keeps its relevance even now
with the current trend toward higher transmission rates
and increased spectral efficiency of
the modulation
formats.
The introduction of all-optical integrated regenerators is
posing additional constraints and limitations to the con-
ventional RP problem. More specifically, all-optical inte-
grated regenerators [1–3]
force wavelength continuity
and a single regeneration per wavelength. Such limitations
may hinder their advantages, as a larger number of regen-
erators may need to be placed in the network.
This paper focuses on the problem of optimally placing
the all-optical integrated regenerators, referred to as the
all-optical regenerator placement problem (ORP problem).
The work aims to model and address the novel ORP prob-
lem that includes additional constraints derived from the
integrated photonic implementation. The purpose of the
work is to understand how and if the additional constraints
impact the placement and thus ultimately the cost and en-
ergy consumption for performing regeneration.
After modeling the ORP problem with a binary linear
programming (BLP) formulation, the paper proposes a ge-
netic algorithm (GA) that aims at minimizing the number
of all-optical regenerators while performing routing and
wavelength assignment (RWA) of the lightpaths and
1943-0620/14/111028-10$15.00/0 © 2014 Optical Society of America
Martinelli et al.
VOL. 6, NO. 11/NOVEMBER 2014/J. OPT. COMMUN. NETW. 1029
ensuring QoT. Simulation results aim to evaluate the opti-
mality and the execution time of the GA approach with
respect to the optimal BLP approach. Moreover, ORP sol-
utions are compared with the RP solution to assess the
increment of required regenerators caused by the addi-
tional constraints brought by the all-optical regenerators.
II. REGENERATOR PLACEMENT PROBLEM IN THE LITERATURE
The general problem of placing opto-electronic regener-
ators (RP problem) in WSONs is known to be NP-hard [4]
and has been well studied in the past. Optimal and ap-
proximated methods mainly based on integer linear pro-
gramming (ILP) formulation and heuristics algorithms,
respectively, have been proposed to address the RP prob-
lem in a variety of scenarios.
The RP problem can be formulated as a connected domi-
nating set problem in a labeled graph [4], which is a NP-
complete problem. Among the optimization methods, a
constraint programming based multiobjective optimization
model has been adopted to minimize the total routing cost,
the total number of regeneration operations, and the num-
ber of nodes performing regeneration in [5]. Other works
exploit approaches based on ILP formulation. The RWA
and RP problems are addressed jointly in [6] with ILP for-
mulation, without enabling wavelength conversion at the
regeneration nodes. In [7,8], the RWA, RP, and traffic
grooming problems are addressed jointly with ILP formu-
lation. In [9] the RP problem is solved jointly with the RWA
problem, with the aim of minimizing the regeneration
equipment cost while avoiding at the same time lightpath
blocking. Also the works in [10–12] propose ILP formu-
lation to jointly solve the RWA and RP problems, while con-
sidering protection schemes.
As the problem size increases, ILP solvers may take an
excessively long time to compute the optimal solution.
Thus, advanced techniques based on ILP or techniques
that combine the ILP approach with a heuristic approach
can be exploited [13–15]. In [13] the ILP formulation for RP
is addressed with a branch and cut approach. In [14] the
RWA and RP problems are solved separately: The RP prob-
lem is addressed with an ILP formulation as well as with a
heuristic algorithm; then the traffic matrix is transformed
into a completely transparent set of connection requests,
which is fed to the RWA algorithm. Similar to the latter
work, a two-step approach is followed by [15], achieving
fast convergence and global CAPEX savings even for large
networks. In the first step the RP problem is solved with
the aim of minimizing the number of regeneration nodes
together with the lightpath length, by using an ILP formu-
lation. Then, in the second step a heuristic algorithm solves
the RWA-RP problem based on the results found in the pre-
vious step.
Among the works focusing on heuristic algorithms, in
[16] a systematic theoretical study is made for the RP prob-
lem by including polynomial time algorithms, NP-complete
results, approximation algorithms, and inapproximability
results. In [13] three heuristics are proposed for the RP
problem. Centralized and distributed approaches are
proposed in [17] for the problem of minimizing the number
of regenerators to guarantee a certain degree of connectiv-
ity. Heuristics approaches for the RWA and RP problems
are also proposed in [6–8,18,19], as well as in [11,12], where
resilience is also accounted for. The objective functions of
the proposed heuristic approaches span from the minimi-
zation of the regenerators [6,12], to the minimization of the
linear combination of the number of rejected lightpaths
with the number of regenerators [12,18] (or with the net-
work cost [19]), to the minimization of the wavelength uti-
lization [11,12], and to the minimization of the network
cost [7,8]. The work in [20,21] focuses on minimizing the
total number of regenerator modules to be placed in the
network instead of the regeneration nodes. For the same
instances exact algorithms exist [20,21]; otherwise this
optimization problem can be addressed with the heuristic
algorithm proposed in [20].
Among the meta-heuristic approaches, a multiobjective
evolutionary algorithm is used to minimize both the num-
ber of regenerators and the blocking probability in [19], and
a GA is exploited for optimizing the mixed placements of
1R/2R/3R regenerators in translucent lightpaths in [8].
All of these works are concerned specifically with opto-
electronic regenerators. In [22,23] a mixed placement of all-
optical 2R and opto-electronic 3R regenerators is exploited.
To the best of our knowledge, we formulated the problem of
placing all-optical regenerators (ORP) for the first time in
[24]. In this paper, the next section presents the ORP prob-
lem and its differences from the RP problem. Then a BLP
formulation and a novel GA approach are presented to ad-
dress the problem.
III. ALL-OPTICAL REGENERATOR PLACEMENT PROBLEM
To model the ORP problem the following notation is
used. Calligraphic letters indicate sets, and capital letters
indicate problem parameters. The ORP problem is defined
as follows. Given a WSON network and a set T of lightpath
requests,
the ORP problem consists of routing and
assigning the wavelengths to the requested lightpaths
and in deciding the optimal placement of the all-optical re-
generators. All-optical regenerators should be placed to
guarantee the QoT of the lightpaths. In this paper, QoT
is enforced by resorting to the concept of maximum optical
reach that can be defined as the longest propagation dis-
tance over which QoT of the optical signal is ensured. Thus,
lightpaths spanning farther than the maximum optical
reach are required to undergo regeneration in one or more
intermediate nodes, so that the distance between two re-
generation nodes (or the terminal node) is always shorter
than (or equal to) the maximum optical reach.
The ORP problem is subject to specific constraints intro-
duced by the all-optical implementation of the integrated
regenerators proposed in [1,2]:
1) Wavelength continuity constraint: All-optical regenera-
tors are unable to offer wavelength conversion capabil-
ity. This means that each lightpath should be assigned a
1030 J. OPT. COMMUN. NETW./VOL. 6, NO. 11/NOVEMBER 2014
Martinelli et al.
1
2
w11ww
w1
w1
3
4
5
node with regenerator
node without regenerator
regenerated lightpaths
non-regenerated lightpaths
Fig. 1. Constraint enforcing one regeneration per wavelength.
)
1
,
,
3
2
(
/
)
2
,
,
3
1
(
3
=
c
1
)
1
,
2
(
/
)
2
1
(
,
2
2
=
c
(
(1,3) / (3,1)
c = 1
3
3
)
)
3 , 1 , 2
) / (
2 , 1 , 3
c = 3
3 , 2
) / (
2 , 3
c = 2
(
( 3 , 4 ) / ( 4 , 3 )
c = 3
(3,5) / (5,3)
c = 2
4
5
1
2
w1
w11ww
w2
w22ww
w3
3
4
5
node with regenerator
node without regenerator
regenerated lightpaths
non-regenerated lightpaths
g p
g
(1,3,5) / (5,3,1)
c = 3
Fig. 3. Auxiliary multigraph derived from graph of Fig. 4 for
R 3.5.
Fig. 2. Constraint enforcing the limited number of regenerations.
single, continuous wavelength from the source node to
the destination node.
2) One regeneration per wavelength: All-optical regenera-
tors are able to regenerate only one single lightpath per
wavelength. An example is shown in Fig. 1, where two
different lightpaths using the same wavelength w1 need
to be regenerated in node 3, which is equipped with an
all-optical regenerator. Then, only one of the lightpaths
may be regenerated, for instance, the one represented
by the solid line.
3) Limited number of regenerations: Each all-optical re-
generator can regenerate a limited, fixed number of
lightpaths, equal to L (L ≤ W). An example is shown
in Fig. 2, where three different lightpaths are repre-
sented and node 3 is equipped with an all-optical regen-
erator. When L 2, the constraint on the limited
number of regenerations imposes that node 3 may re-
generate only two of the three lightpaths passing
through itself. As a result, the dashed lightpath cannot
be regenerated.
IV. ORP PROBLEM MODELING
To find the optimal placement of all-optical regenerators,
the considered WSON network is represented by a directed
graph G
N ; A, where N is the set of nodes, and A is the
set of links. Each link is assumed to carry a single fiber
with W wavelengths. A set of paths (P) between any node
pair is precomputed on G. Based on G and P, an auxiliary
multigraph G0
N ; A0 is built as follows. G0 has the same
set of nodes and the same number of wavelengths per fiber
as G. A link l
s; d; k ∈ A0 represents a candidate route
in G from s to d. Multiple links can be established between
the same node pairs. The notation l
s; d; k ∈ A0 is used
to indicate the k link from s to d and identifies the k route
from s to d in G (ps;d;k ∈ P). The length of link l ∈ A0, c
l, is
equal to the route length. QoT is enforced by including in A0
Fig. 4. Example of graph representing a network topology.
only the links whose length is equal to or shorter than the
maximum optical reach R; i.e., if c
l ≤ R, then l ∈ A0.
Figure 3 shows an example of the auxiliary multigraph
G0 derived from the network graph shown in Fig. 4, when
the maximum optical reach is R 3.5 a:u. Lengths of the
fiber links are as shown in Fig. 4. To ease the display of G0,
undirected links are used with the indication of the corre-
sponding directed paths1 on G and of the corresponding
lengths c
l. Due to the constraint on the maximum optical
reach, some links are not present in the auxiliary multi-
graph G0. For instance, the link from node 1 to node 4 is
absent as it corresponds to a shortest path on G whose
length (4 a.u.) is greater than the maximum optical reach
(R 3.5). On the other hand, between some node pairs in G0
there are multiple paths satisfying the QoT constraint. For
instance, two directed links from node 1 to node 2 exist in
G0, and they correspond to paths 1 → 2 and 1 → 3 → 2,
whose lengths are c 2 and c 3, respectively.
A. BLP Model
The ORP problem is modeled with a BLP formulation as
follows.
Parameters
G0
N ; A0: the auxiliary multigraph for the maximum
optical reach R;
1Only simple paths are considered.
Martinelli et al.
VOL. 6, NO. 11/NOVEMBER 2014/J. OPT. COMMUN. NETW. 1031
T : the set of lightpath requests;
L: the maximum number of regenerations at a node;
W: the number of wavelengths on each link.
Variables
xt;w
ri: binary variable indicating whether a regenerator is
placed at node i ∈ N (ri 1) or not (ri 0);
i;j;k: binary variable indicating whether the link
i; j; k ∈
A0 using wavelength w is used for the tth lightpath
request (xt;w
i;j;k 1) or not (xt;w
i;j;k 0).
The size of the presented BLP formulation grows with
jT j · H · W, where H is the maximum number of arcs in
A0 departing from or arriving at any node, or equivalently
the maximum number of simple paths existing between a
node pair with a length shorter than or equal to R. The
ORP problem includes the coloring problem and the inte-
gral multicommodity flow problem on G0. Such optimization
problems are known to be NP-hard, and thus the ORP
problem is also NP-hard. For this reason, a meta-heuristic
approach based on the GA is proposed next.
V. GENETIC ALGORITHM FOR ORP
X
ri;
X
i∈N
1;
1;
xt;w
i;s;k
i;k:
i;s;k∈A0
X
j;k:
d;j;k∈A0
xt;w
d;j;k
BLP formulation
Minimize :
XW
X
w1
i;k:
s;i;k∈A0
xtw
s;i;k −
∀ t ∈ T :s src
t
X
XW
xt;w
j;d;k −
w1
j;k:
j;d;k∈A0
∀ t ∈ T :d dst
t
X
X
i;j;k
xt;w
xt;w
j;i;k
j;k:
i;j;k∈A0
j;k:
j;i;k∈A0
∀ w 1; …; W; ∀ t ∈ T ; ∀ i ∈ N :i ≠ src
t and
i ≠ dst
t
X
X
i;j;k ≤ 1 ∀ w 1; …; W;
xt;w
∀
l; m ∈ A;
t∈T
i;j;k∈A0:
l;m∈pi;j;k
X
XW
X
i;j;k ≤ L · ri ∀ i ∈ N ;
xt;w
(5)
(6)
X
t∈T :i≠src
t
X
w1
j;k:
i;j;k∈A0
t∈T :i≠src
t
j;k:
i;j;k∈A0
i;j;k ≤ ri ∀ i ∈ N ;
xt;w
∀ w 1; …; W: (7)
The objective function (1) aims at minimizing the num-
ber of all-optical regenerators to be placed in the WSON.
Constraints (2)–(4) are flow conservation constraints at
the source (src), destination (dst), and intermediate node
of each commodity and route the lightpath requests on
the auxiliary graph G0 to determine the regeneration nodes.
Constraint (4) also enforces wavelength continuity when
regenerating the signal. Constraint (5) ensures that two
or more lightpaths having one or more links in common
in G cannot share the same wavelength. Constraint (6) en-
forces a limited number of regenerations: It places an all-
optical regenerator at any intermediate node of the routes
on G0 and enables regeneration of up to L lightpaths.
Constraint (7) enforces one regeneration per wavelength:
Only one single lightpath can be regenerated per each
wavelength at each node.
GAs were first proposed by Holland [25] inspired by the
mechanism of natural selection. The basic idea of GAs is to
consider an initial population of
individuals (chromo-
somes), representing the candidate solutions of the prob-
lem, and to simulate their evolution according to a
selection mechanism until a good (possibly optimal) solu-
tion is found. The quality of a solution is evaluated by a
fitness function, closely related to the objective function
of the problem. The evolutionary process uses two funda-
mental genetic operators: crossover and mutation. The for-
mer recombines “genes” of selected solutions (parents) to
generate a new solution (offspring). The latter alters one
or multiple genes in a chromosome with the aim of avoiding
the convergence of the problem to a local optimal solution.
The following subsection describes the GA used in this
work to solve the ORP problem.
(1)
(2)
(3)
(4)
A. GA Implementation
The flowchart of the GA for the ORP problem is shown in
Fig. 5. The initial population, S1 fσ1; σ2; …; σjS1jg, is ran-
domly generated, and every individual σj is represented by
a vector V fv1; v2; …; vNg, where N is the number of nodes
in the network (i.e., N jNj) and vj is a gene that takes the
value of 1 when an all-optical regenerator is placed on node
j, and 0 otherwise. An example of an individual and its cor-
responding regenerator placement is shown in Fig. 6.
Each regenerator placement is a candidate solution to
the ORP problem, whose feasibility needs to be validated.
Thus, given a regenerator placement σj, RWA is performed
for each lightpath request following the procedure RWA-RP
that is described in more detail below in Subsection V.A.1.
Then, if all the requests can be allocated, the quality of the
placement is measured by the fitness function f
σj. In
P
agreement with Eq. (1), the fitness function is set equal
to the number of regenerators in σj, i.e., f
σj
i1 vi. If
one or more requests cannot be accommodated due to a lack
of regenerators or wavelengths, then the fitness function
value is set to a high number (i.e., greater than jNj).
N
The crossover and mutation operators are applied to the
current population to generate a new population, that is, a
new set of candidate placements. The process of generating
a population and assessing the individuals is then repeated
for a number of iterations. In this evolutionary process, the
1032 J. OPT. COMMUN. NETW./VOL. 6, NO. 11/NOVEMBER 2014
Martinelli et al.
regenerator placement (candidate solution σj), the RWA-
RP algorithm executes the following steps. The set of light-
path requests is initially sorted in descending order of the
number of hops (links) of the precomputed shortest paths
and in case of ties in ascending order of the number of al-
ternate paths. The rationale is that lightpath requests re-
quiring a greater number of resources (i.e., wavelengths on
links) and with the lowest number of candidate paths are
considered first, enhancing the chances that they can be
accommodated.
The pseudo-code of
the algorithm is presented in
Algorithm 1. The algorithm scans the sorted requests and
checks whether each lightpath request can be accommo-
dated for the considered regenerator placement. More spe-
cifically, for each lightpath request t, the precomputed paths
Kt fk1; …; kjKtjg between the node pair of request t are as-
sessed one at the time by starting from the shortest one in
kilometers (line 3). Then, for each path ki (lines 4–13), wave-
length assignment is performed using a first-fit approach
(function FIRSTFITWVLASSIGNMENT), and the constraint
on the maximum optical reach is validated for the consid-
ered regenerator placement σj (function CHECKRP). If the
wavelength assignment and the validation are successful
for the jth path, then a new lightpath request is considered;
otherwise the algorithm checks the feasibility of another
(longer) path for the tth request in Kt. If the constraints
of routing, wavelength assignment and continuity, and
maximum optical reach are satisfied for all the lightpath
requests, then the candidate solution σj is declared feasible.
Fig. 5. Flowchart of GA implementation for ORP problem.
individuals with a low fitness value are privileged, enabling
convergence to a solution with a minimal (possibly with the
minimum) number of all-optical regenerators. The termina-
tion condition of the implemented GA is determined by the
number of generations, which is set a priori and indicated
as MAX_iter. When reached, the solution with the minimal
number of regenerators (σBEST) is returned.
1) RWA-RP Algorithm: For a given set of lightpath re-
quests (T ), set of precomputed simple paths (P), and
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
Algorithm 1 Pseudo-Code of the RWA-RP Algorithm
Algorithm RWA-RP (T , P, σj)
1: for each lightpath request t ∈ T do
2:
3:
done = FALSE;
Kt fk1; …; kjKtjg ∈ P;
paths for t
▹ Precomputed
for i←1; …; jKtj do
done = FIRSTFITWVLASSIGNMENT(ki);
if done then
if LENGTH(ki)> R then
done = CHECKRP(σj, ki);
end if
if done then break;
end if
end if
end for
if !done then
return FALSE;
accommodated
end if
16:
17: end for
18: return TRUE;
accommodated
▹Request t cannot be
▹All the lightpath requests are
Fig. 6. Example of a regenerator placement candidate solution.
VI. PERFORMANCE ASSESSMENT
In this section, the performance of the proposed GA is
assessed and compared with the presented BLP formu-
lation. For both cases, the set of precomputed simple paths
Martinelli et al.
VOL. 6, NO. 11/NOVEMBER 2014/J. OPT. COMMUN. NETW. 1033
0
2
0
2
1
1
3
5
1
2
9
1
1
1
7
6
6
3461
3
860
4
0
8
7
6
2 6 7 9
8 3 3
7
1
8
0
0
8
774
1105
14
11
497
10
534
5
1
9
6 6 9
2
9
4
9
487
487
7
2
5
13
12
225
2
2365
Probability of placing a
regenerator at a node:
1 2 7 6
5
2265
[0% , 20%)
[20% , 40%)
[40% , 70%)
[70% , 100%]
Fig. 7. NSF network topology with the probability of placing an optical regenerator as computed by BLP for W 40, L 40, and
jT j 50 randomly generated requests.
between any node pair is computed using Yen’s algorithm
[26,27]. Also, results of the ORP problem are compared
with the RP problem with opto-electronic regenerators.
The performance is evaluated on the NSF network con-
sisting of 15 nodes and 23 links (Fig. 7) for a maximum
optical reach of R 3461 km and different traffic loads.
For nonuniform traffic, lightpath requests are randomly gen-
erated by uniformly selecting the source and destination
nodes. Collected results are averaged on 30 simulations or
higher until a confidence interval of 15% or better (as shown
in the following figures) is reached with a confidence level of
95%. The machines used for the simulations are quad-core
2.4 GHz Intel Core processors with 2 GB of memory.
A. BLP Formulation Results
The presented BLP formulation is optimally solved us-
ing AMPL and IBM ILOG CPLEX v.12.4 software. To keep
the execution time contained, the maximum running time
of the BLP solver is set to 300 min. Only optimal solutions
found within the time limit are collected.
For creating the auxiliary multigraph G0 used by the BLP
formulation, up to H shortest paths are computed using
Yen’s algorithm. When H → ∞, all the simple paths are
considered and thus the overall optimal solution can be
found. However, the complexity of the BLP formulation
and thus the execution time of the BLP solver can be ex-
cessively long. For smaller values of H, optimality is traded
for faster execution time.
1) Impact of the Maximum Number of Candidate Paths:
The impact of the maximum number of candidate paths (H)
on the optimal number of all-optical regenerators required
in the network and on the execution time to reach the op-
timal solution is first assessed. Due to the high complexity
of the BLP formulation, the results are collected for jT j
50 randomly generated lightpath requests. Figure 8 re-
ports the average number of regenerators to be placed in
the NSF network for W 16 and for different values of
H and L (L ≤ W). Independently of L, even for small values
of H the found optimal solution is as for the case H ∞,
which considers all the possible paths between any node
pairs. The reason is that when increasing the values of
H the longer candidate paths are also considered, but they
may exceed the maximum optical reach, and therefore they
may not be included in the auxiliary multigraph G0.
On the other hand, increasing the value of H leads to an
increase of the number of variables and thus of the execu-
tion time of the BLP solver. Figure 9 shows the average ex-
ecution time in seconds as a function of H. When passing
from H 1 to H 3 the average execution time increases
by a factor of 4. Therefore, in the remainder of the section,
H 1 is considered; i.e., for each node pair only the short-
est path is considered.
2) Impact of L and W: Figure 10 shows the average
number of all-optical regenerators for 50 lightpath re-
quests when increasing the number of wavelengths (W)
and for various limitations on the number of regenerations
per node (L ≤ W). For L 16 or higher, fewer than two
strategically placed all-optical regenerators are sufficient
on average. On the other hand, for L 8, the number of
lightpaths that can be regenerated at a regeneration site
is too low and thus more nodes must be designed for
regeneration. The dependence on W is almost negligible,
Fig. 8. BLP results: average number of all-optical regenerators
for jT j 50 randomly generated requests and W 16.
1034 J. OPT. COMMUN. NETW./VOL. 6, NO. 11/NOVEMBER 2014
Martinelli et al.
Fig. 9. BLP results: average execution times for jT j 50
randomly generated requests, W 16 and L 16.
provided that a sufficient number of wavelengths is allo-
cated for supporting the requested demands. However,
when W L 8 a slightly higher number of all-optical re-
generators is necessary due to the lower network capacity
(small value of W), which forces longer paths and thus a
higher need for regeneration. The probability of placing
an optical regenerator at each node is visualized in Fig. 7
for W L 40. Nodes connected to longer links have a
higher probability of being selected for regeneration.
3) Comparing ORP Versus RP: This subsection compares
the optimal solutions of the ORP problem with those of the
RP problem. The RP problem does not include constraint (7)
and allows wavelength conversion [i.e., constraint (4) does
not apply]. For a fair comparison, constraint (6) expressing
the limited number of regenerations is also included.
Figure 11 shows the number of all-optical regenerators
and opto-electronic regenerators in the NSF network for
W 40 wavelengths per fiber. Interestingly, no differences
in the optimal solutions are detected, indicating that the
additional constraints of the ORP problem do not have any
impact. This can be explained by the fact that the wave-
length continuity constraint has a negligible impact on
the number of wavelengths required in a network [28,29].
Fig. 11. BLP results: all-optical versus opto-electronic regenera-
tor placement for jT j 50 randomly generated requests and
W 40.
B. GA Results
The performance of the GA introduced in Subsection V.A
is now presented. The proposed GA is implemented in C++
using the GAlib library [30]. At each GA iteration the
Grefenstette parameter settings [31] are adopted: The
crossover probability and mutation rate are set to 0.9
and 0.01, respectively, for a population size of 30. The cross-
over method has two points (i.e., two individuals are se-
lected, and their vectors are segmented in two random
positions, and then the different segments are combined).
Mutation is performed on a per-gene basis. Unless other-
wise stated, all the shortest paths have been considered
by GA, i.e., K ∞.
1) Tuning GA Parameters: The maximum number of
iterations of the GA (MAX_iter) determines the quality
of the solution and impacts the execution time. Figure 12
shows the probabilities of reaching the optimal solution (as
computed by the BLP solver) for an increasing number of
GA iterations and for two different traffic loads (jT j 50
and jT j 100), W 40 and L 40. For each traffic load,
the probabilities are obtained by running at least 30
instances of the GA with a different initial population
Fig. 10. BLP results: average number of all-optical regenerators
for jT j 50 randomly generated requests.
Fig. 12. GA results: probability of reaching the optimal solution
for W 40 and L 40.
Martinelli et al.
VOL. 6, NO. 11/NOVEMBER 2014/J. OPT. COMMUN. NETW. 1035
for three different traffic matrices and then by averaging
the results. With only 30 iterations of the GA, it is already
possible to reach the optimal solution in 80% of the simu-
lations. Indeed, the GA is able to quickly converge to the
optimal solution: With a number of iterations equal to or
greater than 100, the GA always finds the optimal solu-
tions in the considered network and scenario. The average
execution time is about a half minute and 1 min for the two
traffic loads, respectively. A more accurate evaluation of
the execution time for jT j 50 is reported in Fig. 13 as
a function of the maximum number of candidate paths
per node pair (K maxt∈T jKtj). The execution time in-
creases with K, but its value is below 30 s. Thus, thanks
to the fast execution time of the GA even for large values
of K, in the rest of the paper the maximum number of GA
iterations is set to MAX iter 400.
For the simulated scenarios of Fig. 13 (i.e., jT j 50 and
W 40), the average number of all-optical generators is
reported as a function of K in Fig. 14. When increasing
the value of K a smaller number of regenerators is required
in the NSF network. In this case, the best solution (as
found for K ∞) can already be obtained for K 10. This
holds for any considered values of L. However, given the
negligible difference of execution time between K 10
and K ∞ (see Fig. 13), in the remainder of the paper
K ∞ is always considered.
2) Comparing ORP Versus RP: The performance of the
GA for the ORP problem is compared with that of the
GA for the RP problem using opto-electronic regenerators.
For the RP case, the GA implementation is modified to al-
low wavelength conversion at each opto-electronic regener-
ator. Also, for a fair comparison, the constraint on the
limited number of regenerations [constraint (6)] is also in-
cluded. Figure 15 shows the ORP and RP results collected
for a uniform traffic matrix and for W 40 wavelengths.
No relevant differences are detected between ORP and
RP solutions, indicating that the additional constraints
of the ORP problem (i.e., wavelength continuity constraint
and one regeneration per wavelength) have a minor or
negligible impact.
Fig. 14. GA results: average number of all-optical regenerators
for jT j 50 randomly generated requests and W 40.
Fig. 15. GA results: all-optical versus opto-electronic regenera-
tors for W 40 and a uniform, complete traffic matrix.
C. Comparing GA With BLP
To conclude the performance analysis of the ORP prob-
lem, the results obtained with the BLP formulation (H 1)
Fig. 13. GA results: average execution time for jT j 50 ran-
domly generated requests and W 40.
Fig. 16. BLP and GA results: average number of all-optical regen-
erators for W 40 and L 40.
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
