Algebra-based scalable overlay network monitoring: algorithms, evaluation, and applications

ABSTRACT

Overlay network monitoring enables distributed Internet applications to detect and recover from path outages and periods of degraded performance within seconds. For an overlay network with n end hosts, existing systems either require O(n²) measurements, and thus lack scalability, or can only estimate the latency but not congestion or failures. Our earlier extended abstract [Y. Chen, D. Bindel, and R. H. Katz, "Tomography-based overlay network monitoring," Proceedings of the ACM SIGCOMM Internet Measurement Conference (IMC), 2003] briefly proposes an algebraic approach that selectively monitors k linearly independent paths that can fully describe all the O(n²) paths. The loss rates and latency of these k paths can be used to estimate the loss rates and latency of all other paths. Our scheme only assumes knowledge of the underlying IP topology, with links dynamically varying between lossy and normal. In this paper, we improve, implement, and extensively evaluate such a monitoring system. We further make the following contributions: i) scalability analysis indicating that for reasonably large n (e.g., 100), the growth of k is bounded as O(n log n), ii) efficient adaptation algorithms for topology changes, such as the addition or removal of end hosts and routing changes, iii) measurement load balancing schemes, iv) topology measurement error handling, and v) design and implementation of an adaptive streaming media system as a representative application. Both simulation and Internet experiments demonstrate we obtain highly accurate path loss rate estimation while adapting to topology changes within seconds and handling topology errors.

REFERENCES

