skip to main content
article

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

Published: 01 October 2007 Publication History

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(n2) 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(n2) 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]
{1} Y. Chen, D. Bindel, and R. H. Katz, "Tomography-based overlay network monitoring," in Proc. ACM SIGCOMM Internet Measurement Conf. (IMC), 2003.
[2]
{2} D. G. Andersen, "Resilient overlay networks," in Proc. ACMSOSP, 2001.
[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]
{5} P. Francis, "IDMaps: A global Internet host distance estimation service," IEEE/ACM Trans. Netw., vol. 9, no. 5, pp. 525-540, Oct. 2001.
[6]
{6} Y. Chen, "On the stability of network distance estimation," in ACM SIGMETRICS Performance Evaluation Rev. (PER), Sep. 2002.
[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]
{8} T. Bu, N. Duffield, F. Presti, and D. Towsley, "Network tomography on general topologies," in Proc. ACM SIGMETRICS, 2002.
[9]
{9} V. Padmanabhan, L. Qiu, and H. Wang, "Server-based inference of Internet link lossiness," in Proc. IEEE INFOCOM, 2003.
[10]
{10} D. Rubenstein, J. F. Kurose, and D. F. Towsley, "Detecting shared congestion of flows via end-to-end measurement," ACM Trans. Netw., vol. 10, no. 3, 2002.
[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]
{12} H. C. Ozmutlu, "Managing end-to-end network performance via optimized monitoring strategies," J. Netw. Syst. Manag., vol. 10, no. 1, 2002.
[13]
{13} C. Tang and P. McKinley, "On the cost-quality tradeoff in topology-aware overlay path probing," in IEEE Proc. ICNP, 2003.
[14]
{14} R. Mahajan, N. Spring, D. Wetherall, and T. Anderson, "User-level internet path diagnosis," in Proc. ACMSOSP, 2003.
[15]
{15} K. Anagnostakis, M. Greenwald, and R. Ryger, "Cing: Measuring network-internal delays using only existing infrastructure," in Proc. IEEE INFOCOM, 2003.
[16]
{16} Y. Chen, "Towards a scalable, adaptive and network-aware content distribution network," Ph.D. dissertation, Univ. of California at Berkeley, Berkeley, CA, Nov. 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]
{18} S. Floyd and V. Jacobson, "Random early detection gateways for congestion avoidance," IEEE/ACM Trans. Netw., vol. 1, no. 4, pp. 397-413, Aug. 1993.
[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]
{21} E. Anderson, LAPACK Users' Guide, Society for Industrial and Applied Mathematics, 3rd ed. Philadelphia, PA:, 1999.
[22]
{22} Y. Zhang, "On the constancy of Internet path properties," in Proc. SIGCOMMIMW , 2001.
[23]
{23} J. W. Demmel, Applied Numerical Linear Algebra. Philadelphia, PA: SIAM, 1997.
[24]
{24} H. Tangmunarunkit, "Network topology generators: Degree-based vs structural," in Proc. ACM SIGCOMM, 2002.
[25]
{25} M. Faloutsos, P. Faloutsos, and C. Faloutsos, "On power-law relationship of the Internet topology," in Proc. ACM SIGCOMM, 1999.
[26]
{26} A. Medina, I. Matta, and J. Byers, "On the origin of power laws in Internet topologies," ACM Comput. Commun. Rev., vol. 30, no. 2, Apr. 2000.
[27]
{27} R. Govindan and H. Tangmunarunkit, "Heuristics for Internet map discovery," in Proc. IEEE INFOCOM, 2000.
[28]
{28} N. Spring, R. Mahajan, and D. Wetherall, "Measuring ISP topologies with rocket fuel," in Proc. ACM SIGCOMM, 2002.
[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]
{31} V. Paxon, "End-to-end routing behavior in the Internet," IEEE/ACM Trans. Netw., vol. 5, no. 5, pp. 601-615, Oct. 1997.
[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]
{34} S. Gringeri, R. Egorov, K. Shuaib, A. Lewis, and B. Basch, "Robust compression and transmission of MPEG-4 video," in ACM Multi-Media , 1999.
[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]
{40} V. Paxon, "End-to-end Internet packet dynamics," in Proc. ACM SIGCOMM , 1997.
[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]
{44} Y. Zhao, Y. Chen, and D. Bindel, "Towards deterministic network diagnosis," in Proc. ACM SIGCOMM, 2006.

Cited By

View all
  • (2023)Overlay Routing Over an Uncooperative UnderlayProceedings of the Twenty-fourth International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing10.1145/3565287.3610274(151-160)Online publication date: 23-Oct-2023
  • (2018)Taming Both Predictable and Unpredictable Link Failures for Network TomographyIEEE/ACM Transactions on Networking10.1109/TNET.2018.283414126:3(1460-1473)Online publication date: 1-Jun-2018
  • (2018)A push-pull network coding protocol for live peer-to-peer streamingComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2017.11.007130:C(145-155)Online publication date: 15-Jan-2018
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 15, Issue 5
October 2007
235 pages

Publisher

IEEE Press

Publication History

Published: 01 October 2007
Published in TON Volume 15, Issue 5

Author Tags

  1. dynamics
  2. load balancing
  3. network measurement and monitoring
  4. numerical linear algebra
  5. overlay
  6. scalability

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Overlay Routing Over an Uncooperative UnderlayProceedings of the Twenty-fourth International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing10.1145/3565287.3610274(151-160)Online publication date: 23-Oct-2023
  • (2018)Taming Both Predictable and Unpredictable Link Failures for Network TomographyIEEE/ACM Transactions on Networking10.1109/TNET.2018.283414126:3(1460-1473)Online publication date: 1-Jun-2018
  • (2018)A push-pull network coding protocol for live peer-to-peer streamingComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2017.11.007130:C(145-155)Online publication date: 15-Jan-2018
  • (2018)On the estimation of link delay distributions by cumulant‐based moment matchingInternet Technology Letters10.1002/itl2.111:1Online publication date: 18-Jan-2018
  • (2015)Sparse Recovery With Graph ConstraintsIEEE Transactions on Information Theory10.1109/TIT.2014.237695561:2(1028-1044)Online publication date: 16-Jan-2015
  • (2014)On the maximum number of linearly independent cycles and paths in a networkIEEE/ACM Transactions on Networking10.1109/TNET.2013.229120822:5(1373-1388)Online publication date: 1-Oct-2014
  • (2013)A general scalable and accurate decentralized level monitoring method for large-scale dynamic service provision in hybrid cloudsFuture Generation Computer Systems10.1016/j.future.2012.11.00129:5(1235-1253)Online publication date: 1-Jul-2013
  • (2012)On identifying additive link metrics using linearly independent cycles and pathsIEEE/ACM Transactions on Networking10.1109/TNET.2011.217464820:3(906-916)Online publication date: 1-Jun-2012
  • (2009)On Optimal Placement of the Monitoring Devices on Channels of Communication NetworkProceedings of the International Conference on Computational Science and Its Applications: Part II10.1007/978-3-642-02457-3_40(465-478)Online publication date: 9-Jul-2009
  • (2009)Multi-layer Monitoring of Overlay NetworksProceedings of the 10th International Conference on Passive and Active Network Measurement10.1007/978-3-642-00975-4_8(77-86)Online publication date: 28-Mar-2009

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media