Mathematics – Statistics Theory
Scientific paper
2005-10-02
Mathematics
Statistics Theory
16 pages, 9 figures, single-spaced
Scientific paper
Network service providers and customers are often concerned with aggregate performance measures that span multiple network paths. Unfortunately, forming such network-wide measures can be difficult, due to the issues of scale involved. In particular, the number of paths grows too rapidly with the number of endpoints 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. We cast the problem as one of statistical prediction--in the spirit of the so-called `kriging' problem in spatial statistics--and show that end-to-end network properties may be accurately predicted in many cases using 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. We characterize the performance of the resulting methods, both analytically and numerically. The success of our methods derives from the low effective rank of routing matrices as encountered in practice, which appears to be a new observation in its own right with potentially broad implications on network measurement generally.
Chua David B.
Crovella Mark
Kolaczyk Eric D.
No associations
LandOfFree
Network Kriging does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Network Kriging, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network Kriging will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-612169