Skip to main navigation Skip to search Skip to main content

FRANTIC: A Fast Reference-based Algorithm for Network Tomography via compressive sensing

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication2014 6th International Conference on Communication Systems and Networks, COMSNETS 2014
DOIs
StatePublished - 2014
Externally publishedYes
Event2014 6th International Conference on Communication Systems and Networks, COMSNETS 2014 - Bangalore, India
Duration: Jan 7 2014 → Jan 10 2014

Publication series

Name2014 6th International Conference on Communication Systems and Networks, COMSNETS 2014

Conference

Conference2014 6th International Conference on Communication Systems and Networks, COMSNETS 2014
Country/TerritoryIndia
CityBangalore
Period1/7/14 → 1/10/14

ASJC Scopus subject areas

  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'FRANTIC: A Fast Reference-based Algorithm for Network Tomography via compressive sensing'. Together they form a unique fingerprint.

Cite this