VOL. E102-B NO. 1
JANUARY 2019
The usage of this PDF file must comply with the IEICE Provisions
on Copyright.
The author(s) can distribute this PDF file for research andeducational (nonprofit) purposes only.
Distribution by anyone other than the author(s) is prohibited.

IEICE TRANS. COMMUN., VOL.E102–B, NO.1 JANUARY 2019

76

PAPER

Measuring Lost Packets with Minimum Countersin Traffic Matrix Estimation∗
Kohei WATABE†a) , Member, Toru MANO†† , Nonmember, Takeru INOUE†† , Kimihiro MIZUTANI†† ,Osamu AKASHI†† , and Kenji NAKAGAWA† , Members

SUMMARY
Traffic matrix (TM) estimation has been extensively studied for decades. Although conventional estimation techniques assume that
traffic volumes are unchanged between origins and destinations, packets
are often lost on a path due to traffic burstiness, silent failures, etc. Counting every path at every link, we could easily get the traffic volumes with
their change, but this approach significantly increases the measurement cost
since counters are usually implemented using expensive memory structures
like a SRAM. This paper proposes a mathematical model to estimate TMs
including volume changes. The method is established on a Boolean fault
localization technique; the technique requires fewer counters as it simply
determines whether each link is lossy. This paper extends the Boolean
technique so as to deal with traffic volumes with error bounds that requires
only a few counters. In our method, the estimation errors can be controlled
through parameter settings, while the minimum-cost counter placement isdetermined with submodular optimization. Numerical experiments are conducted with real network datasets to evaluate our method.
key words: traffic matrix, packet drop, submodular optimization, failure
localization, passive measurement

1.

Introduction

Traffic Matrices (TMs), which specify the traffic volumes
between origin-destination pairs in a network, are used bymany network engineering tasks, such as traffic engineering [1], [2], capacity planning [3], and anomaly detection [4]. These tasks rely heavily on the availability andaccuracy of TMs. Due to their importance, there has been asubstantial body of work on TM estimation [5]–[11]. Conventional TM estimation techniques assume the strict flow
conservation, i.e., traffic volumes are unchanged along apath from the origin to the destination. Traffic, however,can be lost due to packet drops in a network. For example,
bursty traffic could be dropped by the overflow of a switch’s
queue, even if the long-term average throughput is lower
than the link capacity; silent packet drops [12] often happen, i.e., switches for unknown reasons drop packets without showing information about the drops.
This paper studies a mathematical model to estimate
Manuscript received March 12, 2018.
Manuscript revised June 13, 2018.
Manuscript publicized June 2, 2018.
†
The authors are with the Graduate School of Engineering, Nagaoka University of Technology, Nagaoka-shi, 940-2188 Japan.
††
The authors are with NTT Network Innovation Lavoratories,
Yokosuka-shi, 239-0847 Japan.
∗
An earlier version of this paper was presented at the 37th
IEEE International Conference on Distributed Computing Systems(ICDCS 2017) Poster Track.
a) E-mail: k watabe@vos.nagaokaut.ac.jp
DOI: 10.1587/transcom.2018EBP3072

Fig. 1 (Left) Traffic volumes with change. There are three links, e1 , e2 ,and e3 , and two paths, P1 and P2 , in the network. The volumes are indicated by the arrow width. (Right) Identification of failed link with a
Boolean measurement matrix. The rank of this matrix (m = 2) is lower
than the number of variables (n = 3), but we can obtain the solution x
for any y, assuming a single link failure; e.g., for y = (0 1)T , we havex = (0 0 1)T .

TMs with lost packets as shown in Fig. 1(Left). What wewant to estimate in this study differs from the traditionaltraffic matrix. Whereas the volume of traffic on each path isestimated in traditional traffic matrix estimation, our method
estimates where and how much traffic on each path was
lost/passed. Of course, counting every path at every link,
we could easily get the traffic volumes with their change.
The counters are, however, usually maintained on an expensive memory like a SRAM to match to the speed of broadband links, so the number of counters should be minimized
to reduce the measurement cost. This paper specifically discusses the tradeoff between the measurement cost and estimation errors. There are two baseline approaches; one is thelinear algebra approach which determines an upper boundfor the number of counters, while the other is Boolean algebra approach which gives a lower bound.
Linear algebra approach. For the upper bound, we comeup with a naive combination of TMs with link loss-ratio estimation, as follows. Let m be the number of paths and n be
the number of links. Let T be an m × m traffic matrix where
element tii is a traffic volume of i-th path (i = 1, 2, . . . , m)and the other elements are zero, let A be an m × n measurement matrix where element ai j indicates whether i-th
path includes j-th link ( j = 1, 2, . . . , n), let x be an ndimensional column vector whose j-th element is the packet
loss ratio on j-th link, and let y be an m-dimensional column
vector whose i-th element indicates volume of lost traffic
on i-th path (i.e., the difference of traffic volume between
the ingress and the egress on the path). Here, T and y
are measured using counters placed at ingress and egressswitches, while A is determined from forwarding configurations. Given T , A, and y, equation T Ax = y can be
uniquely solved for x if T A satisfies rank(T A) = n ≤ m.
This approach can exactly determine the traffic volumes
with change, but it requires a full-rank matrix as T A; if T A is

Copyright c 2019 The Institute of Electronics, Information and Communication Engineers

WATABE et al.: MEASURING LOST PACKETS WITH MINIMUM COUNTERS IN TRAFFIC MATRIX ESTIMATION

77

rank deficient, some paths have to be divided at intermediateswitches and another counters would be put on them.
Boolean algebra approach. This approach requires fewer
counters, but it only locates failed links without volume
change. Instead of T A used in the above approach, weutilize the Boolean measurement matrix A with another
Boolean vectors x and y, where jth element x j of x indicates whether j-th link is failed while ith element yi of y
indicates whether i-th path is failed. Note that the norm ofx, ||x||, indicates the number of failed links. Boolean matrices have an interesting property: given K ∈ N, there exists
a rank deficient Boolean matrix A that yields an injective
mapping, x 7→ Ax, if ||x|| ≤ K (i.e., for sparse x) [13], [14].
This property allows us to uniquely determine x from y subject to Ax = y though m < n. This is because, roughly
speaking, the Boolean space restricted by K can be smallenough to be covered by a rank deficient matrix. Therefore, at the expense of knowledge of volume change, thisapproach reduces the number of counters since smaller mleads to a smaller number of counters. In Fig. 1(Right), we
measure only two paths for the three links, but failed links
are identifiable assuming a single link failure (K = 1).
Our method proposed in this paper intervenes between
the two approaches; the volume change is estimated witherror bounds, while it requires counters fewer than the linear
algebra approach and close to the Boolean algebra approach.
Since exact volumes are usually not needed if their errors arebounded, this is a good tradeoff. Our method is designed asa passive scheme, which does not disrupt production traffic.
Our contributions are summarized as follows.
• A new theory about the measurability of packet/byte
counts is established (our theory handles both packet
counts and byte counts in a same way, so we only address packet counts in the rest of paper). The TM estimation is reformulated for packet drops with Boolean
algebra. The error bounds can be controlled by threshold parameters.
• Our optimization method that minimizes the number ofcounters is developed based on the measurability theory. The counter placement problem is relaxed to a
submodular optimization problem, and an approximation algorithm is presented.
• Experiments with three real network datasets show thatthe size of the measurement matrix in our method is
close to that of the Boolean algebra approach. Additionally, it is confirmed that the accuracy of our method
is highly guaranteed with tight error bounds for thesedatasets.
The remainder of this paper is organized as follows.
Section 2 clarifies the problem of conventional TM estimation techniques.
Section 3 gives the problem statement. Section 4 discusses our method based on “per-path”
measurement, while Sect. 5 unifies some measurement paths
into a tree (some rows are merged into a single row in thematrix), thereby the number of counters is further decreased.
After describing practical modeling issues in Sect. 6, Sect. 7shows experimental results. Section 8 summarizes related
work and Sect. 9 concludes the paper.
2.

Conventional TM Estimation Techniques

