Gradually Reconfiguring Virtual Network
Topologies based on Estimated Traffic Matrices
Yuichi Ohsita†, Takashi Miyamura§, Shin’ichi Arakawa‡ , Shingo Ata¶
Eiji Oki§, Kohei Shiomoto§ , Masayuki Murata‡†‡

Graduate School of Economics, Osaka University

Graduate School of Information Science and Technology, Osaka University§
NTT Network Service Systems Laboratories, NTT Corporation¶
Graduate School of Engineering, Osaka City University

Abstract— In this paper, we present a practical VNT (virtual
network topology) reconfiguration method for large-scale IP and
optical networks with traffic matrix estimation considerations.
We newly introduce a partial VNT reconfiguration algorithmwith multiple transition stages. By dividing the whole VNTtransition sequence into multiple transitions, estimation errors
are calibrated at each stage by using network state informationof prior stages. Because estimation errors are mainly due to thefewer information in the estimated traffic matrix calculation,
our approach tries to increase the constraint conditions for
traffic matrix estimation by introducing partial reconfiguration,and to relax the impact of estimation errors by limiting thenumber of optical-paths reconfigured at each stage. We also
investigate the effectiveness of our proposal through simulations
and clarify the robustness against estimation errors by using
partial reconfiguration.

I. I NTRODUCTION
In a backbone network, optical layer traffic engineering (TE)is one efficient way for accommodating traffic that fluctuates
unpredictably, which optimizes resource usage by dynamicallyreconfiguring a VNT (virtual network topology). Here, theVNT is defined as a set of optical paths that carry packet traffic
between edge routers. Packet traffic between two IP routers
is routed over the VNT. VNT reconfiguration methods are toconstruct the optimal VNT for a current traffic demand, which
improve the efficiency of network resource utilization [1–8].
These approaches dynamically reconfigure the optical-layer
topology, to accommodate traffic that fluctuates widely.
The VNT reconfiguration methods requires traffic matrix
information in computing the optimal VNT, but it is infeasible
to collect traffic matrix information of a large-scale network
due to the N -square problem. Therefore, we introduce a
traffic matrix estimation method, which presume the whole
traffic matrix information by using the limited (i.e., not awhole) information collected in the network. Several papers
have investigated the performance of existing TE methods inconjunction with estimated traffic matrices, and revealed thatexisting TE methods are less robust and do not work properly
due to estimation errors [9], [10].
We thus develop a practical VNT reconfiguration method
for optical networks with taking traffic matrix estimation
into consideration. According to [10], the full reconfiguration

approach, which computes the new optimal VNT without
limitations on the number of reconfigured optical paths, issensitive to estimation errors, because estimation errors in
the traffic matrix cause addition of many unnecessary opticalpaths and deletion of many necessary optical paths. Therefore,
we newly introduce a partial VNT reconfiguration algorithmwith multiple transition stages, and an estimation method
suitable for the VNT reconfiguration with multiple transition
stages. By dividing the whole VNT transition sequence into
multiple transitions, estimation errors are calibrated at eachstage by using network state information of prior stages.
Therefore, at each stage our estimation method improves theaccuracy of traffic matrix estimation by using network state
information of prior stages. Then, at the next stage, our partial
reconfiguration method uses the traffic matrix whose accuracy
is improved by our estimation method. In addition, our partial
reconfiguration method limits the number of optical paths
added or deleted mistakenly and relax the impact of estimation
errors by limiting the number of optical paths reconfigured ateach stage.
The rest of this paper is organized as follows. Section 2
proposes a VNT reconfiguration method with traffic matrix
estimation. Next, we introduce simulations that demonstrate
the limitations of the conventional method and evaluate theperformance of our algorithm in Section 3. Finally, a brief
conclusion is provided in Section 4.
II. PARTIAL RECONFIGURATION METHOD WITH TRAFFIC
MATRIX ESTIMATION

