IEICE TRANS. COMMUN., VOL.Exx–??, NO.xx XXXX 200x

1

PAPER

Estimation of current traffic matrices from long-term traffic
variations
Yuichi OHSITA†a) , Takashi MIYAMURA††b) , Shin’ichi ARAKAWA†††c) , Eiji OKI††††d) , Members,
Kohei SHIOMOTO††e) , and Masayuki MURATA†††f) , Fellows

SUMMARY
Obtaining current traffic matrices is essential to traffic engineering (TE) methods. Because it is difficult to monitor traffic matrices,
several methods for estimating them from link loads have been proposed.
The models used in these methods, however, are incorrect for some real
networks. Thus, methods improving the accuracy of estimation by changing routes also have been proposed. However, existing methods for estimating the traffic matrix by changing routes can only capture long-term
variations and cannot obtain current traffic matrices accurately. In this paper, we propose a method for estimating current traffic matrices that uses
route changes introduced by a TE method. In this method, we first estimate the long-term variations of traffic by using the link loads monitored
at previous times. Then, we adjust the estimated long-term variations so as
to fit the current link loads. In addition, when the traffic variation trends
change and the estimated long-term variations fail to match the current
traffic, our method detects mismatch. Then, so as to capture the current
traffic variations, the method re-estimates the long-term variations after removing monitored data corresponding to the end-to-end traffic causing themismatches. We evaluate our method through simulation. The results showthat our method can estimate current traffic matrices accurately even whensome end-to-end traffic changes suddenly.
key words: Traffic Matirx, Estimation, Traffic Engineering

1.

Introduction

Obtaining current traffic matrices accurately is essential totraffic engineering (TE) methods [1–4]. By using the current
traffic matrices, TE methods configure routes on a network
so as to fit the current traffic. As a result, even when trafficchanges unpredictably, by reconfiguring routes, the network
can efficiently accommodate all traffic without congestion.
One approach for obtaining traffic matrices is to construct fully meshed label-switched paths using Multiprotocol Label Switching (MPLS) and directly measure the traffic
amounts over each path. This approach, however, does notscale because it requires N -squared label-switched paths.
Another approach is to tally the numbers of packets of each†
Graduate School of Economics, Osaka University, Toyonakashi, 560-0043 Japan††NTT Network Service Systems Laboratories, NTT Corporation, Musashino-shi, 180-8585 Japan†††
Graduate School of Information Science and Technology, Osaka University, Suita-shi, 565-0871 Japan††††
Department of Information and Communication Engineering,
The University of Electro-Communications, Chofu-shi 182-8585
Japana) E-mail: y-ohsita@econ.osaka-u.ac.jpb) E-mail: miyamura.takashi@lab.ntt.co.jpc) E-mail: arakawa@ist.osaka-u.ac.jpd) E-mail: oki@ice.uec.ac.jpe) E-mail: shiomoto.kohei@ist.osaka-u.ac.jpf) E-mail: murata@ist.osaka-u.ac.jp

end-to-end traffic flow at all edge nodes. This, however, isalso difficult to apply in large-scale networks, because tallying these numbers requires a non-negligible amount of CPU
resources at the edge nodes, and gathering the tallied data
for all end-to-end traffic also consumes a non-negligible
amount of network resources such as bandwidth.
Therefore, several methods for estimating traffic matrices from limited information have been proposed [5–14].
In such methods, an entire traffic matrix is estimated using
link loads that can be collected much more easily than by directly monitoring end-to-end traffic. Because the link load
is the sum of the traffic using a link, we haveX(n) = A(n)T (n),(1)

where X(n) is a matrix indicating the amount of traffic oneach link at time n, T (n) is the traffic matrix at time n, andA(n) is the routing matrix (i.e., a matrix in which an element
corresponding to an instance of end-to-end traffic and a linkis 1 if the end-to-end traffic passes the link or 0 if it doesnot). However, because the number of links is much smaller
than the number of elements of the traffic matrix, Eq. (1) has
multiple solutions in which true traffic matrix is included.
Therefore, several methods use traffic matrix models
to estimate the traffic matrix. For example, the tomogravity method [5] uses a model called the gravity model, in
which the amount of traffic from a source node to a destination node is proportional to the total incoming or outgoingtraffic for each edge node. According to [15], however, thegravity model does not fit the actual traffic in some real networks. Traffic matrices estimated by this method include
estimation errors, such as underestimates of end-to-end traffic whose amounts are actually large. As a result, when a TE
method uses traffic matrices estimated by this method, theseunderestimates can cause high link utilizations.
Recently, several methods estimating the traffic matrices more accurately by using additional measurements havebeen proposed [12–14]. These methods obtain the additional measurements by changing the routing matrices andobserving the differences between the link loads before andafter the route changes. For example, Ref. [12] obtains additional measurements by changing routes via a TE method.
By performing TE a sufficient number of times, this approach obtains a sufficient number of measurements andthen estimates the traffic matrix by assuming that the true
traffic matrix does not change throughout the TE method
execution. It takes a long time to change routes sufficientIEICE TRANS. COMMUN., VOL.Exx–??, NO.xx XXXX 200x

times, however, so the current traffic can differ from the initial traffic monitored before the first route change. Therefore, we need a traffic matrix estimation method that considers the time variations of traffic matrices. Ref. [14] proposesa method for modeling traffic variations by using periodic
functions and estimates these functions’ parameters. Whentraffic changes unpredictably, however, a TE method cannot configure routes suitable for the current traffic by using
the traffic variations estimated by this approach, since it can
only estimate the average variations of traffic for a period ofa day by monitoring link loads for several days.
Therefore, in this paper, we propose a new estimation
method, with which we can accurately estimate current traffic matrices by using the route changes introduced via a TE
method. Unlike in Ref. [14], the purpose of our method is toestimate not the long-term variations of traffic but the current traffic matrix, which consists of both long-term variations and short-term variations. By using the accurate trafficmatrix, a TE method can properly work to configure routes
suitable for the current traffic.
In our method, we first estimate the long-term variations of traffic by using the link loads monitored at previous
times. Then, we adjust the estimated long-term variations
so as to fit the current link loads. In addition, when the
traffic variation trends change and the estimated long-term
variations fail to match the current traffic, our method detects mismatch between the estimated long-term variations
and the current traffic. Then, our method re-estimates thelong-term variations after removing monitored data corresponding to the end-to-end traffic causing the mismatches,
so as to capture the current traffic variations.
The rest of this paper is organized as follows. Section 2
describes the proposed method for estimating current trafficmatrices by using route changes. Then, in Section 3, we givethe results of evaluating our method through simulation. Finally, Section 4 provides a conclusion.
2.

2.1

Method for estimating current traffic matrix by using changes in routes
Overview of estimation method

