Building heterogeneous peer-to-peer networks: protocol and analysis

ABSTRACT

In this paper, we propose a simple protocol for building heterogeneous unstructured peer-to-peer (P2P) networks. The protocol consists of two parts--the joining process and the rebuilding process. The basic idea for the joining process is to use a random walk to assist new incoming peers in selecting their suitable neighbors in terms of capacity and connectivity to achieve load-balancing. The rebuilding process specifies how the nodes should react when they lose links. In particular, we examine two representative schemes, namely the probabilistic-rebuilding scheme and the adaptive-rebuilding scheme. Furthermore, we provide a detailed analysis to investigate our proposed protocol under any heterogenous P2P environment. We prove that the topology structure of the P2P network depends heavily on the node heterogeneity. The analytical results are validated by the simulations. Our framework provides a guideline to engineer and optimize a P2P network in different respects under a heterogeneous environment. The ultimate goal of this paper is to stimulate further research to explore the fundamental issues in heterogeneous P2P networks.

REFERENCES

• 1: [1] Gnutella. [Online]. Available: http://www.gnutella.com
• 2: [2] KaZaA. [Online]. Available: http://www.kazaa.com
• 3: [3] Skype. [Online]. Available: http://www.skype.com
• 4: [4] Gnutella2. [Online]. Available: http://en.wikipedia.org/wiki/Gnutella2
• 5: [5] PPLive. [Online]. Available: http://www.pplive.com
• 6: [6] F. Ball, T. Britton, and O. Lyne, "Stochastic multitype epidemics in a community of households: Estimation and form of optimal vaccination schemes," Mathematical Biosciences, vol. 191, no. 1, pp. 19-40, 2004.
• 7: [7] A.-L. Barabási, R. Albert, and H. Jeong, "Mean-field theory for scale-free random networks," Physica A, vol. 272, no. 1, pp. 173-187, 1999.
• 8: [8] B. Bollobás, Random Graphs, 2nd ed. Cambridge, U.K.: Cambridge University Press, 2001.
• 9: 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]
• 10: [10] R. Cohen, K. Erez, D. ben Avraham, and S. Havlin, "Resilience of the Internet to random breakdowns," Phys. Rev. Lett., vol. 85, no. 21, pp. 4626-4628, Nov. 2000.
• 11: [11] Y. Cui, Y. Xue, and K. Nahrstedt, "Max-min overlay multicast: Rate allocation and tree construction," in Proc. IWQoS, 2004.
• 12: [12] S. N. Dorogovtsev and J. F. F. Mendes, "Scaling properties of scale-free evolving networks: Continuous approach," Phys. Rev. E, vol. 63, no. 5, p. 056125, Apr. 2001.
• 13: [13] P. Erdös and A. Rényi, "On random graphs," Publicationes Mathematicae , vol. 6, pp. 290-297, 1959.
• 14: [14] A. Fronczak, P. Fronczak, and J. A. Holyst, "Average path length in random networks," 2002 [Online]. Available: http://arxiv.org/abs/ cond-mat/0212230
• 15: [15] A. Ganesh, L. Massoulié, and D. Towsley, "The effect of network topology on the spread of epidemics," in Proc. IEEE INFOCOM, 2005.
• 16: [16] C. Gkantsidis and P. R. Rodriguez, "Network coding for large scale content distribution," in Proc. IEEE INFOCOM, 2005.
• 17: [17] W. Hastings, "Monte Carlo sampling methods using Markov chains and their applications," Biometrika, vol. 57, no. 1, pp. 97-109, 1970.
• 18: [18] X. Hei, C. Liang, J. Liang, Y. Liu, and K. W. Ross, "A measurement study of a large-scale P2P IPTV system," IEEE Trans. Multimedia, vol. 9, no. 8, pp. 1672-1687, Dec. 2007.
• 19: Min Sik Kim , Simon S. Lam , Dong-Young Lee, Optimal Distribution Tree for Internet Streaming Media, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.116, May 19-22, 2003
• 20: [20] K. W. Kwong and D. H. K. Tsang, "On the relationship of node capacity distribution and P2P topology formation," in Proc. IEEE Workshop on High Performance Switching and Routing (HPSR), 2005.
• 21: [21] K. W. Kwong and D. H. K. Tsang, "Application-aware topology formation algorithm for peer-to-peer networks," in Proc. IEEE Int. Conf. Communications (ICC), 2007.
• 22: [22] J. Liang, R. Kumar, Y. Xi, and K. W. Ross, "Pollution in P2P file sharing systems," in Proc. IEEE INFOCOM, 2005.
• 23: Hao Luan , Danny H. K. Tsang , Kin Wah Kwong, Media overlay construction via a Markov chain Monte Carlo method, ACM SIGMETRICS Performance Evaluation Review, v.34 n.3, December 2006 [doi>10.1145/1215956.1215962]
• 24: Laurent Massoulié , Milan VojnoviĆ, Coupon replication systems, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 25: [25] M. Meo and F. Milan, "A rational model for service rate allocation in peer-to-peer networks," in Proc. IEEE Global Internet Symp., 2005.
• 26: [26] N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, and E. Teller, "Equation of state calculations by fast computing machines," The J. Chemical Phys., vol. 21, no. 6, pp. 1087-1092, 1953.
• 27: [27] Y. Moreno, R. Pastor-Satorras, and A. Vespignani, "Epidemic outbreaks in complex heterogeneous networks," Eur. Phys. J. B, vol. 26, p. 521, 2002.
• 28: [28] G. Pandurangan, P. Raghavan, and E. Upfal, "Building low-diameter peer-to-peer networks," IEEE J. Sel. Areas Commun., vol. 21, pp. 995-1002, 2003.
• 29: Young June Pyun , Douglas S. Reeves, Constructing a Balanced, (log(N)/loglog(N))-Diameter Super-Peer Topology for Scalable P2P Systems, Proceedings of the Fourth International Conference on Peer-to-Peer Computing, p.210-218, August 25-27, 2004 [doi>10.1109/P2P.2004.14]
• 30: Dongyu Qiu , R. Srikant, Modeling and performance analysis of BitTorrent-like peer-to-peer networks, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 31: [31] S. Saroui, P. K. Gummadi, and S. D. Gribble, "Measurement study of peer-to-peer file sharing systems," in Proc. Multimedia Computing and Networking, 2002.
• 32: [32] N. Sarshar and V. Roychowdhury, "Scale-free and stable structures in complex ad hoc networks," Phys. Rev. E, vol. 69, no. 2, p. 026101, 2004.
• 33: [33] D. Stutzbach, S. Zhao, and R. Rejaie, "Characterizing files in the modern gnutella network," Multimedia Syst. J., 2007.
• 34: [34] R. H. Wouhaybi and A. T. Campbell, "Phenix: Supporting resilient low-diameter peer-to-peer topologies," in Proc. IEEE INFOCOM, 2004.
• 35: [35] X. Yang and G. Veciana, "Service capacity of peer to peer networks," in Proc. IEEE INFOCOM, 2004.
• 36: [36] X. Zhang, J. Liu, B. Li, and T. P. Yum, "Coolstreaming/Donet: A data-driven overlay network for peer-to-peer live media streaming," in Proc. IEEE INFOCOM, 2005.
• 37: [37] M. Zhong, K. Shen, and J. Seiferas, "Non-uniform random membership management in peer-to-peer networks," in Proc. IEEE INFOCOM, 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.6 Simulation Output Analysis

General Terms:
Algorithms, Design, Performance

Keywords:
capacity, heterogeneity, random walk, topology, unstructured P2P network