A. Design Principle and Method Overview
We assume that the routes and VNT are calculated by PCE(Path Computation Element) [11]. A PCE first gathers the
network information and estimate the traffic matrix by ourestimation method. Then, PCE calculates the VNT and routes
for the next stage by using the estimated traffic matrix.
Our goal is to provide robust and scalable VNT reconfiguration methods based on traffic matrix estimation; performance degradation due to estimation errors is minimized. The
objective function of our VNT reconfiguration algorithm is
to minimize resource consumption for a given traffic matrix
while avoiding excessive network congestion. Here, network

Traffic volume(i+1)-th reconfiguration
periodi-th reconfiguration
periodTraffic demandStage 1

2

3

K

Time

VNT control
TM Estimation

Fig. 1.

Overview of gradual reconfiguration of VNT

congestion is measured by the maximum link utilization in the
network, thus maximum link utilization should always be held
below a given upper bound (e.g., 80% of link bandwidth).
The main challenges are as follows. 1) If we deploy the fullreconfiguration approach, errors in a few elements can severely
degrade the performance of the whole network according to[10]. 2) We need to estimate traffic matrices as accurate as
possible to perform sophisticated VNT reconfiguration.
To solve these issues, we deploy the partial reconfiguration
approach with multiple transition stages. This tactic provides
robust and safe network control by reducing the negative
impact of estimation errors. By introducing partial reconfiguration, network congestion caused by estimation errors will
be limited to the small portion of the network, and even whenestimation errors cause inadequate VNT reconfiguration, we
can recover at the next stage. In addition, existing traffic matrix
estimation methods use only instantaneous traffic information,
which inevitably contains estimation errors because of thefewer constraint conditions imposed on the estimation. To
avoid this issue, the proposed reconfiguration approach divides
the whole VNT transition sequence into multiple transition
stages and estimation errors are calibrated at each stage byusing network state information of prior stages.
B. A Heuristic Algorithm for Partial Reconfiguration
We propose a heuristic algorithm for calculating the VNT,
which is simple enough to adopt the large-scale ISP backbones. The heuristic algorithm consists of two phases: addition
phase and deletion phase. The algorithm adds new opticalpaths to mitigate congestion and deletes existing underutilized
optical paths if possible for reclamation.
We give preference to adding optical paths over deleting
optical paths because network congestion degrades the performance of the communication using the network. Therefore,
the heuristic algorithm adds new optical paths first until thecongestion is resolved, and then removes underutilized opticalpaths.
In this algorithm, we limit the number of optical paths tobe added or deleted in each stage. N r denotes the maximum
number of optical path to be added or deleted.
The heuristic algorithm uses two threasholds to define thecongested or underutilized state of each optical path; TH and
TL denote thresholds for path congestion and underutilization,

respectively. The general sequence of the heuristic algorithm
is as follows:
Step 1 First we check the link utilizations of all opticalpaths. If at least one congested optical paths is found,
go to the optical path addition phase (Step 2). Else if
the link utilization of an optical path is less than TL ,then go to Step 3
Step 2 Perform the optical path addition phase of the algorithm, which is described below, then go to Step 4.
Step 3 Perform the optical path deletion phase of the algorithm, which is described below, then go to Step 4.
Step 4 The number of controlled paths is updated, N r =N r − 1. If N r > 1, go to Step 1. Otherwise, go to
End.
End
Then, at each stage, after the new VNT is determined,
the routes of packets over the VNT is calculated by using
CSPF (Constraint-based Shortest Path First) [12] so as to makemaximum link utilizations under TH .
The detail of the heuristic algorithm is described as follows.
1) Optical path addition phase:
If the link utilization of an optical path exceeds TH ,a new optical path is set up to reroute traffic awayfrom the congested optical path. The ingress and egress
nodes of the newly added optical paths are selectedfrom the ingress and egress nodes of packet paths on
the congested optical path, and then the packet path isrerouted via the newly added optical path. If there are
more than one packet path in the congested optical path,
the packet path whose amount of traffic is the largest is
selected.
2) Optical path deletion phase:
If the link utilization of an optical path is less than TL ,the optical path is torn down for resource reclamationin order to improve resource efficiency after checking
that the deletion of the optical path does not cause
any congestions. If there is more than one candidateof deleted optical paths, each candidate optical path istested in decreasing order of the link utilizations, so themost under-utilized optical path is selected among thecandidates.
C. Traffic Models and TM Estimation Method
In this subsection, we propose a new estimation method
which collaborates closely with partial VNT reconfiguration.
As described in Subsection II-A, the objective of our TM
estimation method is to increase the accuracy of estimation byeffectively utilizing the feedback information from the resultsof the previous stage in partial VNT reconfiguration.
Suppose that the estimated traffic matrix at the current
stage has large estimation errors. As the result of VNT reconfiguration, some optical path additions/deletions are made.
Under the assumption that the traffic demand of each sourcedestination is constant over the period from before to after
the reconfiguration, we focus on two kinds of additional
information in order to improve the accuracy of the estimation.

