2015 International Symposium on Nonlinear Theory and its Applications
NOLTA2015, Kowloon, Hong Kong, China, December 1-4, 2015

Application of Firefly Algorithm to Optimizationof Translucent Elastic Optical Networks
Haruna Matsushita† , Masahiko Jinno† and Yoshifumi Nishio‡†Department of Electronics and Information Engineering, Kagawa University
2217-20 Hayashi-cho, Takamatsu, Kagawa 761-0396, JAPAN
Email: {haruna, jinno}@eng.kagawa-u.ac.jp‡Department of Electrical and Electronic Engineering, Tokushima University
2-1 Minami-Josanjima, Tokushima 770-8506, JAPAN
Email: nishio@ee.tokushima-u.ac.jp
Abstract—In order to achieve global-scale elastic optical networks, it is important to solve a virtualized-elasticregenerator (VER) placement, and routing and spectrum
assignment (VER-PRSA) problem. This study proposesapplication method of the binary real coded firefly algorithm (BRCFF) for the VER-PRSA problem. BRCFF isused for determining regenerating node candidates wherezero or more VER can be installed. We confirm that the
proposed method reduce the total number of VERs in comparison with the conventional method.
1. Introduction
The elastic optical network (EON) is scalable optical transport network architecture, and it alleviates thestranded bandwidth issue of current wavelength-routed optical networks. In order to achieve global-scale EONs, avirtualized elastic regenerator (VER) was proposed as a solution for eﬃciently regenerating various bandwidth superchannels, including tightly aligned Nyquist WDM superchannels as well as inverse-multiplexed discrete superchannels, in translucent EONs [1]. Although VER is absolutely
necessary to EON, VER placement and the applicable routing between source-destination nodes are important factors
to reduce the total number of VERs, from a viewpoint of installation costs. Furthermore, routing and spectrum assignment in the transparent segment are also important problems to eﬃcient use spectrum resources in each link.
In order to solve the VER placement, and routing andspectrum assignment (VER-PRSA) problem, this study
propose a VER placement method using Firefly Algorithm(FA) [3]. FA is one of nature-inspired multi-agent metaheuristic algorithms and is a metaheuristic algorithm inspired by the flashing behavior of fireflies. The primary
purpose for a firefly’s flash is to act as a signal system toattract other fireflies, and the fireflies of FA search optimal
solution with moving toward other brighter fireflies. Because the standard FA is suitable for continuous optimizations, we apply the binary real coded firefly algorithm (BRCFF) to solve VER placement problem. In the proposed
algorithm, each position vector of firefly corresponds to re-generation sites. If n th element of the position vector is1, it denotes that n th node is a candidates of regenerationsite and VER can be installed at node n. If n th elementof the position vector is 0, VER cannot be installed at thenode even if it is necessary. The proposed method is thefirst application of FA or other multi-agent metaheuristic
algorithm to VER-PRSA problem. Even if other problems
except of VER placement or routing and spectrum assignment are required to optimize EONs, FA can adapt flexibly by modifying the fitness function. We apply the proposed method using BRCFF to four network models, andwe confirm that the proposed method can reduce the total number of VERs in comparison with Shortest-Path andFarthest Node (SP-FN) algorithm [2].
2. Constraint Conditions of VER-PRSA Problem
We explain about the definition of the VER-PRSA problem for a set of static traﬃc demands in a translucent EON.
Note that variables used in this section have no relevanceto the variables used in the Section 4.
The following information are given in advance;• Network graph G = (V, E) which comprises a set ofnodes V = 1, 2, . . . , N and a set of links E ∈ V ×
V connecting nodes in V. Edge costs between two
directly connected nodes.
• An ordered set of frequency-slot units (FSUs) F ={ f1 , f2 , . . . , f| F| } for each link
• Optical reach L• The total number of sub-regenerators in a VER S• Traﬃc demand set D = {d1 , d2 , . . . , d| D| }Each demand d is determined by a source node s, a destination node g, and the requested number of contiguous FSUsn sg between source-destination node pair (s, k).
The constraints are follows;• Regarding the optical path, the length of each transparent segment does not exceed the optical reach L.
• Regarding each transparent segment of the optical path, FSUs allocated to the transparent segment
should be contiguous to each other, should be the- 629 -

