Constructing Internet coordinate system based on delay measurement

Abstract

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 beacon nodes and provides the service of estimating network distance between pairs of 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 raw distance 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 determine their coordinates 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 and GNP), 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 experiments with both real-life and synthetic data sets that ICS makes robust and accurate estimates of network distances, incurs little computational overhead, and its performance is not susceptible to the number of beacon nodes (as long as it exceeds a certain threshold) and the network topology.