In this paper, we propose a new method for estimating current traffic matrices accurately. We assume that a TE method
sometimes changes routes in the network. Under this condition, we can obtain additional measurements, which can beused in estimating the traffic matrices, by monitoring linkloads while some routes are changed.
Because it takes a long time to change routes enoughtimes to obtain a sufficient amount of additional measurements, however, the difference between the initially monitored link loads and the current traffic might be very large.
Therefore, we need to consider long-term variations. By using the link loads monitored at previous times, our method
estimates the long-term variations of traffic instead of estimating the current traffic matrices directly. Then, we obtainthe current traffic matrices by adjusting the estimated long-

Traffic Volume between OD pair2(1) Estimate long-term
variations of traffic(2) Adjust estimated longterm variations so as to fit
current link loads(3) Detect mismatch between
estimated long-term variations
and current trafficTime

Fig. 1

Overview of proposed method

term variations so as to fit the current link loads.
In addition, when the traffic variation trends change,
the changes may cause significant estimation errors if we
also use link loads monitored before the changes, since thedifferences between these previously monitored link loads
and the current traffic can be very large. Therefore, in our
method, we check whether the estimated long-term variations match the current link loads. Then, if the mismatch isdetected, we re-estimate the long-term variations.
Fig. 1 shows an overview of the proposed estimation
method. Our method estimates the traffic matrix throughthe following steps.
Step 1 Estimate the long-term variations of the traffic matrices by using the link loads monitored at previous
times.
Step 2 Obtain estimation results of the current traffic matrix
by adjusting the estimated long-term variations so as tofit the current link loads.
Step 3 Check whether the estimated long-term variations fit
the current link loads. If they do not match the current
link loads, return to Step 1 after removing the previously monitored data about the end-to-end traffic causing the mismatch. Otherwise, proceed to Step 4.
Step 4 Designate the estimation results from Step 2 as the
final estimation results.
In subsection 2.2, we describe the method for estimating the long-term traffic variations. Subsection 2.3 explains
how to adjust the estimated long-term variations so as to fit
the current link loads. Subsection 2.4 describes how to thedetect mismatches between the estimated long-term variations and the current traffic, and how to re-estimate the longterm variations and the current traffic matrix after mismatchdetection.
2.2

Estimating long-term traffic variations

2.2.1 Traffic variation model
According to [14], the amount of traffic between each nodepair varies periodically with a certain cycle, such as one day
or one week. Therefore, in this paper, we model the traffic
amount between nodes i and j asti,j (n) = fi,j (n) + δi,j (n),(2)

OHSITA et al.: ESTIMATION OF CURRENT TRAFFIC MATRICES FROM LONG-TERM TRAFFIC VARIATIONS

3

where ti,j (n) is the traffic volume between nodes i and j attime n, fi,j (n) is a function modeling the periodic variation,and δi,j (n) is the variation not included in fi,j (n). In our
method, we estimate the long-term variations by modelingfi,j (n) and estimating its parameters.
We model fi,j (n) by applying the model used in [14].
This approach models the periodic traffic variation by using Fourier series expansion. With this model, the periodic
variation is represented asfi,j (n) =Nfαh,i,j cos

h=0

+

Nf


2πnh
N cycle

αh+Nf ,i,j sin

h=0



2πnh
N cycle.

(3)

where N cycle is the number of times monitoring link loads
in each cycle, Nf is a parameter determining the numberof terms in Eq. (3), and the αh,i,j are the variables to be
estimated by our estimation method.
This equation can model any periodic traffic variations
by setting Nf to a sufficiently large value. However, setting Nf to a large value, the number of variables to be estimated also increases. In our method, we only have toroughly model the traffic variations, because we can estimate the current traffic matrix by adjusting the roughly estimated long-term variations. That is, in our method, a small
Nf is sufficient.
Though our method uses the periodical function tomodel the traffic variation, there are other estimation methods that do not use the periodical function. For example,
Ref. [16] uses Kalman filter. The method requires to monitor end-to-end traffic in advance. In our model, we can estimate the traffic from αh,i,j that is estimated from the linkloads. We discuss the method to estimate them in subsection 2.2.2.
2.2.2 Method for estimating long-term variations
In the model described by Eq. (3), the variables αh,i,j determine the long-term variations. Therefore, our method estimates the long-term variations by estimating the αh,i,j . We
estimate the αh,i,j by using the link loads monitored at previous times. At any time n, the link loads and the trafficmatrix have a relation described by Eq. (1). Therefore, weestimate all variables so as to satisfy Eq. (1) in any time. In
this paper, we use a least square algorithm to estimate thevariables. That is, when the number of nodes is N , by using
the link loads monitored from the time n − M + 1 to n, thevariables are basically estimated asminimizen
k=n−M +1

where|X(k) − A(k)T̂ est (k)|2(4)⎤
f0,0 (k)
⎥
⎢
..
⎥
⎢
.
⎥
⎢
est
⎥.
⎢
f
(k)
T̂ (k) = ⎢ i,j
⎥
⎥
⎢
..
⎦
⎣
.
fN,N (k)⎡(5)

By using Eq. (4), when some routes are changed, we canuse additional equations for estimating the variables.
With Eq. (4), however, we may not be able to estimate
the long-term variations accurately because of the effects oftraffic variations that cannot be modeled by Eq. (3). Because the actual traffic variations do include variations thatcannot be modeled by Eq. (3) (i.e., δi,j (n) in Eq. (2)), longterm variations modeled by Eq. (3) cannot completely fit all
the monitored link loads. With Eq. (4), however, we estimate the long-term variations so as to completely fit all themonitored link loads. As a result, estimation results from
Eq. (4) can be affected by traffic variations that cannot bemodeled by Eq. (3), making the results very different fromthe actual traffic.
To mitigate the impact of δi,j on the estimated longterm variations, in our method, by placing constraints on
the variables themselves, we avoid estimating the long-term
variations so as to completely fit all the monitored link loads.
We thus use the following equation instead of Eq. (4):minimizen|X(k) − A(k)T̂ est (k)|2k=n−M +1

+Φ


i,j

⎛
⎝mi,j

2Nf



(6)
⎞


(αh,i,j − αh,i,j)2 ⎠ ,

h=0

