We define a DHT system whose aim is to combine the routing efficiency typical of randomized networks, i.e. average path length O(log n/ 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(log n/ log log n) average path length, and that in practice may even slightly outperform randomized networks containing more than 100,000 peers.
Neighbor-of-neighbor routing over deterministically modulated Chord-like DHTs
CHIOLA, GIOVANNI;RIBAUDO, MARINA
2008-01-01
Abstract
We define a DHT system whose aim is to combine the routing efficiency typical of randomized networks, i.e. average path length O(log n/ 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(log n/ log log n) average path length, and that in practice may even slightly outperform randomized networks containing more than 100,000 peers.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
