FRANTIC: A Fast Reference-based Algorithm for Network Tomography via Compressive Sensing

Sheng Cai, Mayank Bakshi, Sidharth Jaggi, Minghua Chen

We study the problem of link and node delay estimation in undirected networks when at most k out of n links or nodes in the network are congested. Our approach relies on end-to-end measurements of path delays across pre-specified paths in the network. We present a class of algorithms that we call FRANTIC. The FRANTIC algorithms are motivated by compressive sensing; however, unlike traditional compressive sensing, the measurement design here is constrained by the network topology and the matrix entries are constrained to be positive integers. A key component of our design is a new compressive sensing algorithm SHO-FA-INT that is related to the prior SHO-FA algorithm for compressive sensing, but unlike SHO-FA, the matrix entries here are drawn from the set of integers {0, 1, ..., M}. We show that O(k log n /log M) measurements suffice both for SHO-FA-INT and FRANTIC. Further, we show that the computational complexity of decoding is also O(k log n/log M) for each of these algorithms. Finally, we look at efficient constructions of the measurement operations through Steiner Trees.

Knowledge Graph



Sign up or login to leave a comment