Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Cluster Computing
Erschienen in: Cluster Computing 4/2015

01.12.2015

An effective game theoretic static load balancing applied to distributed computing

verfasst von: Hajar Siar, Kourosh Kiani, Anthony T. Chronopoulos

Erschienen in: Cluster Computing | Ausgabe 4/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.
Vorheriger Artikel Random task scheduling scheme based on reinforcement learning in cloud computing

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Literatur
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)CrossRef
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)CrossRef
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)
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)CrossRef
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)CrossRef
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)CrossRef
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)CrossRef
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)
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)CrossRef
22.
Charilas, D.E., Panagopoulos, A.D.: A survey on game theory applications in wireless networks. Comput. Netw. 54, 3421–3430 (2010)CrossRef
23.
Rzadca, K., Trystram, D.: Promoting cooperation in selfish computational grids. Eur. J. Oper. Res. 199, 647–657 (2009)MathSciNetCrossRef
24.
Kołodziej, J., Xhafa, F.: Meeting security and user behavior requirements in Grid scheduling. Simul. Model. Pract. Theory 19, 213–226 (2011)CrossRef
25.
Grosu, D., Chronopoulos, A.T.: Noncooperative load balancing in distributed systems. J. Parallel Distrib. Comput. 65, 1022–1034 (2005)CrossRef
26.
Grosu, D., Chronopoulos, A.T., Leung, M.-Y.: Cooperative load balancing in distributed systems. Concurr. Comput. Pract. Exp. 20, 1953–1976 (2008)CrossRef
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)CrossRef
29.
Chana, I.: Bacterial foraging based hyper-heuristic for resource scheduling in grid computing. Future Gen. Comput. Syst. 29, 751–762 (2013)CrossRef
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.
32.
Chen, B., Latifi, S.: Traffic load monitoring and load balancing for the Internet. Clust. Comput. 3, 139–150 (2000)CrossRef
33.
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)
36.
Simon, D.: Evolutionary Optimization Algorithms. Wiley, New York (2013)
37.
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)MathSciNetCrossRef
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)CrossRef
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.
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)CrossRef
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)CrossRef
55.
Černý, V.: Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm. J. Optim. Theory Appl. 45, 41–51 (1985)MathSciNetCrossRef
Metadaten
Titel
An effective game theoretic static load balancing applied to distributed computing
verfasst von
Hajar Siar
Kourosh Kiani
Anthony T. Chronopoulos
Publikationsdatum
01.12.2015
Verlag
Springer US
Erschienen in
Cluster Computing / Ausgabe 4/2015
Print ISSN: 1386-7857
Elektronische ISSN: 1573-7543
DOI
https://doi.org/10.1007/s10586-015-0486-0

Weitere Artikel der Ausgabe 4/2015

Cluster Computing 4/2015 Zur Ausgabe

OriginalPaper

Random task scheduling scheme based on reinforcement learning in cloud computing

OriginalPaper

Auto-localized multimedia platform based on a modular Cyber Physical System aligned in a two-dimensional grid

OriginalPaper

Knowledge discovery in dynamic data using neural networks

OriginalPaper

A distributed frequent itemset mining algorithm using Spark for Big Data analytics

OriginalPaper

Harvesting idle CPU resources for desktop grid computing while limiting the slowdown generated to end-users

OriginalPaper

Application of big data analysis with decision tree for the foot disorder

Premium Partner

    Bildnachweise