Efficient Monitoring of End-to-End Network Properties

Authors: David B. Chua, Eric D. Kolaczyk, Mark Crovella

Complete Citation

David B. Chua, Eric D. Kolaczyk, and Mark Crovella. Efficient Monitoring of End-to-End Network Properties. INFOCOM 2005. Volume: 3, On page(s): 1701- 1711 vol. 3 Digital Object Identifier: 10.1109/INFCOM.2005.1498451

Abstract

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 complete network-wide measurement quickly becomes infeasible. More efficient measurement strategies are therefore needed. Previous work, examining this problem from a linear algebraic perspective, has shown that for exact recovery of complete 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 paper we ask whether measurement strategies of even greater efficiency are possible. We recast the problem as one of statistical prediction and show that end-to-end network properties may be accurately predicted in many cases using a significantly smaller set of carefully chosen paths than needed for exact recovery. 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 which paths to measure. We explore the accuracy of the resulting methods both analytically and numerically, in the context of real network topologies of varying size. The feasibility of our methods derives from the low effective rank of routing matrices as encountered in practice, which appears to be a new observation of interest in its own right. The resulting framework, which is quite general, appears to hold promise for studying and improving the efficiency of monitoring of end-to-end-network properties.

Annotations

This paper talks about how to recover the end-to-end path properties in one network (for most paths rather than the complete set of end-to-edn paths) efficiently. By using statistical prediction, this paper shows that end-to-end network properties may be accurately predicted using a significantly smaller set of carefully chosen paths than needed for exact recovery.

• Map of Abilene:
  

• Two paths to recover 70% meaningful information of the above Abilene network:
  

Related Work

• Y. Chen, D. Bindel, and R. H. Katz, “Tomography-based overlay network monitoring,” in Proceedings of the 2003 ACM SIGCOMM conference on Internet measurement. ACM Press, 2003, pp. 216–231.

Based on a linear algebraic analysis of routing matrices, the paper has shown that it is possible to reduce the number of end-to-end measurements to approximately the number of “virtual links” (identifiable link subsets and yet still recover the complete set of end-to-end path properties exactly.

• H.X. Nguyen and P. Thiran, "Active measurement for multiple link failures diagnosis in ip networks," in Proceedings of Passive and Active Measurement Workshop (PAM), April 2004.

This paper uses active probing to detect and locate link failures, under the assumption that several links can fail at one time. To detect failures, the path that each probe actually follows is compared with the path that the probe should follow according to the current network topology information. If the two paths are different, at least one link in the path determined by the current topology has failed.

-- YingxinJiang - 17 Oct 2007