This is the post-print version of the following article: Kohei Watabe, Toru Mano, Kimihiro Mizutani, Osamu Akashi, Kenji Nakagawa, and Takeru Inoue, ``A Proposal of an Efficient Traffic Matrix Estimation Under Packet Drops,'' in Proceedingsof the 37th IEEE International Conference on Distributed Computing Systems (ICDCS 2017) Poster Track, 2017. The original publication is available at https://doi.org/10.1109/ICDCS.2017.169 (DOI: 10.1109/ICDCS.2017.169). (c) 2017 IEEE.
Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution
to servers or lists, or reuse of any copyrighted components of this work in other works.

A Proposal of an Efficient Traffic Matrix Estimation
under Packet Drops
Kohei Watabe∗ , Toru Mano† , Kimihiro Mizutani† , Osamu Akashi† , Kenji Nakagawa∗ , and Takeru Inoue†∗ Graduate School of Engineering, Nagaoka University of Technology, Kamitomiokamachi 1603–1, Niigata, 940–2188 Japan

Email: {k watabe,nakagawa}@vos.nagaokaut.ac.jp† NTT Network Innovation Laboratories, Hikarinooka 1–1, Kanagawa, 239–0847 Japan

Abstract—Traffic matrix (TM) estimation has been extensively
studied for decades. Although conventional estimation techniques
assume that traffic volumes are unchanged between origins anddestinations, packets are often discarded on a path due totraffic burstiness, silent failures, etc. This paper proposes a novel
TM estimation method that works correctly even under packet
drops. The method is established on a Boolean fault localization
technique; the technique requires fewer counters though it only
determines whether each link is healthy. This paper extends
the Boolean technique so as to deal with traffic volumes witherror bounds just by a small number of counters. Along with
submodular optimization for the minimum counter placement,
we evaluate our method with real network datasets.

I. I NTRODUCTION
Traffic Matrix (TM) including packet drops, i.e., whereand how much packets are dropped on the path, would bevery useful for advanced network engineering; e.g., capacity
planning could consider lost traffic in addition to the traffic
volume, while traffic engineering could avoid bursty links andfailed switch. Conventional TM estimation techniques assume
the strict flow conservation, i.e., traffic volumes are unchanged
along a path from the origin to the destination [1]. Traffic,
however, can be lost due to packet drops in a network.
This paper studies a mathematical model to estimate traffic
volumes with their change along a path. The traffic volumes
will be determined at each link. Though we can easily get
the traffic volumes with their change by counting every pathat every link, the number of counters should be minimized
to reduce the measurement cost. This paper focuses on thetradeoff between the measurement cost and estimation errors.
Our contributions are summarized as follows: 1) By reformulating the TM estimation for packet drops with Boolean
algebra, a new measurability theory that provides the error
bounds of the traffic volume is established; 2) A submodular
optimization method that minimizes the number of counters isdeveloped based on the measurability theory; 3) Experimentswith three real network datasets show that the number ofcounters in our method is close to the corresponding valueof a conventional Boolean technique in most cases, though
the conventional technique cannot provide the error bounds
and traffic volumes.
II. F ORMULATION
A network is represented by a directed graph, G = (V, E).
If there exist some packets forwarded along a path, the pathis called a feasible path P ∈ P, where P is the set of feasible
paths in the network. A path is regarded as a set of arcs.
Let C be a set of counters placed in the network. A counteris placed at the tail of directed arc ej ∈ E (j = 1, 2, . . . , n)and maintains the number of packets transmitted into the arc
along the associated path. Each counter is specified by thepair of arc and path, e.g., (ej , P ) ∈ C and C ⊆ C = E × P,
and the value is denoted by κj . Packets are classified to thecorresponding counters based on their path using path-oriented
packet classification techniques [2]. Let τj ∈ R be the numberof packets transmitted into ej along P in a time unit; ourmodel has κj = τj if a counter is placed at (ej , P ). Let τ̂j be
an estimated value of τj .
The packet drop ratio through arc ej is denoted by ℓj =1 − τj+1 /τj ∈ [0, 1]. We assume that every arc has either anormal state ℓj ≤ ϵ or an abnormal state ℓj ≥ δ, where ϵ < δ;
it is worth noting that our model works without the strong
assumption, ϵ ≪ δ, used in [3]. We assume that every pathobserves the equal drop ratio for the same abnormal arc, anda single arc failure. Packets are dropped only at arcs, not atvertices.
Our problem is defined as follows: for given G, P, and α,min{|C| : C is α-measurable},

(1)

C⊆C

where |C| is the number of counters. α-measurable in theabove problem is defined as follows: The counter set C isα-measurable if,∀P ∈ P, ∀ej ∈ P : α · τj ≤ τ̂j ≤1· τj ,α(2)where 0 < α ≤ 1.
III. M EASURABILITY AND O PTIMIZATION
Separable subpath are consisted by placing counters
on paths in our method. A separable subpath Q ={ej , ej+1 , . . . , ek−1 } ⊆ E is a part of a feasible path P ={e1 , e2 , . . . , el } between a pair of counters {(ej , P ), (ek , P )}and satisfies (1−δ) < (1−ϵ)k−j . Let Q = {Q1 , Q2 , . . . , Qm }be a set of separable subpaths under a counter set C. Ifκk /κj < 1 − δ, we regard P as abnormal.
In our method, an abnormal arc is specified by solving
a Boolean equation y = A(C)x, where element xj of x
indicates whether ej ∈ E is abnormal while yi of y indicates