1) Differences of link utilizations between before and after
VNT reconfiguration: Given a fixed traffic matrix,
the change of routes of packet paths by the VNT
reconfiguration directly impacts the link utilizations of
optical paths that carry the packet paths whose routes
are changed. That is, if the measured link utilizations ofan optical path changes with VNT reconfiguration, thedifference is caused by the change of routes of packets.
The information of these differences can yield additional
equations for solving the traffic matrix calculation.
2) Difference between estimated link utilizations and actual link utilizations: Since VNT reconfiguration is
performed by using traffic matrices that essentially haveestimation errors, the estimated link utilization of opticalpaths may be altered by the errors. After reconfiguration,
there should be some difference between the estimatedand actual link utilizations. The information of thesedifferences is used as feedback to subsequent VNT
reconfigurations.
In the proposed method, we consider both pieces of information above in order to improve estimation accuracy.
We assume that the durations of a stage and reconfiguration
period are small enough and the traffic demand is constantthroughout the reconfiguration period. We denote the actual
traffic matrix by T . At stage i, we denote the routing matrix
and the matrix of link utilizations by Ai and Xi , respectively.
Because link utilization is the sum of the traffic demands
for the source-destination pairs using the links, we have
Xi = Ai T.

(1)

At stage n, by combining all relations from X0 to Xn , wealso have
⎤ ⎡
⎤
⎡
A0
X0
⎥ ⎢
⎥
⎢
..
..
⎥ ⎢
⎥
⎢
.
.
⎥ ⎢
⎥
⎢
⎢ Xi ⎥ ⎢ Ai ⎥
⎥=⎢
⎥ T.
⎢
(2)
⎥ ⎢
⎥
⎢
..
..
⎢
⎥
⎥
⎢
.
.
⎥ ⎢
⎥
⎢
⎣ Xn−1 ⎦ ⎣ An−1 ⎦XnAnThe calculation of T from Eq. (2) requires huge computational
overhead. However, partial reconfiguration changes only asmall number of routes at each stage. That is, most entries
of ΔAi = Ai − Ai−1 are expected to be 0. By applying this,
we introduce following procedure to reduce the size of thematrix. First, we transform Xi and Ai into the matrices,⎤⎡
X1 − X0
⎥
⎢
..
⎥
⎢
.
⎥
⎢
⎢ Xi − Xi−1 ⎥⎥⎢⎥..
X̄n = ⎢
(3)
⎥
⎢
.
⎥
⎢
⎢ Xn−1 − Xn−2 ⎥⎥⎢⎣ Xn − Xn−1 ⎦
Xn

and

⎡

ΔA1
..
.

⎤

