Groupe d’études et de recherche en analyse des décisions

Network Kriging

Eric Kolaczyk

Vigilant monitoring of computer networks by their operators is fundamental to everything from provisioning, to traffic management, to detection of malicious behavior. But complete network-wide measurement strategies for monitoring quickly become infeasible, and more efficient strategies are therefore needed. We consider the problem of monitoring certain path-based (or ?end-to-end?) properties, such as loss rates or packet delays, across an entire computer network, based on a limited number of measurements on some subset of all possible paths. This problem is naturally formulated as one of statistical prediction, and we offer a simple class of predictors for standard quantities of interest (e.g., averages, totals, differences), resulting in a methodology for `network kriging'. Linear algebraic methods of subset selection may be used to make effective choice of which paths to measure. The mean square prediction error properties of our overall approach are characterized through appropriate bounds. The methodology is illustrated through a handful of empirical examples. Crucial to the success of our approach is the low effective rank of so-called ?routing matrices?, as observed in practice, which allows us to exploit interesting ties between sparse network graph structure, dimension reduction techniques, and sparse inference methods.