社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,
INFORMATION AND COMMUNICATION ENGINEERS

信学技報
TECHNICAL REPORT OF IEICE.

オーバーレイネットワークの安定収容のための VNT 制御手法
小泉 佑揮†

宮村

崇††

荒川

伸一†

大木

英司††

塩本 公平††

村田 正幸†† 大阪大学 大学院情報科学研究科†† 日本電信電話株式会社ネットワークサービスシステム研究所
E-mail: †{ykoizumi,arakawa,murata}@ist.osaka-u.ac.jp, ††{miyamura.takashi,oki.eiji,shiomoto.kohei}@lab.ntt.co.jp
あらまし アプリケーションレベルで経路制御（オーバーレイルーティング）を行うことで、サービスが必要とする品質を IP 網上から引き出すオーバーレイネットワークが注目されている。しかし、オーバーレイルーティングとトラヒックエンジニアリングが同一ネットワークに存在すると、互いの経路制御が競合しネットワークの性能および安定性が劣化することが指摘されている。本稿では WDM 技術を用いたトラヒックエンジニアリングである VNT (Virtual Network Topology) 制御とオーバーレイルーティングに着目し、VNT 制御の安定性と性能を向上するための手法を提案する。シミュレーションにより提案手法が VNT 制御の安定性と性能を向上させることを明らかにする。
キーワード

波長分割多重、仮想網制御、オーバーレイルーティング、安定性、ヒステリシス

On the Stability of Virtual Network Topology Control for Overlay Routing
Services
Yuki KOIZUMI† , Takashi MIYAMURA†† , Shin’ichi ARAKAWA† , Eiji OKI†† , Kohei SHIOMOTO†† ,and Masayuki MURATA†† Graduate School of Information Science and Technology, Osaka University†† NTT Network Service Systems Laboratories
E-mail: †{ykoizumi,arakawa,murata}@ist.osaka-u.ac.jp, ††{miyamura.takashi,oki.eiji,shiomoto.kohei}@lab.ntt.co.jp
Abstract Overlay networks achieve new functionality and enhance network performance by allowing routing to be controlled at the application layer. However, these approaches result in degradations of underlying networks due to the selﬁsh behavior of overlay networks. In
this paper, we investigate the stability of virtual network topology (VNT) control under the overlay networks that perform dynamic routing
updates. We reveal that the dynamics of routing on overlay networks cause a high ﬂuctuation in the traﬃc demand, which leads to signiﬁcantinstability of VNT control. To overcome the instability induced by the overlay routing, we introduce three extensions, utilization hysteresis,
two-state utilization hysteresis, and ﬁltering, to VNT control. Through simulations, we show that our methods achieve the stability against
overlay routing without the loss of the adaptability for changes in the traﬃc demand.
Key words Wavelength Division Multiplexing, VNT Control, Overlay Routing, Stability, Hysteresis

1 Introduction
Wavelength Division Multiplexing (WDM) technology, which
carries multiple wavelength channels on a single ﬁber, is expectedto accommodate a huge amount of traﬃc in the current and future Internet. Since the majority of Internet traﬃc is IP, much research has been devoted to methods of carrying IP packets over a
WDM network [1–5]. One approach to accommodate IP traﬃc on a
WDM network is to establish lightpaths between IP routers via optical cross-connects (OXCs). These lightpaths and IP routers forma virtual network topology (VNT) and IP traﬃc is transmitted overthis VNT. To achieve the eﬀective transport of IP traﬃc, VNT con-trol, which conﬁgures VNTs based on the traﬃc demand, has beenstudied [6, 7].
Overlay networks have recently received much attention as a way
to realize new functionality or enhance network performance over
IP networks. One of the key technologies in overlay networks lies
in overlay routing [8, 9]. The fundamental idea of overlay routing
is to construct a logical network above the IP network and to allow
routing to be controlled on that logical topology. In the literature,a virtual network topology provided by a set of lightpaths is sometimes called logical topology. In this paper, we use the term “logical
topology” in the context of an overlay’s logical topology, and use
the term “VNT” for virtual network topology provided by the light—1—

