NetQuest: a flexible framework for large-scale network measurement

ABSTRACT

In this paper, we present NetQuest, a flexible framework for large-scale network measurement. We apply Bayesian experimental design to select active measurements that maximize the amount of information we gain about the network path properties subject to given resource constraints. We then apply network inference techniques to reconstruct the properties of interest based on the partial, indirect observations we get through these measurements.

By casting network measurement in a general Bayesian decision theoretic framework, we achieve flexibility. Our framework can support a variety of design requirements, including i) differentiated design for providing better resolution to certain parts of the network; ii) augmented design for conducting additional measurements given existing observations; and iii) joint design for supporting multiple users who are interested in different parts of the network. Our framework is also scalable and can design measurement experiments that span thousands of routers and end hosts.

We develop a toolkit that realizes the framework on PlanetLab. We conduct extensive evaluation using both real traces and synthetic data. Our results show that the approach can accurately estimate network-wide and individual path properties by only monitoring within 2%-10% of paths. We also demonstrate its effectiveness in providing differentiated monitoring, supporting continuous monitoring, and satisfying the requirements of multiple users.

REFERENCES

• 1: K. Chaloner and I. Verdinelli, "Bayesian experimental design: A review," Statistical Science vol. 10, pp. 273-304, 1995 [Online]. Available: http://www.citeseer.ist.psu.edu/chaloner95bayesian.html
• 2: Yan Chen , David Bindel , Randy H. Katz, Tomography-based overlay network monitoring, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948233]
• 3: Yan Chen , David Bindel , Hanhee Song , Randy H. Katz, An algebraic approach to practical and scalable overlay network monitoring, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 4: D. B. Chua, E. D. Kolaczyk, and M. Crovella, "Efficient monitoring of end-to-end network properties," in Proc. IEEE INFOCOM, 2004, pp. 1701-1711.
• 5: David Chua , Eric D. Kolaczyk , Mark Crovella, A statistical framework for efficient monitoring of end-to-end network properties, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 6: M. A. Clyde, "Experimental design: A Bayesian perspective," International Encyclopedia of Social and Behavioral Sciences, Apr. 2001.
• 7: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 8: T. Davis, "LDL: A Sparse LDL Factorization and Solve Package (Version 1.2)," 2005 [Online]. Available: http://www.cise.ufl.edu/research/ sparse/ldl/
• 9: D. Donoho, "For most large underdetermined systems of linear equations, the minimal 11-norm near-solution approximates the sparsest near-solution," Stanford Univ. [Online]. Available: http://www-stat.stanford.edu/~donoho/Reports/2004/1110approx.pdf
• 10: V. Fedorov, Theory of Optimal Experiments. New York: Academic, 1972.
• 11: Gene H. Golub , Virginia C. Klema , Gilbert W. Stewart, Rank degeneracy and least squares problems, Stanford University, Stanford, CA, 1976
• 12: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 13: Per Christian Hansen, Rank-deficient and discrete ill-posed problems: numerical aspects of linear inversion, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 14: B. Jones, D. Lin, and C. Nachtsheim, "Bayesian D-optimal supersaturated designs," 2004, submitted.
• 15: D. V. Lindley, Bayesian Statistics--A Review. Philadelphia, PA: SIAM, 1972.
• 16: Ratul Mahajan , Neil Spring , David Wetherall , Tom Anderson, Inferring link weights using end-to-end measurements, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637237]
• 17: A. Medina, A. Lakhina, I. Matta, and J. Byers, Boston University Representative Internet Topology Generator (BRITE). [Online]. Available: http://www.cs.bu.edu/brite/
• 18: A. Medina , N. Taft , K. Salamatian , S. Bhattacharyya , C. Diot, Traffic matrix estimation: existing techniques and new directions, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 19: A. J. Miller and N. K. Nguyen, "A Fedorov exchange algorithm for D-optimal design," Applied Statistics, 1994.
• 20: Toby J. Mitchell, An algorithm for the construction of “D-optimal” experimental designs, Technometrics, v.42 n.1, p.48-54, Feb. 2000 [doi>10.2307/1271431]
• 21: Erich M. Nahum , Marcel-Catalin Rosu , Srinivasan Seshan , Jussara Almeida, The effects of wide-area conditions on WWW server performance, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.257-267, June 2001, Cambridge, Massachusetts, United States
• 22: Nam-Ky Nguyen , Alan J. Miller, A review of some exchange algorithms for constructing discrete D-optimal designs, Computational Statistics & Data Analysis, v.14 n.4, p.489-498, Nov. 1992 [doi>10.1016/0167-9473(92)90064-M]
• 23: V. N. Padmanabhan, L. Qiu, and H. Wang, "Server-based inference of Internet link lossiness," in Proc. IEEE INFOCOM, Mar. 2003, 11 pp.
• 24: M. Saunders, "PDCO: Primal-dual interior method for convex objectives," Stanford Univ., Palo Alto, CA, 2003 [Online]. Available: http:// www.stanford.edu/group/SOL/software/pdco.html
• 25: Han Hee Song , Lili Qiu , Yin Zhang, NetQuest: a flexible framework for large-scale network measurement, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 26-30, 2006, Saint Malo, France
• 26: Neil Spring , Ratul Mahajan , David Wetherall, Measuring ISP topologies with rocketfuel, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 27: N. Spring, R. Mahajan, D. Wetherall, and H. Hagerstrom, "Rocketfuel: An ISP topology mapping engine," [Online]. Available: http://www.cs. washigton.edu/research/networking/rocketfuel/
• 28: N. Spring, D. Wetherall, and T. Anderson, "Scriptroute: A facility for distributed internet measurement," in Proc. USITS, Mar. 2003.
• 29: Yin Zhang , Zihui Ge , Albert Greenberg , Matthew Roughan, Network anomography, Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement, p.30-30, October 19-21, 2005, Berkeley, CA
• 30: Yin Zhang , Matthew Roughan , Nick Duffield , Albert Greenberg, Fast accurate computation of large-scale IP traffic matrices from link loads, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 31: Yin Zhang , Matthew Roughan , Carsten Lund , David Donoho, An information-theoretic approach to traffic matrix estimation, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863990]
• 32: Yao Zhao , Yan Chen , David Bindel, Towards unbiased end-to-end network diagnosis, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques; Performance attributes

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo); Experimental design

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance

Keywords:
Bayesian experimental design, network inference, network measurement, network tomography