where the αh,i,j
are the variables estimated the previous
time, mi,j is the amount of previously monitored data, andΦ denotes a parameter by which we can set the weight to theconstraints on the variables themselves. Using this equation,
we estimate all the αh,i,j (0 ≤ h ≤ 2Nf ) of fi,j (n) so as
to fit all the monitored link loads while keeping the values
close to the values estimated the previous time.
When we estimate the long-term variations the first. Thus, intime, however, we have not obtained the αh,i,j
to the elements of traffic masuch cases, we set the α0,i,j
trices estimated by other methods [5–11], and we set the(1 ≤ h ≤ 2Nf ) to 0. By using this approach, we
αh,i,jcan avoid estimating traffic variations as having significantly
larger values than the actual variations.
are not accurate,
In addition, even if the initial αh,i,j
we can estimate the long-term variations more accurately
by using link loads monitored at multiple times as additional
measurements. Then, when we estimate the long-term vari. Thatations the next time, we can use more accurate αh,i,j
is, as we estimate the long-term variations more times, theaccuracies of these estimations increase.
The estimated long-term variation T̂ est (n) may include
negative values. However, we do not eliminate the negativevalues included in T̂ est (n) here, because we eliminate theIEICE TRANS. COMMUN., VOL.Exx–??, NO.xx XXXX 200x

4

negative elements during the adjustment of long-term variations as described in subsection 2.3.
2.3

Adjustment of estimated long-term variations

By using the method in subsection 2.2, we estimate the longterm variations. Because these estimates do not include theδi,j (n) in Eq. (2), however, they do not fit the current linkloads. Therefore, we adjust the long-term variations so as tofit the current link loads.
The adjustment is performed by the method used inRef. [5, 7]. This method calculate the traffic matrix that is
consistent with the current link loads and that is close to a(given) initial traffic matrix. In our case, the initial trafficmatrix is the estimated long-term variations. The method
works as follows. First, by assigning n to the functions corresponding to the estimated long-term variations, we obtaina roughly estimated traffic matrix T̂ est (n). Then, we obtaina traffic matrix T̂ (n) that is close to T̂ est (n) and fits the linkloads monitored at time n. That is, we obtain the estimation
results by applying a least square algorithm so as to satisfy
the following conditions:minimize|T̂ (n) − T̂ est (n)|2

(7)

where
A(n)T̂ (n) = X(n).

(8)

A traffic matrix estimated by a least square algorithm,
however, can include negative values, which are meaningless in the context of a traffic matrix. Therefore, we eliminate negative values through the following steps. We denotethe estimated traffic matrix for the i-th iteration as T̂ (i) (n).
Step 1 Let T̂ (0) (n) ← T̂ (n).
Step 2 Obtain the matrix T̂ (i) (n), in which we replace all
the negative values of T̂ (i) (n) with zero.
Step 3 Obtain D(i) (n) satisfying the following condition:
minimize|D(i) (n)|2

(9)

where

 

A(n) T̂ (i) (n) + D(i) (n) = X(n).

(10)



Step 4 Let T̂ (i+1) (n) ← T̂ (i) (n) + D(i) (n).
Step 5 If all elements of T̂ (i+1) (n) are non-negative, proceed to Step 6. Otherwise, return to Step 1.
Step 6 Let T̂ (i+1) (n) be the final result for the traffic matrixT̂ (n).
2.4

Re-estimation of traffic matrix after mismatch of estimated long-term variations

When traffic variation trends change, long-term variations
estimated by using all the link loads monitored at previous
times can exhibit mismatches with the current traffic. Thisis because the long-term variations are estimated so as to fit

the link loads before the change, which can be significantly
different from the current traffic variations.
In such cases of mismatch, we cannot estimate the current traffic matrices accurately even after adjustment, because the adjustment uses only the current link loads, which
are insufficient for estimating the traffic matrices accurately.
Therefore, in our method, when the estimated longterm variations exhibit mismatches with the current traffic, we detect the mismatches and re-estimate the long-term
variations without using link loads that do not match thecurrent traffic. In this subsection, we describe how to detect mismatches and identify the end-to-end traffic causing
the mismatches, as well as how to re-estimate the long-term
variations after mismatch detection.
2.4.1 Detecting mismatches and identifying end-to-end
traffic causing mismatches
When the difference between the estimated long-term variation and the current traffic is large, the differences between
the current link loads and the link loads calculated using theestimated long-term variations are large. In this case, because the results of adjusting T̂ (n) must satisfy Eq. (8),while difference between A(n)T̂ est (n) and the current linkloads X(n) is very large, the elements of T̂ est (n) − T̂ (n),corresponding to the traffic causing the mismatches, become large. Therefore, we detect mismatches and identify
the end-to-end traffic causing the mismatches by evaluatingT̂ est (n) − T̂ (n).
Because the size of traffic variation that cannot be included in Eq. (3) depends on the end-to-end traffic [14], if
we set a single threshold for the elements of T̂ est (n)− T̂ (n),traffic with large variations that cannot be modeled by Eq.
(3) will be erroneously detected as traffic causing mismatches.
Therefore, we detect mismatches and identify theirsources by comparing T̂ est (n) − T̂ (n) with its previous values. Our method performs the comparison by using theSmirnov-Grubbs method [17], which can easily detect outliers in sampled data.
Here, we define the elements of T̂ est (n) and T̂ (n) corresponding to the traffic between nodes i and j as t̂est
i,j (n)and t̂i,j (n) respectively. In the Smirnov-Grubbs method, we
detect whether |t̂est
i,j (n) − t̂i,j (n)| is an outlier by calculating
di,j =|t̂esti,j (n) − t̂i,j (n)| − μi,j
,
σi,j

(11)

where μi,j and σi,j are the average and standard deviationof |t̂esti,j (k) − t̂i,j (k)|(n − M + 1 ≤ k ≤ n), respectively.
Then, |t̂est
i,j (n) − t̂i,j (n)| is detected as an outlier if di,j islarger than the theshold

2
τθ,M
+2
τ = (M − 1)
(12)2
M (M − 2) + M τθ,M+2
where M is the number of samples, θ is a parameter spec-

OHSITA et al.: ESTIMATION OF CURRENT TRAFFIC MATRICES FROM LONG-TERM TRAFFIC VARIATIONS

5

ifying the detection sensitivity, and τθ,M is a value corresponding to the top θ/M % points of the T distribution with
M − 2 degrees of freedom.
Too small σi,j causes detection of points where(n)− t̂i,j (n)| is small. We do not, however, need to|t̂esti,jdetect such points, because the estimated long-term variations there fit the current traffic, since |t̂est
i,j (n) − t̂i,j (n)| issmall. Therefore, to avoid detecting such points, we introduce a parameter s and set σi,j to s if σi,j is smaller thans.
2.4.2 Re-estimation of long-term variations after detection
When mismatches between the estimated long-term variations and the current traffic are detected, we need to reestimate the long-term variations so as to fit the current
traffic. Because such mismatches occur when we estimate
the long-term variations by using previously monitored linkloads which are significantly different from the current traffic variations, we re-estimate the long-term variations by using link loads and routing matrices in which elements corresponding to the end-to-end traffic causing the mismatches
has been removed.
Our method removes elements corresponding to theend-to-end traffics causing mismatches at time n throughthe following steps. We first remove such elements from therouting matrices A(i)(n − M + 1 ≤ i < n) by setting elements corresponding to the identified end-to-end traffic to
0. We denote the routing matrix after such replacement as
A (i).
Then, we create a link load matrix X  (i)(n − M + 1 ≤i < n) from which elements about the identified end-toend traffic has been removed. The sum of the elementsof traffic matrix T corresponding to the identified end-toend traffic traversing each link at time i is calculated as(A(i) − A (i)) T . Therefore, Xi is given byX  (i) = X(i) − (A(i) − A (i)) T̂ est (i).

