1

Gradually Reconfiguring Virtual Network
Topologies based on Estimated Traffic Matrices
Yuichi Ohsita, Member, IEEE, Takashi Miyamura, Non-Member, Shin’ichi Arakawa, Member, IEEE,
Shingo Ata, Member, IEEE, Eiji Oki, Senior Member, IEEE, Kohei Shiomoto, Member, IEEE, andMasayuki Murata, Member, IEEE

Abstract— Traffic matrix, which is required as an input of
traffic engineering (TE) methods, is difficult to be obtained directly. One possible approach to obtaining the traffic matrix is toestimate it from the limited information such as link utilizations.
However, estimated traffic matrix includes estimation errors
which degrade the performance of TE significantly. In this paper,
we propose VNT reconfiguration and traffic matrix estimation
methods that reduce estimation errors while reconfiguring the
VNT by cooperating with each other. Our method reconfigures
the VNT gradually by dividing it into multiple stages and limiting
the number of optical layer paths reconfigured in each stage. By
dividing the VNT reconfiguration into multiple stages, our trafficmatrix estimation method calibrates and reduces the estimation
errors in each stage by using information monitored in priorstages. In addition, by limiting the number of optical layer paths
reconfigured in each stage, our method avoids mistakenly adding
or deleting many optical layer paths. That is, our reconfiguration
method can mitigate the impact of estimation errors. We also
investigate the effectiveness of our proposal using simulations.
The results show that our method can improve the accuracy of
the traffic matrix estimation and construct an adequate VNT.

I. I NTRODUCTION
Network operators design their backbone networks to accommodate all traffic efficiently (e.g., without congestion orlarge delays). However, even if a backbone network suitable
for actual traffic is constructed, traffic could significantly differ
from the initial traffic as time goes on. As a result, thepreviously constructed backbone network becomes no longer
suitable to the current traffic; it may happen that utilizations ofsome links are extremely high while utilizations of other links
are extremely low. Especially, because high link utilizations
cause congestion or large delays, we need to avoid high link
utilizations even when traffic fluctuates.
Optical layer traffic engineering (TE) [1–8] is one efficient
way of accommodating traffic that fluctuates unpredictably.
Optical layer TE assumes that a network consists of IP routersand optical cross-connects (OXCs), as illustrated in Fig. 1.
Each outbound port of an edge IP router is connected to an
OXC port. Traffic imposed on the network between edge IP
routers is carried over WDM links. Lightpaths (hereafter called
Yuichi Ohsita is with Graduate School of Economics, Osaka University.
Shin’ichi Arakawa and Masayuki Murata are with Graduate School ofInformation Science and Technology, Osaka University.
Takashi Miyamura, Eiji Oki and Kohei Shiomoto are with NTT Service
Systems Laboratories, NTT Corporation.
Shingo Ata is with Graduate School of Engineering, Osaka City University.
A part of this paper was presented at IEEE INFOCOM 2007 minisymposium, Anchorage Alaska, May 2007.

Optical layer
path

IP/Optical network
Packetlayer
Packet layer

IP/MPLS network

IP Router
Packet layer
path

IP/MPLS network
Optical layer

Edge IP
RouterEdge IP
RouterOptical layer
OXC

Fig. 1.

VNTOXC: Optical Cross Connect
VNT: Virtual Network Topology

IP/Optical network.

optical layer paths) are established between two IP routers byconfiguring OXCs along the route between the routers. Opticallayer paths terminate at the transceiver of the last IP router.
A set of optical layer paths forms a VNT (virtual network
topology). Traffic between two routers is carried over the VNTusing IP layer routing. In these conditions, optical layer TE
accommodates traffic that fluctuates widely by dynamicallyreconfiguring VNTs.
In optical layer TE, a traffic matrix, which indicates traffic
volumes between all pairs of edge nodes, is required as an
input. By using the traffic matrix, the VNT reconfiguration
methods configure a new VNT in which constraints suchas maximum utilization of optical layer paths are satisfied.
One approach to obtaining the traffic matrix directly is toconstruct fully meshed label switched paths using MPLS.
However, this approach does not scale because it requires
N -square number of label switched paths. Another approachis to tally the number of packets of each end-to-end traffic
flow at all the edge nodes. However, this is also difficult toapply in large-scale networks, because tallying the number
requires a non-negligible amount of CPU resources of edge
nodes, and gathering the tallied data of all end-to-end traffic
consumes a non-negligible amount of network resources suchas bandwidths.
Therefore, several methods to estimate traffic matrices havebeen proposed [9–12]. In such methods, a whole traffic matrix
is estimated by using the information (e.g., utilizations of
optical layer paths) that can be collected much more easily
than traffic matrices. According to the paper on the performance of the above proposed TE methods in conjunction withestimated traffic matrices [13], estimation errors degrade theperformance of current TE methods, and because of estimation

2

errors, TE methods cannot reduce the maximum utilization of
optical layer paths as expected.
One way of handling such estimation errors is to reconfigure the VNT redundantly, taking the estimation errors into
consideration. Yang et al. [14] proposed a method of designinga VNT redundantly by modeling the uncertainty of elementsof traffic matrices as probability functions. We can apply
this method to reconfiguring a VNT by predicting estimation
errors and setting probability functions based on the predicted
estimation errors, and expect to avoid the impact of estimation
errors. However, if the predicted estimation errors are large,
the redundant reconfiguration may require an unacceptableamount of resources such as wavelengths. To avoid the impactof estimation errors, therefore, reduction of estimation errors
is necessary.
Accordingly, we newly develop VNT reconfiguration andtraffic matrix estimation methods that reduce estimation errors
while reconfiguring the VNT by cooperating with each other.
Our reconfiguration method divides the VNT reconfiguration
into multiple stages and limits the number of optical layer
paths reconfigured in each stage. By dividing the VNT reconfiguration into multiple stages, our traffic matrix estimation
method calibrates and reduces estimation errors in each stage
by using information (e.g., packet layer routing and utilizationsof optical layer paths) monitored in prior stages. As stages arecompleted, a better VNT (e.g., VNT in which the maximum
link utilization is reduced) is configured using the morereliable traffic matrix obtained by our estimation method.
In addition, if the the new VNT is computed without any
restrictions, the traffic matrix with estimation errors causes
the VNT to make mistakes: underestimation of traffic may
cause many necessary optical layer paths to be deleted, andoverestimation may cause many unnecessary optical layer
paths to be added. By limiting the number of optical layer
paths reconfigured in each stage, our reconfiguration method
avoids mistakenly adding or deleting many optical layer paths.
That is, our reconfiguration method mitigates the impact of
estimation errors.
The rest of this paper is organized as follows. Section II
summarizes related works. Then, Section III presents an
overview of the gradual reconfiguration method and the estimation method for the gradual reconfiguration. We explain thereconfiguration and estimation methods in detail in Sections IV
and V, respectively. In Section VI, we discuss the simulations
that we used to demonstrate the limitations of the conventional
method and evaluate our methods. Finally, a brief conclusion
is provided in Section VII.
II. R ELATED WORKIn this section, we summarize past research on VNT reconfiguration algorithms and traffic matrix estimation methods.
A. VNT reconfiguration method
VNT computation algorithms can be categorized as either
full [1], [2] or partial reconfiguration algorithms [3–8]. In fullreconfiguration, the new VNT is computed with no limitationon the number of reconfigured optical layer paths. Mukherjee