First of all, we make the problem of conventional TM estimation techniques clear. To evaluate conventional TM estimation techniques under packet drops, we conducted preliminary experiments using Sparsity Regularized Singular
Value Decomposition (SRSVD) [9]. Figure 1(Left) shows
the network used in the experiments. We assume that path
P1 has 10× more traffic than P2 . Packets are counted at
nodes o1 , d1 , and d2 , and traffic volumes are estimated foreach path using the packet counts. Without packet drops, theestimation is very accurate. However, with packet drops, it
is not; e.g., if 10% of traffic on link e1 drops, estimated volumes are in error by up to 40% on P2 , since the estimators do
not distinguish volumes on e1 and e3 . These large errors arealso inevitable in other conventional estimation techniques,
which assume the strict flow conservation. These large estimation errors are, unfortunately, considered to be unacceptable for most applications. Accurate TMs including volume
changes, i.e., where and how much packets are dropped on
the path, would be very useful for advanced network engineering; e.g., capacity planning could consider lost traffic inaddition to the volume, while traffic engineering could avoid
lossy links and switches.
3.

Model and Problem

3.1

Network Model

A network is represented by a directed graph, G = (V, E)
where V and E represent a set of vertexes and arcs. Givena packet, the forwarding path is determined by the packet
header (e.g., addresses and ports) based on routing protocols
and/or switch configurations. A path along which there exist
some packets forwarded is 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† . We do not consider multi-path
forwarding nor multicasting.
Let C be a set of counters placed in the network. A
counter is placed at the tail of directed arc e j ∈ E ( j =1, 2, . . . , n) and maintains the number of packets transmitted
into the arc along the associated path (or the set of associatedpaths, which forms a tree). Each counter is specified by thepair of arc and path, e.g., (e j , P) ∈ C and C ⊆ C̃ = E×P, andthe value of the counter is denoted by κ j . Packets are classified to the corresponding counters based on their path using path-oriented packet classification techniques [15], [16].
Counter clocks are supposed to be synchronized [17], [18].
We assume that all packets are observed without samplingsome of them; our method could be extended to a samplingversion using hash functions [19]. We assume that packets†
The word “arc”, e ∈ E, is used as an abstraction of transmission media in this paper, since arcs will be used for links as well as
switch internals, as will be described in Sect. 6.

IEICE TRANS. COMMUN., VOL.E102–B, NO.1 JANUARY 201978
Table 1

Notation table.

NotationDefinition
A directed graph (V, E) that represent a network. V and E represent a set ofvertexes and arcs.
P A feasible path: a path along which there exist some packets forwarded.
P The set of feasible paths in the network.
e j An arc.
ea An abnormal arc.
(e j , P) A counter placed at arc e j on path P.
C A set of counters placed in the network.
C̃ The set of all potential counters E × P.
C0 The set of ingress counters in the network.
X A set of additional counters C \ C0 .
X0 An intermediate counter set assuming  = 0.
XALG A counter set that outputted by Algorithm 3.
X ∗ The optimal counter set of (10) for given thresholds  and δ.
X0∗ The optimal counter set of (10) for given thresholds  = 0.
κ j The value of the counter e j .
τ j The number of packets transmitted into e j along P in a measurement period.
τ̂ j An estimated value of τ j .
` j The packet loss ratio through arc e j .
φ An estimator of the pass ratio on the abnormal arc.

The threshold of loss ratio for a normal state. Loss ratio of a normal state arc
is smaller than .
δThe threshold of loss ratio for an abnormal state. Loss ratio of a abnormal
state arc is larger than δ. It also used as a loss threshold for a separable path.
d
The maximum path length max{|P| : P ∈ P}.
Qi A separable subpath: a part of a feasible path between a pair of counters thatsatisfies (1 − δ) < (1 − )k− j (see Fig. 2).
A(C) A measurement matrix whose (i, j) element ai j indicates that a separable path
Qi includes an arc e j (see (4)).
a j The j-th column vector of a measurement matrix A(C).
x A n-dimensional column vector whose j-th element indicates that j-th arc is
an abnormal state.
y A m-dimensional column vector whose i-th element indicates that subpath Qi
includes an abnormal arc.
x∗ The unique solution of Ax = y.
g
A coverage function that represents how close the measurement matrix is to
1-independent.
g0 A coverage function forP = 0.
x
H(x) x-th harmonic number i=1
1/i.

values if a counter is not placed at (e j , P)). The counter set
C is α-measurable if,Gare not fragmented in a network.
The packet loss ratio is defined by ratio of lost packets
to input packet of an arc, and the packet loss ratio througharc e j is denoted by ` j ∈ [0, 1]. We assume that every arc
has either a normal state ` j ≤  or an abnormal state ` j ≥ δ,
where  < δ; it is worth noting that our model works without
the strong assumption,   δ, used in [14]. We assume
that every path observes the equal loss ratio for the sameabnormal arc; e.g., in Fig. 1, if arc e1 were abnormal and theother arcs were loss-less, the both paths (P1 and P2 ) would
experience the equal loss ratio. For the sake of simplicity,
this paper assumes a single arc failure, i.e., K = 1. However,
our theory could be easily extended for multiple failures.
Packets are dropped only at arcs, not at vertices; this issue
will be elaborated in Sect. 6.
For reference, we list our notation throughout the paperin Table 1.
3.2

Problem Statement

