On the treeness of internet latency and bandwidth

ABSTRACT

Existing empirical studies of Internet structure and path properties indicate that the Internet is tree-like. This work quantifies the degree to which at least two important Internet measures--latency and bandwidth--approximate tree metrics. We evaluate our ability to model end-to-end measures using tree embeddings by actually building tree representations. In addition to being simple and intuitive models, these trees provide a range of commonly-required functionality beyond serving as an analytical tool.

The contributions of our study are twofold. First, we investigate the ability to portray the inherent hierarchical structure of the Internet using the most pure and compact topology, trees. Second, we evaluate the ability of our compact representation to facilitate many natural tasks, such as the selection of servers with short latency or high bandwidth from a client. Experiments show that these tasks can be done with high degree of success and modest overhead.

REFERENCES

• 1: Ittai Abraham , Mahesh Balakrishnan , Fabian Kuhn , Dahlia Malkhi , Venugopalan Ramasubramanian , Kunal Talwar, Reconstructing approximate tree metrics, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281110]
• 2: Ittai Abraham , Yair Bartal , Ofer Neiman, Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.502-511, January 07-09, 2007, New Orleans, Louisiana
• 3: S. Banerjee, C. Kommareddy, and B. Bhattacharjee. Scalable peer finding on the Internet. In Proc. of the Global Internet Symposium, Taipei, Taiwan, Nov. 2002.
• 4: A. Barabasi and R. Albert. Emergence of Scaling in Random Networks. Science, 8:509--512, Oct. 1999.
• 5: P. Buneman. A Note on Metric Properties of Trees. Journal of Combinatorial Theory, 17:48--50, 1974.
• 6: Yang-hua Chu , Sanjay G. Rao , Hui Zhang, A case for end system multicast (keynote address), Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.1-12, June 18-21, 2000, Santa Clara, California, United States
• 7: Manuel Costa , Miguel Castro , Antony Rowstron , Peter Key, PIC: Practical Internet Coordinates for Distance Estimation, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.178-187, March 24-26, 2004
• 8: Frank Dabek , Russ Cox , Frans Kaashoek , Robert Morris, Vivaldi: a decentralized network coordinate system, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 9: Marcel Dischinger , Andreas Haeberlen , Krishna P. Gummadi , Stefan Saroiu, Characterizing residential broadband networks, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA [doi>10.1145/1298306.1298313]
• 10: 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
• 11: 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]
• 12: Michael J. Freedman , Karthik Lakshminarayanan , David Mazières, OASIS: anycast for any service, Proceedings of the 3rd conference on Networked Systems Design & Implementation, p.10-10, May 08-10, 2006, San Jose, CA
• 13: M. Freedman and D. Mazières. Sloppy Hashing and Self-Organizing Clusters. In Proc. of International Workshop on Peer-to-Peer Systems (IPTPS), Berkeley, CA, Feb. 2003.
• 14: Krishna P. Gummadi , Stefan Saroiu , Steven D. Gribble, King: estimating latency between arbitrary internet end hosts, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637203]
• 15: Anupam Gupta, Steiner points in tree metrics don't (really) help, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.220-227, January 07-09, 2001, Washington, D.C., United States
• 16: N. Hu, L.E. Li, Z.M. Mao, P. Steenkiste, and J. Wang. A Measurement Study of Internet Bottlenecks. In Proc. of INFOCOM Conference, Miami, FL, Mar. 2005.
• 17: P. Key, L. Massoulie, and D.-C. Tomozei. Non-Metric Coordinates for Predicting Network Proximity. In Proc. of the IEEE INFOCOM Conference, Phoenix, AZ, Apr. 2008.
• 18: C. Kommareddy , B. Bhattacharjee, Finding Close Friends on the Internet, Proceedings of the Ninth International Conference on Network Protocols, p.301, November 11-14, 2001
• 19: E. Lebhar, P. Fraigniaud, and L. Viennot. The Inframetric Model for the Internet. In Proc. of IEEE INFOCOM Conference, Apr. 2008.
• 20: Sanghwan Lee , Zhi-Li Zhang , Sambit Sahu , Debanjan Saha, On suitability of Euclidean embedding of internet hosts, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 26-30, 2006, Saint Malo, France
• 21: Li-wei Lehman , Steven Lerman, PCoord: Network Position Estimation Using Peer-to-Peer Measurements, Proceedings of the Network Computing and Applications, Third IEEE International Symposium, p.15-24, August 30-September 01, 2004
• 22: Hyuk Lim , Jennifer C. Hou , Chong-Ho Choi, Constructing internet coordinate system based on delay measurement, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948222]
• 23: Eng Keong Lua , Timothy Griffin , Marcelo Pias , Han Zheng , Jon Crowcroft, On the accuracy of embeddings for internet coordinate systems, Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement, p.11-11, October 19-21, 2005, Berkeley, CA
• 24: H.V. Madhyastha, E.K. Bassett, T. Anderson, A. Krishnamurthy, and A. Venkataramani. iPlane Nano: Path Prediction for Peer-to-Peer Applications. In Proc. of the Usenix Conference on Networked Systems Design and Implementation (NSDI), Apr. 2009.
• 25: Harsha Madhyastha , Tomas Isdal , Michael Piatek , Colin Dixon , Thomas Anderson , Arvind Krishnamurthy , Arun Venkataramani, iPlane: an information plane for distributed services, Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation, p.26-26, November 06-08, 2006, Seattle, WA
• 26: Yun Mao , Lawrence K. Saul, Modeling distances in large-scale networks by matrix factorization, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028827]
• 27: E. Ng and H. Zhang. Predicting Internet Network Distance with Coordinates-based Approaches. In Proc. of the INFOCOM Conference, New York, NY, June 2002.
• 28: 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]
• 29: M. Pias, J. Crowcroft, S. Wilbur, S. Bhatti, and T. Harris. Lighthouses for Scalable Distributed Location. In Proc. of International Workshop on Peer-to-Peer Systems (IPTPS), Berkeley, CA, Feb. 2003.
• 30: R. Prasad, M. Murray, C. Dovloris, and kc Claffy. Lower Bounds on the Distortion of Embedding Finite Metric Spaces in Graphs. Discrete & Computational Geometry, 19, 1998.
• 31: Y. Rabinovich and R. Raz. Lower Bounds on the Distortion of Embedding Finite Metric Spaces in Graphs. Discrete & Computational Geometry, 19, 1998.
• 32: Robbert Van Renesse , Kenneth P. Birman , Werner Vogels, Astrolabe: A robust and scalable technology for distributed system monitoring, management, and data mining, ACM Transactions on Computer Systems (TOCS), v.21 n.2, p.164-206, May 2003 [doi>10.1145/762483.762485]
• 33: V. Ribeiro, R. Riedi, R. Baraniuk, J. Navratil, and L. Cottrell. pathChirp: Efficient Avalable Bandwidth Estimation for Network Paths. In Proc. of Passive and Active Measurement Workshop, San Diego, CA, Apr. 2003.
• 34: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 35: Yuval Shavitt , Tomer Tankel, Big-bang simulation for embedding network distances in Euclidean space, IEEE/ACM Transactions on Networking (TON), v.12 n.6, p.993-1006, December 2004 [doi>10.1109/TNET.2004.838597]
• 36: Yuval Shavitt , Tomer Tankel, Hyperbolic embedding of internet graph for distance estimation and overlay construction, IEEE/ACM Transactions on Networking (TON), v.16 n.1, p.25-36, February 2008 [doi>10.1109/TNET.2007.899021]
• 37: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 38: L. Subramanian, S. Agarwal, J. Rexford, and R. Katz. Characterzing the Internet Hierarchy from Multiple Vantage Points. In Proc. of the Infocom Conference, New York, NY, June 2002.
• 39: Liying Tang , Mark Crovella, Virtual landmarks for the internet, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948223]
• 40: L. Tauro, C. Palmer, G. Siganos, and M. Faloutsos. A Simple Conceptual Model for the Internet Topology. In Proc. of Global Telecommunications Conference (GLOBECOM), San Antonio, TX, Nov. 2001.
• 41: Bernard Wong , Aleksandrs Slivkins , Emin Gün Sirer, Meridian: a lightweight network location service without virtual coordinates, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 42: Praveen Yalagandula , Mike Dahlin, A scalable distributed information management system, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 43: 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]
• 44: H. Zheng, E.K. Lua, M. Pias, and T. Griffin. Internet routing policies and round-trip-times. In Proceedings of the Passive Active Measurement, pages 236--250, 2005.
• 45: Shelley Q. Zhuang , Ben Y. Zhao , Anthony D. Joseph , Randy H. Katz , John D. Kubiatowicz, Bayeux: an architecture for scalable and fault-tolerant wide-area data dissemination, Proceedings of the 11th international workshop on Network and operating systems support for digital audio and video, p.11-20, January 2001, Port Jefferson, New York, United States [doi>10.1145/378344.378347]
• 46: Akamai SureRoute. http://www.akamai.com/dl/feature_sheets/fs_edgesuite_sureroute.pdf.
• 47: Meridian: A Lighweight Approach to Network Positioning. http://www.cs.cornell.edu/People/egs/meridian.
• 48: PlanetLab: An Open Platform for Developing, Deploying, and Accessing Planetary-Scale Services. http://www.planet-lab.org.
• 49: Network Coordinate Research at Harvard. http://www.eecs.harvard.edu/syrah/nc/, 2006.
• 50: The Gnutella 0.4 Protocol Specification. http://dss.clip2.com/GnutellaProtocol0.4.pdf, 2000.
• 51: S³: Scalable Sensing Service. http://networking.hpl.hp.com/s-cube.
• 52: University of Oregon Route Views Project. http://www.routeviews.org.
• 53: All-Sites-Pings for PlanetLab. http://ping.ececs.uc.edu/ping/, 2006.

INDEX TERMS

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

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

Keywords:
bandwidth, internet topology, latency, sequoia, tree embedding