Heuristic algorithms for optimization of task allocation and result distribution in peer-to-peer computing systems

• Autorzy: Grzegorz Chmaj , Krzysztof Walkowiak , Michał Tarnawski , Michał Kucharzak
• Języki publikacji: EN

Abstrakty

EN

Recently, distributed computing system have been gaining much attention due to a growing demand for various kinds of effective computations in both industry and academia. In this paper, we focus on Peer-to-Peer (P2P) computing systems, also called public-resource computing systems or global computing systems. P2P computing systems, contrary to grids, use personal computers and other relatively simple electronic equipment (e.g., the PlayStation console) to process sophisticated computational projects. A significant example of the P2P computing idea is the BOINC (Berkeley Open Infrastructure for Network Computing) project. To improve the performance of the computing system, we propose to use the P2P approach to distribute results of computational projects, i.e., results are transmitted in the system like in P2P file sharing systems (e.g., BitTorrent). In this work, we concentrate on offline optimization of the P2P computing system including two elements: scheduling of computations and data distribution. The objective is to minimize the system OPEX cost related to data processing and data transmission. We formulate an Integer Linear Problem (ILP) to model the system and apply this formulation to obtain optimal results using the CPLEX solver. Next, we propose two heuristic algorithms that provide results very close to an optimum and can be used for larger problem instances than those solvable by CPLEX or other ILP solvers.

Słowa kluczowe

EN

P2P computing system; distributed computing; optimization; heuristics; evolutionary algorithms

• Wydawca: University of Zielona Gora Press
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2012
• Tom: 22
• Numer: 3
• Strony: 733-748

Daty

wydano

2012

otrzymano

2011-09-08

poprawiono

2012-03-28

Twórcy

autor

Grzegorz Chmaj

• Department of Systems and Computer Networks, Faculty of Electronics, Wrocław University of Technology, Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, Poland

autor

Krzysztof Walkowiak

• Department of Systems and Computer Networks, Faculty of Electronics, Wrocław University of Technology, Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, Poland

autor

Michał Tarnawski

• Department of Systems and Computer Networks, Faculty of Electronics, Wrocław University of Technology, Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, Poland

autor

Michał Kucharzak

• Department of Systems and Computer Networks, Faculty of Electronics, Wrocław University of Technology, Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, Poland

Bibliografia

