This paper introduces PIC, a practical coordinate-based mechanism to estimate Internet network distance (i.e., round-trip delay or network hops). Network distance estimation is important in many applications, for example, network-aware overlay construction and server selection. There are several proposals for distance estimation in the Internet but they all suffer from problems that limit their benefit. Most rely on a small set of infrastructure nodes that are a single point of failure and limit scalability. Others use sets of peers to compute coordinates but these coordinates can be arbitrarily wrong if one of these peers is malicious. While it may be reasonable to secure a small set of infrastructure nodes, it is unreasonable to secure all peers. PIC addresses these problems: it does not rely on infrastructure nodes and it can compute accurate coordinates even when some peers are malicious. We present PIC's design, experimental evaluation, and an application to network-aware overlay construction and maintenance. PIC maps each node to a point in a -dimensional Euclidean space. When a node Ò joins the system, it computes the coordinates of its corresponding point. It probes the network distance to each element of a set of landmarks, Ä, where Ä must have at least · ½ members. Then it obtains the coordinates of each landmark, and uses a multidimensional global optimization algorithm (e.g., Simplex Downhill [16]) to compute its coordinates such that the errors in the Ä predicted distances between Ò and each node in Ä are minimized. The errors are computed using the measured and estimated distances. The probe could use ICMP, application-level round-trip time, or number of IP hops. This is similar to GNP [17] but GNP uses a fixed set Ä for all the nodes that join the system. In PIC, the joining node can pick any node whose coordinates have already been computed to be a landmark. Let
In REF , the distance between two nodes in the Internet is estimated by iteratively minimizing a potential energy function.
PIC: practical Internet coordinates for distance estimation
24th International Conference on Distributed Computing Systems, 2004. Proceedings.
24th International Conference on Distributed Computing Systems, 2004. Proceedings.
Computer Science