Techniques for low-latency proxy selection in wide-area P2P networks

Connectivity constraints due to Internet route outages and symmetric NATs create situations when direct communication is not possible between nodes in P2P deployments, often leading to high latency between high-traffic nodes. In such cases, it is possible to reduce end-to-end latency by routing their communication through another node in the P2P system that is selected based on its Internet latencies to end-nodes. In this paper, we present and compare two decentralized algorithms for discovering low-latency proxy nodes between high-traffic nodes: (1) selecting a node with least Internet latency from the set of randomly-chosen neighbors to which one of the end-nodes is directly connected, and (2) discovery using latency estimates based on network coordinates. We evaluate these techniques in context of IP-over-P2P virtual networks through experiments on realistic wide-area testbeds. Our results indicate that in a network with over 400 nodes on PlanetLab, both the techniques select proxies such that the median penalties over the global optimal are within 16% and 21%, respectively, when all nodes are able to serve as proxies. We also investigate scenarios where subsets of nodes have connectivity constraints preventing them from serving as proxies.