paths. Each overlay node measures status, such as throughput anddelay, of the underlying network, and determines the appropriate
route on the overlay network to improve the performance. The resilient overlay network (RON) architecture is proposed in [8]. RON
provides fast detection and recovery from network failures or performance degradation using the existing Internet infrastructure as
the underlay network. Another architecture is Detour [9]. In [9], itis revealed that a large percentage of ﬂows can ﬁnd better alternative routes by relaying among overlay nodes, which improves theperformance of those ﬂows.
As the amount of traﬃc generated by overlay networks increases,
the dynamics of overlay routing have signiﬁcant impacts on VNT
control. One typical impact is the selﬁsh behavior of overlay routing
as discussed in [10]. Since overlay nodes independently select theirroute in a selﬁsh manner to optimize their own performance, thesystem-wide performance may not be optimized. Another impact
on VNT control is the heavy ﬂuctuation in the traﬃc demand induced by overlay routing. Since origin-destination pairs in overlay
networks traverse several source-destination pairs in IP networks,
the traﬃc demand of the IP networks strongly depends on the overlay routing. When the VNT is reconﬁgured in response to changes
in the traﬃc demand due to the overlay routing, the network statusmeasured at the overlay network may be changed. This leads to there-adaptation of the overlay network via overlay routing, which inturn changes in the traﬃc demand for VNT control. In this way, thecoexistence of overlay routing and VNT control leads to a heavy
ﬂuctuation in the traﬃc demand.
The interaction between overlay routing and packet layer trafﬁc engineering (TE) has been studied in many papers [11, 12]. In
the packet layer TE, the routing of IP traﬃc is controlled to satisfy
its quality requirements. In [12], it is revealed that the interaction
between overlay routing and packet layer TE degrades the performance of TE. However, these papers show that the performance ofthe packet layer TE is degraded in terms of maximum link utilization, network cost, and average latency. Since VNT is conﬁgured
according to the traﬃc demand, the ﬂuctuation in the traﬃc demand
induced by overlay routing is much more serious for VNT control.
In this paper, we consider a network where an overlay network
performs dynamic routing based on its own policy above a VNT.
We ﬁrst show that overlay routing highly degrades the performanceof VNT control. Then we show the instability due to the interaction appears in link utilization and traﬃc demand. To overcome thisinstability and achieve a stable VNT control method against overlay routing, we propose three extensions for VNT control. First, toimprove the stability of VNT control, we introduce utilization hysteresis. We show that utilization hysteresis improves the stability,
but does not always improve the performance. We extend utilization hysteresis, two-state utilization hysteresis, and show that thisimproves both the stability and the performance of VNT control.
However, two-state utilization hysteresis requires a long time until
VNT control becomes stable. Thus, we achieve the fast convergence by adopting a ﬁltering method, which reduces small changes
in VNTs. Finally, we show that our methods follow changes in thetraﬃc demand, and therefore we achieve stable VNT control against
overlay routing.
The rest of this paper is organized as follows. In Section 2, weshow that overlay routing degrades performance of the underlay network and the coexistence of overlay routing and VNT control resultsin signiﬁcant instability of the underlay network. We introduce utilization hysteresis to overcome the instability in Section 3, and showthat this does not always improve the performance. Thus, in Section 4, we extend utilization hysteresis. Although two-state utiliza-

Overlay node 1
Overlay node 6

Overlay layer(Overlay network)
Overlay traffic

Overlay node 5
IP router 4
IP router 1
Non-overlay
IP router 6

traffic

Packet layer(IP network)

IP router 3

IP router 5
IP router 2
OXC 4
OXC 1
OXC 6

Optical layer(WDM network)

OXC 3
OXC 5

OXC 2

Fig. 1 An example of a network consists of three layers; optical, packet,
and overlay layers.

tion hysteresis improves both the stability and the performance, ittakes long time until VNT control gets stable. Therefore, we introduce a ﬁltering method and achieve the fast convergence in Section 5. In Section 6, we show the adaptability of our methods for thechanges in the traﬃc demand, and we ﬁnally conclude this paper in
Section 7.

2 Instability of Network StateIn this section, we investigate the inﬂuence of overlay routing on
the dynamically conﬁgured VNT.
2. 1 Network ModelIn our view, a network consists of three layers: an optical layer, apacket layer, and an overlay layer as shown in Fig. 1. On the opticallayer, the WDM network consists of OXCs and ﬁbers. VNT control conﬁgures lightpaths between IP routers via OXCs and theselightpaths and IP routers form a VNT. On the packet layer, packets are forwarded along the routes that are decided by IP routing on
this VNT. On the overlay layer, overlay nodes built on the packet
layer form an overlay network. In this network, two types of traﬃc
are carried over the VNT: the traﬃc from overlay networks and thetraﬃc from non-overlay networks, which are illustrated as solid anddashed arrows in Fig. 1, respectively. We refer to overlay traﬃc as
the traﬃc in the overlay network and to non-overlay traﬃc as thetraﬃc in the non-overlay network. We also use the term underlay
traﬃc for all traﬃc on the VNT, which contains overlay traﬃc andnon-overlay traﬃc. In Fig. 1, a VNT that has six IP routers andnine links is conﬁgured. On this VNT, three overlay nodes form an
overlay network. Solid arrows show overlay traﬃc from the overlay
node 1 to 6 and dashed arrows show non-overlay traﬃc from the IP
router 1 to 6. The overlay traﬃc in this ﬁgure is forwarded from theoverlay node 1 to 6 by relaying through the overlay node 5. Overlay
links are transport tunnels over the IP network in the sense that thetraﬃc on the overlay links is forwarded on the IP network and its
route on the IP network is decided by IP routing. Thus, the traﬃcon the overlay link between the overlay node 1 and 5 is forwarded
along the route decided by IP routing, that is, from the IP router 1
to 5 through the IP router 2. Then, the overlay traﬃc is forwarded
from the overlay node 5 to 6 in the same way. In this case, the traﬃcdemand from the overlay node 1 to 6 is recognized as the two separated traﬃc demand, which are the traﬃc demand from IP router 1—2—