et al. [1] formulated the full reconfiguration VNT design
problems as optimization problems and proposed heuristic
algorithms based on the simulated annealing approach thatfind nearly optimal solutions. Their main focus is on a methodfor designing VNT on a given physical topology and static
traffic matrix. The full reconfiguration approach can yield asolution that is optimal in terms of network performance suchas maximum utilization of optical layer paths.
However, if we reconfigure the VNT using a full reconfiguration approach, the traffic matrix with estimation errors causes
the VNT to make mistakes. Because full reconfiguration
approaches do not limit the number of optical layer paths to bereconfigured, many necessary optical layer paths are deleted
due to underestimation and many unnecessary optical layer
paths are added due to overestimation. Deleting necessary
optical layer paths causes especially high utilization of otheroptical layer paths.
Therefore, in this study, we use a partial reconfiguration approach at each stage. In partial reconfiguration, the new VNTis computed with limitations on the number of reconfigured
optical layer paths. There are several papers proposing partial
reconfiguration approaches [3–8]. Banerjee and Mukherjee [3]present an integer linear programming (ILP) formulation for
optimal VNT design. Their approach assumes that the future
traffic matrix is given; the future VNT is determined byadapting the current one to accommodate the change in the
traffic matrices. Thus, they did not consider how well the VNT
reconfiguration interacts with the variability of unpredictable
time-varying traffic matrices. Recently, Gieselman et al. [8]proposed a partial reconfiguration algorithm that efficiently
adapts to fluctuations in traffic. However, their algorithm
allows only one optical layer path to be added or deleted ineach stage, so the VNT cannot adequately adapt to fluctuations
when there are unpredictable changes in traffic or a largescale network that requires a large number of controlled paths.
Therefore, in this paper, we extend the partial reconfiguration
method proposed in [8], enabling it to add or delete multiple
optical layer paths for each stage. Our reconfiguration method
is described in detail in Section IV.
B. Traffic Matrix Estimation
In the optical layer TE, information about network resources
and traffic matrices is required as input.
A straightforward approach to collecting traffic matrices is
to use fully meshed label switched paths that are configured
between each pair of edge routers on top of a VNT in the
network. However, this approach does not scale well because
it requires N -square number of label switched paths. Anotherapproach is to tally the number of packets of each end-to-end
traffic flow at the all edge nodes. However, this is also difficult
to apply to a large-scale network, because tallying the number
requires a non-negligible amount of CPU resources of edge
nodes and gathering the tallied data of all end-to-end traffic
consumes a non-negligible amount of network resources suchas bandwidths.
This means that a more scalable method of collecting
traffic matrices is urgently needed for traffic engineering in3large-scale IP/Optical networks. One possible method is tointroduce a traffic matrix estimation approach. This estimatesa traffic matrix based on indirect data (e.g., utilization oflinks). The estimated traffic matrix is used as an input of the
TE algorithm. Several methods of estimating a traffic matrix
have already been proposed. Zhang et al. [9] proposed afast and accurate estimation method called the tomogravity
method. Tomogravity extends a gravity model that assumes
that the amount of traffic from a source to a destination nodeis proportional to the total of the incoming/outgoing traffic foreach edge node. Results reported by [9] and [15] show that
tomogravity can follow rapid changes in amounts of traffic,
and can estimate the traffic matrix on a tier-1 ISP network
within 5 seconds. However, in some cases, the assumptionof gravity model is incorrect and the errors of tomogravity
method are significant [16]. A method is needed that canestimate accurately even in these conditions.
One approach to increasing estimation accuracy is to use
additional information. Recently, Soule et al. [10–12] proposed
methods of obtaining and using additional measurements toestimate the traffic matrix by changing the routes of packet
layer paths and observing the difference between utilizationof links before and after routes are changed. However, thesemethods require changes in packet layer paths that are initiallyunnecessary. Also, they do not consider how to deal withthe sudden changes in traffic that cause significant estimation
errors. Our approach, in contrast, obtains additional information using the difference in utilizations of optical layer
paths caused by the VNT reconfiguration with no unnecessaryroute changes. To avoid significant errors when traffic changes
suddenly, our estimation method separates the information
about sudden changes in traffic from the information (e.g.,
packet layer routing and utilization of optical layer paths) fromprior stages.
III. OVERVIEW
A. Terminology
Before presenting overviews of our reconfiguration andestimation methods, we explain our terminology.
Traffic matrix
A matrix indicating the amount of traffic between all
pairs of IP routers.
Physical topology
A topology physically constructed in the optical layerthat consists of OXCs and WDM optical fibers. Two
OXCs are connected by a single optical fiber.
Optical layer pathAlightpathconfigured
betweentwo
indirectly/directly connected OXCs. An opticallayer path is a set of optical fibers between the
two OXCs determined by the optical layer TE. An
optical layer path occupies one wavelength of each
optical fiber on the route of the optical layer path.
VNT
A topology constructed with optical layer paths.
From the packet layer, an optical layer path isTraffic volumei-th reconfiguration
period(i+1)-th reconfiguration
periodTraffic demandStage 1VNT control
TM Estimation

Fig. 2.

2

3

K

Time

Overview of gradual reconfiguration of VNTregarded as a single directly connected link between
IP routers.
Packet layer pathAn end-to-end packet-layer traffic traversing the
VNT. Packet layer paths traversing the same opticallayer path share the optical layer path bandwidth.
Route of a packet layer path
A set of optical layer paths passed by the packet layer
path.
Utilization of an optical layer path
Amount of traffic traversing the optical layer path
divided by the capacity of the optical layer path.
B. Overview of gradual reconfiguration and traffic matrix
estimation
We assume that routes of both packet and optical layer paths
are calculated by a path computation element (PCE) [17]. A
PCE first gathers network information, such as utilization of
optical layer paths and packet layer routing, and estimates the
traffic matrix. Then, the PCE solves the VNT and packet layer
paths for the next stage.
Our goal is to develop VNT reconfiguration and trafficmatrix estimation methods that reduce the estimation errors
while reconfiguring the VNT by cooperating with each other.
Here, the objective of our VNT reconfiguration algorithm is tominimize the total amount of IP router ports (i.e., minimize thenumber of optical layer paths) used to accommodate the given
traffic while avoiding excessive network congestion. This will
preserve more IP router ports for future change of traffic. We
measured network congestion based on maximum utilizationof optical layer paths in the network, so maximum utilization
should always be held below a given upper bound (e.g., 50%
or 70% of bandwidth of an optical layer path).
There are two main challenges. First, we need to reconfigurea VNT that minimizes the impact of traffic matrix estimation
errors. That is, even if there are some estimation errors in
the traffic matrix, we need to add necessary optical layer
paths, avoid adding unnecessary optical layer paths, and avoid
deleting necessary optical layer paths. Second, we need toestimate traffic matrices as accurately as possible to increase
the sophistication of the VNT reconfiguration.
To resolve these issues, we deploy the gradual reconfiguration approach shown in Fig. 2. To accommodate the current
traffic, the VNT needs to be reconfigured once per reconfiguration period (e.g., on the order of hours). In the gradual

