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

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

International Journal of Applied Mathematics and Computer Science (2012)

  • Volume: 22, Issue: 3, page 733-748
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Grzegorz Chmaj, et al. "Heuristic algorithms for optimization of task allocation and result distribution in peer-to-peer computing systems." International Journal of Applied Mathematics and Computer Science 22.3 (2012): 733-748. <http://eudml.org/doc/244054>.

@article{GrzegorzChmaj2012,
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 close to an optimum and can be used for larger problem instances than those solvable by CPLEX or other ILP solvers.},
author = {Grzegorz Chmaj, Krzysztof Walkowiak, Michał Tarnawski, Michał Kucharzak},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {P2P computing system; distributed computing; optimization; heuristics; evolutionary algorithms},
language = {eng},
number = {3},
pages = {733-748},
title = {Heuristic algorithms for optimization of task allocation and result distribution in peer-to-peer computing systems},
url = {http://eudml.org/doc/244054},
volume = {22},
year = {2012},
}

TY - JOUR
AU - Grzegorz Chmaj
AU - Krzysztof Walkowiak
AU - Michał Tarnawski
AU - Michał Kucharzak
TI - Heuristic algorithms for optimization of task allocation and result distribution in peer-to-peer computing systems
JO - International Journal of Applied Mathematics and Computer Science
PY - 2012
VL - 22
IS - 3
SP - 733
EP - 748
AB - 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.
LA - eng
KW - P2P computing system; distributed computing; optimization; heuristics; evolutionary algorithms
UR - http://eudml.org/doc/244054
ER -

References

top
  1. 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. 
  2. 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. Zbl1192.68066
  3. BOINC (2011). BOINC poject, http://boinc.berkeley.edu/. 
  4. Chmaj, G. and Walkowiak, K. (2008). Data distribution in public-resource computing: Modeling and optimization, Polish Journal of Environmental Studies 17(2B): 11-20. 
  5. 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. 
  6. 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. 
  7. 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. 
  8. 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. 
  9. Cohen, B. (2003). Incentives build robustness in BitTorrent, http://www.bittorrent.org/bittorrentecon.pdf. 
  10. 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. 
  11. 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. 
  12. 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. 
  13. ILOG (2009). AMPL/CPLEX software, http://www.ilog.com/products/cplex/. 
  14. 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. 
  15. 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. 
  16. Kasprzak, A. (2001). Designing of Wide Area Networks, Wrocław University of Technology Press, Wrocław, (in Polish). 
  17. 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. 
  18. 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. 
  19. 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. Zbl0987.68786
  20. 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. 
  21. Michalewicz, Z. (1996). Genetic Algorithms + Data Structures = Evolution Programs, 3rd Edn., Springer-Verlag, London. Zbl0841.68047
  22. 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. 
  23. 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. 
  24. Munidger, J. and Weber, R. (2004). Efficient file dissemination using peer-to-peer technology, Technical report, Statistical Laboratory Research Reports 2004-01, Cambridge. 
  25. 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. Zbl1027.68006
  26. Pioro, M. and Medhi, D. (2004). Routing, Flow, and Capacity Design in Communication and Computer Networks, Morgan Kaufman Publishers, San Francisco, CA. Zbl1069.68021
  27. 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. 
  28. 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. 
  29. 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. 
  30. 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. 
  31. 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. Zbl1214.68051
  32. 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. 
  33. 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. 
  34. Tarkoma, S. (2010). Overlay Networks: Toward Information Networking, 1st Edn., Auerbach Publications, Boston, MA. 
  35. 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. 
  36. Travostino, F., Travostino, F. and Karmous-Edwards, G. (Eds.) (2006). Grid Networks Enabling Grids with Advanced Communication Technology, Wiley, Chichester. 
  37. 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. 
  38. 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. 
  39. 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. 
  40. 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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.