to 5 and 5 to 6, by IP network or VNT control. Therefore, overlay
routing causes the changes in the traﬃc demand. The non-overlay
traﬃc is forwarded from the IP router 1 to 6 through the router 3,
which is also controlled by IP routing. In this paper, we investigate
an interaction between overlay routing and VNT control through the
IP layer. Before we introduce this interaction, we describe overlay
routing and VNT control more precisely.
2. 2 Overlay routing
Several routing policies for overlay networks such as overlay selfish routing and overlay optimal routing are proposed and evaluatedin many papers [11, 13, 14]. Among them, we use overlay selfish routing where each overlay node selects the route that has thelargest available bandwidth. The available bandwidth al on link l is
al = cl − xl , where cl is the capacity of l. The available bandwidthalong route r is represented by a(r) = minl∈r (al ). The overlay network selects the route r that satisﬁes a(r) = maxi∈R a(i), where R
denotes the set of all possible routes.
Several papers propose to improve the performance of the overlay
network by relaxing the selﬁshness or greediness of overlay routing [14]. Moreover, the overlay selﬁsh routing of which the routing
metric is the available bandwidth is one of the greediest overlay
routing services as reported in [14]. In this paper, since our objective is to obtain a robust VNT control method against selﬁsh andgreedy overlay networks, we use the overlay network that selects
the route with the most available bandwidth and do not assume thatit employ those cooperative approaches.
2. 3 VNT control
The VNT is conﬁgured according to its performance objectiveby the VNT control method. Many VNT control algorithms forachieving their performance objectives, such as minimizing average
weighted number of hops, minimizing maximum link utilization,
maximizing single hop traﬃc, and minimizing average delay, arestudied [6, 7, 15, 16]. Since the link utilization directly aﬀects theavailable bandwidth, which the overlay network seeks to optimize,
we employ algorithms for minimizing the maximizing link utilization to investigate the interaction between VNT control and overlay routing. For minimizing the maximum link utilization, MLDA
(Minimum delay Logical topology Design Algorithm) [7] is studied. MLDA aims at minimizing average delay as its performance
objective by solving the RWA problem, but the main objective for
conﬁguring VNTs is to minimize the maximum link utilization.
MLDA conﬁgures a VNT according to traﬃc demand to optimize
its performance objective. Note that VNT control does note distinguish between the traﬃc demand due to the overlay traﬃc and thenon-overlay traﬃc.
2. 4 Interaction between overlay routing and VNT control
A model for evaluating an interaction between overlay routing
and packet layer TE is introduced in [12]. The model consists ofan overlay layer and a packet layer. In this paper, we introduce an
optical layer into that model and evaluate the interaction between
overlay routing and VNT control through the packet layer. Fig. 2 illustrates our model. When the overlay network switches its routes,
the traﬃc demand in the packet layer is changed. To response to thistraﬃc change, VNT control reconﬁgures its VNT. This reconﬁguration changes the available bandwidth. The overlay network again
switches to the new route that is superior to the previous route. In
our simulation experiments, each layer takes the above-mentioned
actions alternately. More speciﬁcally, overlay routing makes its decisions at odd rounds and VNT control reconﬁgures its topology ateven rounds. Since our main purpose is to investigate the interaction
between overlay routing and VNT control, minimum hop routing isused in the packet layer.

Overlay
Traffic

Available Capacity

Overlay Network

Overlay Routing
Multiplexed
Traffic Demand

Packet Layer (VNT)

Underlay Routing(OSPF)

Overlay

Optical Layer

Traffic Demand
Non-overlay

VNT Control

Traffic Demand