4

reconfiguration, the VNT reconfiguration is divided into several stages. The period between two stages is configured on theorder of minutes. For example, the period may be set to 5 min,which is a typical monitoring interval used in SNMP. A partial
reconfiguration is carried out in each stage. Introduction of
gradual reconfiguration will limit network congestion causedby estimation errors to a small portion of the network because
limiting the number of reconfigured optical layer paths at eachstage prevents deletion of a large number of necessary opticallayer paths. We can quickly recover from whatever estimation
errors cause inadequate VNT reconfiguration in the next stage.
Existing traffic matrix estimation methods use utilizationof simultaneously monitored links, setting up equations thatthe traffic matrix should satisfy. Then, these methods find thetraffic matrix that satisfies the equations. However, estimatedtraffic matrices contain estimation errors because the numberof equations, which is equal to the number of utilizations
used by existing estimation methods, is much smaller than
the number of elements of the traffic matrix. To avoid thisproblem, our traffic matrix estimation method cooperates with
the VNT reconfiguration method. In our estimation method,
we increase the accuracy of traffic matrix estimation by using
the utilization of optical layer paths monitored both before andafter the VNT reconfiguration.
IV. H EURISTIC A LGORITHM FOR G RADUALR ECONFIGURATION
In each stage of the gradual reconfiguration, we use theheuristic algorithm proposed in this section to calculate the
VNT for the next stage. The heuristic algorithm consists of
two phases: addition phase and deletion phase. The algorithm
adds new optical layer paths to mitigate congestion and, if
possible, deletes currently underutilized optical layer paths forreclamation.
We prioritize adding optical layer paths over deleting opticallayer paths because congestion, which can be caused by the
optical layer path deletion, seriously damages the network.
Therefore, the heuristic algorithm adds new optical layer paths
until the congestion is resolved. Then, the algorithm removes
underutilized optical layer paths. In this algorithm, we limit
the number of optical layer paths to be added or deleted ateach stage. N denotes the maximum number of paths to be
added or deleted.
The heuristic algorithm uses two thresholds for the utilization of each optical layer path to define the congested andunderutilized states. TH and TL denote thresholds for congested and underutilized, respectively. The general sequenceof the heuristic algorithm is as follows:
Step 1 Check the utilization of all optical layer paths. If
at least one congested optical layer path (i.e., a pathwhose utilization exceeds the threshold TH ) is found,
go to the optical layer path addition phase (Step 2). If
there is an optical layer path whose utilization is lessthan threshold TL , go to Step 3
Step 2 Execute the optical layer path addition phase described below, then go to Step 4.
Step 3 Execute the optical layer path deletion phase described below, then go to Step 4.

A

E
C

B

F

A

E
C

B

Fig. 3.

Packet layer path withlargest amount of traffic

D

Most congested
optical layer path

An optical layer path
between A and E is added

D
F

Example of addition of optical layer path addition phase

Step 4 Decrement the number of optical layer paths to be
added/deleted in this stage, i.e., N = N −1. If N = 0,
go to End. Otherwise, go back to Step 1.
End
After the new VNT is determined, the routes of packet
layer paths over the VNT are calculated as follows. 1) Whenutilizations of all optical layer paths on the route of a packet
layer path in the previous stage are lower than TH , the routeis kept in the current stage because there is no need to change
it. 2) Otherwise, the route is calculated using constraintbased shortest path first (CSPF) [18] so as to limit maximum
utilizations to less than TH .
The details of optical layer path addition/deletion phases are
as follows.
1) Optical layer path addition phase:
If the utilization of an optical layer path exceeds TH ,a new optical layer path is set up to reroute traffic
away from the congested optical layer path. First, wecollect a set of packet layer paths that pass the mostcongested optical layer path. Then, we select the busiestof the collected packet layer paths. Finally, we add the
direct optical layer path between the ingress and egress
nodes of the selected packet layer path. An example of
optical layer path addition phase is shown in Fig. 3. In
this example, the optical layer path from C to D is themost congested. Among packet layer paths traversing theoptical layer path C-D, the packet layer path from A to
E is busiest. In this case, an optical layer path from A
to E is established.
2) Optical layer path deletion phase:
If the utilization of an optical layer path is less than
TL and the deletion of the optical layer path is shown
not to cause congestion, the path is torn down so the
IP router ports and wavelengths can be reclaimed for
future use. The optical layer path is checked for potential
for its deletion to cause congestion by calculating theutilization of optical layer paths after deletion using thetraffic matrix estimated in the current stage. If there ismore than one candidate for deletion, each candidate
path is tested in ascending order of utilization. Thatis, the least utilized underutilized optical layer path isselected from the candidates.

5

V. T RAFFIC M ATRIX E STIMATION M ETHOD S UITABLE FOR
G RADUAL R ECONFIGURATION
Our estimation method collaborates closely with the gradual
VNT reconfiguration. As described in Section III, the objectiveof our traffic matrix estimation method is to increase theaccuracy of estimation by effectively using the utilization of
optical layer paths monitored both before and after the VNT
reconfiguration carried out in the previous stage.
When the VNT is reconfigured, up to N optical layer paths
are added or deleted. The change in routes of packet layer
paths caused by the VNT reconfiguration directly impacts
the utilization of optical layer paths that are passed by the
packet layer paths whose routes are changed. Assuming thatthe network is stable (i.e., the variation in traffic is small)
between two continuous stages, if the measured utilization ofan optical layer path is changed by VNT reconfiguration, it issafe to conclude that the difference is caused by the change
in routes of packet layer paths. These differences can yieldadditional equations for solving the traffic matrix calculation.
In our proposed method, we use the utilizations monitored in
the last M stages.
Hereafter, we call our estimation method the additional
equation method. In Subsection V-A, we describe its basic
idea. In a real network, the traffic may change during the M
stages used in the additional equation method. A significant
variation in traffic causes estimation error because it violates
the fundamental assumption that the network is stable. To deal
with obvious variations in traffic, we propose a method of
eliminating the impact of the non-negligible change in traffic
described in Subsection V-B.

A. Basic Idea
In our method, we use the utilization of optical layer paths
monitored in the last M stages. That is, to estimate the trafficmatrix at stage n, we use the utilization monitored fromstage n − M + 1 to stage n. We assume the duration of astage is small. In stage i, Ti , Ai , and Xi denote the actual
traffic matrix, the routing matrix (i.e., the matrix in which anelement corresponding to a packet layer path and an opticallayer path is 1 if the packet layer path passes the optical layer
path or is set to 0 if not) and the matrix indicating utilizationsof optical layer paths, respectively.
Because utilization of an optical layer path is the sum of
the traffic for the packet layer paths using the optical layer
path, we have