⎥
⎢
⎥
⎢
⎥
⎢
⎢ ΔAi ⎥⎥⎢⎥.
..
ΔĀn = ⎢⎥⎢.
⎥⎢⎢ ΔAn−1 ⎥⎥⎢⎣ ΔAn ⎦
An

(4)

Second, we remove rows ΔAi in ΔĀn if ΔAi = 0. We also
remove the same position of the row Xi − Xi−1 in X̄n . We
denote X̄n and ΔĀn after row removal by X̄n and ΔĀn ,respectively. Finally, we use
X̄n = ΔĀn T,(5)instead of Eq. (2). To estimate the traffic matrix T̂ from
Eq. (5), we apply the pseudo-inverse calculation method
described in [13]. The traffic matrix T̂ is obtained fromT̂ = pinv(Ān )X̄n ,(6)where pinv(Ān ) is the pseudo-inverse of matrix Ān . If we
simply apply [13] to calculate the pseudo-inverse of Ān , someentries in T̂ may have negative values, which are nonexistent
as regards the traffic matrix. The following iteration eliminates
such negative values. We define the estimated traffic matrix forthe i-th iteration as T̂ (i) .
1) Let T̂ (0) ← T̂2) Calculate T̂ (i) from T̂ (i−1) by usingT̂ (i) = T̂ (i−1) + pinv(Ān )(X̄n − Ān T̂ (i−1) ),(7)

where T̂ (i) is a matrix in which we replace all negativevalues of T̂ (i) with zero.
3) If all entries in T̂ (i) are non-negative values, go to Step
4, else back to Step 2.
4) Let T̂ (i) be the final result of traffic matrix T̂
We discuss here why the above method offers better accuracy. As discussed before, we use two types of information
to improve the estimation accuracy. In this model, both areincluded in Eq. (5). More specifically, we use the constantvalue of T for all stages to increase the number of relations in
Eq. (2). Also, Eq. (6) offers an adjustment by keeping Eqs. (1)and (5). Though the errors are included in estimated trafficmatrix T̂i , they do not appear if the routing is not changed,
because the estimated traffic matrix and link utilizations evensatisfy Eqs. (1) and (5). However, because routing changes are
created by reconfiguration, the impact of estimation error on
the new paths appears in Eq. (5).
III. P ERFORMANCE E VALUATIONIn this section, we first address to the aim of our simulation
results followed by the description of simulation conditions.
Second, we perform simulations to demonstrate the effectiveness of the partial reconfiguration method with traffic matrix
estimation and some of these results are presented in thispaper.

200000
Nr=1
Nr=3
Nr=5

Fig. 2.

Abilene topology

Average of squared errors

180000B. Effectiveness of partial reconfiguration with TM Estimation
We first compare the average squared errors of trafficmatrix estimation between existing estimation method called
tomogravity [15] and our method. Fig. 3 shows the results,
where we set the threshold N r to be 1, 3 and 5. From thisfigure, we can observe that our method can decrease theestimation error dramatically compared to the tomogravity.
This is caused by the difference of number of equations usedin the traffic matrix calculation. In the tomogravity model,
the accuracy is improved only because the part of actual
traffic matrix can be directly measured by setting up additionalsource-destination paths, while our method can improve theaccuracy not only by the direct measurements but also by theincrease of the number of equations. However, in some stages,
even our method could not decrease the estimation error (e.g.,
Stages 14–18 for N r = 1). This is because our method can
improve the accuracy only if at least one route is changed
from the previous stage. In cases such as when we set an

140000120000100000
80000
60000
40000
20000

A. Simulation Conditions

0
0

10

20

30

40

50

60

50

60

Stage

(a) Our method

200000180000
Average of squared errors