Provide VNTFig. 2 The interaction between VNT control and overlay routing.

Fig. 3 European Optical Network (EON) topology.

2. 5 Simulation model
We evaluate the interaction described above with the maximum
link utilization, which is the total amount of traﬃc on a link divided by its capacity. Note that a link is overloaded if the utilization
exceeds 1, and in this case, no bandwidth is available at this link.
We set the capacity of one lightpath to 1 and all traﬃc used in ourevaluation is normalized by the capacity of a lightpath. An overlay network constructs a fully connected topology in the same way
as the environments in [8, 11]. We place overlay nodes on all IP
routers. Each overlay node independently selects routes with thelargest available bandwidth. We assign a proportion of the underlay traﬃc demand, D, as overlay traﬃc demand, Do , and the rest as
non-overlay traﬃc demand, Dn , that is, the traﬃc demand of overlay
traﬃc is Do = α·D, and that of non-overlay traﬃc is Dn = (1−α)·D.
We use a randomly generated traﬃc demand in the following evaluations. We use the European Optical Network (EON) topology with
19 nodes and 39 bidirectional links (Fig. 3) for the physical topology. Each node has 8 input ports and 8 output ports and each ﬁber
has enough wavelengths to accommodate lightpaths. That is, thenumber of lightpaths is constrained by the number of ports.
2. 6 Degradation of Underlay Network Performance
For the purposes of comparison, we use ﬁber topologies, wherelightpaths are statically conﬁgured on a single ﬁber, i.e., the VNTis equivalent to the physical topology, and the conﬁgured topology
is ﬁxed. We show the maximum link utilization in Fig. 4. The
horizontal axis shows the total amount of traﬃc demand and thevertical axis shows the maximum link utilization. We observe thatthe maximum link utilization increases as α increases. With a small
amount of overlay traﬃc (α = 0.1), the maximum link utilizationof MLDA with overlay traﬃc is twice as large as the result without overlay traﬃc, and a slight degradation is observed in the caseof the ﬁber topology. Although the utilization of the ﬁber topology
gets larger as α increases, the utilization of MLDA increases much
more severely compared to the result of the ﬁber topology. Two
factors are considered for this degradation. One is due to the interaction between overlay nodes, and another is due to the interaction
between overlay routing and VNT control. We refer to the interaction between overlay routing and VNT control as the vertical interaction and the interaction between overlay nodes as the horizontal
—3—

0.2
0
0

5

10 15 20 25 30
Total Traffic Demand

0.6
No Overlay
α=0.1
α=0.2
α=0.3
α=0.4
α=0.5

0.4
0.2
0

35

40

0

(a) Fiber topology

5

10 15 20 25 30
Total Traffic Demand

35

0.6

0.4

0.2

200

300

0.8

0.6

0.4

0.2

0
0

400

100

Round

200

300

1.5

1.5

Traffic Demand

Traffic DemandFig. 5 Fluctuation of maximum link utilization (α = 0.2, Total traﬃc: 10).
2

1

0.5

0
0

100

200
Node Pair ID(a) Fiber topology

300

1

0.5

0
0

100

100

200
Round

300

400

(b) Utilization Hysteresis

200
Node Pair ID

1.5

1

0.5

0
0

(b) MLDA

2

0
0

400

1

0.5

400

Round

(a) Fiber topology

300

1.5

1

Maximum Link Utilization

Maximum Link Utilization

Maximum Link Utilization

1

200
Round

0.5

Fig. 7 Fluctuation of maximum link utilization (H = 0.4, α = 0.2, Total
traﬃc: 10).

1.2

0.8

100

1

(a) No Hysteresis

Fig. 4 Maximum link utilization.

100

0.5

(b) MLDA

1.2

0
0

1

0
0

40

1.5

Maximum Link Utilization

No Overlay
α=0.1
α=0.2
α=0.3
α=0.4
α=0.5

0.4

Maximum Link Utilization

0.6

0.8

Maximum Link Utilization

1.5

1Maximum Link Utilization

Maximum Link Utilization

1
0.8

300

(b) MLDA

Fig. 6 Fluctuation of traﬃc demand (α = 0.2, Total traﬃc: 10).