Xn , we also have
⎡
⎤ ⎡
⎤
⎡
⎤
n−M +1,nAn−M +1
Xn−M +1
⎢
⎥ ⎢
⎥
⎢
⎥
..
..
..
⎢
⎥ ⎢
⎥
⎢
⎥
.
.
.
⎢
⎥ ⎢
⎥
⎢
⎥
⎢
⎥
⎢
⎥
⎢
⎥
Xi
Ai
i,n
⎥=⎢
⎥ Tn + ⎢⎢⎥ . (2)
⎢
⎥ ⎢
⎥
⎢
⎥
.
.
.
..
..
..
⎢
⎥ ⎢
⎥
⎢
⎥
⎢
⎥ ⎢
⎥
⎢
⎥
⎣ n−1,n ⎦⎣ Xn−1 ⎦ ⎣ An−1 ⎦XnAn0Note here, that because we assume that the duration of astage is small, i,n is also small. To estimate the traffic matrixT̂n from Eq. (2), we apply the pseudo-inverse calculation
method described in [19]. The traffic matrix T̂n is obtainedfrom(3)T̂n = pinv(Ān )X̄n ,where pinv(Ān ) is the pseudo-inverse of matrix, and Ān andX̄n are the matrices defined as,⎤⎡
X0⎢ .. ⎥
⎢ . ⎥
⎥
⎢
⎥
(4)
X̄n = ⎢⎢ Xi ⎥⎢ .. ⎥
⎣ . ⎦
Xn
⎤
A0
⎢ .. ⎥⎢ . ⎥⎥⎢⎥Ān = ⎢⎢ Ai ⎥ .
⎢ . ⎥⎣ .. ⎦
An
⎡

and

(5)

A pseudo-inverse matrix is a generalized inverse matrix andby using pseudo-inverse matrix, Eq. (3) can estimate T̂n so as
to minimize the squared sum of i,n (n − M + 1 ≤ i ≤ n).
However, if we simply apply the pseudo-inverse of Ān
to solve Eq. (3), some elements in T̂n may have negativevalues, which are nonexistent as regards the traffic matrix. The
following iteration eliminates such negative values. We define(i)the estimated traffic matrix for the i-th iteration as T̂n .
(0)
Step 1 Let T̂n ← T̂n
(i)
(i−1)
Step 2 Calculate T̂n from T̂n
by usingT̂n(i) = T̂n(i−1) + pinv(Ān )(X̄n − Ān T̂n(i−1) ), (6)(i)where T̂n is a matrix in which we replace all(i)negative values of T̂n with zero.
(i)
Step 3 If all elements in T̂n are non-negative values, go to
Step 4, or else back to Step 2.
(i)
Step 4 Let T̂n be the final result of traffic matrix T̂n
B. Dealing with non-negligible changes in trafficXi= A i Ti
= Ai Tn + i,n ,(1)where i,n denotes the change in traffic between stages i andn. At stage n, by combining all relations from Xn−M +1 to

The basic idea described above assumes that the network is
stable (i.e., the variation in traffic is small). However, in real
networks, the traffic may change during the M stages we usedin the additional equation method. Significant variation in traffic causes estimation error because it violates the fundamental
assumption of the additional equation method.

6

Therefore, we remove the information about non-negligible
change in traffic from the information monitored in previous
stages in order to avoid violating the assumption. Our proposed
estimation method contains the following steps.
Step 1 Identify the packet layer paths, including nonnegligible changes
Step 2 Remove the information about the traffic of the identified paths from the information monitored in previous
stagesStep 3 Estimate the traffic matrix by using the informationin which information about the traffic of the identified
paths is removed
In the rest of this subsection, we describe these steps indetail.
1) Identify the packet layer paths, including non-negligible
change: First, we identify the packet layer paths including
non-negligible changes. To do this, we use the method proposed in [20], which identifies source nodes of DDoS attacks
based on increase in utilization. We identify the packet layer
paths including non-negligible changes in stage n as follows.
First, we calculate differences Dn between the utilization
monitored at stage n and the utilization forecasted using theestimated traffic matrix from stage n − 1.
Dn = Xn − An T̂n−1(7)Then, we estimate matrix Gn indicating the increases in traffic
flows between all pairs of edge nodes using Dn . Finally, if
there are elements in Gn that are larger than a threshold Γ, we
identify the packet layer paths that correspond to the elements
as the paths that include non-negligible changes.
Though this step requires estimation of Gn , we do not haveto estimate it accurately. The aim of this step is to identify
packet layer paths that include traffic flows that increasesignificantly more than others. Therefore, when estimating Gn ,we have only to estimate the elements corresponding to thepacket layer paths with significantly increasing traffic as large
values. If there is significantly increasing traffic, the elements
in Dn corresponding to the optical layer paths passed bythem are significantly larger than other elements. Moreover,elements in Dn corresponding to the incoming/outgoing traffic
at the source and destination nodes of the packet layer paths
with increasing traffic are also large. In this study, we used
the tomogravity method to estimate Gn from Dn . In the
tomogravity method, the elements of Gn are estimated as thevalue proportional to the incoming/outgoing traffic for eachedge node. That is, the tomogravity method can estimate theelements in Gn that correspond to the packet layer paths withsignificantly increasing traffic as large values.
2) Removal of information about non-negligible changes:
We remove the information about packet layer paths with
non-negligible changes from the information monitored in theprevious stages as follows.
We first remove the information of the identified packet
layer paths from the routing matrices Ai by replacing theelements corresponding to the identified paths by 0. We denote
the routing matrix after the replacement as Ai , in which theelement corresponding to the packet layer path from n to m

and the optical layer path between k and l is given by⎧
if traffic from n to m
⎨ 0,changes significantly,
ain,m,k,l =⎩ n,m,k,l, otherwiseai(8)

where an,m,k,lis the element of Ai indicating whether or notithe packet layer path from n to m passes the optical layer path
between k and l.
Then, we create the utilization matrix Xi in which the information about the identified packet layer paths are removed,
which is given by
Xi = Xi − (Ai − Ai )T̂n−1 .

(9)In this equation, (Ai − Ai )T̂n−1 indicates the matrix of theidentified traffic on each link caluclated by using the trafficmatrix estimated at stage n − 1.
3) Estimate the traffic matrix: To estimate the traffic matrix,
we use the equation,
Xi = Ai Tn + i,n(10)

instead of Eq. (1). Similar to Eq. (2), by combining all relations
from Xn−M +1 to Xn , we also have
⎡
⎤ ⎡ 
⎤
⎡ 
⎤
n−M +1,n
Xn−M +1
An−M +1
⎢
⎥ ⎢
⎥
⎢
⎥
..
..
..
⎢
⎥ ⎢
⎥
⎢
⎥
.
.
.
⎢
⎥
⎥
⎢
⎥
⎢


