Article

Handling churn in a DHT

Authors:

Timothy Roscoe,

John KubiatowiczAuthors Info & Claims

ATEC '04: Proceedings of the annual conference on USENIX Annual Technical Conference

Page 10

Published: 27 June 2004 Publication History

Abstract

This paper addresses the problem of churn--the continuous process of node arrival and departure--in distributed hash tables (DHTs). We argue that DHTs should perform lookups quickly and consistently under churn rates at least as high as those observed in deployed P2P systems such as Kazaa. We then show through experiments on an emulated network that current DHT implementations cannot handle such churn rates. Next, we identify and explore three factors affecting DHT performance under churn: reactive versus periodic failure recovery, message timeout calculation, and proximity neighbor selection. We work in the context of a mature DHT implementation called Bamboo, using the ModelNet network emulator, which models in-network queuing, cross-traffic, and packet loss. These factors are typically missing in earlier simulation-based DHT studies, and we show that careful attention to them in Bamboo's design allows it to function effectively at churn rates at or higher than that observed in P2P file-sharing applications, while using lower maintenance bandwidth than other DHT implementations.

References

[1]

{1} Freepastry 1.3. http://www.cs.rice.edu/CS/Systems/Pastry/.]]

[2]

{2} Gnutella. http://www.gnutella.com/.]]

[3]

{3} Inet topology generator. http://topology.eecs.umich.edu/inet/.]]

[4]

{4} MIT Chord. http://www.pdos.lcs.mit.edu/chord/.]]

[5]

{5} R. Bhagwan, S. Savage, and G. Voelker. Understanding availability. In Proc. IPTPS, Feb. 2003.]]

[6]

{6} C. Blake and R. Rodrigues. High availability, scalable storage, dynamic peer networks: Pick two. 2003.]]

[7]

{7} M. Castro, M. Costa, and A. Rowstron. Performance and dependability of structured peer-to-peer overlays. Technical Report MSR-TR-2003-94, Microsoft, 2003.]]

[8]

{8} M. Castro, M. B. Jones, A.-M. Kermarrec, A. Rowstron, M. Theimer, H. Wang, and A. Wolman. An evaluation of scalable application-level multicast built using peer-to-peer overlays. Apr. 2003.]]

[9]

{9} J. Chu, K. Labonte, and B. N. Levine. Availability and locality measurements of peer-to-peer file systems. In Proc. of ITCom: Scalability and Traffic Control in IP Networks, July 2002.]]

[10]

{10} F. Dabek, M. F. Kaashoek, D. Karger, R. Morris, and I. Stoica. Wide-area cooperative storage with CFS. In Proc. ACM SOSP, Oct. 2001.]]

[11]

{11} F. Dabek, J. Li, E. Sit, J. Robertson, M. F. Kaashoek, and R. Morris. Designing a DHT for low latency and high throughput. In Proc. NSDI, 2004.]]

[12]

{12} K. Gummadi, R. Gummadi, S. Gribble, S. Ratnasamy, S. Shenker, and I. Stoica. The impact of DHT routing geometry on resilience and proximity. In Proc. ACM SIGCOMM, Aug. 2003.]]

[13]

{13} K. P. Gummadi, R. J. Dunn, S. Saroiu, S. D. Gribble, H. M. Levy, and J. Zahorjan. Measurement, modeling, and analysis of a peer-to-peer file-sharing workload. In Proc. ACM SOSP, Oct. 2003.]]

[14]

{14} K. Hildrum, J. D. Kubiatowicz, S. Rao, and B. Y. Zhao. Distributed object location in a dynamic network. In Proc. SPAA, 2002.]]

[15]

{15} V. Jacobson and M. J. Karels. Congestion avoidance and control. In Proc. ACM SIGCOMM, 1988.]]

[16]

{16} J. Li, J. Stribling, T. M. Gil, R. Morris, and F. Kaashoek. Comparing the performance of distributed hash tables under churn. In Proc. IPTPS, 2004.]]

[17]