(13)



where T̂ est (i) is the traffic matrix at time i calculated using
the estimated long-term variations. In calculating T̂ est (i),we use the long-term variations estimated at time n−1, since
the long-term variations estimated at time n can be affectedby changing trends.
Next, our method re-estimates the long-term variations
by using Eq. (14), which is refined from Eq. (6) to useX  (k) and A (k):minimizen−1|X  (k) − A (k)T̂ est (k)|2(14)

k=n−M +1+|X(n) − A(n)T̂ est (n)|2
⎛
⎞
2Nf



⎝mi,j
+Φ
(αh,i,j − αh,i,j)2 ⎠ .
i,jh=0

We only have to re-estimate the long-term variations
so as to fit the current traffic, because the purpose of our

method is to estimate the current traffic matrix. Moreover,in estimating the traffic amounts of the identified end-to-end
traffic by using Eq. (14), we do not need to consider the
related traffic variations, because the traffic amounts corresponding to the identified traffic are included only in X(n).
Therefore, in re-estimating the long-term variations,
we model the amounts of the identified end-to-end trafficbyfi,j (n) = α0,i,j ,(15)instead of using Eq. (3). By using Eq. (15), we can minimize the number of variables to be estimated.
In this re-estimation method, we remove a previously
monitored data corresponding only to the end-to-end traffic
causing the mismatch. Yet, the end-to-end traffic causing themismatch can be estimated accurately from the current linkloads, because the other end-to-end traffic not causing themismatch are accurately estimated by using the previously
monitored data.
2.4.3 Re-estimation of traffic matrix after re-estimation of
long-term variations
After re-estimating the long-term variations, we re-estimate
the current traffic matrix through the same steps describedin subsection 2.3.
3.

Evaluation

3.1

Metrics

In this section, we describe an evaluation of our method bysimulation. In the simulation, we evaluated our method by
two general metrics: (1) the accuracy of estimation, and (2)the performance of a TE method using the estimated trafficmatrices.
To evaluate the accuracy, we used two specific metrics– the root mean squared error (RMSE), and the root meansquared relative error (RMSRE) – as defined below:1(t̂i,j (n) − ti,j (n))2(16)
RMSE =
2
N
1≤i,j≤N
 1
RMSRE =  2Nt̃1≤i,j≤N,ti,j >t̃t̂i,j (n) − ti,j (n)ti,j (n)2

The RMSE gives an overall measure for the errors inestimation, while the RMSRE gives a relative measure. For
small matrix elements, however, the relative errors are notreally important. Thus, in computing the RMSRE, we consider only matrix elements greater than a threshold t̃. Nt̃ isthe number of elements greater than t̃ in a traffic matrix. In
the following simulation, t̃ was set so that the sum of theend-to-end traffic whose actual rate was greater than t̃ composed 75 % of the total traffic.
To evaluate the performance of a TE method using the(17)

IEICE TRANS. COMMUN., VOL.Exx–??, NO.xx XXXX 200x

6
5

14
8

0

15

13
1
7
16
6

2

10

4

12

9

3

17

11

Fig. 2

Case without sudden traffic changes

In this subsection, we investigate the accuracy of our method
for estimating the long-term variations and the effectivenessof adjusting the estimated long-term variations when there
are no sudden traffic changes. In the simulation, we set M =160 and Nf = 2.

18

EON topology

estimated traffic matrices, we investigated whether the purpose of the TE method was achieved. The next subsection
describes the purpose of the TE method used in our simulation.
3.2

3.3

Environment used in evaluation

In our method, we assume that a TE method changes routes
sometimes. In this evaluation, we used the optical layer TE
as an example of a TE method. The optical layer TE establishes optical layer paths between two IP routers over aphysical network consisting of IP routers and optical crossconnects (OXCs). A set of optical layer paths forms a virtual network topology (VNT). Traffic between two routers is
carried over the VNT by using IP layer routing. Under these
conditions, the optical layer TE accommodates traffic thatfluctuates widely by dynamically reconfiguring the VNT.
In our simulation, we used the European Optical Network (EON) (19 nodes, 37 links) shown in Fig. 2 as thephysical topology and executed the optical layer TE method
proposed in [12] once an hour. The purpose of this method
is to keep the maximum link utilization under the threshold
TH . In this method, optical layer paths are added or deletedwith a limitation on the number of optical layer paths reconfigured at one time. Optical layer paths are added if at least
one path whose utilization exceeds the threshold TH exists.
Otherwise, if there is an optical layer path whose utilizationis less than a threshold TL , the path is deleted. In this simulation, we set the maximum number of optical layer paths
reconfigured at one time to 30, TH to 0.7, and TL to 0.4. We
set the bandwidth for an optical layer path to 10 Gbps. We
implement the above TE method by using C++.
In our simulation, we implement our estimation
method by using MATLAB. The link loads used as the inputs of the estimation program are calculated by the actual traffic matrices and current routes. In the simulation,
the actual end-to-end traffic are generated by setting theamplitudes and phases of the sin functions randomly toshow that our method can estimate traffic matrices accurately even when there are no correlation between phasesof end-to-end traffics. The cycles of the sin functions are
set to 1 day. Futhermore, we add the random variations lessthan 0.25 times the amplitudes to the sin functions. Link
loads are monitored once per 20 minutes. That is, N cycle is
24×60
= 72.
20

