A Proposal of an Efficient Traffic Matrix Estimation under Packet Drops
Kohei Watabe†

Toru Mano†† Kimihiro Mizutani†† Osamu Akashi†† Kenji Nakagawa†† Graduate School of Engineering, Nagaoka University of Technology†† NTT Network Innovation Laboratories

Background and Objectives

n We assume that every path observes the equal loss rate for the sameabnormal arc.

Conventional Traffic Matrix Estimationn This paper assumes a single arc failure.

n Traffic Matrices (TMs), which specify the traffic volumes between
origin-destination pairs in a network, are used by many networkengineering tasks.
Per-link counters are placedn traffic engineering

Path P1n capacity planninge1o1

n anomaly detection etc.
n Conventional TM estimation techniques
assume the strict flow conservation.
n Traffic volumes are unchanged along apath from the origin to the destination.

Takeru Inoue††

Path P2e2
e3

Definition of measurabilityn The counter set Cc is aa-measurable if

d1
Lower boundd2

Estimator (see below)

Upper boundFormulation of the problem
Traffic volumes
are unchangedn For given P,

Objective

Measurability Theory and Optimizationn This paper studies a mathematical model to estimate traffic volumes
with their change along a path, by counting the number of packets.
n The number of counters should be minimized to reduce themeasurement cost.
Path P1
Per-path counters
are placedo1e1Path P2
The number of lost packets can bemeasured on a subpath between counters

e2
e3

d1
d2

Traffic volumes are changed
due to link failure

Two baseline approachesn There are two baseline approaches to solve per-link information x
using information yy of nn subpaths.
xx: a measurement matrix whose element aaij indicates whether ii-th
xxxxsubpath includes jjj-th link. It is specified by counter placement.

1. Linear algebra approach can exactly determine the traffic volumes
with change, but it requires many counters to make TA full-rank.
xx: a vector whose x-th element is the packet loss
xxxxrate on x-th link
xx: a vector whose x-th element is volume of lost
xxxxtraffic on x-th path

Estimationn In our method, an abnormal arc is specified by solving a Boolean
equation y = A(C)ccccc.x
n For a feasible path [PPPPPPPPPPPPPPPP], our estimator is[TTTTTTTTTTTT2] if [E is located on the lower side of the specified
abnormal arc, and [TTTTTTTTTTTTT1] otherwise.
e1

e2

e3

Counter value KK

Measurability Theoremn [Theorem] For the above estimator, a counter set C is (1 − ε)d−2 measurable, if the measurement matrix A(C) is 1-independent andevery feasible path PP has at least one counter on it.
n A matrix A(C) is 1-independent if any column vector of A(C) isdifferent from each other and none of them equal to zero vector.

Optimization of Counter Placementn We initially place counters C0 at first arcs for every PP.
n To satisfy 1-independency, additional counter X that maximizes thefollowing coverage function g is placed repeatedly.
n The coverage function g is submodular, and the problem is asubmodular optimization.

xx: an element tttii is a traffic volume of ii-th path and the other elements are zero.

n Subpaths that are longer than xxxxxxxxxxxxxx hops are divided byplacing counters.

2. Boolean algebra approach requires fewer counters, but it only locates
failed links without volume change.

n Inspecting the counter values, we can tell the longer subpath
contains an abnormal arc or not.

n This paper establishes a new measurement method that intervenes
between the two approaches.
n The volume change is estimated with error bounds, while it requires
counters fewer than the linear algebra approach and close to theBoolean algebra approach.

Experiments
n Our approach is evaluated
using
three
configuration
datasets.
nInternet2
nStanford backbone network
nPurdue campus network

Formulation
Network Modeln A counter placed in a network is specified by the pair of arc and path.
n A counter maintains the number of packets transmitted into the arc
along the associated path.

the set of arcs in a network

the set of feasible paths

n We assume that every arc has either a normal state lj ≤ ε or anabnormal state lj ≥ δlll.
n It is worth noting that our model works without the strong
assumption, ε  δe, used in [1].

The result for Internet2
No. of rows ofa measurement matrix

xx: a Boolean vector whose x-th element indicatesxxxxwhether x-th link is failed
xx: a Boolean vector whose x-th element indicatesxxxxwhether x-th subpath is failed

180160140120100806040
Our approach
20
Boolean algebra approach
01.0E-05 1.0E-04 1.0E-03 1.0E-02 1.0E-01

98765432
1

No. of rows ofa measurement matrix

n Accurate TMs including volume changes would be very useful foradvanced network engineering.

Thresholdn Though our method can provide the error bounds(a)andtraffic volumes,
Internet2
it almost converges to the conventional Boolean technique [1] for Fig. 6. Thexxxxxxxxxxxxxxx.

Conclusion

believe that this paper gives a new viewpointn With the solid theory about the measurability based on Boolean
measurement and opens a novel research field bmatrices, we developed an optimization algorithm for the minimum
TM estimation and the fault localization. This recounter set.
embraces mathematical interests as well as practn Experiments showed the great performancewith real datasets.
tance.
We will extend our method under the constrain
References
sizes. We also will investigate the impact of traffic
packet Link-level
samplingAnomalieson the accuracyof our method[1] S. Agrawal, K. V. M. Naidu, and R. Rastogi, and“DiagnosingUsing PassiveProbes,” in IEEE INFOCOM, 2007, pp. 1757– 1765.
assumed path volumes are directly counted at ingre
but they could be estimated by TM estimation techapproach gives us opportunities to reduce countthough estimation errors might not be bounded.