Outline
 Background

Multilayer traffic engineering
Impact of estimation errors of traffic matrix

Gradual Reconfiguration of
Virtual Network Topologies
based on Estimated Traffic Matrices
Yuichi Ohsita
Osaka University
2/18/2008

INFOCOM 2007

 Gradual reconfiguration method based on theestimated traffic matrix
Reconfiguration method to limit the number ofadded/deleted optical paths
Estimation method using the additional information ofchange in routes caused by the VNT reconfiguration
 Evaluation
 Conclusion

12

INFOCOM 2007

2/18/2008

Traffic engineering (TE) in multilayer network

IP / optical multi-layer network
 Packet layer Packet layer TEPacket-layer traffic is routed over the VNT

Optimize the routesof packet paths

 Optical layer

A set of optical paths forms a VNT.
By adding or deleting optical paths, we can easilychange the logical topology

packet layer TE multilayer TE

 Optical layer TE

Reconfigure the VNTWithout TE

optical layer TE Multi-layer TE

Optimize both packet-layer and optical layer
Achieve more efficient accommodation of traffic
Need traffic matrices as an input
INFOCOM 2007

2/18/20083

Traffic matrix estimation

INFOCOM 2007

2/18/2008

4

Goal of this work

 Estimate from the link utilizations
X: link utilization
A：Routing matrix
T: Traffic matrix

X = AT VNT reconfiguration taking traffic matrix estimation

The number of equations is much smaller than thenumber of entries in traffic matrix

into consideration
Limit the impact of estimation errors
 Gradual reconfiguration

 Number of equations:

number of links
 Number of entries: (number of nodes)2

Divide the VNT transition sequence into multiple stages
Limit the number of addition or deletion of optical paths at a stage

 Estimated traffic matrices include estimation errors

Reduce the estimation errors by collaborating with trafficmatrix estimation

 The estimation errors degrade the performance Traffic matrix estimation method using information monitored at

multiple stagesof traffic engineering
We need a VNT reconfiguration method which is robust toestimation errors
2/18/2008

INFOCOM 20075

2/18/2008

INFOCOM 2007

61

Relation between VNT reconfiguration andtraffic matrix estimation

Overview of gradual reconfiguration
 If we change the current VNT to the optimal VNT atonce
TM estimation

Estimation errors degrade the performance of TE for a longtime
Reconfiguration Period

VNT reconfiguration

Reconfiguration Period

Traffic matrix
Monitoring link utilizations
VNT
estimation
reconfiguration

 Gradual reconfiguration

Add the information monitored at
previous stages

Estimation VNT
reconfiguration

We divide the whole VNT transition sequence into multiplestages

 As stages go on

Traffic matrix estimation:

Reconfiguration Period
Reconfiguration Period
Monitoring link utilizations
・・・・・・・・・・・・・・・・・
Stage 1

2

Estimation
VNT2/18/2008
reconfiguration3

 Use more information

VNT reconfiguration:

kEstimation
7

INFOCOM 2007 VNT reconfiguration

2/18/2008

Algorithm for gradual reconfiguration
 VNT reconfiguration with the limitation of number of

optical paths added/deleted at a stage.

to the simultaneous equations⎡ X 0 ⎤ ⎡ A0 ⎤⎢ M ⎥ = ⎢ M ⎥T⎢ ⎥ ⎢ ⎥⎣⎢ X n ⎦⎥ ⎣⎢ An ⎦⎥ Minimize the constructed optical paths

 Method:

Perform following Steps Nr times
 Calculate the link utilizations by using the estimatedtraffic matrix
 If the maximum link utilization is more than Th

INFOCOM 2007

X n：Link utilization at stage n
An：Routing matrix at stage n

The number of equations increases as stages go on
Estimation errors are reduced as stages go on

Add an optical path to reroute the congested path
The optical path is torn down for resource reclamation

910

INFOCOM 2007

2/18/2008

Result (Estimation errors)

Evaluation
 Simulation Conditions

Compare additional equation method with Tomogravity method
Additional equation method reduce the estimation errors dramaticallyAbout setting Nr, there is a trade-off between convergence time andestimation errors

Topology
 Backbone topology of Abilene Maximum number of wavelength：64

Traffic demand：

To estimate more accurately, small Nr is better
Small Nr needs a lot of stages to converge

 Generate sudden change to traffic demand

Nr=1
Nr=3
Nr=5

monitored at Abilene
 We assume the traffic matrix is constant after thebeginning of reconfiguration

Nr=1
Nr=3
Nr=5

 Metrics

Estimation errors of traffic matrix
Number of added optical paths
2/18/2008

8INFOCOM 2007

 Add the link utilizations monitored at each stage

 Make the maximum link utilization less than Th

 If the maximum link utilization is smaller than Th Use more accurate traffic matrix

Additional equation method

Nr: maximum number of added/deleted optical paths
Aim of reconfiguration

2/18/2008

Limit the number ofadded/deleted optical paths

INFOCOM 2007

Tomogravity

Additional equation
11

2/18/2008

INFOCOM 2007122

Conclusion and Future works

Results (Number of optical paths)

 Conclusion Additional equation methods adds smallerGradual VNT reconfiguration method taking
the estimation errors into consideration

number of optical paths than tomogravity
By reducing the estimation errors, we can avoid
adding insufficient optical paths

 Divide the VNT transition sequence into multiple

stagesVNT recnfiguration method limiting a number ofadded/deleted optical paths
Additional equation method

Additional equation
Tomogravity
True TM Future works

Extend our method so as to estimate in thecase of sudden change of traffic

2/18/2008

INFOCOM 200713

2/18/2008

INFOCOM 2007

143