same for each link on the transparent segment, andshould not overlap with those of other optical paths.
• All subchannels within the superchannel for the optical path should be regenerated using the same VER.
Goal of this optimization is to find an optical path foreach demand under the constraints and to minimize the total number of VERs which the whole network needs.

where rand is a random number generator uniformly distributed in [0, 1], and L is the scale of the problem, |xmax −xmin |. The firefly i is attracted to all the brighter fireflies by
repeating Eq. (1) if two or more brighter fireflies exist. The
brightest firefly i moves randomly according toxi (t + 1) = xi (t) + α(t) i .

(5)

5. Binary Real Coded Firefly Algorithm (BRCFF)

3. Shortest-Path and Farthest Node (SP-FN)
SP-FN algorithm is a one of the simplest algorithms tosolve VER-PRSA problem. In SP-FN, the shortest pathcalculated by Dijkstra method is always adopted as the optical path between source-destination node pair, and the regeneration is performed at the farthest node on the pathfrom the source node (or the previous regenerated node)
within the optical reach L. The demand set D is sorted
according to the product of the requested number of contiguous FSUs n sg and the shortest distance between eachnode pair (s, k) in descending order. The required contiguous FSUs are placed according to First-Fit algorithm.

In order to select regeneration nodes in VER-PRSA
problem, binary numbers 0 and 1 are used. In other words,
there are zero or more VERs at a node taking the status 1,
and there is no VERs at a node taking the status 0. Due tothe normal FA explained in Section 4 is a real-coded algorithm, we use a binary coded FF algorithm. The position
vector xi in Eq.(1) is represented by yi = (yi1 , yi2 , · · · , yiD )which takes a value of 0 or 1. The corresponding variationof ri j value varies between -1 to 1, which can be calculatedbyri j d = yin − y jn .
(6)

4. Firefly Algorithm (FA)When the position of the firefly is updated, δy can be calculated by

The FA is inspired by the flashing behavior of fireflies.
The M fireflies search the global optima with being attracted to other fireflies according to their attractiveness.
The attractiveness is proportional to their brightness, andfor any two fireflies, the less brighter one will be attracted
by the brighter one. However, the brightness can decreaseas their distance increases. If there are no fireflies brighter
than a given firefly, it will move randomly. The brightnessof a firefly is determined by the objective function.
Let xi = (xi1 , xi2 , · · · , xiN ) be the position vector for firefly i (i = 1, 2, · · · , M). The initial positions of fireflies are
generated at random (xi ∈ [xmin , xmax ]N ).
The movement of a firefly i is attracted to another more
attractive firefly j having better solution, is determined byoldxnew= xoldi + β(x j (t) − xi ) + α(t) i ,i(1)

where the second term of Eq. (1) is due to the attraction.
The attractiveness β is determined by
β = β0 eγri j ,(2)where β0 is the parameter, and an absorption coeﬃcient γ
determines the speed of the convergence. Thus, the attractiveness will vary with the distance ri j between firefly i andj;√
ri j = kxi − x j k =DΣd=1(xin − x jn )2 .

(3)

The third term of ∆xi is randomization with α(t) being therandomization parameter which increases with time, and i = (i1 , i2 , · · · , in ) is a vector of random numbers;
 i = (rand − 0.5)L,

(4)

old
ynew
= yoldi + β(y j (t) − yi ) + 2i ,i(7)where the third term 2 is the random number generated in
the range (−1, 1), and yoldi and y j takes a value of 0 or 1. On
the other hand, ynew
variesbetween -2.180 to 4.3. To codeiy, we set a threshold level th. If ynew
in > th, then yin = 1. If
ynew
≤
th,
then
y
=
0.
In
this
study,
the threshold level isininmade by a sigmoid functionf (ynewin ) =

