日本オペレーションズ・リサーチ学会
2021年 秋季研究発表会

2-C-1

ILP models for the problem of routing and spectrum allocation in EONs
筑波大学01206770 筑波大学
筑波大学
1. Introduction
In recent years, with the development of newtechnologies such as high-definition video, cloudcomputing, and IoT (Internet of Things), theamount of network traffic around the world has
been increasing rapidly. The growth in traffic has
driven continuous innovation in the architecture
and technology of optical networks. In 2009, Jinno
et al. [1] proposed a so-called SLICE architecture,driving the evolution in optical networkarchitectures from fixed grid wavelength divisionmultiplexing (WDM) -based networks which are
the so-called wavelength switched optical networks(WSONs) to the flexible grid elastic opticalnetworks (EONs). By using a flexible wavelength
allocation technique with smaller and more flexible
granularity of spectrum which is called frequency
slot (FS), EONs can improve the efficiency andflexibility for diverse traffic transmission.
However, due to the small granularity in EONs,
the resource allocation problems become more
complicated than that of the existing WSONs. For
instance, EONs impose more restrictions on theestablishment of light paths, that is, the FS
allocated to a light path must be contiguous in thespectral domain. Such a problem is the well-known
routing and spectrum allocation (RSA) problem,
which has been proved as NP-hard by Ref. [2].
2. ILP models for RSA problem
Our work systematically summarizes the integer
linear programming (ILP) models for the RSA
problem in existing works from two aspects: routingand spectrum allocation. With respect to routing,there are Path-type and Node-type models. With
respect to spectrum allocation, Slot-type andChannel-type models. By combining the routing
models and spectrum allocation models, the ILP
models of the RSA problem can be divided into fourtypes: Path/Slot, Path/Channel, Node/Slot, and*王家鼎WANG Jiading
繁野 麻衣子 SHIGENO Maiko呉謙
WU QianNode/Channel.
2.1 Path/Slot model
Path/Slot model is a model that transmission
paths are selected from the prepared candidate
paths and that allocates FSs by using variables
corresponding to themselves. The following eqs. (1)to (3) are its typical formulations. Among them, 𝑅is the set of connection requests, and 𝑃𝑟 is the setof candidate paths for serving connection request𝑝𝑟 ∈ 𝑅 . 𝑛𝑟 is a set of constants that indicate thenumber of FSs required for transmitting
connection request 𝑟 by using candidate path 𝑝.
𝑝
𝑥𝑟 and 𝑜𝑟𝑟 ′ are binary variables, that indicate
whether connection request 𝑟 uses path 𝑝 , andthe order of the FSs used in spectrum by connection
request 𝑟 and 𝑟 ′ , respectively. 𝑓𝑟 is anonnegative integer variable that indicates theindex of the first FS used by connection request 𝑟.
𝑝(1)∑ 𝑥 = 1, ∀𝑟 ∈ 𝑅𝑟𝑝∈𝑃𝑟𝑜𝑟𝑟 ′ + 𝑜𝑟 ′ 𝑟 = 1, ∀𝑟, 𝑟 ′ ∈ 𝑅: 𝑟 ≠ 𝑟 ′𝑝𝑝𝑝′
𝑓𝑟 + 𝑛𝑟 ≤ 𝑓𝑟 ′ + 𝑀 [3 − (𝑥𝑟 + 𝑥𝑟 ′ + 𝑜𝑟𝑟 ′ )],∀𝑟, 𝑟 ′ ∈ 𝑅, 𝑝 ∈ 𝑃𝑟 , 𝑝′ ∈ 𝑃𝑟 ′ : 𝑟 ≠ 𝑟 ′ , 𝑝 ∩ 𝑝′ ≠ ∅

(2)
(3)

Eq. (1) indicates that only one path 𝑝 can beselected for any connection request 𝑟 from the setof candidate paths. Eqs. (2) and (3) together suggest
the spectrum non-overlapping constraints between
different connection requests for Path-type models.
2.2 Path/Channel modelPath/Channel model is a model thattransmission paths are selected from the preparedcandidate paths and that allocates FSs by using
variables corresponding to the prepared candidate
channels which consist of multiple adjacent FSs.
The formulation of routing constraint for
Path/Channel model is similar to that for Path/Slotmodel. And the formulation of spectrum nonoverlapping constraint for it are shown as eq. (4).

