PALM: Predicting Internet Network Distances Using Peer-to-Peer Measurements

Abstract — Landmark-based architecture has been commonly adopted in the networking community as a mechanism to mea-sure and characterize a host’s location on the Internet. In most existing landmark based approaches, end hosts use the distance measurements to a common, fixed set of landmarks to derive an estimated location on the Internet. This paper investigates whether it is possible for participating peer nodes in an overlay network to collaboratively construct an accurate geometric model of its topology in a completely decentralized peer-to-peer fashion, without using a fixed set of landmarks. We call such a peer-to-peer approach in topology discovery and modeling using landmarks PALM (Peers As LandMarks). We evaluate the performance characteristics of such a decentralized coordinate-based approach under several factors, including dimensionality of the geometric space, peer distance distribution, and the number of peer-to-peer distance measurements used. We evaluate two PALM-based schemes: RAND-PALM and ISLAND. In RAND-PALM, a peer node randomly selects from existing peer nodes as its landmarks. In ISLAND (Intelligent Selection of Landmarks), each peer node selects its landmarks by exploiting the topological information derived based on existing peer nodes ’ coordinates. I