The impact of DHT routing geometry on resilience and proximity

By Krishna P. Gummadi, Ramakrishna Gummadi, S. Gribble, Sylvia Ratnasamy, Scott Shenker, Ion Stoica. Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, 2003

682 citations recorded by the source corpus.

The various proposed DHT routing algorithms embody several different underlying routing geometries. These geometries include hypercubes, rings, tree-like structures, and butterfly networks. In this paper we focus on how these basic geometric approaches affect the resilience and proximity properties of DHTs. One factor that distinguishes these geometries is the degree of flexibility they provide in the selection of neighbors and routes. Flexibility is an important factor in achieving good static resilience and effective proximity neighbor and route selection. Our basic finding is that, despite our initial preference for more complex geometries, the ring geometry allows the greatest flexibility, and hence achieves the best resilience and proximity performance.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/593ad933b7358991648b0bbcdd3f0c148632658c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

Mercury: supporting scalable multi-attribute range queries (2004, methodology): “Our analysis, based on analyzing possible strawman designs using DHTs, indicates that the abstractions provided by a DHT are not enough for implementing range queries.”
Chord: A scalable peer-to-peer lookup service for internet applications (2001, background): “al [6]  Static Resilience: Ability to route successfully w/out recovery  Path Latency: Average end-to-end latency for a lookup  Local Convergence: Property that 2 messages for same location converge at a node near the two sources  From study, [6] conclude ring-structure performs the best!”
In VINI veritas: realistic and controlled network experimentation (2006, methodology): “For example, adding smoother rate-based algorithms such as TFRC [16] to the Congestion Manager (as an alternative to the basic abruptly-changing AIMD algorithm) would require different feedback from the receiver; this would then require a new kernel API to supply the necessary feedback to the new Co”
Graph-theoretic analysis of structured peer-to-peer systems: routing distances and fault resilience (2003, positive): “[16] find that ring-based graphs (such as Chord) offer more flexibility with route selection and provide better performance under random node failure compared to several other traditional DHTs.”
PIC: practical Internet coordinates for distance estimation (2004, background): “Tapestry, Pastry [24], and a recent version of Chord [11] implement PNS. PNS can be used to achieve low delay routes and low bandwidth usage.”
Rarest first and choke algorithms are enough (2006, background): “Whereas content localization has attracted considerable research interest in the last years [7,12,23,25], content replication has started to be the subject of active research only recently.”
Survey of research towards robust peer-to-peer networks: Search methods (2006, background): “Loguinov et al. claimed that there were only two such works [24] [36].”
Taxonomy of trust: Categorizing P2P reputation systems (2006, background): “Higher levels of churn require increased data replication, redundant routing paths, and topology repair protocols [9].”
A scalable distributed information management system (2004, background): “[13] point out the importance of path convergence from the perspective of achieving efficiency and investigate the performance of Pastry and other DHT algorithms respectively.”
Designing a DHT for Low Latency and High Throughput (2004, background): “The latency of the last few hops in a lookup acts as a lower bound on the performance of Proximity Neighbor Selection [37, 16], which approximates 1.”
BotGrep: Finding P2P Bots with Structured Graph Analysis (2010, background): “Further, structured overlay mechanisms are designed to remain robust in the face of churn [48, 32], an important concern for botnets, where individual machines may be frequently disinfected or simply turned off for the night.”