On the Impact of Path Redundancy Awareness in Evolutionary P2P Networking
Elizabeth Pérez-Cortés* and Hiroyuki Sato**
*Electrical Engineering Department, Universidad Autónoma Metropolitana Iztapalapa, San Rafael Atlixco No. 186, Col. Vicentina, 09340, México D.F., Mexico
**Faculty of Informatics and Engineering, The University of Electro-Communications, 1-5-1 Chofugaoka, Chofu, Tokyo 182-8585, Japan
A P2P system is composed by autonomous nodes interconnected to share resources. The interconnections between the nodes define the P2P topology that is traversed to lookup resources. As nodes are autonomous, they are free to decide when to arrive and leave and what resources to share and download. To cope with this dynamism, the Evolutionary P2P Networking approach performs a periodical P2P topology reconfiguration applying evolutionary computation and using the amount of successful lookups as the evaluation function that drives the process. We extended this approach to also consider, as a part of the evaluation function, the creation of redundant paths in the topology and, additionally, we introduced elitism to improve the evolutionary process. In this work we present an extensive evaluation of both approaches. The results show that our approach scales better and produces more connected topologies. The improved connectivity ensures a higher rate of successful lookups under static and dynamic scenarios.
-  A. Passarella, “Review: A Survey on Content-Centric Technologies for the Current Internet: CDN and P2P Solutions,” Computer Communications, Vol.35, No.1, pp. 1-32, Elsevier Science Publishers B. V., 2012.
-  S. Androutsellis-Theotokis and D. Spinellis, “A Survey of Peerto-Peer Content Distribution Technologies,” ACM Computing Surveys, Vol.36, No.4, pp. 335-371, 2004.
-  S.M. Thampi and K. C. Sekaran, “Survey of Search and Replication Schemes in Unstructured P2P Networks,” Network Protocols and Algorithms, Vol.2, No.1, pp. 93-131, 2010.
-  E. Leontiadis, V. V. Dimakopoulos, and E. Pitoura, “Creating and Maintaining Replicas in Unstructured Peer-to-Peer Systems,” Proc. of the 12th Int. Conf. on Parallel Processing, pp. 1015-1025, 2006.
-  W. K. Lin, C. Ye, and D. M. Chiu, “Decentralized Replication Algorithms for Improving File Availability in P2P Networks,” Proc. of the 15th IEEE Int. Workshop on Quality of Service, pp. 29-37, 2007.
-  B. F. Cooper, “An Optimal Overlay Topology for Routing Peer-to-Peer Searches,” Proc. of the ACM/IFIP/USENIX 2005 Int. Conf. on Middleware, pp. 82-101, 2005.
-  B. F. Cooper, “Quickly Routing Searches Without Having to Move Content,” Proc. of the 4th Int. Workshop on Peer-to-Peer Systems, pp. 163-172, 2005.
-  B. Cohen, “Incentives Build Robustness in BitTorrent,” Proc. of the First Workshop on Economics of Peer-to-Peer Systems, 2003.
-  M. Jelasity, R. Guerraoui, A.-M. Kermarrec, and M. van Steen, “The Peer Sampling Service: Experimental Evaluation of Unstructured Gossip-Based Implementations,” Proc. of the 5th ACM/IFIP/USENIX Int. Conf. on Middleware, pp. 79-98, 2004.
-  F. Harary and E. M. Palmer, “Graphical Enumeration,” Academic Press, 1973.
-  D. E. Goldberg, “Genetic Algorithms in Search, Optimization and Machine Learning,” Addison-Wesley Longman Publishing Co., Inc., 1989.
-  S. G. M. Koo, C. S. G. Lee, and K. Kannan, “A Genetic-Algorithm-Based Neighbor-Selection Strategy for Hybrid Peer-to-Peer Networks,” Proc. of the 13th IEEE Int. Conf. on Computer Communications and Networks, pp. 469-474, 2004.
-  K. A. Lehmann and M. Kaufmann, “Evolutionary Algorithms for the Self-Organized Evolution of Networks,” Proc. of the 2005 Conf. on Genetic and Evolutionary Computation, pp. 563-570, 2005.
-  P. Merz and S. Wolf, “Evolutionary Local Search for Designing Peer-to-Peer Overlay Topologies Based on Minimum Routing Cost Spanning Trees,” Proc. of the 9th Int. Conf. on Parallel Problem Solving from Nature, pp. 272-281, 2006.
-  K. Ohnishi and Y. Oie, “Evolutionary P2P Networking that Fuses Evolutionary Computation and P2P Networking Together,” IEICE Trans., Vol.E93-B, No.2, pp. 317-327, 2010.
-  E. Pérez-Cortés and H. Sato, “Evolutionary P2P Networking using a Path Redundancy Aware Evaluation,” Asia Pacific Symp. of Intelligent and Evolutionary Systems 2012, pp. 19-24, 2012.
-  D. Stutzbach and R. Rejaie, “Understanding Churn in Peer-to-Peer Networks,” Proc. of the 6th ACM SIGCOMM Conf. on Internet Measurement, pp. 189-202, 2006.
-  “The Annotated Gnutella Protocol Specification v0.4,” TheoryOrg.
-  E. Pérez-Cortés and H. Sato, “Towards a Distributed Evolutionary P2P Networking Using a Gene Transfer Operation,” Symp. on Evolutionary Computation 2012, pp. 359-365, 2012.
-  K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A Fast and Elitist Multi-Objective Genetic Algorithm: NSGA-II,” IEEE Trans. on Evolutionary Computation, Vol.6, No.2, pp. 182-197, IEEE Press, 2002.
-  E. Zitzler and L. Thiele, “Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach,” Trans. Evol. Comp, Vol.3, No.4, pp. 257-271, 1999.
-  H. Jain and K. Deb, “An Improved Adaptive Approach for Elitist Nondominated Sorting Genetic Algorithm for Many-Objective Optimization,” Proc. of the 7th Int. Conf. on Evolutionary Multi-Criterion Optimization, pp. 307-321, 2013.
-  J. Li, J. Stribling, T. M. Gil, R. Morris, and M. F. Kaashoek, “Comparing the Performance of Distributed Hash Tables Under Churn,” Proc. of the Third Int’l Workshop on Peer-to-Peer Systems, pp. 87-99, 2004.
-  O. Zhonghong, E. Harjula, and M. Ylianttila, “Effects of Different Churn Models on the Performance of Structured Peer-to-Peer Networks,” IEEE 20th Int. Symp. on Personal, Indoor and Mobile Radio Communications, pp. 2856-2860, 2009.
-  G. Dán and N. Carlsson, “Power-law Revisited: Large Scale Measurement Study of P2P Content Popularity,” Proc. of the 9th Int. Workshop on Peer-to-Peer Systems, pp. 1-5, 2010.
-  M. Zhong, “Popularity-Biased Random Walks for Peer-to-Peer Search Under the Square-Root Principle,” Proc. of the 5th Int. Workshop on Peer-to-Peer Systems, 2006.