Outline! "Interaction between Virtual Network Topology
control and overlay routing
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, Japan** NTT Network Service Systems Laboratories, Japan! "Conflict two different routing objectives! "Degrade stability and performance of the network! "To improve the stability and the performance! "Introduce "hysteresis" to VNT control! "Simulation result! "Hysteresis improves the stability! "Two-state hysteresis improves both the stability and theperformance

Virtual Network Topology Control

Overlay Routing! "Virtual Network Topology control! "Overlay routing! "Constructs an (sub-)optimal VNT for measured traffic
demand matrix by configuring lightpaths! "To balance load or remove bottlenecks in the network! "Overlay routing is performed above the VNT! "Constructs a logical topology on the underlying network! "Performs its routing on that topology! "Advantage of overlay routing! "Enhances functionality (QoS, resilience,...) without
modifying the underlying network (IP network)! "Is easily deployed! "Disadvantage of overlay routing! "Overlay routing and existing routing approaches selecttheir routes independently! "Interaction between these routing approaches

Interaction Between TE and Overlay Routing

Interaction Between VNT control and Overlay Routing! "Interaction between MPLS-based TE and overlay
routing [Liu05]! " The routing objective of VNT control is also different fromthat of overlay routing! "The performance of TE is degraded! "The performance of overlay routing is degraded
depending on physical topologies! "Confliction between two different routing objectives! "TE: optimize the performance of the whole network! "E.g., minimizing maximum link utilization! "Overlay: optimize the performance of the each overlay
node or the overlay network! "E.g., minimizing end-to-end delay, maximizing end-to-end
throughput[Liu05] 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.

! " The same interaction will occur! " The interaction will lead to! " Degradation of the efficiency of VNT! "Overlay routing changes the traffic demand matrix! "The current traffic demand matrix is different from the traffic demandmatrix used for constructing the VNT! " No solution to overcome the instability caused by thisinteraction has been proposed! " Our objective! " To improve the stability and the performance of VNT control
against overlay routing! " Approaches! " Hysteresis

Interaction Between VNT control and Overlay Routing

Interaction Between VNT control and Overlay Routing

Overlay nodeOverlay network
Overlay routing
constructs alogical topology
on the IP network

Route on theoverlay network

Traffic demand on theoverlay network

Actual route

IP router

IP network

The IP network
uses the VNT asits infrastructure

Traffic demand on theIP network (measuredby VNT control)

OXC
VNT control
constructs a VNT on
the WDM network

WDM network
lightpath

Interaction Between VNT control and Overlay Routing
7ms

Delay of the red routeis shorter than that ofthe blue route

4ms

Overlay networkchanges to the newroute (red line)

2ms

Traffic demand isdivided according
to overlay routing

2ms

Overlay routing
causes thechanges in thetraffic demandmatrix

5ms
2ms

Interaction Between VNT control and Overlay Routing

2ms

Delay

Trigger ofVNT control

Interaction Between VNT control and Overlay Routing
Trigger of overlay
routing

1ms

4ms
4ms

2ms

This adaptation
results in thechanges in the delay
1ms

VNT control
regenerates a VNT toadapt the changes inthe traffic demandmatrix due to overlay
routing

4ms
2ms

Delay of the redroute is shorter
than that of theblue route

Interaction Between VNT control and Overlay Routing

Overlay networkchanges the route1ms 4ms

2ms

Traffic demandmatrix is changed
1ms

4ms

2ms

Trigger ofVNT control

4ms

2ms

The
2msinteraction leads tothe instability of traffic
demand, link utilization,and so on.

Simulation Model

Instability of Link Utilization! " Physical topology

Traffic demand for almost allnode pair heavily fluctuates! " European Optical Network: 19 nodes and 39 links! = 0.2! " Network model! " VNT control: minimize maximum link utilization! " IP routing: minimum hop routing (static routing)! " Overlay routing: Select routes that has the maximum available
bandwidth! " Initial traffic demand matrix! " Generate randomly! " Overlay traffic demand: a proportion (!) of the total traffic demand! " Performance metric

Introducing overlay
routing increaseslink utilization

Link utilization
heavily fluctuates! " Maximum link utilization

Hysteresis

Utilization Hysteresis! "Hysteresis is! " Estimate the maximum link utilization on the new VNT, uh,before using it! " Compare uh with the current maximum link utilization, u! "A property of a system that does not immediately reactagainst changes in the environment! "Used to increase tolerance against noise! "Apply hysteresis to VNT control to improve thestability of VNT control! " Only if the improvement in the link utilization is larger than H u, thenew VNT is used
! " Otherwise, the current VNT is kept using! " Reduce unnecessary topology changes! "Apply hysteresis to traffic demand! "Absorb heavy fluctuation of the traffic demand due to overlay
routing! "Utilization hysteresis! "Apply hysteresis to link utilization

Utilization Hysteresis (Result)! = 0.2, H = 0.2

Maximum link utilization! " Improve the stability of the network! "Demand hysteresisuuhChange to thenew VNT even if
improvement issmall

Without hysteresis

uuh

Keep using the current
VNT if improvement issmaller than Hu

Hu
Change to the newVNT only if
improvement islarger than Hu

With hysteresis

Two-state Utilization Hysteresis! = 0.3, H = 0.2

Increase
the ratioof overlay
traffic! " To improve both stability and performance! " Limit the range where utilization hysteresis is applied! " Avoid VNT control slipping into the stable state when the maximum
link utilization is high! " Utilization hysteresis is applied to VNT control only when
the current maximum link utilization is lower than "#uu

! " " = ul + (uu - ul)/kStability is improved

Only the fluctuation due
to overlay routing
appears

Stability is improved,
but link utilization is stillhigh.
Hysteresis threshold H
does not control theutilization in the stablestate.

! "uu , ul: the maximum andminimum value of maximum
link utilization! "uu and ul are updated at(uu - ul)/ kevery round of VNT control! "k: control parameter
The range wherehysteresis is applieduu - ul"#ul

Two-state Utilization Hysteresis (Result)! = 0.3
H = 0.2 Hysteresis

Improve bothstability and performance

Summary! " Interaction between VNT control and overlay routing

Two-state hysteresis (k = 3)

! " Degrade the stability and performance of the network! " To improve stability and performance! " Apply hysteresis to VNT control! " Utilization hysteresis! " Improves the stability! " Does not always improve the performance! " Two-state utilization hysteresis
Large k strongly restricts the range.
Though the utilization in the stablestate is low, the convergence isslow.

It takes long time until VNT
control converges to thestable state because
hysteresis is applied in only
a limited range.

! " Improves both the stability and the performance! " Future work
! " Achieve fast convergence for two-state utilization hysteresis