interaction. Note that only the horizontal interaction appears in theﬁber topology since no VNT reconﬁguration is made. In the case of
MLDA, both the vertical interaction and the horizontal interaction
degrade the maximum link utilization since a VNT is reconﬁgured
in response to the dynamics of overlay routing.
2. 7 Instability due to Coexistence of Two Routing
In this section, we show that the vertical interaction leads to instability of VNT control. Fig. 5 shows that the maximum link utilization depends on the rounds at which VNT control or overlay routing
take their actions. As we described above, for both MLDA and ﬁber
topology, the maximum link utilization gets high, if the amount of
the overlay traﬃc is larger than 0.1. Therefore, we set α to 0.2 in thisﬁgure and observe the reason for the degradation mentioned above.
When a VNT is dynamically controlled (i.e., MLDA is applied), theﬂuctuation of the maximum link utilization is larger and the cycleof the ﬂuctuation is irregular. That is, the network becomes unstable
due to the vertical interaction.
Fig. 6 shows the traﬃc demand for each node pair. The error bars
show the maximum and minimum values of the traﬃc demand in
the evaluation and a point in the bar indicates the average value. The
horizontal axis represents the node pair ID that is speciﬁed uniquelyby the source-destination pair. It is observed that the traﬃc demand
ﬂuctuates drastically when the VNT is dynamically controlled by
MLDA. The vertical interaction degrades the stability and the performance of the network drastically. The main reason for this instability is that the VNT control algorithms generate VNTs according
to the traﬃc demand. As shown in Fig. 6, overlay routing causes
the extreme changes in the traﬃc demand. Since VNT control conﬁgures VNTs according to the traﬃc demand, the ﬂuctuation of thetraﬃc demand leads to a signiﬁcant instability of VNT control.

3 Improvements in Stability of Network StateIn this section, we apply hysteresis to VNT control to overcome
the instability due to the vertical interaction.
3. 1 Utilization Hysteresis
Hysteresis is the property of systems that do not immediately react against changes in environments. This property is often used to

100

200
Round

300

(a) No Hysteresis

400

0
0

100

200
Round

300

400

(b) Utilization Hysteresis

Fig. 8 Fluctuation of maximum link utilization (H = 0.4, α = 0.3, Total
traﬃc: 10).

