A hash-free overlay with eventually optimal locality

DOI: 10.5176/978-981-08-7656-2_NTC2010-39

Authors: Martin Raack, Christian Wuertz, Philipp Berndt, and Odej Kao

Abstract:

A key property of efficient Peer-to-Peer (P2P) overlay networks is proximity awareness. Networks that setup theirrouting tables deterministically are in fact able to provide shortoverlay path lengths of O(log n), but the entire path latency tends to grow proportionally to the number of routing steps (hops). On the other hand, those networks that are capable of optimizing their network structure to prefer proximate nodes are able to provide low routing path latencies, independent of the actual number of hops. In this paper, we present a new proximity aware routing algorithm and discovery protocol for the overlay network Papnet[1]. In contrast to classic overlay networks, Papnet does notrely on the hashing of keys and allows for more sophisticated applications than a distributed hash-table (DHT).We show, that a hash-free network like Papnet can provide very low path latencies and compare it to the well known hash-based proximity-awareoverlay network Pastry. Moreover, we show that Papnet is able to guarantee eventual convergence to optimal routing tables, a property that has not been achieved in previous overlay networks.