Virtual landmarks for the internet

ABSTRACT

Internet coordinate schemes have been proposed as a method for estimating minimum round trip time between hosts without direct measurement. In such a scheme, each host is assigned a set of coordinates, and Euclidean distance is used to form the desired estimate. Two key questions are: How accurate are coordinate schemes across the Internet as a whole? And: are coordinate assignment schemes fast enough, and scalable enough, for large scale use? In this paper we make contributions toward answering both those questions. Whereas the coordinate assignment problem has in the past been approached by nonlinear optimization, we develop a faster method based on dimensionality reduction of the Lipschitz embedding. We show that this method is reasonably accurate, even when applied to measurements spanning the Internet, and that it naturally leads to a scalable measurement strategy based on the notion of virtual landmarks.

REFERENCES

• 1: The NLANR active measurement project. http://amp.nlanr.net/active/.
• 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: V. Athitsos and S. Sclaroff. Estimating 3D hand pose from a cluttered image. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, June 2003.
• 4: L. M. Blumenthal. Theory and applications of distance geometry. Chelsea Pub. Co., Bronx, N.Y., second edition, 1970.
• 5: J. Bourgain. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math., 52(1--2):46--52, 1985.
• 6: G. Brown. Internet address space clustering for intelligent route control. Submitted for publication, 2003.
• 7: 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]
• 8: 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]
• 9: P. Francis, S. Jamin, V. Paxson, L. Zhang, D. F. Gryniewicz, and Y. Jin. An architecture for a global Internet host distance estimation service. In IEEE INFOCOM 1999, pages 210--217, New York, NY, March 1999. IEEE.
• 10: 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]
• 11: Gísli R. Hjaltason , Hanan Samet, Properties of Embedding Methods for Similarity Searching in Metric Spaces, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.5, p.530-549, May 2003 [doi>10.1109/TPAMI.2003.1195989]
• 12: W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in modern analysis and probability, pages 189--206. Amer. Math. Soc., 1984.
• 13: A. Lakhina, J. W. Byers, M. Crovella, and I. Matta. On the geographic location of internet resources. IEEE Journal on Selected Areas in Communications, Special Issue on Internet and WWW Measurement, Mapping, and Modeling, 2003.
• 14: 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]
• 15: N. Linial. Finite metric spaces --- combinatorics, geometry and algorithms. In Proceedings of the International Congress of Mathematicians III, pages 573--586, 2002.
• 16: N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic implications. Combinatorica, 15:215--245, 1995.
• 17: E. Ng and H. Zhang. Predicting Internet network distance with coordinates-based approaches. In Proceedings of Infocom, 2002.
• 18: M. Pias, J. Crowcroft, S. Wilbur, S. Bhatti, and T. Harris. Lighthouses for scalable distributed location. In Second International Workshop on Peer-to-Peer Systems (IPTPS '03), Feb 2003.
• 19: William H. Press , Brian P. Flannery , Saul A. Teukolsky , William T. Vetterling, Numerical recipes in C: the art of scientific computing, Cambridge University Press, New York, NY, 1988
• 20: RouteViews. http://www.routeviews.org.
• 21: The skitter project. http://www.caida.org/tools/measurement/skitter/.
• 22: Sockeye Networks. http://www.sockeye.com/.
• 23: G. Strang. Linear Algebra and Its Applications. Harcourt, Inc., 1988.
• 24: H. Tangmunarunkit, R. Govindan, S. Shenker, and D. Estrin. The impact of routing policy on Internet paths. In Proceedings of INFOCOM 2001, pages 736--742, 2001.
• 25: T. Tankel and Y. Shavitt. Big-bang simulation for embedding network distances in Euclidean space. In Proceedings of IEEE INFOCOM 2003, April 2003.
• 26: W. S. Torgerson. Multidimensional scaling: I. theory and method. Psychometrika, 17:401--419, 1952.
• 27: J. Vleugels and R. C. Veltkamp. Efficient image retrieval through vantage objects. Pattern Recognition, 35(1):69--80, Jan 2002.
• 28: Qunfeng Dong , Zhijun Wu, A linear-time algorithm for solving the molecular distance geometry problem with exact inter-atomic distances, Journal of Global Optimization, v.22 n.1-4, p.365-375, January 2002
• 29: F. W. Young and R. M. Hamer. Multidimensional Scaling: History, Theory, and Applications. Lawrence Erlbaum Associates, Hilldale, N.J., 1987.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Algorithms, Measurement, Performance

Keywords:
network coordinates, network distance, principal component analysis