⎢
⎥
⎥
⎢
⎥
⎢
Xi
Ai
i,n
⎥=⎢
⎥ Tn + ⎢
⎢
⎥.
⎢
⎥
⎥
⎢
⎥
⎢
.
.
.
..
..
..
⎢
⎥ ⎢
⎥
⎢
⎥
⎢
⎥ ⎢
⎥
⎢
⎥
⎣ n−1,n ⎦⎦ ⎣ A
⎦
⎣ X
n−1
n−1
Xn
An
0
(11)
Note here, that because we remove the information about thetraffic with non-negligible changes, Xi does not include theinformation about the traffic with non-negligible changes. Thatis, i,n is small.
Therefore, as in Eq. (3), we can estimate T̂n as
T̂n = pinv(Ā n )X̄  n ,(12)where pinv(Ā n ) is the pseudo-inverse of the matrix Ā n , andĀ n and X̄  n are the matrices defined as⎤⎡ Xn−M +1
⎥
⎢
..
⎥
⎢
.
⎥
⎢

⎥
X
X̄  n = ⎢
(13)
i
⎥
⎢
⎥
⎢
..
⎦
⎣
.

Xn
and

⎤
An−M +1
⎥
⎢
..
⎥
⎢
.
⎥
⎢


⎥.
⎢
Ai
Ā n = ⎢
⎥
⎥
⎢
..
⎦
⎣
.
An
⎡

(14)

7

TABLE IG RADUAL RECONFIGURATION VS FULL RECONFIGURATION USING TOMOGRAVITY METHOD

Before the VNT reconfiguration
Gradual reconfiguration (N = 1, Stage 1)
Gradual reconfiguration (N = 1, Stage 15)
Full reconfiguration
Full reconfiguration using true traffic matrix

Fig. 4.

Maximum utilization
0.98
0.95
0.61
0.73
0.49

Number of added optical layer paths
0
1
15
15
18

EON topology

VI. N UMERICAL E VALUATIONIn this section, we describe the simulation conditions, explain how the simulations demonstrate the effectiveness of thegradual reconfiguration method with the existing traffic matrix
estimation, and evaluate the gradual reconfiguration method
using the additional equation method.
A. Simulation Conditions
The simulation conditions used in our evaluation were as
follows. We use the European Optical Network (EON) (19nodes, 37 links) shown in Fig. 4 as the physical topology. In
this figure, circles represent OXCs, and lines represent opticalfibers. The number of wavelengths for each optical fiber is set
to 16. The initial VNT is configured by the algorithm describedin Section IV with N = ∞ using the initial traffic matrix.
In the gradual reconfiguration, we use two thresholds, TH
and TL , to define the congested and underutilized states.
Setting them to large values preserves more resources (e.g.,
IP router ports or wavelengths) for future use. However,setting them to large values makes the network sensitive tofluctuations in traffic. For example, packet loss rates or delays
increase significantly when there is a spike in traffic. Therefore, to maintain a margin of safety, we set these thresholds
to a slightly smaller value than the rate at which network performance degrades significantly (e.g., where delays increasesignificantly). In our simulations, we set the thresholds TH
and TL to 0.5 and 0.3, respectively.
In the additional equation method, we use two parameters: Γand M . Γ is the parameter indicating sensitivity for detectionof change in traffic. The traffic whose increase is larger than
Γ is identified as traffic including non-negligilbe changes,
and the previously monitored information about the traffic
is not used for estimating traffic matrix. If we set Γ to
too large a value, there is still a non-negligible change intraffic in the information used by the additional equation
method. This causes estimation errors. However, a too small Γ
causes misdetection of traffic with no non-negligible changes(false positives). As a result, the additional equation method
cannot use many of the utilizations monitored in the previous

Number of deleted optical layer paths
0
0
0
0
7

stages. Therefore, we should set the Γ to as small a value
as possible such that it will not detect traffic with no nonnegligible change by monitoring the traffic in advance. In our
simulations, Γ is set to 500 Mbps.
The additional equation method uses the utilizations monitored at last M stages for estimating traffic matrix. That is,
we uses more information for estimating the traffic matrix bysetting M to large value. By using more information, we canreduce the number of estimation errors. However, using more
information requires more memory because more monitored
data must be stored. In our simulations, we set M to 50.
B. Effectiveness of gradual reconfiguration
In this subsection, we evaluate the effectiveness of the gradual reconfiguration using the existing traffic matrix estimation
method. Because we focus on the impact of estimation errors,
we assume that the traffic is constant in all stages to avoid theimpact of the change in traffic. We set the initial traffic matrix
according to uniform random values. We added 2 Gbps to two
randomly selected elements of the initial traffic matrix to form
the true traffic matrix used for VNT reconfiguration and chosethe tomogravity method [9] for the traffic matrix estimation.
First, we compare the gradual reconfiguration method withthe full reconfiguration method. Here, we use the algorithm
described in Section IV as our example of the full reconfiguration method by setting N = ∞.
Table I compares the results of full and gradual reconfiguration. In the gradual reconfiguration, we set N to 1. As canbe seen from this table, though full reconfiguration can reduce
maximum utilization, it is still much higher than in the true
traffic matrix and is even higher than in Stage 15 of the gradualreconfiguration where the same number of optical layer paths
are added as in the full reconfiguration.
To investigate in more detail, we compared the maximum
utilization when the full reconfiguration and the gradual reconfiguration both add the same number of optical layer paths.
Figure. 5 shows the results for three different true trafficmatrices that were randomly generated in the steps describedabove. Figuure. 5(a) corresponds to the case shown in Table I.
In these graphs, the horizontal axis represents the numberof added or deleted optical layer paths and the vertical axis
represents maximum utilization. We also plotted the results
for the full reconfiguration using the true traffic matrix as acomparison.
Figure. 5(a) shows the full reconfiguration using the estimated traffic matrix with 15 added optical layer paths.
However, the optical layer paths added after the 12th pathcannot reduce the maximum utilization. This is because theMaximum utilization of optical layer paths

8

1
0.9

Full reconfiguration

0.8

Gradual reconfiguration

0.7
0.6

True TM

0.5
0.4
0.3
0.2
0.1
0
0

5
10
15
20
25
Number of added/deleted optical paths

30

Maximum utilization of optical layer paths(a) Case I

1Full Reconfiguration

0.8

0.6

True TM

0.4

Gradual Reconfiguration

0.2

0
0

5
10
15
20
25
Number of added/deleted optical paths

30

Maximum utilization of optical layer paths(b) Case II

1

0.8

0.6

