Optimization of p2p-based distributed systems

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

Abstrakty

EN

Various kinds of distributed systems gain much attention in recent years. One of the most significant example is the Peer-to-Peer (P2P) paradigm widely used in many applications including: file-sharing systems (e.g. BitTorrent), computing systems (e.g. SETI@home), communication systems (e.g. Skype) and many others. In this work we present our latest research related to the problem of P2P-based distributed systems optimization. We consider two following problems: optimization of data distribution P2P systems and optimization of P2P computing systems. For both problems we formulate Integer Programming models. Due to the complexity of these problems, exact methods can be applied only for relatively small instances. Therefore, we propose several heuristic algorithms including tabu search, evolutionary algorithm, constructive heuristic and random approach. Results of extensive numerical experiments show the effectiveness of proposed algorithms in comparison to optimal results yielded by CPLEX solver. The optimization methods presented in this paper can be used for optimization of various P2P systems.

Słowa kluczowe

EN

optimization; P2P; distributed systems

PL

optymalizacja; P2P; systemy rozproszone

• Wydawca: Wydawnictwo Politechniki Łódzkiej
• Czasopismo: Journal of Applied Computer Science
• Rocznik: 2011
• Tom: Vol. 19, nr 1
• Strony: 117--138
• Opis fizyczny: Bibliogr. 35 poz.

Twórcy

autor

Walkowiak K.

autor

Chmaj G.

autor

Kucharzak M.

autor

Siwek A.

autor

Skowron J.

• Wroclaw University of Technology, Chair of Systems and Computer Networks, Wybrzeze Wyspianskiego 27, 50-370 Wroclaw,

Bibliografia

