Comparison of Evolutionary Algorithm and Heuristics for Flow Optimization in P2P Systems

• Autorzy: Kucharzak M. , Siwek A. , Walkowiak K.
• Języki publikacji: EN

Abstrakty

EN

Nowadays, many Internet users make use of Peer-to-Peer (P2P) systems to download electronic content including music, movies, software, etc. Growing popularity in P2P based protocol implementations for file sharing purposes caused that the P2P traffic exceeds Web traffic and in accordance with to many statistics, P2P systems produce a more than 50% of the whole Internet traffic. Therefore, P2P systems provide remarkable income for Internet Service Providers (ISP). However, at the same time P2P systems generates many problems related to traffic engineering, optimization, network congestion. In this paper we focus on the problem of flow optimization in P2P file sharing systems. Corresponding to BitTorrent-based systems behaviour, the optimization of P2P flows is very complex and in this work we consider different heuristic strategies for content distribution and moreover we propose a new evolutionary algorithm (EA) for this problem. We compare results of the algorithms against optimal results yielded by CPLEX solver for networks including 10 peers and relation to random algorithm for 100-node systems. According to numerical experiments, the EA provides solutions close to optimal for small instances and all of the heuristics exhibit a superior performance over random search.

Słowa kluczowe

EN

P2P; flows; network optimization

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2010
• Tom: Vol. 56, No. 2
• Strony: 145--152
• Opis fizyczny: Bibliogr. 36 poz.

Twórcy

autor

Kucharzak M.

autor

Siwek A.

autor

Walkowiak K.

• Department of Systems and Computer Networks, Wroclaw University of Technology, Poland

Bibliografia

