A Caltech Library Service

Compressed Network Tomography for Probabilistic Tree Mixture Models

Khajehnejad, M. Amin and Khojastepour, Amir and Hassibi, Babak (2011) Compressed Network Tomography for Probabilistic Tree Mixture Models. In: 2011 IEEE Global Telecommunications Conference (GLOBECOM 2011). IEEE , Piscataway, Nj, pp. 1-6. ISBN 978-1-4244-9266-4 .

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


We consider the problem of network tomography in probabilistic tree mixture models. We invoke the theory of compressed sensing and prove that the distribution of a random communication network model with n nodes represented by a probabilistic mixture of k trees can be identified using low order routing summaries pertinent to groups of small sizes d << n in the network. We prove that, if the number of collected statistics m is at least O(n^(log k)), then certain classes of inference algorithms can successfully determine the unknown model, i.e. the topologies of mixing trees and their corresponding probabilities. We show that a variation of ℓ_1 minimization over the space of all possible trees of n nodes can be used for this purpose. In addition, we propose a novel inference algorithm with a complexity polynomial in n^(log k), with the same provable guarantee. The proposed model is applicable to practical situations such as ad-hoc and Peer-to-Peer(P2P) networks, and the presented inference method can lead to distributed protocols for network monitoring and tomography. In particular, we provide preliminary insight and numerical results on how the ideas are amenable to wireless sensor networks.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 2011 IEEE.
Record Number:CaltechAUTHORS:20150224-073614235
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:55132
Deposited By: Shirley Slattery
Deposited On:25 Feb 2015 00:55
Last Modified:03 Oct 2019 08:03

Repository Staff Only: item control page