Project Description
It is often desirable to monitor end-to-end properties, such as loss rates
or packet delays, across an entire network. However, active end-to-end
measurement in such settings does not scale well, and so network-wide
measurement quickly becomes infeasible. Previous work [1] has shown that for
exact recovery of end-to-end network properties, the number of paths that
need to be monitored can be reduced to approximately the number of links
in the network. In this project we recast the problem as one of
statistical prediction, giving up the goal of exact recovery, and show
that such properties may be accurately predicted in many cases using a
significantly smaller set of carefully chosen paths.
Figure 1: Boxplot of the relative prediction error
(Predictor - Actual Mean)/(Actual Mean)
for a 100-trial
simulation.
We formulate a general framework for the prediction problem, propose a
simple class of predictors for standard quantities of interest (e.g.,
averages, totals, differences), and show that linear algebraic methods
of subset selection may be used to make effective choice of paths to
measure. The feasibility of our method relies on the low effective
rank of routing matrices as encountered in practice, which appears to
be a new observation of interest in its own right.
Figure 2: Plots of the scaled eigen-spectra
of the routing matrices for various networks. The
singular values of each routing matrix have been rescaled by the
largest singular
value. The knee in the curves that occurs before k=100 is
indicative of low effective rank.
Overall, our work provides a prototype framework by which end-to-end
network properties may be monitored efficiently -- that is, with high
accuracy from a relatively minimal measurement infrastructure.