• [1] V. Aggarwal, A. Feldmann, and C. Scheideler, “Can ISPS and P2P users cooperate for improved performance?” SIGCOMM Comput. Commun. Rev., vol. 37, no. 3, pp. 29–40, July 2007.
• [2] B. Akbari, H. R. Rabiee, and M. Ghanbari, “An optimal discrete rate allocation for overlay video multicasting,” Comput. Commun., vol. 31, no. 3, pp. 551–562, 2008.
• [3] D. Arthur and R. Paningrahy, “Analyzing BitTorrent and Related Peerto-Peer Networks,” In: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pp. 961–969, 2006.
• [4] A. Bharambe, C. Herley, and V. Padmanabhan, “Analyzing and Improving BitTorrent Performance,” In: Proceedings of IEEE INFOCOM, 2006.
• [5] S.-S. Byun and C. Yoo, “Minimum dvs gateway deployment in dvsbased overlay streaming,” Comput. Commun., vol. 31, no. 3, pp. 537–550, 2008.
• [6] Y. Chen, J. Edler, A. Goldberg, A. Gottlieb, S. Sobti, and P. Yianilos, “A Prototype Implementation of Archival Intermemory,” In: Proceedings of the Fourth ACM International Conference on Digital Libraries, 1999.
• [7] Cisco Systems, “Cisco visual networking index forecast and methodology, 20072012,” White Paper, 2008.
• [8] B. Cohen, “Incentives build robustness in bittorrent,” Online, available at http://www.bittorrent.org/bittorrentecon.pdf, 2003.
• [9] P. Druschel and A. Rowstron, “PAST: A Large-scale, Persistent Peerto-Peer Storage utility,” In: Procedings of HOTOS, pp. 75–80, 2001.
• [10] P. Ganesan and M. Seshadri, “On cooperative content distribution and the price of barter,” in In proc. of the 25th IEEE International Conference on Distributed Computing Systems, 2005.
• [11] ILOG, Inc, “ILOG CPLEX 11.0: User’s manual,” France, 2007.
• [12] A. Iosup, R. Iosup, P. Garbacki, J. Pouwelse, and D. Epema, “Correlating topology and path characteristics of overlay networks and the internet,” in In 6th Int. Workshop on Global and Peer-to-Peer Computing (GP2PC), held in conjunction with the IEEE/ACM CCGrid, 2006.
• [13] Ipoque, “Internet study 2007,” Online, available at http://www.ipoque.com/resources/internet-studies/internet-study-2007, 2007.
• [14] Ipoque, “Internet study 2008/2009,” Online, available at http://www.ipoque.com/resources/internet-studies/internet-study-2008 2009, 2008.
• [15] C. Killian, M. Vrable, A. C. Snoeren, A. Vahdat, and J. Pasquale, “The overlay network content distribution problem,” UCSD/CSE, Tech. Rep. CS2005-0824, 2005.
• [16] J. Kubiatowicz, D. Bindel, Y. Chen, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, W. Weimer, C. Wells, and B. Zhao, “Oceanstore: An Architecture for Global-scale Persistent Storage,” In:Proceedings of ACM ASPLOS, New York, 2000.
• [17] M. Kucharzak and K. Walkowiak, “File Sharing-based Heuristics for Flow Assignment in P2P Systems,” in 2nd International Symposium on Logistics and Industrial Informatics LINDI 2009, Linz, Austria, September 2009.
• [18] M. Kucharzak and K. Walkowiak, “Optimal flows in peer-to-peer based architectures for file sharing services,” in Proc. of the 16th Polish Teletraffic Symposium PTS 2009, Lodz, Poland, September 2009.
• [19] B. Leuf, Peer to Peer: Collaboration and Sharing over the Internet. Addison Wesley, 2002.
• [20] L. Massoulie and M. Vojnovic, “Coupon replication systems,” SIGMET-RICS Perform. Eval. Rev., vol. 33, no. 1, pp. 2–13, 2005.
• [21] Z. Michalewicz, Genetic algorithms + data structures = evolution programs (3rd ed.). London, UK: Springer-Verlag, 1996.
• [22] J. Mundinger and R. R. Weber, “Efficient file dissemination using peerto-peer technology,” Statistical Laboratory Research Reports, Tech. Rep. 2004–01, 2004.
• [23] A. Oram, Ed., Peer-to-Peer : Harnessing the Power of Disruptive Technologies. O’Reilly, 2001.
• [24] M. Pi´oro and D. Medhi, Routing, Flow, and Capacity Design in Communication and Computer Networks. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2004.
• [25] R. Steinmetz and K. Wehrle, Peer-to-Peer Systems and Applications (Lecture Notes in Computer Science). Secaucus, NJ, USA: Springer-Verlag New York, Inc., 2005.
• [26] K. Walkowiak, “Offline Approach to Modeling and Optimization of Flows in Peer-to-Peer Systems,” in Proc. NTMS 2008 - New Technologies, Mobility and Security. Tangier, Morocco: IEEE Press, November 2008, pp. 1–5.
• [27] K. Walkowiak, “On Transfer Costs in Peer-to-Peer Networks Systems: Modeling and Optimization,” in Proc. PGTS 2008 - 5th Polish-German Teletraffic Symposium, Berlin, Germany, October 2008, pp. 217–226.
• [28] K. Walkowiak and M. Kucharzak, “New Approaches to Modeling of Flows in Peer-to-Peer Systems,” in Proc. Modelling and Simulation of Systems MOSIS 2009. Roznov pod Radhostem, Czech Republic: Ostrava: MARQ, April 2009.
• [29] C. Wu and B. Li, “On Meeting P2P Streaming Bandwidth Demand with Limited Supplies,” in Proc. of the Fifteenth Annual SPIE/ACM International Conference on Multimedia Computing and Networking (MMCN 2008), 2008.
• [30] C. Wu, C. Li, and J. Ho, “Improving the Download Time of BitTorrentlike Systems,” In: Proceedings of IEEE International Conference on Communications, pp. 1125–1129, 2007.
• [31] G. Wu and T. Chiueh, “Peer to peer file download and streaming. Rpe report, tr-185,” 2005.
• [32] J. Wu, Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless and Peer-to-Peer Networks. Auerbach Publications, 2006.
• [33] S. Yamazaki, H. Tode, and K. Murakami, “Cat: A cost-aware bittorrent,” in In Proc. of 32nd IEEE Conference on Local Computer Networks, 2007, pp. 609–614.
• [34] X. Yang and G. de Veciana, “Service capacity of peer to peer networks,” in In proc. of INFOCOM 2004, 2004, pp. 2242–2252.
• [35] L. Ying and A. Basu, “Traceroute-based fast peer selection without offline database,” in ISM ’06: Proceedings of the Eighth IEEE International Symposium on Multimedia. Washington, DC, USA: IEEE Computer Society, 2006, pp. 609–614.
• [36] Y. Zhu and B. Li, “Overlay networks with linear capacity constraints,” IEEE Trans. Parallel Distrib. Syst., vol. 19, no. 2, pp. 159–173, 2008.