avoid routing ﬂuctuation [8, 14, 17]. Since the instability appears in
the maximum link utilization as presented in the previous section,
we apply hysteresis to the maximum link utilization. We refer to thisapplication of hysteresis as utilization hysteresis. Utilization hysteresis works as follows. First, we temporarily calculate the VNT,
C h (t), using the current traﬃc demand D(t). Then, we estimate thelink utilization on C h (t), U h (t), using D(t) and C h (t). We next compare the maximum link utilization max(U h (t)) with max(U(t − 1)),
where U(t − 1) is the link utilization after the overlay network updates its route. If the improvement in the maximum link utilizationis larger than the ratio of a hysteresis threshold H, we use C h (t) as
the new VNT. Utilization hysteresis is formulated as follows,
{ h
C (t)
if max(U h (t)) < (1 − H) · max(U(t − 1))
C(t) =.
C(t − 2) otherwise
Utilization hysteresis stabilizes VNT control by keeping the current
VNT if the beneﬁt of changing to the new VNT is small.
3. 2 Performance Evaluation
We use the same simulation model as presented in Section 2.
In obtaining the following ﬁgures, the hysteresis mechanisms are
not applied during the ﬁrst 20 rounds to ignore the transient phase.
Fig. 7 shows the ﬂuctuation of the maximum link utilization. We set
the hysteresis threshold H to 0.4. This ﬁgure clearly shows that the
maximum link utilization with utilization hysteresis is stable compared to the results without hysteresis. We change the ratio of overlay traﬃc α from 0.2 to 0.3 in Fig. 8. Although the maximum link
utilization of VNT control with utilization hysteresis is stable, theutilization with utilization hysteresis is higher than that without hysteresis. Due to the space limitation, we omit to show the result ofother hysteresis threshold values. These results also indicate thatutilization hysteresis does not always improve the maximum link
utilization and the link utilization in the stable state does not dependon the hysteresis threshold H. The reason for this is that routes ofthe overlay network ﬂap between approximately two routes if the
VNT is ﬁxed. Hence, the VNT control method with utilization hysteresis slips into a stable state when it decides to keep using thecurrent VNT for two consecutive rounds of VNT control.

4 Improvements in Network Performance
Applying utilization hysteresis to VNT control improves the stability of the network, but does not always improve the performance.
In this section, we extend utilization hysteresis to improve both thestability and the performance.
4. 1 Two-State Utilization Hysteresis
We extend utilization hysteresis and propose two-state utilization
—4—

1.5

0
0

100

200
Round

300

0
0

400

(a) Utilization Hysteresis

0.5

100

200
Round

300

400

0.5

300

(a) Utilization Hysteresis

3

2

1

400

200

300

400

0.5

100

200
Round

3

2

1

0
0

500

100

200

300

400

(b) Two-State Utilization Hysteresis

Fig. 10 Fluctuation of maximum link utilization (k = 5.0, H = 0.4,
α = 0.3, Total traﬃc: 10).

hysteresis to prevent VNT control from slipping into a stable state
when the maximum link utilization is high. For this purpose, we
introduce another threshold θ that controls whether utilization hysteresis is applied or not. We deﬁne the threshold θ = ul + (uu − ul )/kwhere ul and uu are the minimum and maximum value of the maximum link utilization obtained so far, respectively, and k is a control
parameter for adjusting θ. The utilization ul and uu are updated every time when VNT control is performed. When u is higher thanθ, VNT control regards that the maximum link utilization of thecurrent VNT is high. In this case, utilization hysteresis is not applied to VNT control, and the VNT is immediately reconﬁgured to
avoid slipping into a stable state that has high maximum link utilization. Otherwise, utilization hysteresis is applied. Then VNT
control again searches another stable state where the maximum link
utilization is suﬃciently low.
4. 2 Performance Evaluation
We evaluate two-state utilization hysteresis under the same simulation model as the previous section. The simulation parameters are
set to the same ones as in Fig. 8. Figs. 9 and 10 show the ﬂuctuationof the maximum link utilization in the case that k is 3.0 and 5.0,
respectively. These ﬁgures clearly indicate that VNT control getsstable and the maximum link utilization is lower than that in Fig. 8.
However, these ﬁgures also show that the convergence time, which
is deﬁned as the time until the VNT gets stable, becomes longer
than that in Fig. 8. This is because that a larger value of k more
restricts the region where utilization hysteresis is applied, and thus
it is more diﬃcult to seek the stable state that has lower maximum
link utilization. In the next section, we show another extension to
make the convergence time shorter.

5 Fast Convergence of VNT Control
Two-state utilization hysteresis makes the convergence time
longer, since two-state utilization hysteresis restricts the region
where utilization hysteresis is applied. In this section, we introduce
a ﬁltering method to achieve the fast convergence.
5. 1 Filtering Method against Small Changes in VNT
We observe the number of lightpaths between node pairs. We
select two node pairs that have the typical tendency that we will
describe later and show the result in Fig. 11. The horizontal axis
shows the rounds and the vertical axis shows the number of lightpaths between a node pair. The node ID in this ﬁgure is shown in
Fig. 3. In Fig. 11(a), one lightpath is conﬁgured from the node 0 to
the node 1 at the most of rounds, but at rounds 60, 160, and 350, two

300

400

500

Round

(a) Node Pair (0, 1)(b) Node Pair (10, 9)

Fig. 11 Number of lightpaths (α = 0.3, Total traﬃc: 10, Number of ports:
8, k = 5.0)
1.5

1

0
0

100

4

Round

Maximum Link Utilization

1

200
Round

5

4

0
0

1.5
Maximum Link Utilization

Maximum Link Utilization

1.5

100

5

(b) Two-State Utilization Hysteresis

Fig. 9 Fluctuation of maximum link utilization (k = 3.0, H = 0.4, α = 0.3,
Total traﬃc: 10).

006Number of lightpaths

0.5

1

from 10 to 9

6

1.5
Maximum Link Utilization

1

from 0 to 1

Number of lightpaths

Maximum Link Utilization

Maximum Link Utilization

1.5

1

0.5

0
0

100

200
Round

300

(a) No Filtering

400

1

0.5

0
0

100

200
Round

300

400

(b) Filtering

Fig. 12 Fluctuation of maximum link utilization (Two-state utilization hysteresis, k = 5.0, α = 0.3, Total traﬃc: 10).

lightpaths are conﬁgured in a very short period. Finally, the numberof lightpaths in this node pair converges to 1. In Fig. 11(b), although
the number of lightpaths also decreases or increases in a very shortperiod, two lightpaths are conﬁgured at almost all rounds and thenumber of lightpaths ﬁnally converges to 2. We ﬁnd these results inmore than half of all node pairs. These many small changes in thenumber of lightpaths result in a large change in the VNT.
Therefore, we introduce a ﬁltering method to reduce those smallchanges in the number of lightpaths and achieve the fast convergence of VNT control. The VNT control method with the ﬁltering
method maintains the history of the number of lightpaths that the
VNT control method calculated, that is, C h (t) = {chp (t)} described in
Section 3. Here, we maintain the history of the past 20 rounds of
the VNT control method, (C h (t − 2), C h (t − 4), . . . , C h (t − 40)). If nlightpaths were conﬁgured between a node pair p at more than 80%
rounds in this history, the number of lightpaths between p is set ton even if chp (t) is diﬀerent from n.
5. 2 Performance Evaluation
We evaluate the ﬁltering method under the same simulation environments as those in the previous section. The simulation parameters are set to the same ones as in Fig. 10. The convergence timein Fig. 12(b) is 110 while that in Fig. 12(a) is 360. We also omit toshow other results due to the space limitation, but other results showthat the ﬁltering method reduces the convergence time.

6 Adaptability for Changes in Traﬃc Demand
Both the hysteresis mechanism and the ﬁltering mechanism aim
at improving the stability of VNT control by reducing unnecessarychanges in the VNT. In general, these types of approaches degrade
the adaptability for the changes in the traﬃc demand, since the VNTdesigned for the old traﬃc demand remains. In this section, weshow the adaptability of our method for the changes in the traﬃcdemand.
For evaluating the adaptability, we randomly regenerate the trafﬁc demand at the same interval with holding the sum of the traﬃcdemand constant. We refer to this interval as the changing interval.
Other simulation conditions are the same as those in the previous
section. Fig. 13 shows that the maximum link utilization depends
on the rounds for k = 3.0. In the case that the changing interval is 40(i.e., 20 VNT reconﬁgurations) VNT control follows the almost allchanges in the traﬃc demand, but only at the round 1440 and 1480,
VNT control does not converge until the next traﬃc change occurs.
If the changing interval is longer than 40, VNT control converges

—5—

1.2

1

1

Maximum link utilization

Maximum link utilization

1.2

0.8
0.6
0.4
0.2

0.6
0.4
0.2

0

0
0

200 400 600 800 1000 1200 1400 1600 1800 2000
Round

0

200 400 600 800 1000 1200 1400 1600 1800 2000
Round(a) Changing interval: 400(b) Changing interval: 200

1.2

1.2

1

Maximum link utilization

Maximum link utilization

0.8

0.8
0.6
0.4
0.2

1
0.8
0.6
0.4
0.2

0

0
0

200 400 600 800 1000 1200 1400 1600 1800 2000
Round

0

(c) Changing interval: 100

200 400 600 800 1000 1200 1400 1600 1800 2000
Round(d) Changing interval: 40

Fig. 13 Fluctuation of maximum link utilization (Two-state utilization hysteresis, ﬁltering, α = 0.2, Total traﬃc: 10, Number of ports: 8,
k = 3.0).
1.2

1Maximum link utilization

Maximum link utilization

1.2

0.8
0.6
0.4
0.2

0.6
0.4

0
0

200 400 600 800 1000 1200 1400 1600 1800 2000
Round

0

200 400 600 800 1000 1200 1400 1600 1800 2000
Round(a) Changing interval: 400(b) Changing interval: 200

1.2

1.2

1

Maximum link utilization

Maximum link utilization

1
0.8

0.2

0

0.8
0.6
0.4
0.2

1
0.8
0.6
0.4
0.2

0

0
0

200 400 600 800 1000 1200 1400 1600 1800 2000
Round(c) Changing interval: 100

control. Through simulations, we showed that the ﬁltering method
makes the convergence time shorter. Both the hysteresis method andthe ﬁltering method aim at improving the stability of VNT control
by reducing unnecessary changes in the VNT. Finally, we show that
our approaches achieve the good adaptability for the changes in thetraﬃc demand, since VNT control with our proposals reconﬁgures
VNTs immediately if the maximum link utilization gets high due tothe traﬃc change.
References0

200 400 600 800 1000 1200 1400 1600 1800 2000
Round(d) Changing interval: 40

Fig. 14 Fluctuation of maximum link utilization (Two-state utilization hysteresis, ﬁltering, α = 0.2, Total traﬃc: 10, Number of ports: 8,
k = 5.0).

although the maximum link utilization ﬂuctuates in a short period
after the traﬃc change occurs. We next evaluate the adaptability fork = 5.0 in Fig. 14. VNT control does not follow the changes in thetraﬃc demand in the case that the changing interval is 40. If thelarge k is used, the region where hysteresis is applied becomes narrow and therefore the convergence time becomes longer. This also
results in the degradation of the adaptability for the traﬃc changes.
In the case that the changing interval is 100, VNT control follows
the almost all changes in the traﬃc demand except at the round 200.
Although our methods do not follow the extremely heavy changes
in the traﬃc demand, they show the acceptable adaptability. The
reason for this is that VNT control with our proposals reconﬁgures
its VNT immediately if the performance of the VNT is degraded
due to the changes in the traﬃc demand.

7 Conclusion
In this paper, we investigated the interaction between VNT control and overlay routing. We revealed that this interaction causes
high ﬂuctuations in traﬃc demand, which leads to a signiﬁcant instability of VNT control. To overcome the instability and to make
VNT control more stable, we proposed utilization hysteresis for
VNT control. We found that utilization hysteresis improves the stability, but does not always improve the maximum link utilization.
We therefore proposed two-state utilization hysteresis that applies
utilization hysteresis only when the maximum link utilization is sufﬁciently low. Simulation results indicated that two-state utilization
hysteresis improves both the stability and the maximum link utilization. However, the convergence time becomes longer. To achieve
the fast convergence, we introduced the ﬁltering method to VNT[1] J. Li, G. Mohan, E. C. Tien, and K. C. Chua, “Dynamic routing
with inaccurate link state information in integrated IP over WDM
networks,” Computer Networks, vol. 46, pp. 829–851, Dec. 2004.
[2] T. Ye, Q. Zeng, Y. Su, L. Leng, W. Wei, Z. Zhang, W. Guo, andY. Jin, “On-line integrated routing in dynamic multiﬁber IP/WDM
networks,” IEEE Journal on Selected Areas in Communications,vol. 22, pp. 1681–1691, Nov. 2004.
[3] S. Arakawa, M. Murata, and H. Miyahara, “Functional partitioning for multi-layer survivability in IP over WDM networks,” IEICE
Transactions on Communications, vol. E83-B, pp. 2224–2233, Oct.
2000.
[4] J. Comellas, R. Martinez, J. Prat, V. Sales, and G. Junyent, “Integrated IP/WDM routing in GMPLS-based optical networks,” IEEE
Network Magazine, vol. 17, pp. 22–27, Mar./Apr. 2003.
[5] Y. Koizumi, S. Arakawa, and M. Murata, “An integrated routing mechanism for cross-layer traﬃc engineering in IP over WDM
networks,” IEICE Transactions on Communications, vol. E90-B,
pp. 1142–1151, May 2007.
[6] B. Mukherjee, D. Banerjee, S. Ramamurthy, and A. Mukherjee,“Some principles for designing a wide-area WDM optical network,”
IEEE/ACM Transactions on Networking, vol. 4, no. 5, pp. 684–696,
1996.
[7] R. Ramaswami and K. N. Sivarajan, “Design of logical topologies
for wavelength-routed optical networks,” IEEE Journal on Selected
Areas in Communications, vol. 14, pp. 840–851, June 1996.
[8] D. G. Andersen, H. Balakrishnan, M. F. Kaashoek, and R. Morris,“Resilient overlay networks,” in Proceedings of SOSP, Oct. 2001.
[9] S. Savage, T. Anderson, A. Aggarwal, D. Becker, N. Cardwell,
A. Collins, E. Hoﬀman, J. Snell, A. Vahdat, G. Voelker, and J. Zahorjan, “Detour: a case for informed internet routing and transport,”
IEEE Micro, vol. 19, pp. 50–59, Jan. 1999.
[10] T. Roughgarden and E. Tardos, “How bad is selﬁsh routing?,” Journal of the ACM, vol. 49, pp. 236–259, Mar. 2002.
[11] L. Qiu, Y. R. Yang, Y. Zhang, and S. Shenker, “On selﬁsh routing
in internet-like environments,” in Proceedings of ACM SIGCOMM,
Aug. 2003.
[12] Y. Liu, H. Zhang, W. Gong, and D. Towsley, “On the interaction between overlay routing and underlay routing,” in Proceedings of IEEE
INFOCOM, pp. 2543–2553, Mar. 2005.
[13] W. Jiang, D.-M. Chiu, and J. C. S. Lui, “On the interaction of multiple overlay routing,” Performance Evaluation, vol. 62, pp. 229–246,
Oct. 2005.
[14] M. Seshadri and R. H. Katz, “Dynamics of simultaneous overlay network routing,” Tech. Rep. UCB/CSD-03-1291, EECS Department,
University of California, Berkeley, 2003.
[15] R. Dutta and G. N. Rouskas, “A survey of virtual topology design algorithms for wavelength routed optical networks,” Optical Networks
Magazine, vol. 1, pp. 73–89, Jan. 2000.
[16] J. Katou, S. Arakawa, and M. Murata, “A design method for logical
topologies with stable packet routing in IP over WDM networks,” IEICE Transactions on Communications, vol. E86-B, pp. 2350–2357,
Aug. 2003.
[17] R. Gao, C. Dovrolis, and E. W. Zegura, “Avoiding oscillations due
to intelligent route control systems,” in Proceedings of IEEE INFOCOM, Apr. 2006.

—6—