{17} D. Liben-Nowell, H. Balakrishnan, and D. Karger. Analysis of the evolution of peer-to-peer systems. In Proc. ACM PODC, July 2002.]]

[18]

{18} B. T. Loo, R. Huebsch, I. Stoica, and J. Hellerstein. The case for a hybrid P2P search infrastructure. In Proc. IPTPS, 2004.]]

[19]

{19} R. Mahajan, M. Castro, and A. Rowstron. Controlling the cost of reliability in peer-to-peer overlays. In Proc. IPTPS, Feb. 2003.]]

[20]

{20} P. Maymounkov and D. Mazieres. Kademlia: A peer-to-peer information system based on the XOR metric. In Proc. IPTPS, 2002.]]

[21]

{21} C. Plaxton, R. Rajaraman, and A. Richa. Accessing nearby copies of replicated objects in a distributed environment. In Proc. of ACM SPAA, June 1997.]]

[22]

{22} S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A scalable content-addressable network. In Proc. ACM SIGCOMM, Aug. 2001.]]

[23]

{23} S. Rhea, D. Geels, T. Roscoe, and J. Kubiatowicz. Handling churn in a DHT. Technical Report UCB//CSD-03-1299, University of California, Berkeley, December 2003.]]

[24]

{24} A. Rowstron and P. Druschel. Pastry: Scalable, distributed object location and routing for large scale peer-to-peer systems. In Proc. of IFIP/ACM Middleware, Nov. 2001.]]

[25]

{25} S. Saroiu, P. K. Gummadi, and S. D. Gribble. A measurement study of peer-to-peer file sharing systems. In Proc. MMCN, Jan. 2002.]]

[26]

{26} S. Sen and J. Wang. Analyzing peer-to-peer traffic across large networks. In Proc. of ACM SIGCOMM Internet Measurement Workshop , Nov. 2002.]]

[27]

{27} I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for Internet applications. In Proc. ACM SIGCOMM, Aug. 2001.]]

[28]

{28} A. Vahdat, K. Yocum, K. Walsh, P. Mahadevan, D. Kostic, J. Chase, and D. Becker. Scalability and accuracy in a large-scale network emulator. In Proc. OSDI, Dec. 2002.]]

[29]

{29} B. Y. Zhao, Y. Duan, L. Huang, A. D. Joseph, and J. D. Kubiatowicz. Brocade: Landmark routing on overlay networks. In Proc. IPTPS, March 2002.]]

[30]

{30} B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph, and J. D. Kubiatowicz. Tapestry: A resilient global-scale overlay for service deployment. IEEE JSAC, 22(1):41-53, Jan. 2004.]]

Cited By

Kakivaya GXun LHasha RAhsan SPfleiger TSinha RGupta ATarta MFussell MModi VMohsin MKong RAhuja APlaton OWun ASnider MDaniel CMastrian DLi YRao AKidambi VWang RRam AShivaprakash SNair RWarwick ANarasimman BLin MChen JMhatre ASubbarayalu PCoskun MGupta IOliveira RFelber PHu Y(2018)Service fabricProceedings of the Thirteenth EuroSys Conference10.1145/3190508.3190546(1-15)Online publication date: 23-Apr-2018
https://dl.acm.org/doi/10.1145/3190508.3190546
Cha MKim DKim HKim Y(2017)Adaptive metadata rebalance in exascale file systemThe Journal of Supercomputing10.1007/s11227-016-1812-x73:4(1337-1359)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1007/s11227-016-1812-x
Kaur RSangal AKumar K(2016)A Persistent Structured Hierarchical Overlay Network to Counter Intentional Churn AttackJournal of Computer Networks and Communications10.1155/2016/51914052016(4)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1155/2016/5191405
Show More Cited By

Index Terms

Recommendations

Bandwidth and Latency Model for DHT Based Peer-to-Peer Networks under Variable Churn
ICW '05: Proceedings of the 2005 Systems Communications

Distributed Hash Table (DHT) based Peer-to-Peer (P2P) algorithms are very promising for their efficient routing performance. However, most commercial P2P systems do not adapt DHT algorithms due to reasons like routing information maintenance overhead, ...
Churn: A Key Effect on Real-World P2P Software
ICPP '13: Proceedings of the 2013 42nd International Conference on Parallel Processing