The simulation conditions used in our performance evaluation is as follows. We use the Abilene backnone as the network
topology as shown in Fig. 2. The number of wavelengthes foreach physical link is set to be eight. As a true traffic matrix,
we adopt real data collected from the Abilene backbone
network [14]. However, the actual traffic demand does notmake a significant impact to VNT reconfiguration due to low
variations of the actual traffic. In order to verify the effect of
VNT reconfiguration, we scale the monitored traffic enoughto make most of links to be congested. Furthermore, we
add 1 Gbps of traffic to four randomly picked up sourcedestination pairs to cause significant route changes after VNT
reconfiguration. On the simulation, we first create the initial
VNT topology by using our VNT reconfiguration algorithm fora given traffic demand, we then change the traffic to abovementioned one to evaluate how our proposed method works.
For performance measures, we evaluate followings: i) average of squared estimation error, and ii) maximum number of
output ports additionally required for the VNT reconfiguration.
The former is the metric which directly indicates the accuracyof the traffic matrix estimation method. The latter is a useful toconsider the impact of estimation errors on the network cost,i.e., if the required number of ports is larger, we need morecost to construct the network.

160000160000140000120000100000
80000
Nr=1
Nr=3
Nr=5

60000
40000
20000
0
0

10

20

30

40

Stage

(b) Tomogravity
Fig. 3.

Average squared errors of traffic matrix estimation

additional path for the already connected source-destination
pair, or when we delete one of multiple paths for the same
source-destination pair.
Fig. 3 also shows the effect of the parameter N r for the
traffic matrix estimation. We found from this figure that there
is a trade-off between the convergense time and the accuracyof estimation. That is, when N r = 5 the VNT becomes stable
faster (i.e., smaller number of stages) than the case whenN r = 1, while the accuracy becomes worse when N r = 5.
To improve the accuracy, the smaller N r is better, however,small value of N r requires a lot of stages to be converged,
which lead a heavy measurement overhead or long time tomake the VNT stable. One possible solution is to set N r
as small as possible for given acceptable maximum numberof stages for partial reconfiguration which is determined by
the traffic monitoring period and preferable duration for thereconfiguration.
We next evaluate the impact of reducing estimation errors.

of the network. We also investigated the effectiveness of our
proposal through simulations and clarified the robustness ofthe proposed control method under estimated traffic.
One of our future works is to evaluate our method in thecase of frequent change of traffic.

Number of additional optical paths

30
25
20
15

ACKNOWLEDGEMENT

10

We acknowledge all the people that permitted the Abilene
Netflow data to be available on-line, and particularly Mark
Fullmer.

5
Our method
Tomogravity
True traffic matrix

0-5

R EFERENCES

-10
0

10

20

30

40

50

60

Stage

Fig. 4. Variation of difference of the number of paths from the beginningof VNT reconfiguration

