Compressed Network Monitoring
Mark Coates
Department of Electrical and Computer Engineering
McGill U

This talk will describe a procedure for estimating a full set of network path metrics from a limited number of measurements. The approach exploits the strong spatial and temporal correlation observed in path-level metric data, which arises due to shared links and stationary components of the observed phenomena. We derive diffusion wavelets from the routing matrix to generate a basis in which the signals are compressible (coefficients exhibit approximately power law decay). This allows us to exploit powerful non-linear estimation algorithms that strive for sparse solutions. We demonstrate our results using measurements of end-to-end delay in the Abilene network and simulations of bit error rate in an all-photonic network. Our results show that the number of routes we need to monitor is surprisingly low (e.g., we can recover network mean end-to-end delay with 5% accuracy while monitoring only 7% of the routes).