We define a DHT system whose aim is to combine the routing efficiency typical of randomized networks, i.e. average path length O(logn/ log log n), with the ease of coding and the start-up efficiency of an optimized uniform system. Our proposed system is non-uniform, even though it is not explicitly randomized. In particular, the difference in terms of finger tables between two adjacent peers in a large system is very moderate, and predictable based on an approximation of the peers' keys. These characteristics allow us to adopt a (multi-hop) Neighbor of Neighbor routing algorithm, which asymptotically achieves O(logn/ log logn) average path length, and that in practice may even slightly outperform randomized networks containing more than 100,000 peers.
['Giovanni Chiola', 'Marina Ribaudo']
Neighbor-of-neighbor routing over deterministically modulated Chord-like DHTs