Know thy Neighbor's Neighbor: The Power of Lookahead in Randomized P2P Networks

Abstract

Several peer-to-peer networks are based upon randomized graph topologies that permit efficient GREEDY routing, e.g., randomized hypercubes, randomized Chord, skip-graphs and constructions based upon small-world percolation networks. In each of these networks, a node has out-degree \theta(log n), where n denotes the total number of nodes, and GREEDY routing is known to take O(log n) hops on average. We establish low- bounds for GREEDY routing for these networks, and analyze Neighbor-of-Neighbor (NoN)-GREEDY routing. The idea behind NoN, as the name suggests, is to take a neighbor's neighbors into account for making better routing decisions. The following picture emerges: Deterministic routing networks like hypercubes and Chord have diameter \theta(log n) and GREEDY routing is optimal. Randomized routing networks like randomized hypercubes, randomized Chord, and constructions based on small-world percolation networks, have diameter \theta(log n / log log n) with high probability. The expected diameter of Skip graphs is also \theta(log n / log log n). In all of these networks, GREEDY routing fails to find short routes, requiring \theta(log n) hops with high probability. Surprisingly, the NoN-GREEDY routing algorithm is able to diminish route-lengths to theta(log n / log log n) hops, which is asymptotically optimal.

Back to publications
Back to previous page