Understanding churn in peer-to-peer networks

ABSTRACT

The dynamics of peer participation, or churn, are an inherent property of Peer-to-Peer (P2P) systems and critical for design and evaluation. Accurately characterizing churn requires precise and unbiased information about the arrival and departure of peers, which is challenging to acquire. Prior studies show that peer participation is highly dynamic but with conflicting characteristics. Therefore, churn remains poorly understood, despite its significance.In this paper, we identify several common pitfalls that lead to measurement error. We carefully address these difficulties and present a detailed study using three widely-deployed P2P systems: an unstructured file-sharing system (Gnutella), a content-distribution system (BitTorrent), and a Distributed Hash Table (Kad). Our analysis reveals several properties of churn: (i) overall dynamics are surprisingly similar across different systems, (ii) session lengths are not exponential, (iii) a large portion of active peers are highly stable while the remaining peers turn over quickly, and (iv) peer session lengths across consecutive appearances are correlated. In summary, this paper advances our understanding of churn by improving accuracy, comparing different P2P file sharingdistribution systems, and exploring new aspects of churn.

REFERENCES

• 1: eMule. http://www.emule-project.net, 2005.
• 2: slyck.com. http://www.slyck.com, 2005.
• 3: R. Bhagwan, S. Savage, and G. Voelker. Understanding Availability. In International Workshop on Peer-to-Peer Systems, 2003.
• 4: A. Bharambe and C. Herley. Analyzing and Improving BitTorrent Performance. Technical Report MSR-TR-2005-03, Microsoft Research, 2005.
• 5: F. E. Bustamante and Y. Qiao. Friendships that last: Peer lifespan and its role in P2P protocols. In International Workshop on Web Content Caching and Distribution, 2003.
• 6: J. Chu, K. Labonte, and B. N. Levine. Availability and Locality Measurements of Peer-to-Peer File Systems. In ITCom: Scalability and Traffic Control in IP Networks II Conferences, 2002.
• 7: Mark E. Crovella , Azer Bestavros, Self-similarity in World Wide Web traffic: evidence and possible causes, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.835-846, Dec. 1997 [doi>10.1109/90.650143]
• 8: Free Peers, Inc. BearShare Network Statistics. http://www.bearshare.com/stats/, 2005.
• 9: Krishna P. Gummadi , Richard J. Dunn , Stefan Saroiu , Steven D. Gribble , Henry M. Levy , John Zahorjan, Measurement, modeling, and analysis of a peer-to-peer file-sharing workload, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 10: L. Guo, S. Chen, Z. Xiao, E. Tan, X. Ding, and X. Zhang. Measurements, Analysis, and Modeling of BitTorrent-like Systems. In Internet Measurement Conference, 2005.
• 11: M. Izal, G. Urvoy-Keller, E. W. Biersack, P. A. Felber, A. A. Hamra, and L. Garces-Erice. Dissecting BitTorrent: Five Months in a Torrent's Lifetime. In PAM, 2004.
• 12: T. Karagiannis, A. Broido, N. Brownlee, K. Claffy, and M. Faloutsos. Is P2P dying or just hiding? In Globecom, 2004.
• 13: T. Karagiannis, P. Rodriguez, and K. Papagiannaki. Should Internet Service Providers Fear Peer-Assisted Content Distribution? In Internet Measurement Conference, 2005.
• 14: Derek Leonard , Vivek Rai , Dmitri Loguinov, On lifetime-based node failure and stochastic resilience of decentralized peer-to-peer networks, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 15: J. Li, J. Stribling, F. Kaashoek, R. Morris, and T. Gil. A Performance vs. Cost Framework for Evaluating DHT Design Tradeoffs under Churn. In INFOCOM, 2005.
• 16: J. Li, J. Stribling, R. Morris, and M. F. Kaashoek. Bandwidth-efficient Management of DHT Routing Tables. In Networked Systems Design and Implementation, 2005.
• 17: J. Liang, R. Kumar, and K. W. Ross. The KaZaA Overlay: A Measurement Study. Computer Networks Journal (Elsevier), 2005.
• 18: David Liben-Nowell , Hari Balakrishnan , David Karger, Analysis of the evolution of peer-to-peer systems, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571863]
• 19: Lime Wire LLC. Crawler Compatability. Gnutella Developer's Forum, 2003.
• 20: Petar Maymounkov , David Mazières, Kademlia: A Peer-to-Peer Information System Based on the XOR Metric, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.53-65, March 07-08, 2002
• 21: J. Pouwelse, P. Garbacki, D. Epema, and H. Sips. The Bittorrent P2P File-sharing System: Measurements and Analysis. In International Workshop on Peer-to-Peer Systems (IPTPS), 2005.
• 22: S. Rhea, D. Geels, and J. Kubiatowicz. Handling Churn in a DHT. In USENIX, 2004.
• 23: Stefan Saroiu , Krishna P. Gummadi , Steven D. Gribble, Measuring and analyzing the characteristics of Napster and Gnutella hosts, Multimedia Systems, v.9 n.2, p.170-184, August 2003 [doi>10.1007/s00530-003-0088-1]
• 24: Subhabrata Sen , Jia Wang, Analyzing peer-to-peer traffic across large networks, IEEE/ACM Transactions on Networking (TON), v.12 n.2, p.219-232, April 2004 [doi>10.1109/TNET.2004.826277]
• 25: Kunwadee Sripanidkulchai , Bruce Maggs , Hui Zhang, An analysis of live streaming workloads on the internet, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028795]
• 26: D. Stutzbach and R. Rejaie. Capturing Accurate Snapshots of the Gnutella Network. In Global Internet Symposium, 2005.
• 27: D. Stutzbach, R. Rejaie, and S. Sen. Characterizing Unstructured Overlay Topologies in Modern P2P File-Sharing Systems. In Internet Measurement Conference, 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network monitoring

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development

General Terms:
Measurement, Reliability, Verification

Keywords:
Gnutella, bitTorrent, churn, kad, peer-to-peer, session length, uptime