The gradual reconfiguration, in contrast, is not completed
until the maximum utilization drops to less than TH , though
the maximum utilization increases at some stages due toestimation errors. This is because the utilizations are monitoredeach time an optical layer path is added or deleted. By
monitoring utilizations, the gradual reconfiguration algorithm
decides whether additional optical layer paths are needed
based on the monitored utilizations. Therefore, no optical layer
paths are added that cannot circumvent traffic traversing theoptical layer path with maximum utilization.
However, there are cases in which the addition of an opticallayer path by the gradual reconfiguration also cannot reducethe maximum utilization. This is because the routes of packet
layer paths over the VNT are inadequate due to estimation
errors. For example, though the estimated maximum utilization
after the addition of the 8th optical layer path is reduced to
0.80, the actual utilization is 0.98, which is much higher than
before the 8th optical layer path is added. These increases
in the maximum utilization caused by estimation errors also
cause reconfiguration instability. In the case shown in Fig. 5(a),because of estimation errors, the maximum utilization neverdrops below the threshold, and optical layer paths continue tobe added.
The results shown in Figs. 5(b) and 5(c) are similar to
those shown in Fig. 5(a). In all cases, the full reconfiguration
stops adding optical layer paths even though the maximum
utilization is still high. The gradual reconfiguration, in contrast, continues to add optical layer paths until the maximum
utilization drops below TH . However, because of estimation
errors, the maximum utilization never does drop below TH .
That is, estimation errors also have impact on the gradual reconfiguration. To avoid this impact, estimation errors must be
reduced, which will be discussed in the next two subsections.

True TM
Full Reconfiguration

0.4

C. Effectiveness of reducing estimation errors: the case of nochange in traffic

Gradual Reconfiguration

0.2

0
0

5

10

15

20

25

30

Number of added/deleted optical paths(c) Case III
Fig. 5.
Number of added/deleted paths vs maximum utilization (using
tomogravity method)full reconfiguration decides whether additional optical layer
paths are needed based on utilization calculated using thetraffic matrix estimated at the beginning of the VNT reconfiguration. In this case, after the 12th optical layer path isadded, though the actual maximum utilization is 0.73, theestimated utilization of the optical layer path with the largest
actual utilization is 0.50. As a result, the optical layer path ismistakenly identified as a path whose utilization is less than
TH . Therefore, no optical layer paths are added to circumvent
traffic traversing the optical layer path. Finally, though the
maximum utilization is still over the threshold, the VNT
reconfiguration is completed.

Here, we evaluate the gradual reconfiguration using theadditional equation method to estimate the traffic matrix. First,
to compare the result for this combined method with those
discussed in the previous subsection, we evaluate our methods
when traffic is constant in all stages. Then, we evaluate themwhen traffic changes in the nexe subsection.
First, we evaluate the combined method to estimate thetraffic matrix when traffic is constant in all stages. In thissimulation, we intend to compare the tomogravity method andthe additional equation method setting N to 1, 5, and 10. We
conducted the simulations using ten different traffic matrices
generated by the same steps as discussed in the previous
subsection. In this paragraph, we present the average of theresults.
Figure. 6 shows the average of squared estimation errors
for each stage. In this graph, the horizontal axis represents
the number of stages after the beginning of the VNT reconfiguration, and the vertical axis represents the average ofsquared estimation errors. As can be seen in this figure, theadditional equation method dramatically reduces estimation
errors as the stages are completed, while estimation errors ofAverage of squared errors [Mbsp*Mbps]

9

50000

40000

30000

20000

N=10
N=5
N=1

10000

0
0

5

10

15
Stages

20

25

30

25

30

Average of squared errors [Mbps*Mbps](a) Additional equation method

50000

40000
N=1

N=10

N=5
30000

20000

10000

0
0

5

10

15

20

Stages(b) Tomogravity
Fig. 6.

Average squared errors of traffic matrix estimation

the tomogravity method are large in all stages. This is causedby the difference in the number of equations used in trafficmatrix calculation. The tomogravity method uses only theutilizations monitored at each stage. That is, the tomogravity
method uses only the same number of equations as the numberof optical layer paths. On the other hand, when some routes ofpacket layer paths are changed, the additional equation method
adds the equations about the packet layer paths whose routes
are changed. As a result, the number of equations used by theadditional equation method increases as it progresses throughthe stages.
Figure. 6 also shows that before Stage 5, the estimation
errors are reduced to the same level regardless of N . Thisis because the number of packet layer paths whose routes
are changed are almost the same regardless of N . In thissimulation, a packet layer path is routed on the VNT according to the following policy; when a packet layer path canbe accommodated to the same route as the previous stages
without causing utilizations higher than TH , the packet layer
path is accommodated on the same route as the previous
stage, otherwise the routes are re-calculated using CSPF so
as to limit the maximum link utilization to less than TH .
When one or more optical layer paths are added, the packet
layer path traversing the optical layer paths whose utilizations
are higher than TH moves to the optical layer paths whose
utilizations are low. Because the number of packet layer paths
traversing optical layer paths whose utilizations are higher than

TH before the VNT reconfiguration is the same regardless of
N , the number of packet layer paths whose routes are changed
is also almost the same regardless of N .
In contrast, in the final stage, by setting N to a smaller
value, we can estimate the matrix more accurately. This isbecause, when we set N to a large value, the VNT reconfiguration is completed in a small number of stages. Therefore,
the number of additional equations is smaller when setting N
to a large value than when setting N to a small value. Thisway, by setting N to a small value, we can estimate moreaccurately and limit the number of optical layer paths to be
added or deleted before reducing the estimation errors.
Figure. 7 shows the maximum utilization in each stage.
In this figure, as described in the previous subsection, thegradual reconfiguration using the traffic matrix estimated by
the tomogravity method is unstable and cannot reduce themaximum utilization to less than TH . In contrast, the additional equation method can reduce the estimation errors as
it progresses through the stages. Because of this, the gradualreconfiguration using the traffic matrix estimated by additional
equation method can reconfigure an adequate VNT whose
maximum utilization is under TH . In the case of the gradualreconfiguration with the additional equation method, the larger
N is, the faster the maximum utilization is reduced. This isbecause, if we set N to a small value, the number of opticallayer paths added in each stage is limited, and more stages are
required to reduce the maximum utilization.
Figure. 8 shows the number of optical layer paths added
or deleted by the gradual reconfiguration using the additional
equation method until the VNT becomes stable. In this figure,
we compare the cases where N = 1, 5, and 10. In this figure,
if we set N to a larger value, we need to add or delete more
optical layer paths until the VNT becomes stable. This isbecause many optical layer paths are added or deleted before
the estimation errors are reduced when there is a large N . As
a result, due to estimation errors, many unnecessary opticallayer paths are added.
This means that there is a trade-off between the time needed
to reduce the maximum utilization and the number of added
or deleted optical layer paths. If we set N to a large value, themaximum utilization is reduced quickly. However, in this case,more optical layer paths are added or deleted, which requires
more resources, such as IP router ports and wavelengths. By
setting N to a small value, on the other hand, we can achieve
the adequate VNT by adding or deleting a small number of
optical layer paths even though it will take more stages toachieve the adequate VNT. Therefore, N should be set to as
small a value as possible without leaving significantly highutilizations for multiple stages. One possible approach is toset N dynamically based on current utilization. However, thisis beyond the scope of the current study and is left to futurework.
D. Effectiveness of reducing estimation errors: the case that
traffic changes
The evaluation described above assumes that the traffic
is constant after the beginning of the VNT reconfiguration.

Average of squared errors [Mbps*Mbps]

Maximum utilization of optical layer paths

10

1

0.8

N=1
N=5

0.6
N=10

0.4

0.2

0
5

10

15
Stages

20

25

25000
20000
lambda=0.10
15000
lambda=0.15
10000
5000
0