1.
1 + exp(−ynew
in )

(8)

6. Application of BRCFF for VER placement
This section explains the algorithm of solving VERPRSA problem by using BRCFF. BRCFF is used to determine candidates of regeneration nodes and optimizes thenumber of total VERs installed in whole network.
The proposed algorithm composed of the following
steps.
(Step1) Initialize each firefly position yi = (yi1 , yi2 , . . . , yiN )randomly in the range [−1, 1]. N represents the dimensionof search space and is equivalent to the number of nodes in
the network.
(Step2) Order demand set D as is the case with SP-FN.
(Step3) Find optical paths for respective demands, install
VERs and place required contiguous FSUs, by using eachfirefly position yi .
(Step3-A) Find k path candidates for each demand d by K
shortest path routing algorithm (Yen’s algorithm).
(Step3-B) Check whether a path of the candidates is usable.
When the length of the transparent segment exceeds the- 630 -

200

5

12
460

480

11
1

1

1

3

1

5

1

7

1

1

1

1

1

2

4

1

6

1

8

5

1

8

1

11

1

14

280

1

1

10

3

1

(a)

6

1

9

1

1

1

1

1

12

1

250

260

1

1

1

360

7

4

3
70

180

2

490

590

1
80

6
260

520

9

500

80

3

290
540

4 160

13

330

7
320

440

8
600

300

10

10
250

480
380

340

11
340

5

350

8

250

15

(b)

60 2

460

6

13

340

1
1

10

1

9
2

1

7

1

1

1

1

1

4

1

220

50
360

12
160

13

9

(c)

300
240

14

(d)

Figure 1: Benchmark network models. (a) 2 × 5 regular ladder network model. (b) 3 × 5 regular ladder network model.
(c) JP13 network model. (d) DE14 network model.

optical reach, it must be regenerated by VER. The regeneration is performed by the farthest node method, however,
VERs can be installed at only nodes n where yin = 1. If
all the transparent segment is regenerated before the length
exceeds the optical reach, the path is adopted as the pathfor the traﬃc demand d. If not, check next shortest path.
Repeat the Step3-B until the reachable path is found. If all
k path candidates are rejected, the fitness f (yi ) of the firefly
i is set as ∞, and consider next firefly.
(Step3-C) Repeat the Step3 until all the demand of all thefireflies are considered.
(Step4) Evaluate the fitness of each firefly i byf (yi ) = #total V ERsi ,(9)where #total V ERsi denotes the total number of VERs.
Therefore, this is a minimum optimization problem.
(Step5) Update yi of each firefly i by Eq. (7) and Eq. (8).
(Step6) Return to the Step 3 and repeat these steps until thegeneration step is terminated.
(Step7) With respect to the best firefly needing the least
number of VERs, place the required contiguous FSUs according to First-Fit algorithm and calculate the highest
FSU-index.
7. Simulation Results
7.1. Networks and Parameters
In order to evaluate the proposed FA-FN, we consider
four networks containing 2 × 5 and 3 × 5 regular networkmodels and real-world network models: Japan networkmodel JP13 and Germany network model DE14, as shownin Fig. 1. The traﬃc demand for each node pair was chosen uniformly from 100 Gb/s , 200 Gb/s, 300 Gb/s and
400 Gb/s. For each traﬃc demand, we assumed the following required number of 25-GHz width FSUs, and subregenerators, expressed as a tuple as (100 Gb/s,2,1), (200Gb/s,3,2), (300 Gb/s,4,3) and (400 Gb/s,5,4). We carry out
30 simulations with diﬀerent traﬃc demand sets.
The parameters of the proposed algorithm using BRCFF
are summarized in Table 1. The number of fireflies M is

