Hyuk Lim
ABSTRACT
In this paper, we consider the problem of how to represent the locations of Internet hosts in a Cartesian coordinate system to facilitate estimate of the network distance between two arbitrary Internet hosts. We envision an infrastructure that consists of beacon nodes and provides the service of estimating network distance between two hosts without direct delay measurement. We show that the principal component analysis (PCA) technique can effectively extract topological information from delay measurements between beacon hosts. Based on PCA, we devise a transformation method that projects the distance data space into a new coordinate system of (much) smaller dimensions. The transformation retains as much topological information as possible and yet enables end hosts to easily determine their locations in the coordinate system. The resulting new coordinate system is termed as the Internet Coordinate System (ICS). As compared to existing work (e.g., IDMaps [1] and GNP [2]), ICS incurs smaller computation overhead in calculating the coordinates of hosts and smaller measurement overhead (required for end hosts to measure their distances to beacon hosts). Finally, we show via experimentation with real-life data sets that ICS is robust and accurate, regardless of the number of beacon nodes (as long as it exceeds certain threshold) and the complexity of network topology.
- 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 Proceedings of IEEE Infocom, 1999.Google Scholar
- E. Ng and H. Zhang, "Predicting Internet network distance with coordinates-based approaches," in Proceedings of Infocom, 2002.Google Scholar
- S. Hotz, Routing information organization to support scalable interdomain routing with heterogeneous path requirements, Ph.d. thesis, Univ. of Southern California, 1994.Google Scholar
- J. D. Guyton and M. F. Schwartz, "Locating nearby copies of replicated Internet servers," in Proceedings of ACM Sigcomm, 1995. Google ScholarDigital Library
- L. Tang and M. Crovella, "Virtual landmarks for the Internet," in Proceedings of ACM Internet Measurement Conference, 2003. Google ScholarDigital Library
- T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, MIT Press, 1990. Google ScholarDigital Library
- S. Ratnasamy, M. Handley, R. Karp, and S. Shenker, "Topologically-Aware overlay construction and server selection," in Proceedings of Infocom, 2002.Google Scholar
- J. A. Nelder and R. Mead, "A simplex method for function minimization," Computer Journal, vol. 7, pp. 308--313, 1965.Google ScholarCross Ref
- I. T. Jolliffe, Principal component analysis, New York: Springer-Verlag, 1986.Google Scholar
- B. Noble and J. W. Daniel, Applied Linear Algebra, Prentice Hall, 1988.Google Scholar
- K. Y. Yeung and W. L. Ruzzo, "Principal component analysis for clustering gene expression data," Bioinformatics, vol. 17, no. 9, pp. 763--774, 2001.Google ScholarCross Ref
- C. Ding, X. He, H. Zha, and H. Simon, "Adaptive dimension reduction for clustering high dimensional data," in Proceedings of the 2nd IEEE Int'l Conf. Data Mining, 2002, pp. 147--154. Google ScholarDigital Library
- T. P. Minka, "Automatic choice of dimensionality for PCA," in Technical report 514, MIT Media Laboratory, 2000.Google Scholar
- V. Paxson, "End-to-end routing behavior in the Internet," in Proceedings of SIGCOMM '96, August 1996. Google ScholarDigital Library
- National laboratory for applied~network research, "Active measurement project (AMP)," http://watt.nlanr.net/.Google Scholar
- A. Jain and R. C. Dubes, Algorithms for clustering data, Prentice Hall, 1988. Google ScholarDigital Library
- E. W. Zegura, K. Calvert, and S. Bhattacharjee, "How to model an Internetwork," in Proceedings of IEEE Infocom, 1996.Google Scholar
- J. Fall and K. Varadhan, "ns manual," http://www.isi.edu/nsnam/ns/ns-documentation, 2001.Google Scholar
Index Terms
- Constructing internet coordinate system based on delay measurement
Recommendations
Virtual landmarks for the internet
IMC '03: Proceedings of the 3rd ACM SIGCOMM conference on Internet measurementInternet 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 ...
Constructing internet coordinate system based on delay measurement
In this paper, we consider the problem of how to represent the locations of Internet hosts in a Cartesian coordinate system to facilitate estimation of network distances among arbitrary Internet hosts. We envision an infrastructure that consists of ...
Implementation of Coordinate Transformation System and Research on Related Problems
ICETCE '12: Proceedings of the 2012 Second International Conference on Electric Technology and Civil EngineeringAlong with the development of science and surveying technology, different countries need to establish a variety of coordinate systems in different periods, and generating a lot of geo spatial information data based on different coordinates. In this paper,...
Comments