𝑝𝑐𝑓 𝑝𝑐
𝑥𝑟 ≤ 1,∑ ∑ ∑ 𝛿𝑟(4)∀𝑒 ∈ 𝐸, 𝑓 ∈ 𝐹𝑟∈𝑅 𝑝∈𝑃𝑟 𝑐∈𝐶 𝑝𝑟𝑒⊆𝑝𝑝

In eq. (4), 𝐸, 𝐹 and 𝐶𝑟 are the sets of links innetwork topology, FSs on each link, and candidate
channels that fit the number of required FSs fortransmitting connection request 𝑟 by path 𝑝 ,𝑝𝑐𝑓

respectively. 𝛿𝑟is a binary constant thatindicates whether channel 𝑐 containing the FS 𝑓𝑝𝑐
is assigned to connection request 𝑟 on path 𝑝. 𝑥𝑟
is a binary variable, that indicates whether
connection request 𝑟 uses channel 𝑐 on path 𝑝.
2.3 Node/Slot model
Node-type models construct transmission paths
for given connection requests by using variables
corresponding to links as shown in eq. (5). 𝑉, 𝜎𝑣+ ,𝜎𝑣− are the sets of nodes in network topology, links
leaving from node 𝑣, and links entering node 𝑣,respectively. 𝑠𝑟 and 𝑑𝑟 indicate the index of origin
and destination nodes for connection request r,respectively. And 𝑥𝑟𝑒 is a binary variable, that
denotes whether connection request 𝑟 uses link 𝑒.
Eq. (5) using flow conservation law indicates that at
each node in the network, one connection request
can use only one path.
1 𝑖𝑓 𝑣 = 𝑠𝑟
∑ 𝑥𝑟𝑒 − ∑ 𝑥𝑟𝑒 = {−1 𝑖𝑓 𝑣 = 𝑑𝑟(5)−+𝑒∈𝜎0𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒𝑒∈𝜎𝑣𝑣∀𝑣 ∈ 𝑉, 𝑟 ∈ 𝑅
Node/Slot model is a Node-type model that
allocates FSs with the formulation similar to thatof the Path/Slot model.
2.4 Node/Channel model
Node/Channel model is a Node-type model that
constructs transmission paths with the formulation
similar to that of Node/Slot model and allocates FSs

employing a formulation similar to that of thePath/Channel model.
3. Simulation and numerical results
We set the objective functions of all four models
to minimize the maximum index of the FSs used,and perform a comparative simulation experiment
to compare between the models on the N6S9
network which is consisting of 6 nodes and 18
directed links. Table 1 shows the average of theresults of 20 traffic data sets when the number ofconnection requests is 40. The channels used in themodel for both Channel-types (i.e., Path/Channel
and Node/Channel) contain all cases of channels
that can be used in the entire spectrum. “K” is thenumber of candidate paths. “FS index” is the valueof objective at optimal solution.
We can observe that the Path/Channel model
showed overwhelming performance. Considering
the advantages of the model, the availability of thePath/Channel model in large backbone networks(e.g., NSFNET and ARPANET) and more complex
EONs (e.g., space-division multiplexing elasticoptical networks) are also worth being looked
forward to.
References[1] M. Jinno, H. Takara, B. Kozicki, Y. Tsukishima,
Y. Sone and S. Matsuoka, “Spectrum-efficient andscalable elastic optical path network: architecture,benefits, and enabling technologies,” IEEE
Communications Magazine, vol. 47, no. 11, pp.
66~73, 2009.
[2] Y. Wang, X. Cao and Y. Pan, “A study of therouting and spectrum allocation in spectrum-sliced
elastic optical path networks,” 2011 Proceedings
IEEE Infocom, pp. 1503~1511, 2011.

Table 1: Results of comparative experiment at |𝑅| = 40 on N6S9 network
Path/SlotPath/Channel

Node/Slot Node/Channel

K=2

K=3

K=4

K=2

K=3

K=4

FS index

28.05

27.50

27.50

28.05

27.50

27.50

27.50

27.50

Runtime (s)

0.38

14.73

4.69

0.19

0.23

0.29

199.37441.41