Table 1: Parameters that are used in simulations.
Parameter
Symbol Value
Attractiveness parameter
β00.2
Absorption coeﬃcientγ
1Maximum number of evaluationsT
300

equivalent to the number of network nodes N, namely, 10,
15, 13 or 14. In the same way, the number of dimensionsof fireflies is equivalent to N.
7.2. Results
Figure 2 shows comparison results of SP-FN and the proposed method using BRCFF. The node occupancy rate denotes the percentage of the number of nodes where one ormore VERs are installed. Regarding the three priorities,
the smaller values are better. We can see that on all the
optical reach L for all the network models, the proposed
method needed less VERs than SP-FN. Furthermore, thenode occupancies of the proposed method are smaller than
SP-FN. From these results, we can conclude that the proposed method can eﬀectively place VERs.
On the other hand, the highest FSU-index of the proposed methods is bigger than SP-FN. This is because thecost function of BRCFF (Eq. (9)) considers only the total
number of VERs. If this function is modified to consider
not only the total number of VERs, but also the highest
FSU-index, we can expect to obtain better results with abalance between the number of VERs and the highest FSUindex.
8. Conclusions
This study has been proposed a novel VER placement
method using BRCFF. BRCFF is used to optimize VER
placement problem and reduces the total number of VERs.
The simulation results showed that the proposed method
can eﬀectively place VERs. Future works include the mod-- 631 -

Total # of VERs

VERocp (SP−FN)
VERocp (BRCFF)

10
5

Node occupancy [%] Highest FSU−index

0
100

50

0
80
60
40
20
0.5

1

1.5

2
2.5
Optical Reach3

3.5

Node occupancy [%] Highest FSU−index

Total # of VERs

50
15

40

VERocp (SP−FN)
VERocp (BRCFF)

30
20
10

0
100

50

0
100

50

0
0.5

1

1.5

(a)

3.5

900

950

20
Total # of VERs

Total # of VERs

3

(b)

25
20
15
10

VERocp (SP−FN)
VERocp (BRCFF)

5

15
10
5

VERocp (SP−FN)
VERocp (BRCFF)

0100

Node occupancy [%] Highest FSU−index

0
Node occupancy [%] Highest FSU−index

2
2.5
Optical Reach

100

50
0
80
60
40
20
550

600

650

700 750 800
Optical Reach

850

900

950

50
0
50
40
30
20
550

(c)

600

650

700 750 800
Optical Reach

850

(d)

Figure 2: Comparison results of SP-FN and the proposed method in terms of the total number of VERs, the highest FSUindex and the node occupancy rate on VER. (a) 2 × 5 regular ladder network model. (b) 3 × 5 regular ladder networkmodel. (c) JP13 network model. (d) DE14 network model.

ification of the fitness function, parameter tuning, path
planning and so on.
Acknowledgment
This work was supported by KAKENHI 24700226 and“Research and development on constructing techniquesof elastic optical networks”, the Commissioned Researchof National Institute of Information and Communications
Technology (NICT).

[2] M. Jinno, T. Takagi and K. Kiyokawa, “Minimal
Virtualized-Elastic-Regenerator Placement and Least
Congestion Resources Assignment for Translucent
Elastic Optical Networks,” in Proc. of Optical Fiber
Communication (OFC), pp. Th3J. 2, 2015.
[3] X-S. Yang, Nature-Inspired Metaheuristic Algorithms,
Luniver Press, 2008.
[4] K. Chandrasekaran, S. P. Simon and N. P. Padhy,“Binary real coded firefly algorithm for solving unit
commitment problem,” Information Sciences, vol. 249,
pp. 67–84, 2013.

References[1] M. Jinno, H. Takara, K. Yonenaga and A. Hirano, “Virtualization in Optical Networks from Network Level toHardware Level,” Journal of Optical Communications
and Networking, Vol. 5, Iss. 10, pp. A46–A56, 2013.

- 632 -