TY - GEN
T1 - FRANTIC
T2 - 2014 6th International Conference on Communication Systems and Networks, COMSNETS 2014
AU - Cai, Sheng
AU - Bakshi, Mayank
AU - Jaggi, Sidharth
AU - Chen, Minghua
PY - 2014
Y1 - 2014
N2 - 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 SHO-FA algorithm [1] 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(klogn/logM) measurements suffice both for SHO-FA-INT and FRANTIC. Further, we show that the computational complexity of decoding is also O(klogn/logM) for each of these algorithms. Finally, we look at efficient constructions of the measurement operations through Steiner Trees.
AB - 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 SHO-FA algorithm [1] 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(klogn/logM) measurements suffice both for SHO-FA-INT and FRANTIC. Further, we show that the computational complexity of decoding is also O(klogn/logM) for each of these algorithms. Finally, we look at efficient constructions of the measurement operations through Steiner Trees.
UR - https://www.scopus.com/pages/publications/84896740668
UR - https://www.scopus.com/pages/publications/84896740668#tab=citedBy
U2 - 10.1109/COMSNETS.2014.6734865
DO - 10.1109/COMSNETS.2014.6734865
M3 - Conference contribution
AN - SCOPUS:84896740668
SN - 9781479936359
T3 - 2014 6th International Conference on Communication Systems and Networks, COMSNETS 2014
BT - 2014 6th International Conference on Communication Systems and Networks, COMSNETS 2014
Y2 - 7 January 2014 through 10 January 2014
ER -