Residual-based estimation of peer and link lifetimes in P2P networks

ABSTRACT

Existing methods of measuring lifetimes in P2P systems usually rely on the so-called Create-Based Method (CBM), which divides a given observation window into two halves and samples users "created" in the first half every Δ time units until they die or the observation period ends. Despite its frequent use, this approach has no rigorous accuracy or overhead analysis in the literature. To shed more light on its performance, we first derive a model for CBM and show that small window size or large Δ may lead to highly inaccurate lifetime distributions. We then show that create-based sampling exhibits an inherent tradeoff between overhead and accuracy, which does not allow any fundamental improvement to the method. Instead, we propose a completely different approach for sampling user dynamics that keeps track of only residual lifetimes of peers and uses a simple renewal-process model to recover the actual lifetimes from the observed residuals. Our analysis indicates that for reasonably large systems, the proposed method can reduce bandwidth consumption by several orders of magnitude compared to prior approaches while simultaneously achieving higher accuracy. We finish the paper by implementing a two-tier Gnutella network crawler equipped with the proposed sampling method and obtain the distribution of ultrapeer lifetimes in a network of 6.4 million users and 60 million links. Our experimental results show that ultrapeer lifetimes are Pareto with shape α ≅ 1.1; however, link lifetimes exhibit much lighter tails with α ≅ 1.8.

REFERENCES

• 1: R. Bhagwan, S. Savage, and G. M. Voelker, "Understanding availability," in Proc. IPTPS, Feb. 2003, pp. 256-267.
• 2: F. E. Bustamante and Y. Qiao, "Friendships that last: Peer lifespan and its role in P2P protocols," in Proc. Int. Workshop on Web Content Caching and Distribution, Sep. 2003.
• 3: G. Casella and R. L. Berger, Statistical Inference, 2nd ed. New York: Duxbury/Thomson Learning, 2002.
• 4: Yatin Chawathe , Sylvia Ratnasamy , Lee Breslau , Nick Lanham , Scott Shenker, Making gnutella-like P2P systems scalable, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.864000]
• 5: J. Chu, K. Labonte, and B. N. Levine, "Availability and locality measurements of peer-to-peer file systems," in Proc. ITCom Conf., Jul. 2002, vol. 4868, pp. 310-321.
• 6: Nick Duffield , Carsten Lund , Mikkel Thorup, Estimating flow distributions from sampled flow statistics, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863992]
• 7: Richard J. Dunn , John Zahorjan , Steven D. Gribble , Henry M. Levy, Presence-Based Availability and P2P Systems, Proceedings of the Fifth IEEE International Conference on Peer-to-Peer Computing, p.209-216, August 31-September 02, 2005 [doi>10.1109/P2P.2005.27]
• 8: Z. Ge, D. R. Figueiredo, S. Jaiswal, J. Kurose, and D. Towsley, "Modeling peer-peer file sharing systems," in Proc. IEEE INFOCOM, Mar. 2003, vol. 3, pp. 2188-2198.
• 9: Gnutella. [Online]. Available: http://www.gnutella.com/
• 10: K. Gummadi , R. Gummadi , S. Gribble , S. Ratnasamy , S. Shenker , I. Stoica, The impact of DHT routing geometry on resilience and proximity, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863998]
• 11: KaZaA. [Online]. Available: http://www.kazaa.com/
• 12: S. Krishnamurthy, S. El-Ansary, E. Aurell, and S. Haridi, "A statistical theory of chord under churn," in Proc. IPTPS, Feb. 2005, pp. 93-103.
• 13: 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
• 14: Jian Liang , Rakesh Kumar , Keith W. Ross, The FastTrack overlay: a measurement study, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.6, p.842-858, 13 April 2006 [doi>10.1016/j.comnet.2005.07.014]
• 15: Sidney I. Resnick, Adventures in stochastic processes, Birkhauser Verlag, Basel, Switzerland, 1992
• 16: Matei Ripeanu , Adriana Iamnitchi , Ian Foster, Mapping the Gnutella Network, IEEE Internet Computing, v.6 n.1, p.50-57, January 2002 [doi>10.1109/4236.978369]
• 17: Drew Roselli , Jacob R. Lorch , Thomas E. Anderson, A comparison of file system workloads, Proceedings of the annual conference on USENIX Annual Technical Conference, p.4-4, June 18-23, 2000, San Diego, California
• 18: S. Saroiu, P. K. Gummadi, and S. D. Gribble, "A measurement study of peer-to-peer file sharing systems," in Proc. SPIE/ACM Multimedia Computing and Networking, Jan. 2002, vol. 4673, pp. 156-170.
• 19: 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]
• 20: Daniel Stutzbach , Reza Rejaie, Understanding churn in peer-to-peer networks, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil [doi>10.1145/1177080.1177105]
• 21: Daniel Stutzbach , Reza Rejaie , Nick Duffield , Subhabrata Sen , Walter Willinger, On unbiased sampling for unstructured peer-to-peer networks, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil [doi>10.1145/1177080.1177084]
• 22: Daniel Stutzbach , Reza Rejaie , Subhabrata Sen, Characterizing unstructured overlay topologies in modern P2P file-sharing systems, Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement, p.5-5, October 19-21, 2005, Berkeley, CA
• 23: Zhongmei Yao , Derek Leonard , Xiaoming Wang , Dmitri Loguinov, Modeling Heterogeneous User Churn and Local Resilience of Unstructured P2P Networks, Proceedings of the Proceedings of the 2006 IEEE International Conference on Network Protocols, p.32-41, November 12-15, 2006 [doi>10.1109/ICNP.2006.320196]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols
      C.2.m Miscellaneous
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Design, Performance, Reliability

Keywords:
Gnutella networks, lifetime estimation, peer-to-peer, residual sampling