Papillon: Greedy Routing in Rings
|
Gurmeet Manku |
|
|
|
Abstract We study greedy routing over n
nodes placed in a ring, with the distance between two nodes defined to
be the clockwise or the absolute distance between them along the ring. Such graphs arise in the context of
modeling social networks and in routing networks for peer-to-peer systems. We construct the first network over n
nodes in which greedy routing takes O(log
n / log d) hops in the worst-case, with d out-going links per node. Our result has the first asymptotically optimal
greedy routing complexity. Previous
constructions required O(log2n
/d) hops. |
||
