The Impact of DHT Routing Geometry on Resilience andProximityK. Gummadi∗, R. Gummadi†,S.Gribble‡, S. Ratnasamy§, S. Shenker¶, I. Stoica,∗ABSTRACTThe various proposed DHT routing algorithms embody sev-eral different underlying routing geometries. These geome-tries include hypercubes, rings, tree-like structures, and but-terfly networks. In this paper we focus on how these ba-sic geometric approaches affect the resilience and proximityproperties of DHTs. One factor that distinguishes thesegeometries is the degree of flexibility they provide in the se-lection of neighbors and routes. Flexibility is an importantfactor in achieving good static resilience and effective prox-imity 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 henceachieves the best resilience and proximity performance.Categories and Subject DescriptorsC.2 [Computer Systems Organisation]: Computer Com-munication NetworksGeneral TermsAlgorithms, PerformanceKeywordsDHT, Routing Geometry, Flexibility∗University of Washington. [email protected]†USC, Los Angeles. [email protected]‡University of Washington. [email protected]§Intel Research, Berkeley. [email protected]¶ICSI, Berkeley. [email protected]UC Berkeley. [email protected]∗This work is supported in part by NSF grants CCR-0121341, ITR-0085670, IIS-0205635, ANI-0196514, ANI-0207399, ITR-0205519, ITR-0081698, ITR-0121555, ANI-00225660, ANI-0133811 and Stoica’s Sloan Foundation Fel-lowship.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.SIGCOMM’03, August 25–29, 2003, Karlsruhe, Germany.Copyright 2003 ACM 1-58113-735-4/03/0008 ...$5.00.1. INTRODUCTIONThe unexpected and unprecedented explosion of peer-to-peer file-sharing, ignited by Napster and refueled by a suc-cession of less legally vulnerable successors (e.g., Gnutella,Kazaa), inspired the development of distributed hash ta-bles (DHTs). DHTs offer a promising combination of ex-treme scalability (scaling typically as log n) and useful se-mantics (supporting a hash-table-like lookup interface), andhave been proposed as a substrate for many large-scale dis-tributed applications (see, for example, [5, 12, 22]).Our focus here is not on the uses of DHTs but on the un-derlying DHT routing algorithms. A wide variety of DHTrouting algorithms have been proposed, and the list growslonger with each passing conference. However, the DHTrouting literature is still very much in its infancy; as a re-sult, most DHT routing papers describe new algorithms andvery few provide more general insight across algorithms orusefully compare between algorithms.In this paper we attempt to take a very small step in thisdirection by looking at the basic geometry underlying DHTrouting algorithms and how it impacts their performance intwo important areas: static resilience and proximity routing.While the current collection of DHT routing algorithms dif-fers in many respects, perhaps the most fundamental distinc-tion between them lies in their different routing geometries.For instance, CAN [19] (when the dimension is taken to belog n) routes along a hypercube, Chord [25] routes alonga ring, Viceroy [14] uses a butterfly network, and PRR’salgorithm [16] uses a tree-like structure. These geometrieshave differing degrees of flexibility in choosing neighbors andnext-hop paths. The importance of geometry, and the re-sulting flexibility, isn’t clear when looking only at the typicalmetrics of concern – state (the number of neighbors) and ef-ficiency (the average path length) – because many of thesealgorithms can achieve the same state/efficiency trade offs.However, geometry (and flexibility) becomes more relevantwhen looking at other performance issues.One of the crucial questions facing DHTs is whether theycan operate in an extremely transient environment where asignificant fraction of the nodes are down at any one time.There are many facets to this issue, most notably the speedand overhead of recovery algorithms, but one relatively (butnot completely; see [13, 22]) unexplored area is static re-silience, which is how well the DHT can route even beforethe recovery algorithms have had a chance to work theirmagic. We discuss this issue in Section 3.Another crucial question is how well DHTs can adapt tothe underlying Internet topology. Much research has been381devoted to incorporating proximity into DHT routing pro-tocols, and there are two areas of concern. The first is thetotal latency of the DHT routing path, which should be nomore than a small multiple of the underlying Internet la-tency. We discuss path latency in Section 4. The second iswhether such paths converge; the various tasks of providingefficient caching, building parsimonious multicast trees, andfinding the closest server out of many are all made easier ifDHT routing paths have a local convergence property thatwe explore in Section 5.Our paper examines the extent to which geometry impactsthe performance in these two areas, and thus we begin ourpaper by discussing geometry in Section 2. However, beforeembarking on this discussion, which we hope provides someinsight, we readily confess that our paper is a very initialstab at the problem and is undoubtedly incomplete. Ourvarious sins include (1) only picking a few, not all, of thecurrently proposed DHT routing algorithms, (2) not consid-ering factors, such as symmetry, that may affect the statemanagement overhead and (3) only focusing on two perfor-mance issues (resilience and proximity), and not consideringinteractions between these various properties. Rectifyingthese omissions is the subject of future work.2. GEOMETRIES AND ALGORITHMSTo provide context for the technical material to follow,we first discuss the philosophy that motivates this work. Asnoted before, there are a myriad of DHT designs in the liter-ature, all extensively analyzed and energetically promoted.However, we envision that there will be only one or a fewvery large-scale DHT infrastructures. Thus, out of the