lambda=0.05

N=1
0.8

0.6
N=10
N=5

0.2

0
0

5

10

15

20

25

30

Stages(b) Tomogravity

Number of added/deleted optical layer paths

Maximum utilization
60
50

deleted optical layer path
added optical layer path

40
30
20
10
0
N=1

N=5

N=10

True TM

Fig. 8. Number of added/deleted optical layer paths of additional equation
methodHowever, real traffic changes over time. Therefore, in thissubsection, we evaluate our methods assuming that trafficchanges.
1) Adaptability to the fluctuations in traffic: We evaluatedthe robustness of the additional equation method to changes
in traffic, generating changes in traffic as follows.
ti,j,n = αi,j + γi,j,n

20

30

40

50

Fig. 9. Impact of fluctuations in traffic on estimation errors (additional
equation method)

1

0.4

10

Stages30(a) Additional equation method

Maximum utilization of optical layer paths

30000

0
0

Fig. 7.

35000

(15)

where ti,j,n is the amount of traffic from node i to node j
at stage n, αi,j is the average of traffic from node i to nodej, and γi,j,n is the factor by which traffic fluctuates. In thissimulation, we generated the value of γi,j,n based on normal
random values whose average is 0 and variance is (λαi,j )2 .

Then, by changing the value of λ, we changed the size of thefluctuation in traffic.
Figure. 9 shows the results for λ = 0.05, 0.10, and0.15. In this simulation, we set N to 1. Like the simulation
described in the previous paragraph, the initial traffic matrix
was generated according to uniform random values. Then,we generated the traffic matrices after the beginning of the
VNT reconfiguration using Eq.(15). We set αi,j equal to theelement of the matrix generated by adding 2 Gbps to two
randomly selected elements of the initial traffic matrix. In thisgraph, the horizontal axis represents number of stages since
the beginning of the VNT reconfiguration, and the vertical axis
represents the average of squared estimation errors. From thisfigure, the smaller λ is, the faster we can reduce the estimation
errors. However, even when λ = 0.15, the additional equation
method can reduce estimation errors significantly because, inthis method, the number of equations used to estimate thetraffic matrix increases as it progresses through the stages.
The additional equations constrain the solution of the trafficmatrix estimation. Here, in this simulation, we generate thefluctuation component of traffic according to normal random
values whose average is 0. Therefore, no utilization monitored
in any stage is far from the traffic in the current stage. In
addition, the utilizations monitored in stages with temporallyhigh or low traffic are balanced out. As a result, since theconstraints from the additional equations are appropriate to
the current traffic, we can increase the accuracy of the trafficmatrix estimation as we progress through the stages.
2) Adaptability to sudden change in traffic: There is another type of change of traffic. The real traffic may change
suddenly. We evaluated the adaptability of our additional
equation method to such sudden changes in traffic. In thissimulation, we generated sudden changes in traffic by adding
2 Gbps to two randomly selected elements in the traffic matrix
described in the previous paragraph. We set λ to 0.10 and N
to 1 and added a sudden change in Stage 9.
Figure. 10 compares estimation errors for the following
three methods.
• Additional equation method (with detection of nonnegligible change)• Additional equation method (without detection of nonnegligible change)• Tomogravity
In this figure, the horizontal axis represents stages since theAverage of squared errors [Mbps*Mbps]

11

80000

R EFERENCES

70000

Tomogravity

60000
50000

Without detection of non-negligible change

40000
With detection of non-negligible change
30000
20000
10000
0
0

Fig. 10.

10

20

30

40
50
Stages60

70

80

Estimation errors when there is a sudden change in traffic

beginning of the VNT reconfiguration and the vertical axis
represents the average of squared estimation errors. In thisfigure, as in the case shown in Fig. 6, the tomogravity method
cannot reduce estimation errors because it uses only theutilization monitored at the current stage. On the other hand,the additional equation methods can reduce the estimation
errors as they progress through the stages. However, afterStage 9, the estimation errors of the additional equation
method without detection of non-negligible change increasesignificantly. This is because the utilization before the suddenchange, which is far from the current traffic, is used to estimate
the traffic matrix. These large estimation errors continue while
the additional equation method uses the information before thesudden change (i.e., until Stage 59). On the other hand, theadditional equation method with detection of non-negligible
change can reduce the estimation errors even after Stage 9
because it can remove the information about the traffic with
non-negligible change. That is, even when there is a suddenchange in traffic, by identifying and deleting the information
about the traffic with such changes, the additional equation
method can estimate a traffic matrix accurately. As a result,an accurate traffic matrix is available for VNT reconfiguration.
VII. C ONCLUDING R EMARKS
We have proposed a VNT reconfiguration and traffic matrix
estimation methods that reduce estimation errors during VNT
reconfiguration by cooperating with each other. Our method
reconfigures the VNT gradually by dividing it into multiple
stages and limiting the number of optical layer paths reconfigured in each stage. By dividing the VNT reconfiguration into
multiple stages, our traffic matrix estimation method calibrates
and reduces the estimation errors in each stage by using
information monitored in prior stages. As progresses throughthe stages, a more adequate VNT is configured with the morereliable traffic matrix obtained by our estimation methods.
In addition, by limiting the number of optical layer paths
reconfigured in each stage, our method avoids mistakenly
adding or deleting many optical layer paths. That is, ourreconfiguration method can mitigate the impact of estimation
errors. We have also investigated the effectiveness of our
proposal using simulations. The results show that our method
can improve the accuracy of the traffic matrix estimation andconstruct an adequate VNT. In future work we plan to set
parameters (e.g, N ) automatically.

[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] 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.
[3] 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.
[4] 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.
[5] 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.
[6] 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.
[7] 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.
[8] 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.
[9] 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.
[10] A. Nucci, R. Cruz, N. Taft, and C. Diot, “Design of IGP link weightchanges for estimation of traffic matrices,” in Proceedings of IEEE
INFOCOM 2004, vol. 4, pp. 2341–2351, May 2004.
[11] A. Soule, A. Nucci, R. Cruz, E. Leonardi, and N. Taft, “How to
identify and estimate the largest traffic matrix elements in a dynamic
environment,” in Proceedings of ACM SIGMETRICS, pp. 73–84, Dec.
2004.
[12] A. Soule, A. Nucci, R. Cruz, E. Leonardi, and N. Taft., “Estimating
dynamic traffic matrices by using viable routing changes,” IEEE/ACM
Transactions on Networking,, pp. 1063–6692, June 2007.
[13] M. Roughan, M. Thorup, and Y. Zhang, “Traffic engineering withestimated traffic matrices,” in Proceedings of ACM SIGCOMM Internet
Measurement Conference 2003, pp. 248–258, Oct. 2003.
[14] F. Yang, L. Li, S. Wang, and X. Zhang, “A novel method for virtual
topology design of WDM networks under traffic demand uncertainties,”in Proceedings of International Conference on Communications, Circuits
and Systems, vol. 3, pp. 1882–1886, June 2006.
[15] A. Soule, A. Lakhina, N. Taft, K. Papagiannaki, K. Salamatian, A. Nucci,
M. Crovella, and C. Diot, “Traffic matrices: Balancing measurements,
inference and modeling,” in Proceedings of ACM SIGMETRICS 2005,
pp. 362–373, June 2005.
[16] A. Gunnar, M. Johansson, and T. Telkamp, “Traffic matrix estimation
on a large IP backbone –a comparison on real data,” in Proceedings of
ACM SIGCOMM Internet Measurement Conference 2004, pp. 149–160,
Oct. 2004.
[17] A. Farrel, J. P. Vasseur, and J. Ash, “A path computation element (PCE)based architecture.” RFC 4655, Aug. 2006.
[18] B. S. Davie and Y. Rekhter, MPLS: Technology and Applications.
Morgan Kaufmann Publishers, 2000.
[19] J. C. Nash, Compact Numerical Methods for Computers: Linear Algebra
and Function Minimisation. Adam Hilger, 1990.
[20] Y. Ohsita, S. Ata, and M. Murata, “Identification of attack nodes fromtraffic matrix estimation,” in Proceedings of 4th International Trusted
Internet Workshop, Dec. 2005.

