For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Measuring Lost Packets with Minimum Counters in Traffic Matrix Estimation
IEICE TRANSACTIONS on Communications
Publication Date: 2019/01/01
Online ISSN: 1745-1345
Type of Manuscript: PAPER
Category: Fundamental Theories for Communications
traffic matrix, packet drop, submodular optimization, failure localization, passive measurement,
Full Text: PDF(1.7MB)>>
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 is determined with submodular optimization. Numerical experiments are conducted with real network datasets to evaluate our method.