Churn refers to a large number of arriving and departing participants within a short time in peer-to-peer (P2P) networks. This paper studies the impact of churn on real-world unstructured P2P networks. To this end, we need collecting snapshots of P2P ...
Churn Tolerance Improvement Techniques in an Algorithm-Neutral DHT
AIMS '09: Proceedings of the 3rd International Conference on Autonomous Infrastructure, Management and Security: Scalability of Networks and Services

Churn resilience is an important topic in DHT research. In this paper, I present techniques to improve churn resilience and their effects. All the techniques can be implemented in a DHT layer and require no change to underlying routing layers. In other ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ATEC '04: Proceedings of the annual conference on USENIX Annual Technical Conference

June 2004

572 pages

Publisher

USENIX Association

United States

Publication History

Published: 27 June 2004

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

187
Total Citations
View Citations
28
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kakivaya GXun LHasha RAhsan SPfleiger TSinha RGupta ATarta MFussell MModi VMohsin MKong RAhuja APlaton OWun ASnider MDaniel CMastrian DLi YRao AKidambi VWang RRam AShivaprakash SNair RWarwick ANarasimman BLin MChen JMhatre ASubbarayalu PCoskun MGupta IOliveira RFelber PHu Y(2018)Service fabricProceedings of the Thirteenth EuroSys Conference10.1145/3190508.3190546(1-15)Online publication date: 23-Apr-2018
https://dl.acm.org/doi/10.1145/3190508.3190546
Cha MKim DKim HKim Y(2017)Adaptive metadata rebalance in exascale file systemThe Journal of Supercomputing10.1007/s11227-016-1812-x73:4(1337-1359)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1007/s11227-016-1812-x
Kaur RSangal AKumar K(2016)A Persistent Structured Hierarchical Overlay Network to Counter Intentional Churn AttackJournal of Computer Networks and Communications10.1155/2016/51914052016(4)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1155/2016/5191405
Guerraoui RKermarrec APavlovic MSeredinschi D(2016)AtumProceedings of the 17th International Middleware Conference10.1145/2988336.2988356(1-14)Online publication date: 28-Nov-2016
https://dl.acm.org/doi/10.1145/2988336.2988356
Chen CVitenberg RJacobsen HGal AWeidlich MKalogeraki VVenkasubramanian N(2016)OMenProceedings of the 10th ACM International Conference on Distributed and Event-based Systems10.1145/2933267.2933305(105-116)Online publication date: 13-Jun-2016
https://dl.acm.org/doi/10.1145/2933267.2933305
Srivastava AAhmad P(2016)A Probabilistic Gossip-based Secure Protocol for Unstructured P2P NetworksProcedia Computer Science10.1016/j.procs.2016.02.12278:C(595-602)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.1016/j.procs.2016.02.122
Li JLi CFang ZWang HWu Y(2016)Optimal layer division for low latency in DHT-based hierarchical P2P networkNetworks10.1002/nem.192226:2(95-110)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.1002/nem.1922
Vasilomanolakis EKaruppayah SMühlhäuser MFischer M(2015)Taxonomy and Survey of Collaborative Intrusion DetectionACM Computing Surveys10.1145/271626047:4(1-33)Online publication date: 11-May-2015
https://dl.acm.org/doi/10.1145/2716260
Chiluka NAndrade NPouwelse JSips HBao FMiller SZhou JAhn G(2015)Social Networks Meet Distributed SystemsProceedings of the 10th ACM Symposium on Information, Computer and Communications Security10.1145/2714576.2714606(507-518)Online publication date: 14-Apr-2015
https://dl.acm.org/doi/10.1145/2714576.2714606
Lee HSeibert JFistrovic DKillian CNita-Rotaru C(2015)GatlingACM Transactions on Information and System Security10.1145/271456517:4(1-34)Online publication date: 24-Apr-2015
https://dl.acm.org/doi/10.1145/2714565
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents