Shortcut Routing for Chord Graphs in the Domus Hash Space

J. Rufino, A. Pina, A. Alves, and J. Exposto (Portugal)


Distributed Hash Tables, Distributed Lookup, Evaluation.


We present and evaluate shortcut routing algorithms for Chord graphs in the hash space, specifically developed to accelerate distributed lookups in the Distributed Hash Ta bles (DHTs) of the Domus framework. The algorithms ex plore our findings about the relation of exponential and eu clidean distances in Chord graphs, in conjunction with the availability, in each DHT node, of multiple routing tables of the underlying Chord graph. The outcome are routing deci sions capable of achieving average distances as low as 40% of those offered by Chord’s conventional routing method. Moreover, the supplemental computational effort to take the shortcut routing decisions is sufficiently low to make the al gorithms useful in a broad set of application scenarios.

Important Links:

Go Back