• [1] Aggarwal, V., Feldmann, A., and Scheideler, C., Can ISPS and P2P users cooperate for improved performance? SIGCOMM Comput. Commun. Rev., Vol. 37, No. 3, July 2007, pp. 29-40.
• [2] Steinmetz, R. and Wehrle, K., Peer-to-Peer Systems and Applications (Lecture Notes in Computer Science), Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2005.
• [3] Kulbak, Y. and Bickson, D., The eMule protocol specification, School of Computer Science and Engineering, The Hebrew University of Jerusalem, Jerusalem, January 2005.
• [4] Maymounkov, P. and Mazieres, D., Kademlia: A Peer-to-peer Information System Based on the XOR Metric, In Proceedings of the 1st International Workshop on Peer-to Peer Systems (IPTPS02), 2002.
• [5] Walkowiak, K., O_ine Approach to Modeling and Optimization of Flows in Peer-to-Peer Systems, In: Proc. NTMS 2008 - New Technologies, Mobility and Security, IEEE Press, Tangier, Morocco, November 2008, pp. 1-5.
• [6] Wu, J., Handbook On Theoretical And Algorithmic Aspects Of Sensor, Ad Hoc Wireless, and Peer-to-Peer Networks, Auerbach Publications, Boston, MA, USA, 2005.
• [7] Subramanian, R. and Goodman, B. D., Peer to Peer Computing: The Evolution of a Disruptive Technology, IGI Publishing, Hershey, PA, USA, 2005.
• [8] ILOG, Inc, ILOG CPLEX 11.0: User's Manual, 2007.
• [9] Killian, C., Vrable, M., Snoeren, A. C., Vahdat, A., and Pasquale, J., The Overlay Network Content Distribution Problem, Tech. rep. cs2005-0824, UCSD/CSE, 2005.
• [10] Krauter, K., Buyya, R., and Maheswaran, M., A Taxonomy and Survey of Grid Resource Management Systems for Distributed Computing, Softw. Pract. Exper., Vol. 32, No. 2, 2002, pp. 135-164.
• [11] Milojicic, D., Kalogeraki, V., Lukose, R., Nagaraja, K., Pruyne, J., Richard, B., Rollins, S., and Xu, Z., Peer-to-Peer Computing, Tech. Rep. HPL-2002-57, HP Laboratories Palo Alto, March 2002.
• [12] Mundinger, J. and Weber, R. R., E_cient File Dissemination using Peer-to-Peer Technology, Tech. rep. 2004-01, Statistical Laboratory Research Reports, 2004.
• [13] Taylor, I. J., From P2P to Web Services and Grids, Springer, London, 2005.
• [14] Walkowiak, K. and Chmaj, G., Data Distribution in Public-Resource Computing: Modeling and Optimization, Polish Journal of Environmental Studies, Vol. 17, No. 2B, 2008, pp. 11-20.
• [15] Wu, C. and Li, B., On Meeting P2P Streaming Bandwidth Demand with Limited Supplies, In: In Proc. of SPIE/ACM International Conference on Multimedia Computing and Networking, 2008.
• [16] Zhu, Y., Overlay Networks with Linear Capacity Constraints, IEEE Trans. Parallel Distrib. Syst., Vol. 19, No. 2, 2008, pp. 159-173, Senior Member-Li, Baochun.
• [17] Akbari, B., Rabiee, H. R., and Ghanbari, M., An Optimal Discrete Rate Allocation for Overlay Video Multicasting, Comput. Commun., Vol. 31, No. 3, 2008, pp. 551-562.
• [18] Christin, N. and Chuang, J., On the Cost of Participating in a Peer-to-Peer Network, Lecture Notes in Computer Science, Vol. 3279, 2004, pp. 22-32.
• [19] Pióro, M. and Medhi, D., Routing, Flow, and Capacity Design in Communication and Computer Networks, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2004.
• [20] Walkowiak, K., On Transfer Costs in Peer-to-Peer Networks Systems: Modeling and Optimization, In: Proc. PGTS 2008 - 5th Polish-German Teletra_c Symposium, Berlin, Germany, October 2008, pp. 217-226.
• [21] Walkowiak, K. and Kucharzak, M., New Approaches to Modeling of Flows in Peer-to-Peer Systems, In: Proc. Modelling and Simulation of Systems MOSIS 2009, Ostrava: MARQ, Roznov pod Radhostem, Czech Republic, April 2009.
• [22] Kucharzak, M. and Walkowiak, K., Optimal flows in peer-to-peer based architectures for file sharing services, In: Proc. of the 16th Polish Teletra_c Symposium PTS 2009, Lodz, Poland, September 2009.
• [23] Anderson, D. P., Cobb, J., Korpela, E., Lebofsky, M., and Werthimer, D., SETI@home: an experiment in public-resource computing, Commun. ACM, Vol. 45, No. 11, 2002, pp. 56-61.
• [24] Foster, I. and Iamnitchi, A., On Death, Taxes, and the Convergence of Peerto-Peer and Grid Computing, Lecture Notes in Computer Science, Vol. 2735, 2003, pp. 118-128.
• [25] Nabrzyski, J., Schopf, J. M., and Weglarz, J., editors, Grid resource management: state of the art and future trends, Kluwer Academic Publishers, Norwell, MA, USA, 2004.
• [26] Samanta, R., Funkhouser, T., and Li, K., Parallel Rendering with K-Way Replication, In: PVG '01: Proceedings of the IEEE 2001 Symposium on Parallel and Large-Data Visualization and Graphics, IEEE Press, Piscataway, NJ, USA, 2001, pp. 75-84.
• [27] Cohen, B., Incentives Build Robustness in BitTorrent, Online, available at http://www.bittorrent.org/bittorrentecon.pdf, 2003.
• [28] Bharambe, A. R., Herley, C., and Padmanabhan, V. N., Analyzing and Improving a BitTorrent Network's Performance Mechanisms, 2006.
• [29] Kucharzak, M. and Walkowiak, K., 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.
• [30] Wu, C. and Li, B., 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.
• [31] Gendreau, M., An Introduction to Tabu Search, Universite de Montreal, Canada, 2002.
• [32] Glover, F. and Laguna, M., Tabu Search, Springer, 1997.
• [33] Skowron, J. and Walkowiak, K., Optimization of data distribution in peer-to-peer networks using tabu search algorithm, In: Proc. PTS 2009 - Polish Teletraffic Symposium, Lodz, Poland, October 2009.
• [34] Siwek, A. and Walkowiak, K., Evolutionary Algorithm for Flow Optimization in P2P Systems, In: Proc. BroadBandCom 2009 - 4th International Conference on Broadband Communication, Information Technology & Biomedical Applications, Lodz, Poland, September 2009.
• [35] Chmaj, G. and Walkowiak, K., Heuristic Algorithm for Optimization of P2Pbased Public-Resource Computing Systems, In: ICDCIT '08: Proceedings of the 5th International Conference on Distributed Computing and Internet Technology, Springer-Verlag, Berlin, Heidelberg, 2009, pp. 180-187.