3.3.1 Accuracy of estimation of long-term variations
In our method, we estimate long-term traffic variations byusing Eq. (6) instead of Eq. (4) to avoid the impact of traffic
variations that cannot be modeled by Eq.(3). Therefore, toverify the effectiveness of using Eq. (6), we compared theestimation results obtained with Eqs. (4) and (6).
Note that estimation results obtained with Eq. (6) depend on previously estimated variables (i.e., the long-term
variations are accurately estimated when the estimation results of the previous time are accurate). Here, however, because the purpose of this comparison was to verify the effectiveness of adding constraints on the variables themselves, we set α0,i,j= μ andeven in the case of inaccurate αh,i,j
αh,i,j = 0(1 ≤ i ≤ 2Nf ), where μ is the total volume ofincoming traffic divided by the amount of end-to-end traffic.
Figure 3 shows the comparison results. As seen fromthis figure, both Eq. (4) and Eq. (6) can be applied to accurately estimate the traffic between nodes 2 and 14. The traffic between nodes 12 and 16, however, cannot be estimatedaccurately with Eq. (4), and the estimated traffic variation issignificantly larger than the actual traffic variation.
This is because Eq. (4) estimates the variables so as tocompletely fit all the link loads monitored at previous times,
even though the actual traffic variations include those thatcannot be modeled by Eq. (3) (i.e., δi,j (n) in Eq. (2)). As aresult, the long-term variations estimated by Eq. (4) are affected by δi,j (n), and the long-term variations of some endto-end traffic become very different from the actual variations.
On the other hand, by using Eq. (6), we can avoid estimating variations as significantly larger than the actual variations. That is, by adding constraints on the variable themselves, we can mitigate the impact of δi,j (n) and increase
the accuracy of estimating long-term variations.
Next, to evaluate the effectiveness of the constraints on
the variables themselves in detail, we estimated the longterm variations with various values of Φ. Figure 4 shows therelation between Φ and the maximum RMSRE for the estimated long-term variations. According to this figure, when
Φ is set to a value close to 0, the RMSRE becomes larger.
This is because with small values of Φ, the estimation results
become more sensitive to δi,j (n). As a result, δi,j (n) causes
estimation errors like that shown in Fig. 3(b). On the other
hand, with large values of Φ, the variables in the long-term. As avariations are estimated so as to be close to the αh,i,j
result, when Φ is too large, the long-term variations cannot
be estimated so as to fit the monitored link loads. The opti-

OHSITA et al.: ESTIMATION OF CURRENT TRAFFIC MATRICES FROM LONG-TERM TRAFFIC VARIATIONS

7

8
Estimated amount
Actual amount7

Traffic amount [Gbps]

Traffic amount [Gbps]

8
6
5
4
3
2
1
0

Estimated amount
Actual amount

7
6
5
4
3
2
1
0

0

10

20

30

40

50

60

0

10

20

Time [Hour](a) Traffic between nodes 2 and 14 (case of using Eq.(4))

50

60

8
Estimated amount
Actual amount7

Traffic amount [Gbps]

Traffic amount [Gbps]

40(b) Traffic between nodes 12 and 16 (case of using Eq.(4))

8
6
5
4
3
2
1
0

Estimated amount
Actual amount

7
6
5
4
3
2
1
0

0

10

20

30

40

50

Time [Hour]Fig. 3

60

0

10

20

30

40

50

60

Time [Hour](c) Traffic between nodes 2 and 14 (case of using Eq.(6) with Φ=0.01)

Average of squared errors

30Time [Hour](d) Traffic between nodes 12 and 16 (case of using Eq.(6) with Φ=0.01)

Results of estimating long-term variations

with the accuracies of the following methods:

0.35
0.3
0.25
0.2
0.15
0.1
0.05
0
0

0.005 0.01 0.015 0.02 0.025
ΦFig. 4

RMSRE vs. Φ

mal Φ depends on the environment (e.g., the amplitudes oftraffic variations), and determining optimal value of Φ is agoal for our future works. From Fig. 4, however, we can seethat the estimation errors are not significant even if Φ is not
optimal.
3.3.2 Effectiveness of adjustment
In our method, we obtain estimation results by adjusting theestimated long-term variations so as to fit the current linkloads. Therefore, we investigated the effectiveness of adjusting the estimated long-term variations, by comparing theaccuracy of the estimated traffic matrices after adjustment• A method using only the current link loads. By comparison with this method, we investigated the effectiveness of using the link loads monitored at previous times. For this method, we used the tomogravity
method with the simple gravity model [5]. Although
the simple gravity model does not fit the traffic matrices
used in our simulation, because we use randomly generated traffic matrices, this model also is not incorrect
in some real networks [15]. The focus of this comparison is the effectiveness of using link loads monitored
at previous times when the simple gravity model is notcorrect.
• A method using the link loads monitored at previous
times but not considering the time variations of traffic. By comparison with this method, we investigatedthe effectiveness of modeling long-term traffic variations. For this method, we used the additional equation
method proposed in [12].
• A method using the link loads monitored at previous times but only estimating the long-term variations.
That is, this method uses T̂ est (k) described in subsection 2.3 as the final estimation results. We call this

IEICE TRANS. COMMUN., VOL.Exx–??, NO.xx XXXX 200x

1400
Our method
Long-term estimation
Additional equation method
Tomogravity

1200

800

0.5

8

0.4

6

0.3

4

0.2

d

RMSE [Mbps]

1000

10

600
400

d
Estimation error

2
200

0

10

Fig. 520

30
40Time [Hour]

50

Time variation of RMSE

Fig. 7

0.3
0.6
0.9
1.2
Rate of additional traffic

1.5

d2,14 vs. rate of added traffic

rately as long as the amount of traffic between each nodepair varies periodically because Eq. (3) can model any periodic traffic variations by setting Nf to a sufficiently large
value.

Our method
Long-term estimation
Additional equation method
Tomogravity

0.6

0
0

60

0.7

0.5
RMSRE

0.1

0

0

Relative error

8

0.4
0.3

3.4

0.2
0.1
0
0

10

Fig. 620

30
40Time [Hour]

50

60

Time variation of RMSRE

method Long-term estimation. By comparison withthis method, we investigated the effectiveness of adjusting the estimated long-term variations so as to fit
the current link loads. In this simulation, for estimating the long-term variations, we set Φ to 0.01.
Figures 5 and 6 show the RMSE and RMSRE, respectively, at each time. The results show that the errors for the
tomogravity method are the largest. This is because the tomogravity method uses only the current link loads, which
is an insufficient amount of measurements, while othermethods use the additional measurements caused by routechanges.
However, the errors for the additional equation method
are also large. This is because that method does not consider traffic variations but assumes instead that the true traffic matrix does not change during TE execution. Therefore,
this method cannot estimate traffic matrices accurately whentraffic varies, even while monitoring the link loads a sufficient number of times.
On the other hand, the errors for the method estimating the long-term variations are relatively small. That is,
by including the link loads monitored at previous times inconsidering the time variations of traffic, we can effectively
use the additional measurements caused by route changes
and estimate traffic matrices accurately. In addition, by adjusting the estimated long-term variations, we can estimate
traffic matrices even more accurately. This is because theadjustment enables the estimation results to also follow traffic variations that cannot be modeled by Eq. (3).
The traffic variations in the real networks may be different from the traffic matrices used in this simulation. Even
if the traffic variations are different from the case of thissimulation, our method can estimate traffic matrices accu-

