The Power of Lookahead in Small-World Routing Networks: Greedy routing, aided by 1-Lookahead, has O(log n / log log n) latency for several randomized P2P routing networks.

Abstract

We present tight bounds for GREEDY routing with/without 1-LOOKAHEAD in several randomized networks. The idea of 1-LOOKAHEAD is for a node to consider its neighbor's neighbors for better routing decisions. In practice, such information is available (almost) for free since pairs of nodes are connected by TCP connections which exchange keep-alive messages. Deterministic topologies like hypercubes and Chord have Theta(log n) links per node where n denotes the number of nodes; the diameter is Theta(log n); GREEDY routing is optimal as it routes along shortest paths; 1-LOOKAHEAD offers no improvement. Randomized variants of both the networks, defined quite naturally, shrink the diameter to Theta(log n / log log n) in expectation. GREEDY routing fails to find short routes, requiring Theta(log n) on average. Surprisingly, augmented with just 1-LOOKAHEAD, routes are Theta(log n / log log n) on average, which is asymptotically optimal. The same behavior is true for adaptations of Kleinberg's construction, which we analyze for smaller values of out-degree per node as well. In the process, we bring out the connections between Kleinberg's construction, randomized hypercubes and Chord. We also present a deterministic variant of hypercubes that can route in worst case Theta(log n / log log n) hops with only Theta(log n / log log n) links per node.