Udi Wieder
Weizmann Institute

Know thy Neighbor's Neighbor: Better Routing for Skip-Graphs and Small Worlds.

ABSTRACT
--------

We investigate an approach for routing in p2p constructions called
"neighbor-of-neighbor (NoN) greedy". We show that this approach may
reduce significantly the number of hops used, when routing in skip
graphs and small worlds. Furthermore we show that a simple variation
of Chord is degree optimal. While not being Greedy per-se, the
NoN-Greedy algorithm preserves some good properties of greedy
algorithms. Furthermore we show a lower bound proving that in order to
reduce the number of hops, information regarding neighbors only is
insufficient, thus the NoN approach is essential.

Joint work with Moni Naor