• Anderson, D.P. (2004). BOINC: A system for public-resource computing and storage, 5th IEEE/ACM International Workshop on Grid Computing, Pittsburgh, PA, USA, pp. 4-10.
• Arthur, D. and Panigrahy, R. (2006). Analyzing BitTorrent and related peer-to-peer networks, Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA'06, ACM, New York, NY, pp. 961-969, DOI: 10.1145/1109557.1109664.
• BOINC (2011). BOINC poject, http://boinc.berkeley.edu/.
• Chmaj, G. and Walkowiak, K. (2008). Data distribution in public-resource computing: Modeling and optimization, Polish Journal of Environmental Studies 17(2B): 11-20.
• Chmaj, G. and Walkowiak, K. (2009). Heuristic algorithm for optimization of P2P-based public-resource computing systems, in M. Parashar and S.K. Aggarwal (Eds.), Proceedings of the 5th International Conference on Distributed Computing and Internet Technology, ICDCIT '08, Springer-Verlag, Berlin/Heidelberg, pp. 180-187, DOI: 10.1007/978-3-540-89737-8 19.
• Chmaj, G. and Walkowiak, K. (2010a). A P2P computing system for overlay networks, Future Generation Computer Systems, DOI: 10.1016/j.future.2010.11.009.
• Chmaj, G. and Walkowiak, K. (2010b). Random approach to optimization of overlay public-resource computing systems, International Journal of Electronics and Telecommunications 56(1): 55-62.
• Christakidis, A., Efthymiopoulos, N., Fiedler, J., Dempsey, S., Koutsopoulos, K., Denazis, S. G., Tombros, S., Garvey, S. and Koufopavlou, O. G. (2011). Vital++, a new communication paradigm: Embedding P2P technology in next generation networks, IEEE Communications Magazine 49(1): 84-91.
• Cohen, B. (2003). Incentives build robustness in BitTorrent, http://www.bittorrent.org/bittorrentecon.pdf.
• Couto da Silva, A.P., Leonardi, E., Mellia, M. and Meo, M. (2011). Chunk distribution in mesh-based large-scale P2P streaming systems: A fluid approach, IEEE Transactions on Parallel and Distributed Systems 22(3): 451-463, DOI: 10.1109/TPDS.2010.63.
• Ganesan, P. and Seshadri, M. (2005). On cooperative content distribution and the price of barter, in D.C. Martin (Ed.), Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, ICDCS '05, IEEE Computer Society, Washington, DC, pp. 81-90, DOI: 10.1109/ICDCS.2005.53.
• González-Vélez, H. and Kontagora, M. (2011). Performance evaluation of MapReduce using full virtualisation on a departmental cloud, International Journal of Applied Mathematics and Computer Science 21(2): 275-284, DOI: 10.2478/v10006-011-0020-3.
• ILOG (2009). AMPL/CPLEX software, http://www.ilog.com/products/cplex/.
• Jansen, K. and Muller, H. (1994). The minimum broadcast time problem, in M. Cosnard, A. Ferreira and J. Peters (Eds.), Parallel and Distributed Computing Theory and Practice, Lecture Notes in Computer Science, Vol. 805, Springer-Verlag, Montreal, pp. 219-234.
• Jin, H., Luo, F., Zhang, Q., Liao, X. and Zhang, H. (2006). GTapestry: A locality-aware overlay network for high performance computing, in P. Bellavista and C.M. Chen (Eds.), Proceedings of the 11th IEEE Symposium on Computers and Communications, ISCC '06, IEEE Computer Society, Washington, DC, pp. 76-81, DOI: 10.1109/ISCC.2006.82.
• Kasprzak, A. (2001). Designing of Wide Area Networks, Wrocław University of Technology Press, Wrocław, (in Polish).
• Killian, C., Vrable, M., Snoeren, A.C., Vahdat, A. and Pasquale, J. (2005). The overlay network content distribution problem, Technical Report CS2005-0824 UCSD, University of California, San Diego, CA.
• Kim, H.K., Kim, J.K. and Ryu, Y.U. (2009). Personalized recommendation over a customer network for ubiquitous shopping, IEEE Transactions on Services Computing 2(2): 140-151, DOI: 10.1109/TSC.2009.7.
• Krauter, K., Buyya, R. and Maheswaran, M. (2002). A taxonomy and survey of grid resource management systems for distributed computing, International Journal of Software: Practice and Experience 32(2): 135-164, DOI: 10.1002/spe.432.
• Liu, X., Qiao, C., Yu, D. and Jiang, T. (2010). Applicationspecific resource provisioning for wide-area distributed computing, IEEE Network: The Magazine of Global Internetworking 24(4): 25-34, DOI: 10.1109/MNET.2010.5510915.
• Michalewicz, Z. (1996). Genetic Algorithms + Data Structures = Evolution Programs, 3rd Edn., Springer-Verlag, London.
• Miller, K. and Wolisz, A. (2011). Transport optimization in peer-to-peer networks, in Y. Cotronis, M. Danelutto and G.A. Papadopoulos (Eds.), Proceedings of the 2011 19th International Euromicro Conference on Parallel, Distributed and Network-Based Processing, PDP'11, IEEE Computer Society, Washington, DC, pp. 567-573, DOI: 10.1109/PDP.2011.26.
• Milojicic, D., Kalogeraki, V., Lukose, R., Nagaraja, K., Pruyne, J., Richard, B., Rollins, S., and Z, X. (2002). Peer-to-peer computing, Technical report, HP Laboratories, Palo Alto, CA, HPL-2002-57.
• Munidger, J. and Weber, R. (2004). Efficient file dissemination using peer-to-peer technology, Technical report, Statistical Laboratory Research Reports 2004-01, Cambridge.
• Nabrzyski, J., Schopf, J.M. and Weglarz, J. (Eds.) (2004). Grid Resource Management: State of the Art and Future Trends, Kluwer Academic Publishers, Norwell, MA.
• Pioro, M. and Medhi, D. (2004). Routing, Flow, and Capacity Design in Communication and Computer Networks, Morgan Kaufman Publishers, San Francisco, CA.
• Pop, F. (2012). Heuristics analysis for distributed scheduling using MONARC simulation tool, ICMS 2012: International Conference on Modeling and Simulation, Zurich, Switzerland, pp. 157-163.
• Przewozniczek, M., Walkowiak, K. and Wozniak, M. (2011). Optimizing distributed computing systems for k-nearest neighbors classifiers: Evolutionary approach, Logic Journal of IGPL 19(2): 357-372, DOI: 10.1093/jigpal/jzq034.
• Ramzan, N., Quacchio, E., Zgaljic, T., Asioli, S., Celetto, L., Izquierdo, E. and Rovati, F. (2011). Peer-to-peer streaming of scalable video in future Internet applications, IEEE Communications Magazine 49(3): 128-135, DOI: 10.1109/MCOM.2011.5723810.
• Samanta, R., Funkhouser, T. and Li, K. (2001). Parallel rendering with k-way replication, in S.N. Spencer (Ed.), Proceedings of the IEEE 2001 Symposium on Parallel and LargeData Visualization and Graphics, PVG'01, IEEE Press, Piscataway, NJ, pp. 75-84.
• Shen, X., Yu, H., Buford, J. and Akon, M. (Eds.) (2009). Handbook of Peer-to-Peer Networking, 1st Edn., Springer Publishing Company, New York, NY.
• Stutzbach, D., Zappala, D. and Rejaie, R. (2004). Swarming: Scalable content delivery for the masses, Technical Report CIS-TR-2004-1, University of Oregon, Eugene, OR.
• Suri, N., Benincasa, G., Tortonesi, M., Stefanelli, C., Kovach, J., Winkler, R., Kohler, R., Hanna, J., Pochet, L. and Watson, S. (2010). Peer-to-peer communications for tactical environments: Observations, requirements, and experiences, IEEE Communications Magazine 48(10): 60-69.
• Tarkoma, S. (2010). Overlay Networks: Toward Information Networking, 1st Edn., Auerbach Publications, Boston, MA.
• Terzo, O., Mossucca, L., Cucca, M. and Notarpietro, R. (2011). Data intensive scientific analysis with grid computing, International Journal of Applied Mathematics and Computer Science 21(2): 219-228, DOI: 10.2478/v10006-011-0016z.
• Travostino, F., Travostino, F. and Karmous-Edwards, G. (Eds.) (2006). Grid Networks Enabling Grids with Advanced Communication Technology, Wiley, Chichester.
• Vanderster, D.C., Dimopoulos, N.J., Parra-Hernandez, R. and Sobie, R.J. (2009). Resource allocation on computational grids using a utility model and the knapsack problem, Future Generation Computer Systems 25(1): 35-50, DOI: 10.1016/j.future.2008.07.006.
• Wozniak, M. (2009). Evolutionary approach to produce classifier ensemble based on weighted voting, in A. Abraham, A. Carvalho, F. Herrera and V. Pai (Eds.), Nature and Biologically Inspired Computing, IEEE, Coimbatore, pp. 648-653.
• Yang, X. and de Veciana, G. (2004). Service capacity of peer to peer networks, INFOCOM 2004. 23rd Annual Joint Conference of the IEEE Computer and Communications Societies, Hong Kong, China, Vol. 4, pp. 2242-2252.
• Zhou, Y., Chiu, D.-M. and Lui, J.C.S. (2011). A simple model for chunk-scheduling strategies in P2P streaming, IEEE/ACM Transactions on Networking 19(1): 42-54, DOI: 10.1109/TNET.2010.2065237.

Identyfikatory

DOI

10.2478/v10006-012-0055-0