 |
Center for Nonlinear Studies |
Internet service providers and customers are often concerned with performance measures such as the average delay (or loss rate) for data packets sent along paths in a network. Unfortunately, issues of scale can make forming such network-wide measures difficult. In particular, the number of paths grows too rapidly with the size of the network to make exhaustive measurement practical. As a result, it is of interest to explore the feasibility of methods that dramatically reduce the number of paths measured in such situations while maintaining acceptable accuracy. This talk casts the problem as one of statistical prediction--in the spirit of the so-called `kriging' problem in spatial statistics--and shows that such network-wide properties may be accurately predicted in many cases by measuring a surprisingly small set of carefully chosen paths. More precisely, we formulate a general framework for the prediction problem, propose a class of linear predictors for standard quantities of interest (e.g., averages, totals, differences) and show that linear algebraic methods of subset selection may be used to effectively choose which paths to measure. The performance of the resulting methods are characterized both analytically and numerically. This is joint work with Prof. Eric Kolaczyk and Prof. Mark Crovella of Boston University.