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

Chmaj, Grzegorz; Walkowiak, Krzysztof; Tarnawski, Michał; Kucharzak, Michał

doi:10.2478/v10006-012-0055-0

Abstract

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

References

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.
Search in Google Scholar
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/.
Search in Google Scholar
Chmaj, G. and Walkowiak, K. (2008). Data distribution in public-resource computing: Modeling and optimization, Polish Journal of Environmental Studies 17(2B): 11-20.
Search in Google Scholar
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.10.1007/978-3-540-89737-8
Search in Google Scholar
Chmaj, G. andWalkowiak, K. (2010a). A P2P computing system for overlay networks, Future Generation Computer Systems, DOI: 10.1016/j.future.2010.11.009.10.1016/j.future.2010.11.009
Search in Google Scholar
Chmaj, G. andWalkowiak, K. (2010b). Random approach to optimization of overlay public-resource computing systems, International Journal of Electronics and Telecommunications 56(1): 55-62.10.2478/v10177-010-0007-2
Search in Google Scholar
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.10.1109/MCOM.2011.5681020
Search in Google Scholar
Cohen, B. (2003). Incentives build robustness in BitTorrent, http://www.bittorrent.org/bittorrentecon.pdf.
Search in Google Scholar
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.10.1109/TPDS.2010.63
Search in Google Scholar
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.10.1109/ICDCS.2005.53
Search in Google Scholar
Gonz´alez-V´elez, 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/.
Search in Google Scholar
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.10.1007/3-540-58078-6_19
Search in Google Scholar
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.10.1109/ISCC.2006.82
Search in Google Scholar
Kasprzak, A. (2001). Designing of Wide Area Networks, Wrocław University of Technology Press, Wrocław, (in Polish).
Search in Google Scholar
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.
Search in Google Scholar
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.10.1109/TSC.2009.7
Search in Google Scholar
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.10.1002/spe.432
Search in Google Scholar
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.10.1109/MNET.2010.5510915
Search in Google Scholar
Michalewicz, Z. (1996). Genetic Algorithms + Data Structures = Evolution Programs, 3rd Edn., Springer-Verlag, London.
Search in Google Scholar
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.10.1109/PDP.2011.26
Search in Google Scholar
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.
Search in Google Scholar
Munidger, J. and Weber, R. (2004). Efficient file dissemination using peer-to-peer technology, Technical report, Statistical Laboratory Research Reports 2004-01, Cambridge.
Search in Google Scholar
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.
Search in Google Scholar
Pioro, M. and Medhi, D. (2004). Routing, Flow, and Capacity Design in Communication and Computer Networks, Morgan Kaufman Publishers, San Francisco, CA.10.1016/B978-012557189-0/50011-1
Search in Google Scholar
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.
Search in Google Scholar
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.10.1093/jigpal/jzq034
Search in Google Scholar
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.10.1109/MCOM.2011.5723810
Search in Google Scholar
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 Large-Data Visualization and Graphics, PVG’01, IEEE Press, Piscataway, NJ, pp. 75-84.10.1109/PVGS.2001.964407
Search in Google Scholar
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.
Search in Google Scholar
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.
Search in Google Scholar
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.10.1109/MCOM.2010.5594678
Search in Google Scholar
Tarkoma, S. (2010). Overlay Networks: Toward Information Networking, 1st Edn., Auerbach Publications, Boston, MA.
Search in Google Scholar
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-0016-z.10.2478/v10006-011-0016-z
Search in Google Scholar
Travostino, F., Travostino, F. and Karmous-Edwards, G. (Eds.) (2006). Grid Networks Enabling Grids with Advanced Communication Technology, Wiley, Chichester.10.1002/0470028696
Search in Google Scholar
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.10.1016/j.future.2008.07.006
Search in Google Scholar
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.10.1109/NABIC.2009.5393446
Search in Google Scholar
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.
Search in Google Scholar
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.10.1109/TNET.2010.2065237
Search in Google Scholar

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

Abstract

Paradigm

My account