Case with sudden traffic changes

In the previous subsection, we evaluated our method in thecase without sudden traffic changes. In real networks, however, traffic can change suddenly, and traffic variation trends
can also change. When the trends change and the estimatedlong-term variations do not match the current traffic, ourmethod detects mismatch and identifies the end-to-end traffic causing them, after which it re-estimates the long-term
variations. In this subsection, we investigate the accuracyof this detection and the effectiveness of re-estimation after
detection. In addition, we investigate how well a TE method
works when it uses traffic matrices estimated by our method.
In all the simulations described below, we set Φ to 0.01, θ to
0.01, and s to 60 Mbps.
3.4.1 Accuracy of detection of trend changes
To investigate the accuracy of mismatch detection, we calculated d2,14 for the traffic generated by adding suddenchanges to the traffic between nodes 2 and 14 in the scenario
from the previous subsection. Figure 7 shows the results. In
Fig. 7, the horizontal axis represents the rate of added traffic
divided by the maximum rate of traffic before the addition,and the vertical axis represents d2,14 . In addition, we show
the maximum relative error corresponding to the traffic between nodes 2 and 14 for the case without re-estimation.
From this figure, we can see that the larger the added
traffic is, the larger d2,14 becomes. This is because the difference between the estimated long-term variations and thecurrent link loads becomes large when the rate of added traffic is large. As a result, the differences between the trafficmatrices before and after adjustment also become large. In
this simulation, because we set M to 160 and θ to 0.01, thethreshold τ calculated from Eq. (12) is 3.75. Therefore, if
the added traffic is more than 0.3 times the rate of the traffic
before addition (i.e., when the added traffic causes a relative
error of more than 0.20 in the case without re-estimation),
we can detect mismatches between the estimated traffic variations and the current traffic. In this situation, our method

OHSITA et al.: ESTIMATION OF CURRENT TRAFFIC MATRICES FROM LONG-TERM TRAFFIC VARIATIONS

Fig. 81400

1

Our method with re-estimation
Our method without re-estimation
Additional equation method
Tomogravity

1200

0.1

RMSE [Mbps]

Complementary cumulative distribution

9

0.01

0.001

1000
800
600
400
200
0
0

0.0001
-2

-1

0

1

2
d

3

4

5

6

Complementary cumulative distribution of di,j with no changes

re-estimates the long-term variations so as to fit the current
traffic.
In detecting mismatches, false positives (i.e., the casesof mistakenly detecting end-to-end traffic with no changes)
can occur. Thus, we investigated the likelihood of suchfalse positives. Figure 8 shows the complementary cumulative distribution of di,j in the case without adding sudden changes. The vertical line in Fig. 8 represents 3.75,
the threshold τ calculated above. This figure shows thatthe probability of mistaken detection in the case with nochanges is about 0.03 %. We discuss the impacts of these
false positives later.
3.4.2 Effectiveness of re-estimation
When mismatches between the estimated long-term variations and the current traffic are detected, we re-estimate thelong-term variations after removing monitored data about
the end-to-end traffic identified as causing the mismatches.
In this subsection, we investigate the effectiveness of the reestimation through simulation. In this simulation, we usedtraffic generated by adding sudden changes to the traffic
used for the simulation described in the previous subsection.
We added sudden increases to the traffic from nodes 2 to 4,
9 to 1, and 0 to 12 at times 22, 36, and 47, respectively. The
rates of the sudden increases from nodes 2 to 4, 9 to 1, and0 to 12 were, respectively, 120 % , 150 %, and 160 % of the
maximum rate of traffic before the addition. The increased
rates from nodes 2 to 4 and 9 to 1 continue until the end of
this simulation. The increased rate from 0 to 12 continues
for 1 hour.
Figure 9 shows the RMSE when we added these sudden
traffic changes, for four different methods: our method withre-estimation, our method without re-estimation, the additional equation method, and the tomogravity method. For
our method without re-estimation, we estimated the longterm variations and adjusted them but did not re-estimate
them even when the variation trends changed.
From this figure, similarly to the results shown in
Figs. 5 and 6, we can see that the RMSEs for the tomogravity method and the additional equation method are large.
The figure also shows that the RMSE for our method without re-estimation is small before time 22 but increases afterward, whereas the RMSE for our method with re-estimation
remains small after time 22. This difference is caused by theFig. 9

10

20

30
40
Time {Hour]

50

60

Time variation of RMSE (when some traffic variations change)

sudden changes, whose impact we discuss in detail later.
The results shown in Fig. 9 also verify that the impactof false positives is small. As described above, about 0.03 %of the end-to-end traffic without changes in the traffic variation trends will be mistakenly identified as causing mismatches between the estimated long-term variations and thecurrent traffic. For example, at time 21 in Fig. 9, the end-toend traffic between nodes 1 and 10 is mistakenly identified
as causing a mismatch. From the figure, however, we cansee that the RMSE for our method does not become significant even when such false positives occur; it always remains the smallest among the four methods. This is because
we have sufficient measurements to estimate the long-term
variations and traffic matrices accurately even when somefalse positives occur and measurements about the mistakenly identified end-to-end traffic is removed.
To investigate the impact of sudden changes in detail,
we compared the estimation results obtained for traffic withsudden changes added. Figures 10 and 11 show the estimation results for our method with and without re-estimation,
respectively.
These figures show that both methods can accurately
estimate all the traffic amounts before adding the suddenchanges. After adding the changes, however, the traffic rateestimated by our method without re-estimation cannot capture the changes. This is because that method also uses
the link loads monitored before adding the sudden changes,
which are significantly different from the current traffic variations. Therefore, because of this link loads that does not fit
the current traffic variations, the long-term variations cannot be estimated accurately. Even though we adjust the estimated long-term variations so as to fit the current link loads,
the adjusted results still do not capture the sudden changes,
because the adjustment process can use only the current linkloads, which is insufficient to estimate the traffic matrices
accurately.
On the other hand, our method with re-estimation canestimate all the traffic amounts accurately even after adding
the sudden changes. This is because by re-estimating thelong-term variations after removing monitored data about
the end-to-end traffic causing the mismatches between theestimated long-term variations and the current traffic, weavoid the impact of monitored link loads which are significantly different from the current traffic variations.
According to the result of traffic between nodes 0 and
12, our method can correctly detect sudden changes in the

IEICE TRANS. COMMUN., VOL.Exx–??, NO.xx XXXX 200x

10

12

10
8
6
4
2

10
8
6
4
2

0

0
0

10

20
30
40
Time [Hour]

50

60

10

20
30
40
Time [Hour]

50

6
4
2
0
50

60

20
30
40
Time [Hour]

50

60

12
Estimated amount
Actual amount

10
8
6
4
2

Estimated amount
Actual amount

