Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

An effective game theoretic static load balancing applied to distributed computing

  • Published:
Cluster Computing Aims and scope Submit manuscript

Abstract

In this paper an algorithm has been proposed to balance the loads in a distributed computing system based on game theory which models the load balancing problem as a non-cooperative game among the users. The proposed load balancing game, which is infinite and with perfect information, aims to establish fairness both in system and user level. The optimal or near-optimal solution of the game is approximated by a genetic algorithm and an introduced hybrid population-based simulated annealing algorithm, using the concept of Nash equilibrium. Since all users responses are shown to converge to their near-optimal solution, distribution of users’ jobs is “fair”. Simulations demonstrate near-optimality of the proposed algorithms in terms of makespan and fairness for the proposed load balancing scheme.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

References

  1. Silberschatz, A., Galvin, P.B., Gagne, G.: Operating System Concepts, vol. 8. Wiley, New York (2013)

  2. Penmatsa, S., Chronopoulos, A.T.: Game-theoretic static load balancing for distributed systems. J. Parallel Distrib. Comput. 71, 537–555 (2011)

    Article  Google Scholar 

  3. Tanenbaum, A., Van Steen, M.: Distributed Systems. Pearson Prentice Hall, Upper Saddle River (2007)

  4. Stallings, W., Paul, G.K., Manna, M.M.: Operating Systems: Internals and Design Principles, vol. 3. Prentice Hall, Upper Saddle River (1998)

  5. Eftekhari, N., Zeinalabedin, F.H., Haghighat, A.T.: A novel threshold-based dynamic load balancing algorithm using mobile agent in distributed system. In: Computational Intelligence and Information Technology, pp. 103–109. Springer, Berlin (2011)

  6. Li, Y., Yang, Y., Ma, M., Zhou, L.: A hybrid load balancing strategy of sequential tasks for grid computing environments. Future Gen. Comput. Syst. 25, 819–828 (2009)

    Article  Google Scholar 

  7. Penmatsa, S., Chronopoulos, A.T.: Cooperative load balancing for a network of heterogeneous computers. In: 20th International Parallel and Distributed Processing Symposium, 2006 (IPDPS 2006), p. 8 (2006)

  8. Chonggun, K., Kameda, H.: Optimal static load balancing of multi-class jobs in a distributed computer system. IEICE Trans. 1976–1990(73), 1207–1214 (1990)

    Google Scholar 

  9. Zomaya, A.Y., Teh, Y.-H.: Observations on using genetic algorithms for dynamic load-balancing. IEEE Trans. Parallel Distrib. Syst. 12, 899–911 (2001)

    Article  Google Scholar 

  10. Okhovvat, M., Sharifi, M., Momeni, H.: Task allocation to actors in wireless sensor actor networks: an energy and time aware technique. Procedia Comput. Sci. 3, 484–490 (2011)

    Article  Google Scholar 

  11. Meyerson, A., Roytman, A., Tagiku, B.: Online multidimensional load balancing. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 287–302. Springer, Berlin (2013)

  12. Jain, R., Chiu, D.-M., Hawe, W.: A quantitative measure of fairness and discrimination for resource allocation in shared computer systems. Computing Research Repository, vol. cs.NI/9809 (1998)

  13. Drozdowski, M.: Selected problems of scheduling tasks in multiprocessor computer systems. Citeseer (1997)

  14. Bharadwaj, V., Ghose, D., Robertazzi, T.G.: Divisible load theory: a new paradigm for load scheduling in distributed systems. Clust. Comput. 6, 7–17 (2003)

    Article  Google Scholar 

  15. Bharadwaj, V., Barlas, G.: Scheduling divisible loads with processor release times and finite size buffer capacity constraints in bus networks. Clust. Comput. 6, 63–74 (2003)

    Article  Google Scholar 

  16. Veeravalli, B., Ghose, D., Mani, V., Robertazzi, T.G.: Scheduling Divisible Loads in Parallel and Distributed Systems. IEEE Computer Society Press, Los Almitos (1996)

    Google Scholar 

  17. Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V.: Algorithmic Game Theory, vol. 1. Cambridge University Press, Cambridge (2007)

  18. Osborne, M.J., Rubinstein, A.: A Course in Game Theory. MIT Press, Cambridge (1994)

  19. Fudenberg, D., Tirole, J.: Game Theory, vol. 393. Cambridge (1991)

  20. Fudenberg, D.: The Theory of Learning in Games, vol. 2. MIT Press, Cambridge (1998)

  21. Shamshirband, S., Patel, A., Anuar, N.B., Kiah, M.L.M., Abraham, A.: Cooperative game theoretic approach using fuzzy Q-learning for detecting and preventing intrusions in wireless sensor networks. Eng. Appl. Artif. Intell. 32, 228–241 (2014)

    Article  Google Scholar 

  22. Charilas, D.E., Panagopoulos, A.D.: A survey on game theory applications in wireless networks. Comput. Netw. 54, 3421–3430 (2010)

    Article  Google Scholar 

  23. Rzadca, K., Trystram, D.: Promoting cooperation in selfish computational grids. Eur. J. Oper. Res. 199, 647–657 (2009)

    Article  MathSciNet  Google Scholar 

  24. Kołodziej, J., Xhafa, F.: Meeting security and user behavior requirements in Grid scheduling. Simul. Model. Pract. Theory 19, 213–226 (2011)

    Article  Google Scholar 

  25. Grosu, D., Chronopoulos, A.T.: Noncooperative load balancing in distributed systems. J. Parallel Distrib. Comput. 65, 1022–1034 (2005)

    Article  Google Scholar 

  26. Grosu, D., Chronopoulos, A.T., Leung, M.-Y.: Cooperative load balancing in distributed systems. Concurr. Comput. Pract. Exp. 20, 1953–1976 (2008)

    Article  Google Scholar 

  27. Schmidt, C.: Game Theory and Economic Analysis: A Quiet Revolution in Economics. Routledge, Lodnon (2003)

  28. Pendharkar, P.C.: Game theoretical applications for multi-agent systems. Expert Syst. Appl. 39, 273–279 (2012)

    Article  Google Scholar 

  29. Chana, I.: Bacterial foraging based hyper-heuristic for resource scheduling in grid computing. Future Gen. Comput. Syst. 29, 751–762 (2013)

    Article  Google Scholar 

  30. Mani, V., Suresh, S., Kim, H.: Real-coded genetic algorithms for optimal static load balancing in distributed computing system with communication delays. In Computational Science and Its Applications—ICCSA 2005, pp. 269–279. Springer, Berlin (2005)

  31. Song, S., Lv, T., Chen, X.: Load balancing for future internet: an approach based on game theory. J. Appl. Math. 2014, 959782 (2014). doi:10.1155/2014/959782.959782

  32. Chen, B., Latifi, S.: Traffic load monitoring and load balancing for the Internet. Clust. Comput. 3, 139–150 (2000)

    Article  Google Scholar 

  33. Amazon elastic compute cloud. http://www.amazon.com/

  34. Buyya, R., Yeo, C.S., Venugopal, S.: Market-oriented cloud computing: vision, hype, and reality for delivering it services as computing utilities. In: 10th IEEE International Conference on High Performance Computing and Communications, 2008 (HPCC’08), pp. 5–13 (2008)

  35. Goldenberg, D.: Genetic Algorithms in Search, Optimisation and Machine Learning. Adisson Wesley, Reading (1989)

    Google Scholar 

  36. Simon, D.: Evolutionary Optimization Algorithms. Wiley, New York (2013)

  37. Holland, J.H.: Genetic algorithms. Sci. Am. 267, 66–72 (1992)

    Article  Google Scholar 

  38. Williams, A., Arlitt, M., Williamson, C., Barker, K.: Web workload characterization: ten years later. In: Web Content Delivery, pp. 3–21. Springer, Berlin (2005)

  39. Nozaki, S.A., Ross, S.M.: Approximations in finite-capacity multi-server queues with Poisson arrivals. J. Appl. Probab. 15, 826–834 (1978)

  40. Kleinrock, L.: Queueing Systems. Wiley, New York (1975)

  41. Tantawi, A.N., Towsley, D.: Optimal static load balancing in distributed computer systems. J. ACM 32, 445–465 (1985)

    Article  MathSciNet  Google Scholar 

  42. Jain, R.: The Art of Computer Systems Performance Analysis. Wiley, New York (2008)

  43. Iosup, A., Ostermann, S., Yigitbasi, M.N., Prodan, R., Fahringer, T., Epema, D.H.: Performance analysis of cloud computing services for many-tasks scientific computing. IEEE Trans. Parallel Distrib. Syst. 22, 931–945 (2011)

    Article  Google Scholar 

  44. Evangelinos, C., Hill, C.: Cloud computing for parallel scientific HPC applications: feasibility of running coupled atmosphere-ocean climate models on Amazon’s EC2. Ratio 2, 2–34 (2008)

  45. Ekanayake, J., Fox, G.: High performance parallel computing with clouds and cloud technologies. In: Cloud Computing, pp. 20–38. Springer, Berlin (2010)

  46. GoGrid: GoGrid Cloud-Server Hosting. http://www.gogrid.com

  47. Tang, X., Chanson, S.T.: Optimizing static job scheduling in a network of heterogeneous computers. In: Proceedings of the 2000 International Conference on Parallel Processing, pp. 373–382 (2000)

  48. Riechmann, T.: Genetic algorithm learning and evolutionary games. J. Econ. Dyn. Control 25, 1019–1037 (2001)

    Article  Google Scholar 

  49. Protopapas, M.K., Kosmatopoulos, E.B.: Determination of sequential best replies in n-player games by Genetic Algorithms. Int. J. Appl. Math. Comput. Sci. 5, 19–24 (2009)

  50. Sefrioui, M., Perlaux, J.: Nash genetic algorithms: examples and applications. In: Proceedings of the 2000 Congress on Evolutionary Computation, pp. 509–516 (2000)

  51. Vorobeychik, Y., Wellman, M.P.: Stochastic search methods for Nash equilibrium approximation in simulation-based games. In: Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems, vol. 2, pp. 1055–1062 (2008)

  52. Holland, J.H.: Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. Uinversity of Michigan Press (1975)

  53. Aboutalebi, M., Siar, H., Javadi, H.H.S.: Static task scheduling in homogeneous multiprocessor systems based on genetic algorithm. In: International Conference on Software Technology and Engineering (ICSTE) (2009)

  54. Bertsimas, D., Tsitsiklis, J.: Simulated annealing. Stat. Sci. 8, 10–15 (1993)

    Article  Google Scholar 

  55. Černý, V.: Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm. J. Optim. Theory Appl. 45, 41–51 (1985)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgments

We gratefully acknowledge the reviewers for their helpful and constructive suggestions which considerably improved the quality of the manuscript.

Author information

Authors and Affiliations

  1. Faculty of Electrical and Computer Engineering, Semnan University, Semnan, Iran

    Hajar Siar & Kourosh Kiani

  2. Department of Computer Science, University of Texas at San Antonio, San Antonio, TX, USA

    Anthony T. Chronopoulos

Authors
  1. Hajar Siar
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kourosh Kiani
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Anthony T. Chronopoulos
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hajar Siar.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Siar, H., Kiani, K. & Chronopoulos, A.T. An effective game theoretic static load balancing applied to distributed computing. Cluster Comput 18, 1609–1623 (2015). https://doi.org/10.1007/s10586-015-0486-0

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10586-015-0486-0

Keywords

Search

Navigation