Sequential Loss Tomography Using Compressed Sensing

Kazushi TAKEMOTO  Takahiro MATSUDA  Tetsuya TAKINE  

IEICE TRANSACTIONS on Communications   Vol.E96-B   No.11   pp.2756-2765
Publication Date: 2013/11/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E96.B.2756
Print ISSN: 0916-8516
Type of Manuscript: Special Section PAPER (Special Section on Progress in Information Network Science)
network tomography,  loss tomography,  compressed sensing,  sparse vector,  

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

Network tomography is a technique for estimating internal network characteristics from end-to-end measurements. In this paper, we focus on loss tomography, which is a network tomography problem for estimating link loss rates. We study a loss tomography problem to detect links with high link loss rates in network environments with dynamically changing link loss rates, and propose a window-based sequential loss tomography scheme. The loss tomography problem is formulated as an underdetermined linear inverse problem, where there are infinitely many candidates of the solution. In the proposed scheme, we use compressed sensing, which can solve the problem with a prior information that the solution is a sparse vector. Measurement nodes transmit probe packets on measurement paths established between them, and calculate packet loss rates of measurement paths (path loss rates) from probe packets received within a window. Measurement paths are classified into normal quality and low quality states according to the path loss rates. When a measurement node finds measurement paths in the low quality states, link loss rates are estimated by compressed sensing. Using simulation scenarios with a few link states changing dynamically from low to high link loss rates, we evaluate the performance of the proposed scheme.