10
8
6
4
2
0

0

(a) Traffic between nodes 2 and 4

10

20
30
40
Time [Hour]50(b) Traffic between nodes 9 and 1
Fig. 1110(c) Traffic between nodes 0 and 12

0
20
30
40
Time [Hour]20

Traffic amount [Gbps]

Traffic amount [Gbps]

8

10

4

60

12
Estimated amount
Actual amount0

6

Estimation results for our method with re-estimation

12
10

8

(b) Traffic between nodes 9 and 1
Fig. 10

Estimated amount
Actual amount

10

0
0

(a) Traffic between nodes 2 and 4

Traffic amount [Gbps]

12
Estimated amount
Actual amount

Traffic amount [Gbps]

Estimated amount
Actual amount

Traffic amount [Gbps]

Traffic amount [Gbps]

12

60

0

10

20
30
40
Time [Hour]5060(c) Traffic between nodes 0 and 12

Estimation results for our method without re-estimation

traffic rate and can estimate traffic matrices accurately evenwhen the increase of the traffic is temporal.
3.4.3 Impact on performance of TE methods
Finally, we evaluate the performance of TE methods using
traffic matrices estimated by our method. The TE method
used in our simulations configured the VNT and routes overthe VNT so as to keep the maximum link utilization under
the threshold TH . When we use traffic matrices including
estimation errors, however, these errors can cause the maximum link utilization to be above TH . Therefore, in thisevaluation, we investigated the maximum link utilization after TE was performed. For this simulation, we used the same
traffic described in the previous subsection.
Figure 12 shows the results of this simulation. The figure shows that when using the tomogravity method or the
additional equation method, the maximum link utilization
becomes significantly larger than the threshold TH . This isbecause the estimation errors of these methods are large, as
described above. When the estimation errors are large, thelink utilizations after executing the TE method, as calculatedusing the estimated traffic matrix, can be very different fromthe actual link utilizations. As a result, the link utilizations
after TE are mistakenly regarded as being lower than TH ,even though the actual link utilizations are still high and thenecessary optical layer paths have not been added.
This figure also shows that the maximum link utilizations in the case of using our method without re-estimation
sometimes become significantly larger than the threshold,as well. This is caused by significant underestimation of
the traffic including the sudden changes. As shown in
Fig. 11, our method without re-estimation cannot capture
the added sudden changes and significantly underestimates
their amounts. Because of these underestimates, when the
TE method changes the routes of the underestimated traffic,
it does not reserve enough bandwidth. As a result, since theactual traffic rates are much higher than expected, the link
utilizations become high.
On the other hand, in the case of using our methodwith re-estimation, we can reduce the maximum link utilization to around TH at all times. This is because, withre-estimation, our method can estimate traffic matrices accurately even when the traffic changes suddenly.
Although the maximum link utilization is reduced toaround TH with traffic matrices estimated by our methodwith re-estimation, however, it is not always smaller than
TH . This is because estimation errors can still be includedin the results of our method with re-estimation, even though
this method is the most accurate of the four methods considered here.

OHSITA et al.: ESTIMATION OF CURRENT TRAFFIC MATRICES FROM LONG-TERM TRAFFIC VARIATIONS

11

Maximum link utilization

1
0.9
0.8
0.7
Our method with re-estimation
Our method without re-estimation
Simple additional equation method
Tomogravity

0.6
0.5
0.4
0

Fig. 12

10

20

30
40
Time [Hour]

50

60

Variation in maximum link utilization after TE execution

Especially when multiple instances of end-to-end traffic are identified as causing mismatches between the estimated long-term variations and the current traffic, the estimation errors increase, because removing the previously
monitored data about these multiple instances decreases theamount of monitored data used for estimation. That is, if
many instances of end-to-end traffic are errorneously identified as causing the mismatch at the same time, these false
positives cause a increase in the estimation error. Thus, toestimate traffic matrices more accurately, we need to minimize the number of false positives by setting parametersoptimally or using a more sophisticated detection method.
These considerations remain for our future work.
Minimizing the number of false positives is insufficient, however, because it is possible for multiple instancesof end-to-end traffic to actually change suddenly, causing
mismatches between the estimated long-term variations andthe current traffic. When this happens, increases in estimation errors are difficult to avoid, because we cannot obtainsufficient measurements about such traffic changing suddenly. Therefore, to avoid the impact of such errors on methods using estimated traffic matrices, TE methods also needto consider estimation errors. This is another topic for our
future work.
4.

Concluding remarks

In this paper, we have proposed a method for estimating current traffic matrices by using the changes in routing matrices
introduced via a TE method. In this method, we first estimate the long-term variations of traffic matrices by using thelink loads monitored at previous times. Then, we obtain thecurrent traffic matrix by adjusting the estimated long-term
variations of traffic so as to fit the current link loads. In addition, when the traffic variation trends change and the estimated long-term variations cannot fit the current variations,
our method detects mismatch and identifies the end-to-end
traffic causing them. Then, our method re-estimates thelong-term traffic variations after removing monitored data
about the end-to-end traffic causing the mismatches.
We evaluated our method through simulation. According to the results, our method can obtain accurate traffic matrices by adjusting the estimated long-term variations. In
addition, when some end-to-end traffic changes suddenly
and the estimated long-term variations do not match the cur-rent traffic, our method can detect mismatches accurately.
Then, by re-estimating the long-term variations after removing monitored link loads about the end-to-end traffic causing
the mismatches, the method can estimate current traffic matrices accurately even when some end-to-end traffic changes
suddenly.
In addition to evaluating the proposed method, we evaluated a TE method using traffic matrices estimated by our
method. According to these results, by using the traffic matrices estimated by our method, a TE method can reduce themaximum link utilization to around its target value, whereas
the maximum link utilization becomes high with other methods considered here.
Our future works include optimally setting parameterssuch as Φ and Nf . In particular, although we used fixedvalues of Nf in this work, it might be possible to estimate
traffic matrices more accurately by setting Nf dynamicallyaccording to the current measurement. Another future work
is to evaluate our method using the traffic traces of the real
networks. In addition, our future works also include constructing a TE method that considers estimation errors.
Acknowledgement
This work was partially supported by Japan Society for the
Promotion of Science (JSPS), Grant-in-Aid for Young Scientists (Start-up) 19800023.
References[1] B. G. Jozsa, D. Orincsay, and L. Tamasi, “Multi-hour design of dynamically reconfigurable MPLS networks,” in Proceedings of Networking 2004, pp. 502–503, May 2004.
[2] B. Fortz and M. Thorup, “Internet traffic engineering by optimizing
OSPF weights,” in Proceedings of IEEE INFOCOM 2000, pp. 519–
527, Mar. 2000.
[3] K. Shiomoto, E. Oki, W. Imajuku, S. Okamoto, and N. Yamanaka, “Distributed virtual network topology control mechanism
in GMPLS-based multiregion networks,” IEEE Journal on Selected
Areas in Communications, vol. 21, pp. 1254–1262, Oct. 2003.
[4] 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, Apr. 2003.
[5] Y. Zhang, M. Roughan, N. Duffield, and A. Greenberg, “Fast accurate computation of large-scale IP traffic matrices from link loads,”
in Proceedings of ACM SIGMETRICS 2003, pp. 206–217, June
2003.
[6] A. Medina, K. Salamatian, N. Taft, I. Matta, and C. Diot, “A twostep statistical approach for inferring network.” Technical Report
BUCS-2004-11, Computer Science Department, Boston University,
Mar. 2004.
[7] Y. Zhang, M. Roughan, C. Lund, and D. Donoho, “An informationtheoretic approach to traffic matrix estimation,” in Prodceedigs of
ACM SIGCOMM, pp. 301–312, Aug. 2003.
[8] C. Tebaldi and M. West, “Bayesian inference of network traffic using
link count data,” Journal of the American Statistical Association,
vol. 93, pp. 557–576, June 1998.
[9] J. Cao, D. Davis, S. V. Wiel, and B. Yu, “Time-varying network tomography,” Journal of the American Statistical Association, vol. 95,
pp. 1063–1075, Feb. 2000.
[10] Y. Vardi, “Network tomography: Estimating source-destination traffic intensities from link data,” Journal of the Americal Statistical