Let τ j ∈ R be the number of packets transmitted into e jalong P in a measurement period; our model has κ j = τ j if acounter is placed at (e j , P). The loss ratio ` j is expressed by1−τ j+1 /τ j for path P shown in Fig. 2. Let τ̂ j be an estimatedvalue of τ j (Note that counters are not necessarily placedat all arcs, and τ j cannot be obtained directly from counter∀P ∈ P, ∀e j ∈ P, ∀τ j : α · τ j ≤ τ̂ j ≤1· τ j,
α(1)where 0 < α ≤ 1. Our problem is defined as follows: forgiven G and P,
min {|C| : C is α-measurable},

C⊆E×P

(2)

where |C| is the number of counters and α is a constant thatsatisfies 0 < α ≤ 1 (this optimization problem will be redefined rigorously in Sect. 4.3 after establishing the theory).
There is a trivial solution of 1-measurable; if we put
counters at every arc on every feasible path, i.e., C ={(e, P) : P ∈ P, e ∈ P}, it is clearly
1-measurable, butP
it requires many counters, |C| = P∈P |P| ≤ d|P|, whered = max{|P| : P ∈ P}. Our target is an α-measurable
counter set whose size is close to the number of feasible
paths, since this paper tries to estimate volume change ateach arc given ingress volumes for each feasible path, |P| isthe lower bound for |C|.
4.

Per-Path Measurement

This section proposes a polynomial-time algorithm thatfinds a counter set that is α-measurable, based on “per-path”
traffic measurement; per-path measurement means that every counter is associated with a single feasible path (Sect. 5
associates some counters with a set of paths).
Before going into detail, we overview this section; therelationship among the measurement matrix A(C), the measurability condition, and the algorithm. Intuitively, each column of the matrix corresponds to the arc and each row corresponds to the path on which we can distinguish whether
it contains abnormal arc (Fig. 1). If any column vector of
A(C) is different from each other and none of them equal
to zero, the matrix A(C) is called 1-independent. When
α = (1 − )d−2 , 1-independence is a sufficient condition formaking a counter set C α-measurable. Hence, we reformulate our problem as follows,min {|C| : A(C) is 1-independent}

C⊆E×P

(3)

and leverage submodularity [20], which is a discrete analog
of convexity, of the measurement matrix A(C) and propose
polynomial-time algorithm with a theoretically guaranteed
approximation ratio O(log(n)).
In the rest of this section, Sect. 4.1 defines the measurement matrix and other related notions, Sect. 4.2 induces thesufficient condition, and Sect. 4.3 proposes an approximation algorithm.
4.1

Definitions

To define the matrix, we define a separable subpath Q ⊆ E.
A separable subpath Q = {e j , e j+1 , . . . , ek−1 } is a part of a

WATABE et al.: MEASURING LOST PACKETS WITH MINIMUM COUNTERS IN TRAFFIC MATRIX ESTIMATION

79

Fig. 2 A subpath Q of feasible path P. Counters, (e j , P) and (ek , P), areplaced at the black vertices.

Algorithm 1: Transmitted Packets Estimation (PerPath)1

feasible path P = {e1 , e2 , . . . , el } between a pair of counters{(e j , P), (ek , P)} (Fig. 2) and satisfies (1 − δ) < (1 − )k− j . Inspecting the counter values {κ j , κk }, we can tell the subpath
contains an abnormal arc or not; The subpath contains anabnormal arc if and only if κk /κ j ≤ 1 − δ. The condition(1 − δ) < (1 − )k− j is needed in order to make subpaths containing an abnormal arc separable. The minimum loss ratioof a subpath containing an abnormal arc is δ. Conversely,
the maximum loss ratio of a subpath in which all arc is normal state is 1 − (1 − )k− j . If (1 − )k− j ≤ (1 − δ), we cannot
judge whether the subpath contains an abnormal arc or not.
A measurement matrix, A(C), is defined as follows (wesometimes omit the argument C if it is clear from the context). Let Q = {Q1 , Q2 , . . . , Qm } be a set of separable subpaths under a counter set C. Measurement matrix A = (ai j )is defined as the m × n Boolean matrix of1 e j ∈ Q i.
(4)
ai j = 0 otherwise
The j-th column vector is denoted by a j ( j = 1, 2, . . . , n).
A matrix A is 1-independent if any column vector of A
is different from each other and none of them equal to zero;i.e., ∀ j , j0 : a j , a j0 and ∀ j : a j , 0.
Vectors x and y in the introduction are rigorously redefined as follows. x is an n-dimensional column vector
whose j-th element indicates that j-th arc is an abnormal
state. y is a m-dimensional column vector whose i-th element indicates that subpath Qi includes an abnormal arc.
4.2
4.2.1

Measurability Theorem and Estimation Algorithm
Theorem

When α = (1 − )d−2 , we can relate the sufficient conditionsof α-measurable to the measurement matrix. Given themeasurement matrix A(C), sufficient conditions of measurability are described by the following theorem.
Theorem 1. When τ j is estimated by Algorihtm 1, a counterset C is (1 − )d−2 -measurable, if the measurement matrix
A(C) is 1-independent and every feasible path P has at least
one counter on it.
In the following, we explain an algorithm that is used
to estimate τ̂. Then, we prove its correctness together withthe proof of Theorem 1.
For the sake of simplicity, we assume that the maximum length of feasible path is at least 3, d ≥ 3, and every
feasible path P has an ingress counter (e1 , P) to satisfy thesecond condition of the Theorem 1 where e1 is the ingressarc of feasible path P. Also, we write the set of ingresscounters as C0 = {(e1 , P) : P ∈ P} and a set of additional

2

Input: Paths P, Separable subpaths {Q1 , . . . , Qm }, and counter values κ.
Output: Estimated number of packets τ̂ at every arc for each feasible
path.
forall i ∈ {1, . . . , m} do
if Qi contains an abnormal arc then yi ← 1 else yi ← 0;8

ea ← Null;φ ← 0;
if y , 0 then // Find an abnormal arc
ea ← Find an arc e j such that y = a j ;Find a separable subpath Q = {e j0 , . . . , ek0 −1 } that contains ea ;φ ← κk0 /(βk0 − j0 −1 κ j0 );9return { Estimate(P, ea , κ) : P ∈ P };

3
4
5
6
7

counters as X = C \ C0 .
4.2.2

Algorithm

Algorithm 1 estimates the number τ̂ of transmitted packets
for every arc and every path, given a per-path
p counter set
C and their values κ, where β j equals to (1 − ) j for all
integer j. The basic idea is as follows. If there is no abnormal arc between e1 and e j−1 , for any arc e j on a feasible
path P = {e1 , . . . , el }, the number of transmitted packets τ jfalls between (1 − ) j−1 τ1 and τ1 , (1 − ) j−1 τ1 ≤ τ j ≤ τ1 ,since a loss ratio of normal arc is less than or equal to 
and there are j − 1 arcs between e1 and e j−1 . Therefore, we
define the estimator τ̂ j = β j−1 κ1 as the midpoint between(1 − ) j−1 κ1 and κ1 in a logarithmic scale since κ1 = τ1 fromthe definition. Consequently, the estimated value τ̂ j satisfies the condition β j−1 τ j ≤ τ̂ j ≤ τ j /β j−1 for measurability.
If there is an abnormal arc between e1 and e j−1 , τ j satisfies(1 − `a )(1 − ) j−2 τ1 ≤ τ j ≤ (1 − `a )τ1 , since a loss ratio of
normal arc is less than or equal to  and there are j − 2 normal arcs between e1 and e j−1 . By replacing (1 − `a ) with theestimator φ of the pass ratio (1 − `a ), we define the estimatorτ̂ j = φβ j−2 κ1 . Rigorous arguments, including the definitionof φ are given in later in this section. The estimation algorithm that shown in Algorithm 1 runs as follows.
First, Algorithm 1 constructs the system of Boolean
equations Ax = y from measurement results κ (Lines 1 to
2). Algorithm 1, then, solves the equations and identifies anabnormal arc ea and estimates its loss ratio if it exists (Lines
3 to 8). Finally, the transmitted packets τ̂ j are estimatedthrough the subroutine Estimate (Line 9 in Algorithm 1 andAlgorithm 2). In the subroutine, the estimator τ̂ j of loss ratioof arc e j is β j−1 κ1 if j ≤ a, and φβ j−2 κ1 otherwise. Correctness of Algorithm 1 and 2 is provided in the following alongwith the proof of the Theorem 1.
4.2.3

Proof

We show that if A(C) is 1-independent then the output of the
Algorithm 1, τ̂, satisfies∀P ∈ P, ∀e j ∈ P : β2(d−2) · τ j ≤ τ̂ j ≤1· τ j.
β2(d−2)(5)

IEICE TRANS. COMMUN., VOL.E102–B, NO.1 JANUARY 201980

the abnormal arc ea and a separable subpath that contains
ea , respectively. Then

Algorithm 2: Estimate (Per-Path)

1
2
3
4
5
6
7
8

Input: A feasible path P = {e1 , . . . , el }, an abnormal arc ea , and countervalues.
Output: Estimated number of packets τˆj at each arc e j on the path P.
T ← ∅;
forall j ∈ {1 . . . , l} do
if ea < P ∨ j ≤ a thenτ̂ j ← β j−1 κ1 ;else
τ̂ j ← φβ j−2 κ1 ;βk0 − j0 −1 · (1 − `a ) ≤ φ ≤1· (1 − `a ),βk0 − j0 −1(8)where φ = κk0 /(βk0 − j0 −1 κ j0 ) is an estimator of the pass ratio
1 − `a on the abnormal arc.

T ← T ∪ {τ̂ j };Proof. This is because the separable subpath Q =00{e j0 , . . . , ek0 −1 } contains ea and (1 − )k − j −1 · (1 − `a ) · κ j0 ≤
κk0 ≤ (1 − `a ) · κ j0 since κk0 = τk0 .


return T ;This proves the correctness of Algorithm 1 and Theorem 1
since (1 − )d−2 = β2(d−2) .
First, we show that the Algorithm 1 identifies an abnormal arc if it exists. Next, we evaluate accuracy of estimatedvalue τ̂.
The following Lemma 1 shows that the abnormal arc is
uniquely determined at Line 6 in Algorithm 1. Note that ∨denotes Boolean OR operator and Boolean OR operator isused instead of the ordinary sum in Boolean equations.

Lemma 4. Let P = {e1 , e2 , . . . , el } be a feasible path that
contains an abnormal arc, ea (1 ≤ a ≤ l). And let
Q = {e j0 , . . . , ek0 −1 } be a separable subpath that contains
the abnormal arc. Then

Lemma 1. Let x j be a binary variable ( j = 1, . . . , n). Thenthe system of Boolean equations Ax = y,Proof. If j ≤ a then use Lemma 2. Otherwise, j > a, use
the next Lemma 3 and the fact that (1 − ) j−2 (1 − `a ) · κ1 ≤
τ j ≤ (1 − `a )κ1 where `a is the loss ratio at the abnormal arc
ea .


ai1 x1 ∨ ai2 x2 ∨ · · · ∨ ain xn = yi(i = 1, 2, . . . , m), (6)have unique solution x∗ among to kx∗ k ≤ 1 and x∗j = 1 if
and only if the arc e j is abnormal.
Proof. The mapping x 7→ Ax is injective if the domain is{x ∈ {0, 1}n : kxk ≤ 1}. This is because the measurement
matrix A is 1-independent.
Note that if the j-th arc is abnormal, x∗j = 1, then Ax∗ =a j . Hence, Algorithm 1 can identify the abnormal arc at
Line 6. As we mentioned in Section 3.1, we assume thatevery arc has either a normal state ` j ≤  or an abnormal
state ` j ≥ δ, i.e., there is no arc whose loss ratio is  <` j < δ. If loss ratios of some arcs are  < ` j < δ, it isdifficult to judge that a subpath contains an abnormal arc,
since a subpath may not contain an abnormal arc even if
κk /κ j ≤ 1 − δ. Hence, (6) cannot be solved or the solution
does not corresponds to the abnormal arc due to unreliableyi .
Lemma 2 and 4 evaluate accuracy of the transmitted
packets on normal and abnormal paths.
Lemma 2. Let P = {e1 , e2 , . . . , el } be a feasible path that
does not include abnormal arcs. Thenβ j−1 τ j ≤ τ̂ j ≤

1
τj
β j−1

( j = 1, 2, . . . , l),(7)where τ̂ j = β j−1 κ1 is the estimator of loss ratio of arc e j .
Proof. This is because (1 − ) j−1 · κ1 ≤ τ j ≤ κ1 for all j =1, 2, . . . , l.

Lemma 3. Let `a and Q = {e j0 , . . . , ek0 −1 } be the loss ratio of

βk0 − j0 + j−3 ·τ j ≤ τ̂ j ≤1·τ j
βk0 − j0 + j−3( j = 1, 2, . . . , l), (9)where the estimator τ̂ j of loss ratio of arc e j is β j−1 κ1 if
j ≤ a, and φβ j−2 κ1 otherwise.

Hence, we have (5) because in Lemma 2 we have j −1 ≤ d − 1 ≤ 2(d − 2) from d ≥ 3, and in Lemma 4 we havek0 − j0 + j − 3 ≤ 2(d − 2) from 1 ≤ j, j0 , k0 ≤ d.
4.3

Counter Set Minimization Algorithm

To describe the counter placement algorithm, we reformulate our problem (2) based on the Theorem 1 as followsnomin |X| : g(X) = g(C̃) ,
(10)
X⊆C̃

where C̃ is the set of per-path counters, E × P, and g is afunction that represents how close the measurement matrix
A(C0 ∪ X) is to 1-independent. The function g is defined asg(X) = {( j, k) : 0 ≤ j < k ≤ n, a j , ak } ,(11)where a j is j-th column vector of the measurement matrix
A(C0 ∪ X) and a0 is the zero vector 0. We call this function g coverage function.
Note that the coverage function
g(X) equals to n+1
if
and
only if the matrix A(C0 ∪ X) is2
1-independent. We leverage submodularity of this coveragefunction g for algorithm design.
In this subsection, we give a constructive proof of Theorem 2 by using Algorithm 3.
Theorem 2. There exists a polynomial-time approximation
algorithm of (10) and its approximation ratio is!
!
n(n + 1)
d−1
1+
H
,
(12)
log1− (1 − δ) − 1
2

WATABE et al.: MEASURING LOST PACKETS WITH MINIMUM COUNTERS IN TRAFFIC MATRIX ESTIMATION

81

Algorithm 3: Counter Placement (Per-Path)
1
2
3
4
5
6
7

Input: A set of feasible paths P and loss thresholds , δ.
Output: A set of additional counters XALG that satisfies g(XALG ) = g(C̃).
X0 ← ∅;
while ∃x ∈ C̃ : g0 (x|X0 ) > 0 dox∗ ← arg max x∈C̃ g0 (x|X0 );X0 ← X0 ∪ {x∗ };Q0 ← Irreducible separable subpaths of X0 at  = 0;
forall Q ∈ Q0 do XALG ←Separate(Q, X0 , , δ);return XALG ;Algorithm 4: Separate (Per-Path)

6

Input: A subpath Q = {e j , . . . , ek−1 } ⊆ P, a counter set X0 , and loss
thresholds , δ.
Output: A counter set XALG that divides the subpath Q into separable
subpaths.
k0 ← j − 1 + dlog1− (1 − δ)e;
XALG ← X0 ;if k0 < k thenXALG ← XALG ∪ {(ek0 , P)};Q ← {ek0 , . . . , ek−1 };XALG ← Separate(Q, XALG , , δ);7

return XALG ;

1
2
3
4
5

where H(x) is x-th harmonic number

Px

i=1 1/i.

In the following Sect. 4.3.1 introduces some notations,Sect. 4.3.2 explains the algorithm, and Sect. 4.3.3 proves the
Theorem 2.
4.3.1

Notations

Here we introduce some notations to explain Algorithms 3
and 4.
A function g(x|X) represents the gain of counter x ∈ C̃added to X: g(x|X) = g(X ∪ {x}) − g(X). The function g0
is the coverage function for  = 0, and we have g0 (x|X) =g0 (X ∪ {x}) − g0 (X).
An irreducible separable subpath Q = {e j , . . . , ek−1 } ⊆P of a counter set C0 ∪ X is a separable subpath of C0 ∪ X
and it does not have any counter in the inside it: ∀e j0 ∈Q \ {e j , ek−1 } = {e j+1 , . . . , ek−2 } : (e j0 , P) < X. Intuitively, if
a subpath is separable but not irreducible, then it is unnecessary to identify abnormal arcs. A separable but not irreducible subpath does not contribute to make a measurement
matrix 1-independent since ai1 j , ai1 j0 ⇒ ai2 j , ai2 j0 ∨ai2 j ,ai2 j0 for all j and j0 , where Qi1 is a separable but not irreducible subpath that includes two irreducible subpaths Qi2and Qi3 .
An irreducible measurement matrix of a counter set
C0 ∪ X is the matrix constructed from the irreducible separable subpaths of C0 ∪ X along with the definition (4). Notethat the measurement matrix is 1-independent if and only if
the irreducible one is 1-independent.
Let X0 be the intermediate counter set assuming  = 0
at Line 5 in Algorithm 3, XALG be the output of Algorithm 3,
X ∗ be the optimal counter set of (10) for given thresholds and δ. We define a feasible counter set as a counter set thatmakes a measurement matrix 1-independent. Both X0 and

XALG are feasible counter sets.
4.3.2

Algorithm

To approximately solve the problem (10), we solve the problem for  = 0 and convert its solution X0 into a solution
XALG for given  and δ. This is because, when the lower
threshold  equals to 0, the coverage function g0 becomesa submodular function (Proof sketch in Appendix A.1) anda simple greedy algorithm yields an approximate solution
with a theoretical guarantee in polynomial-time [21]. Also,
the counter set conversion runs in linear time and the counterincrease is theoretically bounded. Note that the solution
XALG for given  and δ can differ from the solution X0 for = 0 since the measurement matrix A(X) can be changed
depending on  and δ. The measurement matrix is definedby separable subpaths under the given counters, and whether
or not a subpath is separable depends on  and δ. If  = 0,
all subpaths are separable from the definition. Conversely,for example, subpaths with 3 or more arcs are not separable
when  = 0.1 and δ = 0.2.
First, from Line 1 to Line 4, Algorithm 3 finds a feasible counter set for  = 0. In the while loop, we can find thecounter x∗ that maximizes the gain by calculating the gain
g(x|X) for all counters x = (e, P) ∈ E ×P\ X. After the while
loop, the counter set X0 is a feasible counter set for  = 0:
g0 (X0 ) = g0 (C̃) (Lemma 6).
Then, Algorithm 3 converts the feasible counter set X0
into a feasible one for given thresholds  and δ by adding
counters through the subroutine Separate (Lines 5, 6, andAlgorithm 4). Every time the subroutine adds a counter(ek0 , P), the subpath Q = {e j , . . . , ek−1 } is divided into two
subpaths Q1 = {e j , . . . , ek0 −1 } and Q2 = {ek0 , . . . , ek−1 }. Line
1 identifies the subscript k0 of the arc at which a countershould be added. −1 + dlog1− (1 − δ)e means the maximum0
integer d0 that satisfies 1 − δ < (1 − )d (i.e. d0 is the maximum length for a subpath to be separable). Note that, now
the former subpath Q1 is separable for given thresholds and δ. As a result, every irreducible subpath Q for  = 0
is divided into irreducible subpaths Q1 , Q2 , . . . , Ql for given
thresholds  and δ. After Line 6, the counter set XALG is afeasible counter set: g(XALG ) = g(C̃) (Lemma 5).
4.3.3

Proof

First, we prove the correctness of the Algorithm 3, i.e., theoutput counter set XALG satisfies g(XALG ) = g(C̃). Then, we
prove the Theorem 2 by evaluating the approximation ratioof Algorithm 3. Note that it is trivial to show that Algorithm 3 runs in polynomial time for |E| and |P|.
To show the correctness, it is sufficient to prove the following two lemmas.
Lemma 5. If the intermediate counter set X0 satisfies
g0 (X0 ) = g0 (C̃) then the output counter set XALG satisfies
g(XALG ) = g(C̃).
Lemma 6. The intermediate counter set X0 satisfies

IEICE TRANS. COMMUN., VOL.E102–B, NO.1 JANUARY 201982

g0 (X0 ) = g0 (C̃).
Proof of Lemma 5. We will prove by contradiction. Let
A = (ai j ) be the measurement matrix of XALG for given and δ, A0 = (a0i j ) be the irreducible measurement matrix of
X0 for  = 0. As shown in Algorithm 3, the subroutine Separate shown in Algorithm 4 computes the difference between
XALG and X0 . The irreducible separable subpath of X0 for = 0 is divided into separable subpaths for geven  and δ
by XALG . Suppose that g(XALG ) < g0 (X0 ). Then, there exist
two arc e j and ek such that a j = ak and a0j , a0k . Hence,
there exists an irreducible separable subpath Q0i for  = 0 at
X0 such that a0i j , a0ik . This subpath Q0i must be divided intosome subpaths Qi1 , . . . , Qil through the subroutine Separate.
Thus, we havea0i j = ai1 j ∨ ai2 j ∨ · · · ∨ ail j ,(13)

a0ik = ai1 k ∨ ai2 k ∨ · · · ∨ ail k ,(14)since all arcs in subpath Qi are included in either of
Qi1 , . . . , Qil . The right-hand sides of (13) and (14) must not
be equal since a0i j , a0ik . However, this contradicts a j = ak
because the right-hand sides of (13) and (14) are equal if
a j = ak .
Proof of Lemma 6. The problem of (10) for  = 0 iscalled the submodular cover [21], [22] because the function g0 is monotone submodular for  = 0 (Sketch of
proof in Appendix). The previous research [21] showsthat the greedy algorithm from Lines 1 to 4 in Algorithm 3 finds a feasible solution and its approximation ratiois H(max x∈C̃ g0 ({x})).
To prove the approximation ratio, it is sufficient toprove the following two lemmas.
Lemma 7. For given , δ, and d, the following inequality
holds.
!
d−1|XALG | ≤ 1 +|X0 |.
(15)
log1− (1 − δ) − 1
Lemma 8. For given n, the following inequality holds.
!
n(n + 1)
|X ∗ |.
(16)|X0 | ≤ H
2
Proof of Lemma 7. We have |Q0 | = |X0 | since there is a oneto-one relation between the last arc ek−1 of an irreducible
separable subpath Q ⊆ P and a counter (ek , P) ∈ X0 . For
each irreducible separable subpath Q ∈ Q0 , Separate adds at
most log d−1(1−δ)−1 counters to X0 . Hence, we have

Proof of Lemma 8. From the proof of Lemma 6, we have!
n(n + 1)∗
|X0∗ |(19)|X0 | ≤ H(max g0 ({x}))|X0 | ≤ H
2x∈C̃where X0∗ is an optimal solution of (10) for  = 0. Also, we
have |X0∗ | ≤ |X ∗ | since X ∗ is also a feasible counter set for = 0. This is because every irreducible separable subpath
Q of X ∗ for given  and δ is also separable for  = 0.
5.

Path-Set Measurement

This subsection briefly discusses how to extend Sect. 4 for“path-set” measurement, in order to reduce the number ofcounters. Figure 3 shows a tree that is the union of l paths;
the ingress arcs, e1 , e2 , . . . , el , are their own but the egressarc e0 is common. If the l paths were observed individually,
we would require 2l counters, but the tree has only l + 1
counters because the egress counter covers the l paths. Thisimplies that a counter is defined as a pair of an arc and a setof feasible paths, i.e., C ⊆ E × 2P .
Due to lack of space, we only present the overview of
the theorems in an informal manner. The measurement matrix A(C) is also defined for path-set counter C in a similar manner. This matrix induces also sufficient condition of
measurability:
Theorem 3. When τ j is estimated by a similar algorithmwith Algorithm 1, a counter set C is weakly α-measurable,
if the measurement matrix A(C) is 1-independent, where theconstant α is defined as†
v
u
s

u
t 
!2




1 + ζ

1−ζ


α= ζ
−
+
δ
−

.
(20)





2
2


where ζ equals to (1 − )d−2 .
Here weakly α-measurable is a relaxed condition of αmeasurable. The counter set C is weakly α-measurable if,∀P ∈ P, ∀e j ∈ P, ∀τ j :1· τ j or,α1
α · λ j ≤λ̂ j ≤ · λ j ,αα · τ j ≤τ̂ j ≤where λ j is the number of packets dropped between e1 ande j−1 , i.e., λ j = τ1 − τ j . Again, we reformulate our problem†
The last term δ −  can be considered as the overhead of pathset measurement since if we remove the last term then we obtain,
α = ζ = (1 − )d−2 ; the same results of Theorem 1.

1−

d−1
|Q0 |
log1− (1 − δ) − 1
!
d−1
≤ 1+
|X0 |.
log1− (1 − δ) − 1|XALG | ≤ |X0 | +

(17)
(18)


Fig. 3 A subtree Q. The root arc is e0 while the leaf arcs are e j ( j =1, 2, . . . , l); the root is not included in Q. Counters, (e j , P j )’s, are placed at
the black vertices.

WATABE et al.: MEASURING LOST PACKETS WITH MINIMUM COUNTERS IN TRAFFIC MATRIX ESTIMATION

83

Algorithm 5: Counter Placement (Path-Set)
Input: A set of feasible paths P and loss thresholds , δ,counter values κ, and a real number ρ.
Output: A counter set XALG that satisfies g(XALG ) = g(C̃).
1 X0 ← ∅;2 while ∃x ∈ C̃ : g0 (x|X0 ) > 0 do
3x̃ ← Find x such that((1/3) − ρ) max x∗ ∈C̃ g0 (x∗ |X0 ) ≤ g0 (x|X0 );4
X0 ← X0 ∪ { x̃};
Q0 ← Irreducible separable subtrees of X0 at  = 0;
forall Q ∈ Q0 do XALG ← Separate(Q, X0 , , δ, κ) ;7 return XALG

5

6

Algorithm 6: Separate (Path-Set)
S
Input: A subtree Q = {e j , . . . , ek−1 } ⊆ P0 , a counter set
X0 , loss thresholds , δ, and counter values κ.
Output: A counter set XALG that divides the subtree Q
into separable subtrees.
1 XALG ← X0 ;2 if Q is separable then return XALG ; // Do nothing
3 e∗ ← arg mine ∈Q h̃(ek );k4 P∗ ← arg minP ∈P h̃(P j );j0
5 if h̃(e∗ ) ≤ h̃(P∗ ) then // Divide at e∗
6
XALG ← XALG ∪ (e∗ , ∪e∗ ∈P j P j );7
(Q1 , Q2 ) ← (Ue∗ , Q \ Ue∗ );8 else // Peel off P∗
9
XALG ← XALG \ {(e0 , P0 )} ∪ {(e0 , P∗ ), (e0 , P{∗ )};10(Q1 , Q2 ) ← (Q ∩ P∗ , Q ∩ P{∗ );XALG ← Separate(Q1 , XALG , , δ, κ);
XALG ← Separate(Q2 , XALG , , δ, κ);
13 return XALG

11

12

as follows,min {|C| : A(C) is 1-independent}.

C⊆E×2P(21)

Due to the space limit, we do not describe the path-set version of Algorithms 1 and 2, which are used to estimate traffic
volumes based on packet counts.
The remaining of this section, we explain the differences between path-set algorithm shown in Algorithms 5
and 6 and per-path one.
The algorithm approximately finds the maximum gainarg max g0 (x|X0 ) since calculating all the gain g0 (x|X0 ) for
all x ∈ C̃ \ X0 takes exponential time (Compare Line 3 inAlgorithms 3 and 5). This is because the number of candidate counters roughly equals to |E|2|P| . The following Theorem provides ((1/3) − ρ)-approximation algorithm by utilizing a submodular maximization algorithm [23] (We omit
the proof due to lack of space).
Theorem 4. There exists a polynomial-time ((1/3) − ρ)approximation algorithm for the problem max x∈C̃ g0 (x|X0 ).
We explain differences between subroutine for path-set(Algorithm 6) and per-path (Algorithm 4). Algorithm 6 divides a subtree Q and/or peels off a path from it to makeit separable
for given  and δ. Algorithm 6 adds a counterS(ek , ek ∈P j P j ) inside the subtree and the subtree is divided
into an upper part Uek and a lower part Q \ Uek (Lines 6
and 7). Here Uek is the upper side of the subtree that obtained by dividing the subtree Q at the arc ek (ek is excluded
from Uek ). Or, Algorithm 6 replaces the counter on theroot arc (e0 , P0 ) with two counters {(e0 , P j ), (e0 , P{j )}, whereS
P{j is the path set of Q other than P j : P{j = lj0 =1: j0 , j P j(Line 9). This peels the subpath Q ∩ P j from the subtree
Q and we have new subpath Q ∩ P j and subtree Q ∩ P{j(Line 10). Algorithm 6 selects counter addition or replacement based on a greedy strategy, which minimizes the deviation of the separable condition for path-set (Line 3 to 5).
This deviation is measured by the following function h:

 l

 X 
1 − (1 − )d j κ j − δ min κ j  . (22)h(Q) = max 0,jj=1

Note that h(Q) = 0 if and only if Q is separable. Hence,
we define the deviation
 of dividing at ek as h̃(ek ) =max h(Uek ), h(Q \ Uek ) and that of peeling off P j ash̃(P j ) = max h(Q ∩ P j ), h(Q ∩ P{j ) .
6.

Practical Modeling Issues

This section describes how to model a network that consistsof actual switches. We begin with a switch model. We assume that each switch consists of a forwarding element andseveral ports. A forwarding element includes a forwarding
information base (FIB) and a switching bus; the FIB determines an output port through which a packet transmitted,
while the switching bus transfers the packet to the output
port. Each port has a packet queue, an access control list
(ACL), and counters. Ports are categorized to input ports
and output ports. A pair of input and output ports at different switches is connected by a point-to-point link.
A FIB and ACL is a set of rules. Each rule associatesa packet filter with an action; a FIB action is one of output ports in the switch, while an ACL action is “permit”
or “discard”. A path along which a packet is transferred isdetermined by rules matched to the packet, and so we cancalculate all the feasible paths in a network using the FIBs
and ACLs [24], [25]. Counters are associated with a set of
feasible paths in our method, so packets have to be classified based on the paths. Packet classification was traditionally designed only for actions at a single switch, but recently
new techniques has been developed to classify packets basedon a combination of switch actions, i.e., a path, at the rateof 10 Gbps links [15], [16]; this advancement has made ourmethod feasible. We only consider paths that are not terminated by ACLs, since we are interested in transit traffic for
the TM estimation.
In our graph model introduced in Sect. 3, a FIB and
ACL is represented by a tail of arc, because a path isswitched by FIBs and packets are counted around ACLs.
Figure 4 shows an example. For an input port, we assume

IEICE TRANS. COMMUN., VOL.E102–B, NO.1 JANUARY 201984
Table 2

Fig. 4

Switches
Ports usedFeasible paths |P|
Maximum path length dArcs with FIB/ACL |E|

A part of network and the corresponding graph model.

Table 3that the tail includes the ACL and counters while the arc isthe bus to the FIB. For a forwarding element, the vertex is
the FIB while each arc represents a bus to the corresponding output port. For an output port, the tail is the ACL andcounters, while the arc includes the output queue, the link,
and the opposed input queue.
Since no counter is usually placed at forwarding elements in ordinary switches, we assume that tails of forwarding elements cannot have counters. This implies that wemight not be able to make a network measurable due to thelack of counters. The packet loss ratios of indistinguishable
arcs should be estimated conservatively in Algorithm 1; takethe worst case as if either arc were determined as abnormal.
Note that this cannot be an issue in OpenFlow networks,
because OpenFlow switches are required to return packet
counts for every flow entry.
7.

Experiments

We perform experiments to evaluate our approach using
three configuration datasets and one traffic dataset. The configuration datasets are obtained from Internet2† , Stanford
backbone network [26], and Purdue campus network [27],while the traffic data comes from Internet2†† . The configuration datasets include a network topology and FIBs at every switch. Actual ACLs are used only for Stanford. Alltransit paths are extracted from the datasets and are used as
feasible paths. The paths for Stanford including ACLs are
extracted according to the model described in Sect. 6. The
statistics are given in Table 2 (arcs on no transit path are
ignored). In the traffic dataset, traffic volumes in byte for
144 paths were measured every 5 min for 7 days. The average, the variance, and the maximum/minimum ratio are
9.47 × 108 , 2.32 × 1018 , and 1.89 × 105 , respectively. Traffic
volume in the traffic dataset is randomly mapped to a path ina configuration dataset. Since the traffic data is used to determine packet counts κ, the traffic volume in byte is translated
into the traffic volume in packets, by assuming the average
packet length equals for all paths.
7.1

Per-Path Measurement

7.1.1

Size of Counter Set

We first calculate the optimal counter set, C0 ∪ X, for perpath measurement and examine indistinguishable arc-pairs†††

http://vn.grnoc.iu.edu/Internet2/fib
http://www.cs.utexas.edu/ yzhang/research/AbileneTM/

Number of elements in the configuration datasets.
Internet2

Stanford

Purdue914011,159
5
140

16
58
331
9
132

1,503
526
2,985
5
526

Number of counters and arc-pairs for  = 0.

Initial counters |C0 |Additional counters |X|
Indistinguishable arc-pairs / all arc-pairs

Table 4

Internet2

Stanford

Purdue11,159116
0 / 9,730

331
65
49 / 8,646

2,985
380
0 / 138,075

Number of matrix rows for the Boolean algebra approach.

Number of matrix rows

Internet2

Stanford

Purdue

115

66

380

for  = 0; an arc pair (ei , e j ) ∈ E 2 is indistinguishable if thecorresponding column vectors ai , a j are equal. As shown in
Table 3, some arc-pairs are indistinguishable only for Stanford due to the limitation noted in Sect. 6, but they are only
successive FIB and ACL in a same switch, and the arc-pairs
are mutually exclusive. The number of additional counters,
which is shown in Table 3, corresponds to the number ofrows in the measurement matrix. The number of rows is
also calculated for the Boolean algebra approach [14], andthe results are shown in Table 4. The number of additionalcounters |X| in Table 3 and the number of matrix rows in Table 4 are almost the same value. The results imply that ourapproach almost agrees with the lower bound provided by
the Boolean algebra approach; our approach is better thanthe bound for Stanford due to the approximation of optimization algorithms.
Next, we verify the number of matrix rows when  , 0.
In this case, the number of matrix rows depends on threshold δ; Fig. 5 shows the number of matrix rows for  = 10−5
and 10−5 ≤ δ ≤ 10−1 . The green horizontal line shows thelower bound, i.e., the number of rows for the Boolean algebra approach [14]. Our approach almost converges to thelower bound for δ > 5.0 × 10−5 , and the number at δ = 10−1
is coincident with that for  = 0 and δ = 1. The Boolean
algebra approach [14] assumes   δ to clearly distinguishabnormal links, but the results show the assumption is unnecessary even for the traffic volume estimation, which is far
beyond the Boolean algebra approach. Note that, for δ ≈ in Stanford, measurement matrices cannot be obtained since
separable subpaths are not able to be composed due to therestrictions mentioned in Sect. 6.
7.1.2

Error Bounds

Theorem 1 shows that our approach is (1 − )d−2 -measurable
for per-path measurement. For  = 10−5 and d shown in Table 2, (1−)d−2 ≥ 0.99993. The error bounds on a estimationof traffic volumes are only ±0.01%. Our approach can accu-

WATABE et al.: MEASURING LOST PACKETS WITH MINIMUM COUNTERS IN TRAFFIC MATRIX ESTIMATION

85

Fig. 5
Table 5The number of rows in a measurement matrix.

Additional counters |X| for per-path and path-set measurements.

Additional counters |X| (per-path)
Additional counters |X| (path-set)Internet2

Stanford

Purdue

116
116

65
67

380
359

rately estimate traffic volumes, since the accuracy is highly
guaranteed with these error bounds.
7.2

Path-Set Measurement

The size of counter set is also evaluated for path-set measurement; Table 5 gives the size for  = 0 and δ = 1. Purdue gets the largest gain, because it has many large trees
like Fig. 3. The results for Internet2 and Stanford are similar to the results in Table 3 though |X| for Stanford slightly
increases due to the approximation algorithm. Internet2
has the largest number of feasible paths but they cannot bemerged into trees due to the loss of measurability, while
Stanford does not have feasible paths enough to reduce thecounters.
The time to spend for the path-set version of Algorithm 4 is shorter than 10 sec using a PC with 3.4 GHz Intel
Core i5 processor. The algorithm can be done in an online
manner following a change of traffic volume in 10 sec timescale or longer.
8.

Related WorkTo estimate the traffic volumes, conventional TM estimation methods [5]–[11], [28] rely on link traffic measured atedge switches without breaking the traffic volume to paths orflows. The estimation is performed with EM algorithm [5],entropy maximization [6], neural networks [7], and compressive sensing [8], [9]. Some methods are comparedin [10], [11]. Computational costs [28] and monitoring errors [9] are studied. To the best of our knowledge, no literature addresses packet drops in the context of TM estimation.
A rich collection of fault localization techniques in networks has been developed. Network tomography localizes
failed links usually using active probes [29]–[33]. Since active probes disrupt production traffic, their use is limited to
off-peak hours. Passive approach to the network tomography has been also studied [14], [34]–[36]. References [34]–[36] depend on TCP signaling packets (e.g., TCP-ACK),
they cannot be applied to UDP traffic. In addition to the network tomography, machine learning approaches have been

also proposed in order to diagnose fault cause [37]. There
has been no method designed to estimate the amount of lost
packets, while the conventional tomography techniques report loss ratio of packets.
Optimization algorithms regarding a submodular function are well-studied in combinatorial optimization [20].
Approximation algorithms for the submodular cover problem has been proposed [21], and it is recently generalized
to a monotone submodular cost function [22]. A constantfactor approximation for maximizing nonnegative submodular functions has been achieved in reference [23].
9.

Conclusion

This paper proposed a TM estimation method that handles
packet dropping in a network. With the solid theory about
the measurability based on Boolean matrices, we developed
an optimization algorithm for the minimum counter set. Experiments in real datasets showed its strong performance.
We believe that this paper gives a new viewpoint to network
measurement and opens a novel research field linking theTM estimation and the fault localization. This research fieldembraces mathematical interests as well as practical importance.
We will extend our method to consider the constraintof SRAM size. We also will investigate the impact of traffic fluctuation and packet sampling on the accuracy of our
method. This paper assumed path volumes are directly
counted at ingress switches, but they could be estimated by
TM estimation techniques; this approach gives us opportunities to reduce counters further, though estimation errors
might not be bounded.
Acknowledgments
This work was partly supported by the Japan Prize Foundation, and JSPS KAKENHI Grant Number JP17K00008 and
JP18K18035.
References[1] B. Fortz and M. Thorup, “Optimizing OSPF/IS-IS weights ina changing world,” IEEE J. Sel. Areas Commun., vol.20, no.4,
pp.756–767, 2002.
[2] M. Roughan, M. Thorup, and Y. Zhang, “Traffic engineering withestimated traffic matrices,” ACM IMC, pp.248–258, 2003.
[3] R.S. Cahn, Wide Area Network Design: Concepts and Tools for
Optimization, Morgan Kaufmann, 1998.

IEICE TRANS. COMMUN., VOL.E102–B, NO.1 JANUARY 201986

[4] Y. Zhang, Z. Ge, A. Greenberg, and M. Roughan, “Network
anomography,” ACM IMC, pp.317–330, 2005.
[5] Y. Vardi, “Network tomography: Estimating source-destination traffic intensities from link data,” J. Am. Stat. Assoc., vol.91, no.433,
pp.365–377, 1996.
[6] Y. Zhang, M. Roughan, C. Lund, and D.L. Donoho, “Estimating point-to-point and point-to-multipoint traffic matrices: An
information-theoretic approach,” IEEE/ACM Trans. Netw., vol.13,
no.5, pp.947–960, 2005.
[7] D. Jiang, X. Wang, L. Guo, H. Ni, and Z. Chen, “Accurate estimationof large-scale IP traffic matrix,” Int. J. Electron. Commun., vol.65,
no.1, pp.75–86, 2011.
[8] D. Jiang, Z. Xu, Z. Chen, Y. Han, and H. Xu, “Joint time-frequency
sparse estimation of large-scale network traffic,” Comput. Netw.,
vol.55, no.15, pp.3533–3547, 2011.
[9] M. Roughan, Y. Zhang, W. Willinger, and L. Qiu, “Spatio-temporalcompressive sensing and internet traffic matrices (extended version),” IEEE/ACM Trans. Netw., vol.20, no.3, pp.662–676, 2012.
[10] A. Gunnar, M. Johansson, and T. Telkamp, “Traffic matrix estimation on a large IP backbone: A comparison on real data,” ACM IMC,
pp.149–160, 2004.
[11] M.M. Rahman, S. Saha, U. Chengan, and A.S. Alfa, “IP traffic matrix estimation methods: Comparisons and improvements,” IEEE
ICC, pp.90–96, 2006.
[12] C. Guo, L. Yuan, D. Xiang, Y. Dang, R. Huang, D. Maltz, Z. Liu,
V. Wang, B. Pang, H. Chen, Z.W. Lin, and V. Kurien, “Pingmesh: Alarge-scale system for data center network latency measurement andanalysis,” ACM SIGCOMM Comput. Commun. Rev., vol.45, no.4,
pp.139–152, 2015.
[13] H.X. Nguyen and P. Thiran, “Active measurement for multiple link
failures diagnosis in IP networks,” 5th Passive and Active Measurement Conference (PAM 2004) Workshop, pp.185–194, 2004.
[14] S. Agrawal, K.V.M. Naidu, and R. Rastogi, “Diagnosing link-levelanomalies using passive probes,” IEEE INFOCOM, pp.1757–1765,
2007.
[15] T. Inoue, T. Mano, K. Mizutani, S.i. Minato, and O. Akashi, “Rethinking packet classification for global network view of softwaredefined networking,” IEEE ICNP, pp.296–307, 2014.
[16] H. Wang, C. Qian, and S.S. Lam, “Practical network-wide packet
behavior identification by AP classifier,” CoNEXT, 2015.
[17] S.B. Moon, P. Skelly, and D. Towsley, “Estimation and removal ofclock skew from network delay measurements,” IEEE INFOCOM,
vol.1, pp.227–234, 1999.
[18] Y. Gu, L. Breslau, N. Duffield, and S. Sen, “On passive one-way
loss measurements using sampled flow statistics,” IEEE INFOCOM,
pp.2946–2950, 2009.
[19] N.G. Duffield and M. Grossglauser, “Trajectory sampling for directtraffic observation,” IEEE/ACM Trans. Netw., vol.9, no.3, pp.280–
292, 2001.
[20] S. Fujishige, Submodular Functions and Optimization, Elsevier,
2005.
[21] L.A. Wolsey, “An analysis of the greedy algorithm for the submodular set covering problem,” Combinatorica, vol.2, no.4, pp.385–393,
1982.
[22] R.K. Iyer and J.A. Bilmes, “Submodular optimization with submodular cover and submodular knapsack constraints,” Advances in Neural Information Processing Systems 26, pp.2436–2444, Curran Associates, 2013.
[23] U. Feige, V.S. Mirrokni, and J. Vondrák, “Maximizing nonmonotone submodular functions,” SIAM J. Comput., vol.40, no.4,
pp.1133–1153, 2011.
[24] G. Xie, J. Zhan, D. Maltz, H. Zhang, A. Greenberg, G. Hjalmtysson, and J. Rexford, “On static reachability analysis of IP networks,”
IEEE INFOCOM, pp.2170–2183, 2005.
[25] H. Yang and S.S. Lam, “Real-time verification of network properties using atomic predicates,” IEEE/ACM Trans. Netw., vol.24, no.2,
pp.887–900, 2016.

[26] P. Kazemian, G. Varghese, and N. McKeown, “Header space analysis: Static checking for networks,” 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI 2012), 2012.
[27] 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.
[28] G. Liang, N. Taft, and B. Yu, “A fast lightweight approach toorigin-destination IP traffic estimation using partial measurements,”
IEEE/ACM Trans. Netw., vol.52, no.6, pp.2634–2648, 2006.
[29] M. Coates and R. Nowak, “Network loss inference using unicast
end-to-end measurement,” 13th ITC Specialist Seminar on IP Traffic, Measurement, and Modeling, 2000.
[30] N. Duffield, “Network tomography of binary network performance
characteristics,” IEEE Trans. Inf. Theory, vol.52, no.12, pp.5373–
5388, 2006.
[31] H.X. Nguyen and P. Thiran, “Network loss inference with second
order statistics of end-to-end flows,” ACM IMC, p.227, 2007.
[32] M.H. Firooz and S. Roy, “Network tomography via compressedsensing,” IEEE GLOBECOM, 2010.
[33] T. Matsuda, M. Nagahara, and K. Hayashi, “Link quality classifier
with compressed sensing based on `1 -`2 optimization,” IEEE Commun. Lett., vol.15, no.10, pp.1117–1119, 2011.
[34] V. Padmanabhan, L. Qiu, and H. Wang, “Server-based inference ofInternet link lossiness,” IEEE INFOCOM, pp.145–155, 2003.
[35] Y. Tsang, M. Yildiz, P. Barford, and R. Nowak, “Network radar: Tomography from round trip time measurements,” ACM IMC, pp.175–
180, 2004.
[36] Y. Tsang, M. Yildiz, P. Barford, and R. Nowak, “On the performanceof round trip time network tomography,” IEEE ICC, pp.483–488,
2006.
[37] M. Chen, A.X. Zheng, J. Lloyd, M.I. Jordan, and E. Brewer, “Failure diagnosis using decision trees,” 1st International Conference on
Autonomic Computing (ICAC 2004), pp.36–43, 2004.

Appendix:
A.1

ProofsSubmodularity of Coverage Functions

This appendix proves the following Theorem 5.
Theorem 5. Coverage function g0 for  = 0 is submodular.
We only show the proof for the path measurability, but
the proof for the pathset is almost same.
The function g0 for  = 0 is submodular if and only if
g0 (x|X) ≤ g0 (x|X 0 ) for all X ⊇ X 0 and x < X. If ai = a j
in X but a0i , a0j in X ∪ {x}, this is mentioned as the arc
pair, e j , ek , is distinguished by adding the new counter x to
X where (ai j ) and (a0i j ) are the measurement matrices of X
and X 0 , respectively. A part of feasible path P, which starts
from ei to e j , is denoted by Pi→ j (ei ∈ Pi→ j but e j < Pi→ j ).
Lemma 9. Let a new counter x = (el , P) be added tocounter set X and be placed after an arc ek , where ek was
the last counter arc on feasible path P (Fig. A· 1 (Top)). If
an arc pair, ei , e j ∈ E, is distinguished by the new counter x,then they satisfy ei ∈ Pk→l ∧ e j < P1→l or vice versa.
Proof. Proof by contradiction. Suppose the other the otherarc e j is in P1→l . If e j is in the same part Pk→l , then the pairei , e j is clearly undistinguished, which is a contradiction. If
e j is in P1→k , then the pair ei , e j is already distinguished inWATABE et al.: MEASURING LOST PACKETS WITH MINIMUM COUNTERS IN TRAFFIC MATRIX ESTIMATION

87

Toru Mano
is a researcher in NTT Network
Innovation Labs. He received the B.E. and M.E.
degrees in Information Science and Technology
from the University of Tokyo in 2009 and 2011,
respectively. His research interests are networkarchitectures and network optimization.

Fig. A· 1 (Top) Counter (el , P) is put at the red vertex, which follows thepreceding counters. (Bottom) Counter (el , P) is put at the red vertex, which
is between other counters.

X. This, however, contradicts to the assumption that adding
x distinguishes the pair ei , e j .
Lemma 10. Let a new counter x = (el , P) be added tocounter set X and be placed between two counter arcs ek
and em on feasible path P (Fig. A· 1 (Bottom)). If an arc
pair, ei , e j ∈ E, is distinguished by x, then they satisfy
ei ∈ Pk→l ∧ e j ∈ Pl→m or vice versa.
Proof. It can be proven by contradiction like Lemma 9.

The submodularity of g is finally shown in the following lemma.
Lemma 11. The submodularity condition, g0 (x|X)
g0 (x|X 0 ), holds for X ⊇ X 0 and x < X.

Takeru Inoue
is a senior researcher in NTT
Laboratories. He was an ERATO researcher
at the Japan science and technology agency
from 2011 through 2013. His research interests widely cover the design and control of network systems. He received the best paper award
from the Asia-Pacific conference on communications in 2005, and also the research awards ofthe IEICE Information Network Group in 2002,
2005, and 2012. He received the B.E., M.E., andPh.D. degrees from Kyoto University, Kyoto,
Japan, in 1998, 2000, and 2006, respectively. He is a member of IEEE.

≤
Kimihiro Mizutani
is a researcher in NTT
Network Innovation Labs. He received the M.S.
degree in information system from Nara Institute Science and Technology in 2010. His research interests include future internet architectures. He received the best student paper
from International Conference on Communication Systems and Application (ICCSA) in 2010.
He also received research awards from IPSJ and
IEICE in 2010 and 2013, respectively. He isa member of IEICE and IEEE Communication

Proof. It is sufficient to show that any arc pair distinguishedby adding x to X is also distinguished by adding x to X 0 .
• Consider the case that the counter x = (el , P) is placed
after the last counter arc on P (Fig. A· 1 (Top)). If an arc
pair ei , e j is distinguished by adding the new counter x
to X, then ei ∈ Pk→l and e j < P1→l from Lemma 9. Thisarc pair is also distinguished by adding x to X 0 , because
every feasible path has the ingress counter (e1 , P) as C0
and ei is in the subpath of P1→l , which is created by x.
• Consider the other case, the counter x = (el , P) is
placed before the last counter arc on P (Fig. A· 1 (Bottom)). In a similar way with the previous case, we canshow that the arc pair is also distinguished by adding x
to X 0 , using Lemma 10.
Kohei Watabe
received his B.E. and M.E.
degrees in Engineering from Tokyo Metropolitan University, Tokyo, Japan, in 2009 and 2011,
respectively. He also received the Ph.D. degree from Osaka University, Japan, in 2014. He
was a JSPS research fellow (DC2) from April
2012 to March 2014. He has been an AssistantProfessor of Graduate School of Engineering,
Nagaoka University of Technology since April
2014. He is a member of the IEEE and the
IEICE.

Society.

Osamu Akashi
is a senior research scientist
in NTT Network Innovation Laboratories. He
received the M.S. degree in information scienceand the Ph.D. degree in mathematical and computing sciences from Tokyo Institute of Technology, in 1989 and 2001, respectively. His
research interests include distributed systems,
multi-agent systems, and network architectures.

Kenji Nakagawa
received the B.S., M.S.
and D.S. degrees from Tokyo Institute of Technology, Tokyo, Japan, in 1980, 1982 and 1986,
respectively. In 1985, he joined NTT (Nippon
Telegraph and Telephone Corp.). Since 1992,
he has been an associate professor of Graduate
School of Engineering, Nagaoka University ofTechnology. He is an associate editor of the
IEICE Transactions on Communications. His
research interests include queueing theory, performance evaluation of networks, and geometrictheory of statics. Dr. Nakagawa is a member of the IEEE, SITA, and Mathematical Society of Japan.