Finding close friends on the Internet

We consider the problem of finding nearby application-peers (close friends) over the Internet. We focus on unicast-only solutions and introduce a new scheme -Beaconing-for finding peers that are near. Our scheme uses distance measurement points (called beacons) and can be implemented entirely in the application-layer without investing in large infrastructure changes. We present an extensive evaluation of Beaconing and compare it to existing schemes including Expanding Ring searches and Triangulation. Our experiments show that 3-8 beacons are sufficient to provide efficient peer-location service on 10 000 node Internet-like topologies. Further, our results are 2-5 times more accurate than existing techniques. We also present results from an implementation of Beaconing over a non-trivial wide-area testbed. In our experiments, Beaconing is able to efficiently (< 3 K Bytes and < 50 packets on average), quickly (< 1 second on average), and accurately (< 20 ms error on average) find nearby peers on the Internet.