IEICE TRANS. COMMUN., VOL.Exx–??, NO.xx XXXX 200x

12

Association,, pp. 365–377, Mar. 1996.
[11] I. Juva, S. Vaton, and J. Virtamo, “Quick traffic matrix estimation
based on link count covariances,” in Proceedings of IEEE ICC 2006,
vol. 2, pp. 603–608, June 2006.
[12] Y. Ohsita, T. Miyamura, S. Arakawa, S. Ata, E. Oki, K. Shiomoto,and M. Murata, “Gradually reconfiguring virtual network topologies
based on estimated traffic matrices,” in Proceedings of INFOCOM
2007, pp. 2511–2515, May 2007.
[13] A. Nucci, R. Cruz, N. Taft, and C. Diot, “Design of IGP link weightchanges for estimation of traffic matrices,” in Proceedings of INFOCOM 2004, vol. 4, pp. 2341–2351, Mar. 2004.
[14] 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, vol. 13, pp. 485–498, June
2007.
[15] A. Gunnar, M. Johansson, and T. Telkamp, “Traffic matrix estimation on a large IP backbone –a comparison on real data,” in Proceedings of Internet Measurement Conference, pp. 149–160, Oct. 2004.
[16] 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.
[17] S. Burke, “Missing values, outliers, robust statistics & nonparametric methods,” LC-GC Europe Online Supplement, Statistics& Data Analysis, vol. 2, pp. 19–24, Jan. 2001.

Yuichi Ohsita
received the M.E. and
Ph.D. degrees in Information and Computer Science from Osaka University, Japan, in 2005 and2008, respectively. 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
ACM and IEEE.

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 was engaged in researchand development of a high-speed IP switchingrouter. He is now researching next-generation
backbone network architecture and design. He
received Paper Awards from the 7th Asia-PacificConference on Communications in 2001. He isa member of the Operations Research Society of Japan.

Shin’ichi Arakawa
received the M.E. and
D.E. degrees in Informatics and Mathematical
Science from Osaka University, Osaka, Japan,
in 2000 and 2003, respectively. He is currently
an Assistant Professor at the Graduate Schoolof Information Science and Technology, Osaka
University, Japan. His research work is in thearea of photonic networks. He is a member ofIEEE.

Eiji Okiis an Associate Professor of
University of Electro-Communications, TokyoJapan. He received B.E. and M.E. degrees inInstrumentation Engineering and a Ph.D. degree in Electrical Engineering from Keio University, Yokohama, Japan, in 1991, 1993, and1999, respectively. In 1993, he joined Nippon
Telegraph and Telephone Corporation’s (NTT’s)
Communication Switching Laboratories, TokyoJapan. He has been researching multimediacommunication network architectures based on
ATM techniques, traffic-control methods, and high-speed switching systems. From 2000 to 2001, he was a Visiting Scholar at Polytechnic University, Brooklyn, New York, where he was involved in designing terabit switch/router systems. He was engaged in researching and developing
high-speed optical IP backbone networks with NTT Laboratories. Dr. Oki
was the recipient of the 1998 Switching System Research Award and the1999 Excellent Paper Award presented by IEICE, and the 2001 Asia-Pacific
Outstanding Young Researcher Award presented by IEEE Communications
Society for his contribution to broadband 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.

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 (NTT), Tokyo, Japan in April 1989,
where he was engaged in research and development of ATM traffic control and ATM switchingsystem architecture design. From August 1996
to September 1997, he was engaged in researchon high-speed networking as Visiting Scholar at
Washington University in St. Louis, MO, USA.
From September 1997 to June 2001, he was directing architecture designfor 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 routerdesign, routing algorithm, and GMPLS routing and signaling standardization at NTT Network Innovation Laboratories. Since April 2004, he has
been engaged in the research fields of photonic IP router design, routing
algorithm, and GMPLS routing and signaling standardization at NTT Network Service Systems Laboratories. Since April 2006, he has been leading the IP Optical Networking Research Group in NTT Network Service
Systems Laboratories. He is active in standardization of GMPLS in the
IETF. He received the B.E., M.E., and Ph.D degrees in information andcomputer sciences from Osaka University, Osaka in 1987 1989, and 1998,
respectively. He is a member of IEEE, and ACM. He was a Secretary of International Relations of the Communications Society of IEICE from June
2003 to May 2005. He was the Vice Chair of Information Services ofIEEE ComSoc Asia Pacific Board from January 2004 to December 2005.

OHSITA et al.: ESTIMATION OF CURRENT TRAFFIC MATRICES FROM LONG-TERM TRAFFIC VARIATIONS

13

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. He received theSwitching System Research Award from the IEICE in 1995 and 2001. Heco-authored ”GMPLS Technologies: Broadband Backbone Networks andSystems (Optical Engineering)” Marcel Dekker Inc.

Masayuki Murata
received the M.E. and
D.E. degrees in Information and Computer Sciences from Osaka University, Japan, in 1984 and1988, respectively. In April 1984, he joinedTokyo Research Laboratory, IBM Japan, as a
Researcher. From September 1987 to January
1989, he was 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 and domestic journals andconferences. His research interests include computer communication networks, performance modeling and evaluation. He is a member of ACM,
The Internet Society and IPSJ.