The Impact of DHT Routing Geometry on Resilience and Proximity

This paper discusses DHTs and compares the performance of different routing designs. The paper focuses on routing geometry rather than algorithmic details. Flexibility, that is, the amount of freedom available in choosing neighbors and next-hop paths, is a direct consequence of the geometry and in turn affects such properties as static resilience, path latency, and local convergence. Geometries that have little optimal path route selection flexibility are tree, butterfly, XOR and hybrid geometries, while hypercube and butterfly geometries have little flexibility in neighbor selection.

Based on path latency experiments, the atuhors suggest that geometries only actually affect path latency based on their ability to implement Proximity Neighbor/Route Selection. The authors tentatively suggest that the comparatively simple ring geometry be used more frequently because it is flexible and performs just as well or better than other geometries in a variety of tests. It seems odd that the authors should sound so tentative about using ring geometries, seeing as Chord had already been successfully implemented prior to this paper's publishing.