Algorithm 1: Counter Placement
Input: A set of feasible paths P and drop thresholds ϵ, δ.
Output: A set of additional counters X that satisfies
g(X) = g(C).
1 X ← ∅;2 while ∃x ∈ C : g0 (x|X) > 0 do
3x∗ ← arg maxx∈C g0 (x|X);
4X ← X ∪ {x∗ };Q′ ← Separable subpaths of X at ϵ = 0;
′6 while ∃Q ∈ Q : |Q| − 1 > ⌊log1−ϵ (1 − δ)⌋ do
7X ← X ∪ {(ej+⌊log1−ϵ (1−δ)⌋ , P )};8Q′ ← Separable subpaths of X;

TABLE IN UMBER OF COUNTERS AND ARC - PAIRS FOR ϵ = 0 AND δ = 1

Initial counters |C0 |Additional counters |X0 |Indistinguishable arc-pairs
per all arc-pairs

Internet2

Stanford

Purdue11,159
116

331
65

2,985
380

0 / 9,730

49 / 8,646

0 / 138,075

9return X;

whether Qi is abnormal. A measurement matrix A(C) = (aij )is defined as the m × n Boolean matrix of{1 ej ∈ Qi
aij =.
(3)0 otherwise
The j-th column vector is denoted by aj (j = 1, 2, . . . , n). Amatrix A(C) is 1-independent if any column vector of A(C)is different from each other and none of them equal to zero;i.e., ∀j ̸= j ′ : aj ̸= aj ′ and ∀j : aj ̸= 0.
For a√feasible path P = {e1 , e2 , . . . , el }, our estimatorτ̂j = κ1 (1 − ϵ)j−2 if ej is located √on the lower side of thespecified abnormal arc, and τ̂j = κ1 (1 − ϵ)j−1 otherwise.
The error of τ̂j is bounded by α = (1 − ϵ)d−2 whered = max{|P | : P ∈ P}. Given the measurement matrix
A(C), sufficient conditions of measurability are described bythe following theorem.
Theorem 1. A counter set C is (1 − ϵ)d−2 -measurable, if themeasurement matrix A(C) is 1-independent and every feasible
path P has at least one counter on it.
Based on Theorem 1, we approximately solve the problem (1). To satisfy the condition that every feasible path P
has at least one counter on it in Theorem 1, we initially placecounters C0 at first arcs for every P . Additional counters
X are optimized based on the coverage function g(X) =|{(j, k) : 0 ≤ j < k ≤ n, aj ̸= ak }|, where aj is j-th column
vector of the measurement matrix A(C0 ∪X) and a0 is the zero
vector 0. A function g(x|X) represents the gain of counterx ∈ C added to X: g(x|X) = g(X ∪ {x}) − g(X). Thefunction g0 is the coverage function for ϵ = 0.
In Algorithm 1, we first solve the problem for ϵ = 0, andthen we convert its solution X0 into a solution XALG for given
ϵ and δ. This is because, when the lower threshold equals to0, ϵ = 0, the coverage function g0 becomes a submodular
function and a simple greedy algorithm yields an approximate
solution with a theoretical guarantee in polynomial-time [4].
IV. E XPERIMENTS
We perform experiments to evaluate our method using three
configuration datasets. The configuration datasets are obtained

No. of rows ofa measurement matrix

5180160
140120100806040200
1.0E-05

Our approach
Conventional Boolean algebra approach
1.0E-04

1.0E-03

1.0E-02

1.0E-01

Threshold δFig. 1. The number of rows in a measurement matrix.

from Internet21 , Stanford backbone network [5], and Purdue
campus network [6].
The optimization results are shown in Table I for ϵ = 0 andδ = 1. An arc pair (ei , ej ) ∈ E 2 is indistinguishable if thecorresponding column vectors ai , aj are equal. Though somearc-pairs are indistinguishable only for Stanford due to restrictions of counter placement, most arc-pairs are distinguishable.
The number of rows of measurement matrix (i.e. |XALG | inour method) depends on threshold δ; Fig. 1 shows the numberof matrix rows for ϵ = 10−5 and 10−5 ≤ δ ≤ 10−1 forInternet2. Though our method can provide the error bounds
and traffic volumes, for all the datasets, we confirmed that
our method almost converges to the conventional Booleantechnique [3] for δ > 5.0 × 10−5
V. C ONCLUSION
This paper proposed a TM estimation method that handles
packet drops in a network. With the solid theory about themeasurability based on Boolean matrices, we developed anoptimization algorithm for the minimum counter set. Experiments showed the great performance with real datasets.
R EFERENCES[1] M. Roughan, Y. Zhang, W. Willinger, and L. Qiu, “Spatio-Temporal
Compressive Sensing and Internet Traffic Matrices (Extended Version),”IEEE/ACM Trans. Netw., vol. 20, no. 3, pp. 662–676, 2012.
[2] T. Inoue, T. Mano, K. Mizutani, S.-i. Minato, and O. Akashi, “Rethinking
Packet Classification for Global Network View of Software-DefinedNetworking,” in IEEE ICNP, 2014, pp. 296–307.
[3] S. Agrawal, K. V. M. Naidu, and R. Rastogi, “Diagnosing Link-level
Anomalies Using Passive Probes,” in IEEE INFOCOM, 2007, pp. 1757–1765.
[4] L. A. Wolsey, “An Analysis of the Greedy Algorithm for the Submodular
Set Covering Problem,” Combinatorica, vol. 2, no. 4, pp. 385–393, 1982.
[5] P. Kazemian, G. Varghese, and N. McKeown, “Header Space Analysis:
Static Checking for Networks,” in NSDI 2012, 2012.
[6] Y.-W. E. Sung, X. Sun, S. G. Rao, G. G. Xie, and D. A. Maltz, “Towards
Systematic Design of Enterprise Networks,” IEEE/ACM Trans. Netw.,
vol. 19, no. 3, pp. 695–708, 2011.
1 http://vn.grnoc.iu.edu/Internet2/fib