Massachusetts Institute of Technology
Cambridge, MA
Email: lilehman@mit.edu
Title: “PCoord: A Decentralized Network Coordinate System for Internet Distance Prediction”
Author: Li-wei Lehman
Advisor: Dr. Steven Lerman, former Director of Project Athena and Chair of MIT Faculty, Director of Center for Educational Computing Initiatives at MIT.
Committee: Dr. Hari Balakrishnan and Dr. Kevin Amaratunga
Abstract: Ph.D. thesis develops a decentralized network coordinate system PCoord for Internet distance prediction. In PCoord, the network is modeled as a D-dimensional geometric space. Each host computes its coordinates in this geometric space to characterize its network location. Network latency between two end hosts is estimated by the Euclidean distance between the two hosts’ assigned coordinates. Previous approaches rely on a fixed set of landmark nodes to construct network coordinates. In contrast, PCoord constructs network coordinates in a fully decentralized fashion, which is significantly more flexible and robust than the traditional approaches. In PCoord, each host constructs its own coordinates based on a small number of peer-to-peer measurements. The key challenge in such a decentralized approach is to ensure that locally derived host coordinates converge stably to a global geometric configuration that accurately captures the actual network distance relationships using as few network measurements as possible. Our simulation results using real Internet measurements suggest that, even under an extremely challenging flash-crowd scenario where 1740 hosts simultaneously join the system, PCoord is able to converge to 12% median prediction error within 10 seconds, where each host performs less than 10 coordinate updates using 10 reference points per update. Our results indicate that PCoord is able to converge to a low system-wide medium prediction error using half as many samples as Vivaldi, a concurrently-developed decentralized coordinate system. Additionally, PCoord provides a set of stability mechanisms that facilitate robust and fault-tolerant coordinate construction in a peer-to-peer system with high churn, high fractions of faulty or misbehaving peers, and high degrees of path anomalies in the underlying network paths.