12

PLACE
PHOTO
HERE

PLACE
PHOTO
HERE

Yuichi Ohsita received the M.E. degree in Information and Computer Science from Osaka University,
Japan, in 2005. He is now an Assistant Professor
in the Graduate School of Economics at Osaka
University. His research interests include traffic matrix estimation and countermeasure against DDoS
attacks. He is a member of IEICE.

Takashi Miyamura received the B.S. and M.S.
degrees from Osaka University, Osaka, Japan, in
1997 and 1999, respectively. In 1999, he joined
NTT (Nippon Telegraph and Telephone Corp.) Network Service Systems Laboratories, where he wasengaged in research and development of a highspeed IP switching router. He is now researchingnext-generation backbone network architecture anddesign. He received Paper Awards from the 7th AsiaPacific Conference on Communications in 2001. He
is a member of the Operations Research Society ofEiji Oki received B.E. and M.E. degrees in Instrumentation Engineering and a Ph.D. degree inElectrical Engineering from Keio University, Yokohama, Japan, in 1991, 1993, and 1999, respecPLACE
tively. In 1993, he joined Nippon Telegraph and
PHOTO
Telephone Corporation’s (NTT’s) Communication
HERE
Switching Laboratories, Tokyo Japan. He has been
researching multimedia-communication network architectures based on ATM techniques, traffic-control
methods, and high-speed switching systems. From2000 to 2001, he was a Visiting Scholar at Polytechnic University, Brooklyn, New York, where he was involved in designing terabit switch/router systems. He is now engaged in researching and developing
high-speed optical IP backbone networks as a Senior Research Engineer withNTT Network Service Systems Laboratories. Dr. Oki was the recipient of the1998 Switching System Research Award and the 1999 Excellent Paper Award
presented by IEICE, and the 2001 Asia-Pacific Outstanding Young ResearcherAward presented by IEEE Communications Society for his contribution tobroadband network, ATM, and optical IP technologies. He co-authored two
books, “Broadband Packet Switching Technologies,” published by John Wiley,
New York, in 2001 and “GMPLS Technologies,” published by RC Press, Boca
Raton, in 2005. He is an IEEE Senior Member.

Japan.

PLACE
PHOTO
HERE

PLACE
PHOTO
HERE

Shin’ichi Arakawa received the M.E. and D.E.
degrees in Informatics and Mathematical Sciencefrom Osaka University, Osaka, Japan, in 2000 and
2003, respectively. He is currently an Assistant Professor at the Graduate School of Economics, Osaka
University, Japan. His research work is in the areaof photonic networks. He is a member of IEICE.

Shingo Ata received M.E. and Ph.D. degrees inInformatics and Mathematical Science from Osaka
University in 1998 and 2000, respectively. He isan Associate Professor in Information and Communication Engineering at Osaka City University,
Japan. His research works include networking architecture, design of communication protocols, andperformance modeling on communication networks.
He is a member of IEICE and ACM.

Kohei Shiomoto is a Senior Research Engineer,
Supervisor, Group Leader at NTT Network Service Systems Laboratories, Tokyo, Japan. He joined
the Nippon Telegraph and Telephone Corporation
PLACE(NTT), Tokyo, Japan in April 1989, where he was
PHOTO
engaged in research and development of ATM trafHERE
fic control and ATM switching system architecture
design. From August 1996 to September 1997, hewas engaged in research on high-speed networking
as Visiting Scholar at Washington University in St.
Louis, MO, USA. From September 1997 to June
2001, he was directing architecture design for high-speed IP/MPLS label
switching router research project at NTT Network Service Systems Laboratories, Tokyo, Japan. From July 2001 to March 2004, he was engaged
in the research fields of photonic IP router design, routing algorithm, and
GMPLS routing and signaling standardization at NTT Network Innovation
Laboratories. Since April 2004, he has been engaged in the research fieldsof photonic IP router design, routing algorithm, and GMPLS routing andsignaling standardization at NTT Network Service Systems Laboratories.
Since April 2006, he has been leading the IP Optical Networking ResearchGroup in NTT Network Service Systems Laboratories. He is active instandardization of GMPLS in the IETF. He received the B.E., M.E., and Ph.D
degrees in information and computer sciences from Osaka University, Osakain 1987 1989, and 1998, respectively. He is a member of IEICE, IEEE, andACM. He was a Secretary of International Relations of the Communications
Society of IEICE from June 2003 to May 2005. He was the Vice Chair ofInformation Services of IEEE ComSoc Asia Pacific Board from January 2004
to December 2005. He was engaged in organization of several international
conferences including HPSR 2002, WTC 2002, HPSR 2004, WTC 2004,
MPLS 2004, iPOP 2005, MPLS 2005, WTC2006, iPOP 2006, and MPLS
2006. He received the Young Engineer Award from the IEICE in 1995. Hereceived the Switching System Research Award from the IEICE in 1995 and2001. He co-authored ”GMPLS Technologies: Broadband Backbone Networks
and Systems (Optical Engineering)” Marcel Dekker Inc.

13

Masayuki Murata received the M.E. and D.E.
degrees in Information and Computer Sciences from
Osaka University, Japan, in 1984 and 1988, respectively. In April 1984, he joined Tokyo RePLACE
search Laboratory, IBM Japan, as a Researcher.
PHOTO
From September 1987 to January 1989, he was
HERE
an Assistant Professor with Computation Center,
Osaka University. In February 1989, he moved to the
Department of Information and Computer Sciences,
Faculty of Engineering Science, Osaka University.
From 1992 to 1999, he was an Associate Professor
in the Graduate School of Engineering Science, Osaka University, and from
April 1999, he has been a Professor of Osaka University. He moved to
Graduate School of Information Science and Technology, Osaka University
in April 2004. He has more than three hundred papers of international anddomestic journals and conferences. His research interests include computercommunication networks, performance modeling and evaluation. He is afellow of IEICE and a member of ACM, The Internet Society and IPSJ.