Gurmeet Singh Manku, Moni Naor, and Udi Wieder
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 networks. In each of these networks, a node has out-degree O(log n), where n denotes the total number of nodes, and greedy routing is known to take O(log n) hops on average. Our contribution in this paper is twofold. First we investigate the limitations of greedy routing and establish lower-bounds for greedy routing for these networks. The main contribution of the paper is the analysis of the 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 such as hypercubes and Chord have diameter Theta(log n). This means that greedy routing is optimal in the sense that its routing distance is at most (approximately) the diameter, yet networks with average degree of O(log n) may have diameter O( log n/(log log n)). Randomized routing networks such as skip-graphs, randomized hypercubes, randomized Chord, and constructions based upon small-world percolation networks, have diameter Θ(log n/(log log n)) with high probability. In all of these networks, greedy routing fails to find short routes, requiring Omega(log n) hops with high probability. Surprisingly, the NoN-greedy routing algorithm is able to diminish route-lengths to Θ(log n/(log log n)) hops, which is asymptotically optimal.
|Published in||STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing|
|Address||New York, NY, USA|