• 1: 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]
• 2: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 3: [3] T. S. E. Ng and H. Zhang, "Predicting Internet network distance with coordinates-based approaches," in Proc. IEEE INFOCOM, 2002.
• 4: [4] S. Ratnasamy, "Topologically-aware overlay construction and server selection," in Proc. IEEE INFOCOM, 2002.
• 5: Paul Francis , Sugih Jamin , Cheng Jin , Yixin Jin , Danny Raz , Yuval Shavitt , Lixia Zhang, IDMaps: a global internet host distance estimation service, IEEE/ACM Transactions on Networking (TON), v.9 n.5, p.525-540, October 2001 [doi>10.1109/90.958323]
• 6: Yan Chen , Khian Hao Lim , Randy H. Katz , Chris Overton, On the stability of network distance estimation, ACM SIGMETRICS Performance Evaluation Review, v.30 n.2, September 2002 [doi>10.1145/588160.588164]
• 7: [7] M. Coates, A. Hero, R. Nowak, and B. Yu, "Internet tomography," IEEE Signal Process. Mag., vol. 19, no. 3, pp. 47-65, 2002.
• 8: Tian Bu , Nick Duffield , Francesco Lo Presti , Don Towsley, Network tomography on general topologies, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 9: [9] V. Padmanabhan, L. Qiu, and H. Wang, "Server-based inference of Internet link lossiness," in Proc. IEEE INFOCOM, 2003.
• 10: Dan Rubenstein , Jim Kurose , Don Towsley, Detecting shared congestion of flows via end-to-end measurement, IEEE/ACM Transactions on Networking (TON), v.10 n.3, p.381-395, June 2002 [doi>10.1109/TNET.2002.1012369]
• 11: [11] Y. Shavitt, X. Sun, A. Wool, and B. Yener, "Computing the unmeasured: An algebraic approach to Internet mapping," in Proc. IEEE INFOCOM , 2001.
• 12: H. Cenk Ozmutlu , Natarajan Gautam , Russell Barton, Managing End-to-End Network Performance via Optimized Monitoring Strategies, Journal of Network and Systems Management, v.10 n.1, p.107-126, March 2002 [doi>10.1023/A:1014457726450 ]
• 13: Chiping Tang , Philip K. McKinley, On the Cost-Quality Tradeoff in Topology-Aware Overlay Path Probing, Proceedings of the 11th IEEE International Conference on Network Protocols, p.268, November 04-07, 2003
• 14: Ratul Mahajan , Neil Spring , David Wetherall , Thomas Anderson, User-level internet path diagnosis, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 15: [15] K. Anagnostakis, M. Greenwald, and R. Ryger, "Cing: Measuring network-internal delays using only existing infrastructure," in Proc. IEEE INFOCOM, 2003.
• 16: Yan Chen , Randy H. Katz, Towards a scalable, adaptive and network-aware content distribution network, University of California, Berkeley, 2003
• 17: [17] R. Caceres, N. Duffield, J. Horowitz, and D. Towsley, "Multicast-based inference of network-internal loss characteristics," IEEE Trans. Inf. Theory, vol. 45, no. 7, pp. 2462-2480, Nov. 1999.
• 18: Sally Floyd , Van Jacobson, Random early detection gateways for congestion avoidance, IEEE/ACM Transactions on Networking (TON), v.1 n.4, p.397-413, Aug. 1993 [doi>10.1109/90.251892]
• 19: [19] N. Duffield, "Multicast-based loss inference with missing data," IEEE J. Sel. Areas Commun., vol. 20, no. 4, 2002.
• 20: [20] G. H. Golub and C. F. Van Loan, Matrix Computations. Baltimore, MD: The Johns Hopkins Univ. Press, 1989.
• 21: E. Anderson , Z. Bai , C. Bischof , L. S. Blackford , J. Demmel , Jack J. Dongarra , J. Du Croz , S. Hammarling , A. Greenbaum , A. McKenney , D. Sorensen, LAPACK Users' guide (third ed.), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 22: Yin Zhang , Nick Duffield, On the constancy of internet path properties, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505228]
• 23: James W. Demmel, Applied numerical linear algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
• 24: Hongsuda Tangmunarunkit , Ramesh Govindan , Sugih Jamin , Scott Shenker , Walter Willinger, Network topology generators: degree-based vs. structural, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 25: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 26: Alberto Medina , Ibrahim Matta , John Byers, On the origin of power laws in Internet topologies, ACM SIGCOMM Computer Communication Review, v.30 n.2, April 2000 [doi>10.1145/505680.505683]
• 27: [27] R. Govindan and H. Tangmunarunkit, "Heuristics for Internet map discovery," in Proc. IEEE INFOCOM, 2000.
• 28: 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
• 29: [29] L. Subrmanian, S. Agarwal, J. Rexford, and R. H. Katz, "Characterizing the Internet hierarchy from multiple vantage points," in Proc. IEEE INFOCOM, 2002.
• 30: [30] G. W. Stewart, Matrix Algorithms: Basic Decompositions. Philadelphia, PA: SIAM, 1998.
• 31: Vern Paxson, End-to-end routing behavior in the Internet, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.601-615, Oct. 1997 [doi>10.1109/90.649563]
• 32: [32] Y. Zhang, V. Paxson, and S. Shenker, "The stationarity of internet path properties: Routing, loss, and throughput," ACIRI Tech. Rep., May 2000.
• 33: [33] T. Wiegand, "Overview of the H.264/AVC video coding standard," IEEE Trans. Circuits Syst. Video Technol., vol. 13, no. 7, pp. 560-576, 2003.
• 34: Steven Gringeri , Roman Egorov , Khaled Shuaib , Arianne Lewis , Bert Basch, Robust compression and transmission of MPEG-4 video, Proceedings of the seventh ACM international conference on Multimedia (Part 1), p.113-120, October 30-November 05, 1999, Orlando, Florida, United States [doi>10.1145/319463.319478]
• 35: [35] Winamp, [Online]. Available: http://www.winamp.com, Nullsoft.
• 36: [36] Shoutcast, [Online]. Available: http://www.shoutcast.com, Nullsoft.
• 37: [37] PlanetLab, [Online]. Available: http://www.planet-lab.org.
• 38: [38] PacketShaper: Bandwidth Control and IP Management, [Online]. Available: http://www.bandwidth-management.org, Workgroup Solutions.
• 39: [39] Pre-processing and Encoding: Making the Most of Your Bandwidth, [Online]. Available: http://service.real.corn/learnnav/ppthl.html, RealOne Player.
• 40: Vern Paxson, End-to-end Internet packet dynamics, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.139-152, September 14-18, 1997, Cannes, France
• 41: [41] R. Barrett, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd ed. Philadelphia, PA: SIAM, 1994.
• 42: [42] N. Spring, D. Wetherall, and T. Anderson, "Scriptroute: A facility for distributed Internet measurement," in Proc. USITS, 2003.
• 43: [43] D. B. Chua, E. D. Kolaczyk, and M. Crovella, "Efficient monitoring of end-to-end network properties," in Proc. IEEE INFOCOM, 2005.
• 44: Yao Zhao , Yan Chen , David Bindel, Towards deterministic network diagnosis, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 26-30, 2006, Saint Malo, France

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network monitoring

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques; Performance attributes

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Design, Management, Measurement, Performance

Keywords:
dynamics, load balancing, network measurement and monitoring, numerical linear algebra, overlay, scalability