Compressed Network Tomography for Probabilistic Tree Mixture Models

Abstract

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.

Additional details