TitleComparison of Evolutionary Algorithm and Heuristics for Flow Optimization in P2P Systems
Journal titleInternational Journal of Electronics and Telecommunications
Divisions of PASNauki Techniczne
AbstractComparison of Evolutionary Algorithm and Heuristics for Flow Optimization in P2P Systems 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.
PublisherPolish Academy of Sciences Committee of Electronics and Telecommunications
IdentifierISSN 2081-8491 (until 2012) ; eISSN 2300-1933 (since 2013)
ReferencesAggarwal V. (2007), Can ISPS and P2P users cooperate for improved performance?, SIGCOMM Comput. Commun. Rev, 37, 3, 29, doi.org/10.1145/1273445.1273449 ; Akbari B. (2008), An optimal discrete rate allocation for overlay video multicasting, Comput. Commun, 31, 3, 551, doi.org/10.1016/j.comcom.2007.08.025 ; Arthur D. (2006), Analyzing BitTorrent and Related Peer-to-Peer Networks, null, 961. ; Bharambe A. (2006), Analyzing and Improving BitTorrent Performance, null. ; Byun S.-S. (2008), Minimum dvs gateway deployment in dvsbased overlay streaming, Comput. Commun, 31, 3, 537, doi.org/10.1016/j.comcom.2007.08.018 ; Chen Y. (1999), A Prototype Implementation of Archival Intermemory, null. ; Cisco Systems, "Cisco visual networking index forecast and methodology, 20072012," White Paper, 2008. ; B. Cohen, "Incentives build robustness in bittorrent," Online, available at <a target="_blank" href='http://www.bittorrent.org/bittorrentecon.pdf'>http://www.bittorrent.org/bittorrentecon.pdf</a> ; Druschel P. (2001), PAST: A Large-scale, Persistent Peer-to-Peer Storage utility, null, 75. ; Ganesan P. (2005), On cooperative content distribution and the price of barter, null. ; ILOG, Inc, "ILOG CPLEX 11.0: User's manual," France, 2007. ; Iosup A. (2006), Correlating topology and path characteristics of overlay networks and the internet, null. ; Ipoque, "Internet study 2007," Online, available at <a target="_blank" href='http://www.ipoque.com/resources/internet-studies/internet-study-2007'>http://www.ipoque.com/resources/internet-studies/internet-study-2007</a> ; Ipoque, "Internet study 2008/2009," Online, available at <a target="_blank" href='http://www.ipoque.com/resources/internet-studies/internet-study-2008_2009'>http://www.ipoque.com/resources/internet-studies/internet-study-2008_2009</a> ; 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. ; Kubiatowicz J. (2000), Oceanstore: An Architecture for Global-scale Persistent Storage, null. ; Kucharzak M. (2009), File Sharing-based Heuristics for Flow Assignment in P2P Systems, null. ; Kucharzak M. (2009), Optimal flows in peer-to-peer based architectures for file sharing services, null. ; Leuf B. (2002), Peer to Peer: Collaboration and Sharing over the Internet. ; Massoulie L. (2005), Coupon replication systems, SIGMETRICS Perform. Eval. Rev, 33, 1, 2, doi.org/10.1145/1071690.1064215 ; Michalewicz Z. (1996), Genetic algorithms + data structures = evolution programs, doi.org/10.1007/978-3-662-03315-9 ; J. Mundinger and R. R. Weber, "Efficient file dissemination using peer-to-peer technology," Statistical Laboratory Research Reports, Tech. Rep. 2004-01, 2004. ; (2001), Peer-to-Peer : Harnessing the Power of Disruptive Technologies. ; Pióro M. (2004), Routing, Flow, and Capacity Design in Communication and Computer Networks. ; Steinmetz R. (2005), Peer-to-Peer Systems and Applications (Lecture Notes in Computer Science). ; Walkowiak K. (2008), Offline Approach to Modeling and Optimization of Flows in Peer-to-Peer Systems, null, 1. ; Walkowiak K. (2008), On Transfer Costs in Peer-to-Peer Networks Systems: Modeling and Optimization, null, 217. ; Walkowiak K. (2009), New Approaches to Modeling of Flows in Peer-to-Peer Systems, null. ; Wu C. (2008), On Meeting P2P Streaming Bandwidth Demand with Limited Supplies, null. ; Wu C. (2007), Improving the Download Time of BitTorrentlike Systems, null, 1125. ; G. Wu and T. Chiueh, "Peer to peer file download and streaming. rpe report, tr-185," 2005. ; Wu J. (2006), Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless and Peer-to-Peer Networks. ; Yamazaki S. (2007), Cat: A cost-aware bittorrent, null, 609. ; Yang X. (2004), Service capacity of peer to peer networks, null, 2242. ; Ying L. (2006), Traceroute-based fast peer selection without offline database, null, 609. ; Zhu Y. (2008), Overlay networks with linear capacity constraints, IEEE Trans. Parallel Distrib. Syst, 19, 2, 159, doi.org/10.1109/TPDS.2007.70726