Estimating latent processes on a network from indirect measurements
Preprint
Abstract
In a communication network, point-to-point traffic volumes over time are critical for designing protocols that route information efficiently and for maintaining security, whether at the scale of an internet service provider or within a corporation. While technically feasible, the direct measurement of point-to-point traffic imposes a heavy burden on network performance and is typically not implemented. Instead, indirect aggregate traffic volumes are routinely collected. We consider the problem of estimating point-to-point traffic volumes, x_t, from aggregate traffic volumes, y_t, given information about the network routing protocol encoded in a matrix A. This estimation task can be reformulated as finding the solutions to a sequence of ill-posed linear inverse problems, y_t = A x_t, since the number of origin-destination routes of interest is higher than the number of aggregate measurements available. Here, we introduce a novel multilevel state-space model of aggregate traffic volumes with realistic features. We implement a naive strategy for estimating unobserved point-to-point traffic volumes from indirect measurements of aggregate traffic, based on particle filtering. We then develop a more efficient two-stage inference strategy that relies on model-based regularization: a simple model is used to calibrate regularization parameters that lead to efficient and scalable inference in the multilevel state-space model. We apply our methods to corporate and academic networks, where we show that the proposed inference strategy outperforms existing approaches and scales to larger networks. We also design a simulation study to explore the factors that influence the performance. Our results suggest that model-based regularization may be an efficient strategy for inference in other complex multilevel models.Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- On Delay Tomography: Fast Algorithms and Spatially Dependent ModelsIEEE Transactions on Signal Processing, 2012
- Dynamic Markov BasesJournal of Computational and Graphical Statistics, 2012
- Identifiability of flow distributions from link measurements with applications to computer networksInverse Problems, 2007
- A fast lightweight approach to origin-destination IP traffic estimation using partial measurementsIEEE Transactions on Information Theory, 2006
- Data augmentation in multi-way contingency tables with fixed marginal totalsJournal of Statistical Planning and Inference, 2006
- Maximum pseudo likelihood estimation in network tomographyIEEE Transactions on Signal Processing, 2003
- Multicast-based inference of network-internal delay distributionsIEEE/ACM Transactions on Networking, 2002
- Blind source separation of more sources than mixtures using overcomplete representationsIEEE Signal Processing Letters, 1999
- The estimation of origin-destination matrices by constrained generalised least squaresTransportation Research Part B: Methodological, 1991
- Maximum Likelihood Reconstruction for Emission TomographyIEEE Transactions on Medical Imaging, 1982