To reconfigure the VNT, we add the optical paths between
nodes where estimated traffic is large. Thus, in the case of large
estimation errors, the actual traffic on the added optical paths
may be small. That is, estimation errors cause optical paths
added unnecessarily. Therefore, we evaluate the impact of reducing estimation errors by investigating the number of added
optical paths. Fig 4 shows the variation of difference of thenumber of paths from the beginning of VNT reconfiguration.
The number of paths is increasing linearly by passing stages.
When the VNT satisfies the condition that the maximum link
utilization is less than TH , the reconfiguration algorithm tries
to delete as many unused paths as possible. The number ofpaths is therefore descreasing linearly. From this figure, more
output ports are required when we use the tomogravity due tolarger estimation errors. This is because the estimation errors
cause the optical path added inadequately where the actual
traffic is small. As a result, we cannot decrease the maximum
link utilization as well as the case of small estimation errors
and we add more optical paths to make the maximum link
utilization under the threashold.
Also, tomogravity requires more stages to reach the stable
VNT. It is because the VNT reconfiguration algorithm isrequired to delete more paths which are unnecessarily addedcaused by estimation errors.
On the other hand, our method needs almost the same
number of paths as the true traffic matrix. That is, eventhough estimation errors at the first stage are as large as
tomogravity method, improving the accuracy of traffic matrix
by our method avoids adding the unnecessary optical paths.
IV. C ONCLUDING R EMARKSIn this paper, we proposed a practical VNT reconfiguration
method with traffic matrix estimation considerations. We presented a partial VNT reconfiguration approach as optimization
problems. We presented the heuristic algorithms for partial
reconfiguration. The key technology lies in a partial VNT
reconfiguration algorithm with multiple transition stages. By
introducing the partial reconfiguration, network congestion
caused by estimation errors can be limited to small portion[1] B. Mukherjee, D. Banerjee, S. Ramamurthy, and A. Mukherjee, “Someprinciples for designing a wide-area WDM optical network,” IEEE/ACM
Transactions on Networking, vol. 4, pp. 684–696, Oct. 1996.
[2] D. Banerjee and B. Mukherjee, “Wavelength-routed optical networks:
Linear formulation, resource budgeting tradeoffs, and a reconfiguration
study,” IEEE/ACM Transactions on Networking, vol. 8, pp. 598–607,
Oct. 2000.
[3] J. Wei, C.-D. Liu, S.-Y. Park, K. Liu, R. Ramamurthy, H. Kim, and
M. Maeda, “Network control and management for the next generation
Internet,” IEICE Transactions on Communications, vol. 83-B, pp. 2191–
2209, Oct. 2000.
[4] L. Zhang, K. Lee, and C.-H. Youn, “Adaptive virtual topology reconfiguration policy employing multi-stage traffic prediction in optical
Internet,” in Proceedings of Workshop on High Performance Switching
and Routing, pp. 26–29, May 2002.
[5] K. Shiomoto, E. Oki, W. Imajuku, S. Okamoto, and N. Yamanaka,“Distributed virtual network topology control mechanism in GMPLSBased multiregion networks,” IEEE Journal on Selected Areas in Communications, vol. 21, pp. 1254–1262, Oct. 2003.
[6] A. Gencata and B. Mukherjee, “Virtual-topology adaptation for WDM
mesh networks under dynamic traffic,” IEEE/ACM Transactions on
Networking, vol. 11, pp. 236–247, Oct. 2003.
[7] S. Gieselman, N. Singhal, and B. Mukherjee, “Minimum-cost virtualtopology adaptation for optical WDM mesh networks,” in Proceedingsof IEEE ICC, vol. 3, pp. 1787–1791, June 2005.
[8] R. Hayashi, T. Miyamura, M. Aoki, and S. Urushidani, “Simulation of a
dynamic multi-layer optimization algorithm with SRLG consideration,”in Proceedings of OECC/COIN 2004, July 2004.
[9] M. Roughan, M. Thorup, and Y. Zhang, “Traffic engineering withestimated traffic matrices,” in Proceedings of ACM SIGCOMM Internet
Measurement ConferenceIMC 2003, pp. 248–258, Oct. 2003.
[10] Y. Ohsita, T. Miyamura, S. Arakawa, S. Ata, E. Oki, K. Shiomoto,
S. Urushidani, and M. Murata, “Traffic engineering strategies in IP and
optical multi-layer networks,” Technical Reports of IEICE (PN2006–11),
pp. 7–12, Aug. 2006.
[11] A. Farrel, J. P. Vasseur, and J. Ash, “A path computation element (PCE)based architecture.” RFC 4655, Aug. 2006.
[12] B. S. Davie and Y. Rekhter, MPLS: Technology and Applications.
Morgan Kaufmann Publishers, 2000.
[13] J. C. Nash, Compact Numerical Methods for Computers: Linear Algebra
and Function Minimisation. Adam Hilger, 1990.
[14] “Abilene network status.”
available at http://abilene.
internet2.edu/observatory/.
[15] Y. Zhang, M. Roughan, N. Duffield, and A. Greenberg, “Fast accuratecomputation of large-scale IP traffic matrices from link loads,” inProceedings of ACM SIGMETRICS 2003, pp. 206–217, June 2003.