
For FullText 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
Kohei WATABE Toru MANO Takeru INOUE Kimihiro MIZUTANI Osamu AKASHI Kenji NAKAGAWA
Publication
IEICE TRANSACTIONS on Communications
Vol.E102B
No.1
pp.7687 Publication Date: 2019/01/01 Publicized: 2018/07/02 Online ISSN: 17451345
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)>>
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 minimumcost counter placement is determined with submodular optimization. Numerical experiments are conducted with real network datasets to evaluate our method.


