Measuring Lost Packets with Minimum Counters in Traffic Matrix Estimation

Kohei WATABE  Toru MANO  Takeru INOUE  Kimihiro MIZUTANI  Osamu AKASHI  Kenji NAKAGAWA  

Publication
IEICE TRANSACTIONS on Communications   Vol.E102-B   No.1   pp.76-87
Publication Date: 2019/01/01
Publicized: 2018/07/02
Online ISSN: 1745-1345
DOI: 10.1587/transcom.2018EBP3072
Type of Manuscript: PAPER
Category: Fundamental Theories for Communications
Keyword: 
traffic matrix,  packet drop,  submodular optimization,  failure localization,  passive measurement,  

Full Text: PDF(1.7MB)>>
Buy this Article



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 is determined with submodular optimization. Numerical experiments are conducted with real network datasets to evaluate our method.