Abstract
In this work we present analytic expressions for the expected values of the performance metrics of parallel applications when the distributed computing infrastructure has a complex topology. Through active probing tests we analyse the structure of a real distributed computing environment. From the resulting network we both validate the analytic expressions and explore the performance metrics under different conditions through Monte Carlo simulations. In particular we gauge computing paradigms with different hierarchical structures in computing services. Fully decentralised (i.e., peer-to-peer) environments provide the best performance. Moreover, we show that it is possible to improve significantly the parallel efficiency by implementing more intelligent configurations of computing services and task allocation strategies (e.g., by using a betweenness centrality measure). We qualitatively reproduce results of previous works and provide closed-form solutions that link topology, application’s structure and allocation parameters when job dependencies and a complex network structure are considered.
Similar content being viewed by others
References
Barabási, A.: Scale-free networks: a decade and beyond. Science 325(5939), 412 (2009)
Kahanwal, B., Singh, T.P.: The Distributed Computing Paradigms: P2P, Grid, Cluster, Cloud, and Jungle. Int. J. Latest Res. Sci. Technol. 1(2), 183–187 (2012)
Foster, I., Kesselman, C., Tuecke, S.: The anatomy of the grid: Enabling scalable virtual organizations. Int. J. High Perform. Comput. Appl. 15(3), 200 (2001)
Buyya, R., Brogerg, J.: Cloud computing: principles and paradigms. Wiley series on parallel and distributed computing. Wiley-Blackwell (2011)
Karagiannis, T.: Filesharing in the internet: A characterization of p2p traffic in the backbone. Tech. rep., UC Riverside (2003)
Muttoni, L., Casale, G., Granata, F., Zanero, S.: Optimal number of nodes for computation in grid environments. In: Proceedings of the 12th Euromicro Conference on Parallel, Distributed and Network-Based Processing (PDP04), pp. 282–289 (2004)
Iamnitchi, A., Ripeanu, M., Foster, I.: Locating data in (small-world?) peer-to-peer scientific collaborations. In: IPTPS ’01 Revised Papers from the First International Workshop on Peer-to-Peer Systems, pp. 232–241. Springer-Verlag (2002)
da Fontoura Costa, L., Travieso, G., Ruggiero, C.: Complex grid computing. Eur. Phys. J. B 44(1), 119–128 (2005)
Ilijašić, L., Saitta, L.: Characterization of a computational grid as a complex system. In: GMAC ’09 Proceedings of the 6th International Conference Industry Session on Grids Meets Autonomic Computing. ACM, pp. 9–18 (2009)
de Mello, R.F., Ishii, R.P., Yang, L.T.: A complex network-based approach for job scheduling in grid environments. In: High Performance Computing and Communications of Lecture Notes in Computer Science, vol. 4782, pp. 204–215 (2007)
Derbal, Y.: Entropic grid scheduling. J. Grid Comput. 4(4), 373–394 (2006)
Batista, D., da Fonseca, N., Granelli, F., Kliazovich, D.: Self-adjusting grid networks. In: IEEE international conference on communications. IEEE, pp. 344–349 (2007)
Jones, B.: An overview of the egee project. In: Türker, C., Agosti, M., Schek, H.-J. (eds.) Peer-to-Peer, Grid, and Service-orientation in Digital Library Architectures of Lecture Notes in Computer Science, vol. 3664, pp. 1–8. Springer, Berlin Heidelberg (2005)
McCreary, C.L., Khan, A.A., Thompson, J.J., McArdle, M.E.: A comparison of heuristics for scheduling dags on multiprocessors. In: Proceedings of 8th International Parallel Processing Symposium. IEEE, pp. 446–451 (1994)
Forti, A.: Dag scheduling for grid computing systems. Ph.D. Thesis. Udine University (2006)
Deelman, E., Blythe, J., Gil, Y., Kesselman, C., Mehta, G., Vahi, K., Blackburn, K., Lazzarini, A., Arbree, A., Cavanaugh, R.: Mapping abstract complex workflows onto grid environments. J. Grid Comput. 1(1), 25–39 (2003)
Cao, H., Jin, H., Wu, X., Wu, S., Shi, X.: DAGMap: Efficient and dependable scheduling of DAG workflow job in Grid. J. Supercomput. 51(2), 201–223 (2009)
European grid infrastructure project: (http://www.egi.eu)
Faloutsos, M., Faloutsos, P., Faloutsos, C.: On power-law relationships of the internet topology. In: Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication on SIGCOMM ’99. ACM, pp. 251–262 (1999)
Chen, Q., Hyunseok, Q.C., Govindan, R., Jamin, S., Shenker, S.J., Willinger, W.: The origin of power laws in internet topologies revisited. In: Proceedings of 21th Annual Joint Conference of the IEEE Computer and Communications Societies. IEEE, vol. 2, pp. 608–617 (2002)
Siganos, G., Faloutsos, M., Faloutsos, P., Faloutsos, C.: Power laws and the AS-level internet topology. IEEE/ACM Trans. Networking 11(4), 514–524 (2003)
Pansiot, J.-J., Grad, D.: On routes and multicast trees in the internet. ACM SIGCOMM Comput. Commun. Rev. 28(1), 41–50 (1998)
Amini, L., Shaikh, A., Schulzrinne, H.: Issues with inferring internet topological attributes. Comput. Commun. 27(6), 557–567 (2004)
Willinger, W., Alderson, D., Doyle, J.C.: Mathematics and the internet: A source of enormous confusion and great potential. Not. AMS 56(5), 586–599 (2009)
Clauset, A., Shalizi, C.R., Newman, M.E.: Power-law distributions in empirical data. SIAM Rev. 51(4), 661–703 (2009)
Clauset, A.: http://tuvalu.santafe.edu/~aaronc/powerlaws/
Rewini, H.E., Lewis, T.G., Ali, H.H.: Task scheduling in parallel and distributed systems. Prentice-Hall, Englewood Cliffs (1994)
Peterson, L., Davie, B.: Computer networks: A systems approach. Morgan Kauffman (2007)
Zhang, Y.: Grid-centric scheduling strategies for workflow applications. Ph.D. thesis, Rice University (2009)
Fujii, K., Goto, S.: Correlation between hop count and packet transfer time. APAN/IWS2000 (2000)
Bollobás, B.: Modern graph theory. Springer, Berlin Heidelberg New York (1998)
Kendall, M.G.: The advanced theory of statistics, vol. 1. C. Griffin & Company Limited (1945)
Arnold, B.C., Balakrishnan, N., Nagaraja, H.N.: A First Course in Order Statistics. Society for Industrial and Applied Mathematics (2008)
Buyya, R., Murshed, M.: Gridsim: A toolkit for the modeling and simulation of distributed resource management and scheduling for grid computing. Concurr. Comput. Pract. Experience 14(13-15), 1175–1220 (2002)
O’Madadhain, J., Fisher, D., White, S., Boey, Y.: The JUNG (Java Universal Network/Graph) Framework. Tech. rep., UCI-ICS (2003)
Chung, F., Lu, L.: The Diameter of sparse random graphs. Adv. Appl. Math. 26(4), 257–279 (2001)
Barabasi, A., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509 (1999)
Bollobás, B.: Graph theory and combinatorics. Ch. The evolution of sparse graphs. Cambridge Academic Press (1984)
Fronczak, A., Fronczak, P., Hołyst, J.A.: Average path length in random networks. Phys. Rev. E 70(5), 056110 (2004)
Blondel, V.D., Guillaume, J.-L., Hendrickx, J.M., Jungers, R.M.: Distance distribution in random graphs and application to network exploration. Phys. Rev. E 76(6), 066101 (2007)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Prieto-Castrillo, F., Astillero, A. & Botón-Fernández, M. A Stochastic Process Approach to Model Distributed Computing on Complex Networks. J Grid Computing 13, 215–232 (2015). https://doi.org/10.1007/s10723-014-9317-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10723-014-9317-4