Dezentrales grid scheduling mittels computational intelligence
| dc.contributor.advisor | Schwiegelshohn, Uwe | |
| dc.contributor.author | Lepping, Joachim | |
| dc.contributor.referee | Hüllermeier, Eyke | |
| dc.date.accepted | 2011-03-28 | |
| dc.date.accessioned | 2011-04-12T12:34:00Z | |
| dc.date.available | 2011-04-12T12:34:00Z | |
| dc.date.issued | 2011-04-12 | |
| dc.description.abstract | Das ständig wachsende Bedürfnis nach universell verfügbarer Rechen- und Speicherkapazität wird durch die in den letzten Jahren vorangetriebene Entwicklung neuer Architekturen für die vernetzte Interaktion zwischen Nutzern und Anbietern von Rechenressourcen mehr und mehr erfüllt. Dabei ist die Umsetzung einer Infrastruktur zur koordinierten Nutzung global verteilter Rechenressourcen längst in Forschung und Wirtschaft realisiert worden. Diese als Grid-Computing bezeichnete Infrastruktur wird künftig integraler Bestandteil der globalen Ressourcenlandschaft sein, sodass die Ausführung von lokal eingereichten Berechnungsaufgaben nicht mehr ortsgebunden ist, sondern flexibel zwischen unterschiedlichen Ressourcenanbietern migriert werden kann. Bereits heute sind unterschiedliche Nutzergemeinschaften im Rahmen von Community-Grids in virtuellen Organisationen zusammengefasst, die neben einem gemeinsamen Forschungs- oder Anwendungsinteresse auch häufig eine Menge von IT-Ressourcen gemeinsam nutzen. Ziel ist es aber, auf lange Sicht eine Community-übergreifende Kooperation im Sinne einer globalen Grid-Infrastruktur unter Wahrung lokaler Autonomie weiter zu fördern. Dabei bringt die Interaktion mit anderen Communities im Grid sowohl Chancen als auch Herausforderungen mit sich, da durch die Nutzbarkeit global verteilter Ressourcen auch höhere Anforderungen in Bezug auf Berechnungsgeschwindigkeit und Wartezeiten von Seiten der Nutzer gestellt werden. Der Schlüssel für den effizienten Betrieb künftiger Computational Grids liegt daher in der Entwicklung tragfähiger Architekturen und Strategien für das Scheduling, also in der Zuteilung der Jobs zu den Ressourcen. Bisher sind die Methoden für die Verhandlung von Jobübernahmen zwischen Ressourcenanbietern jedoch nur sehr rudimentär entwickelt. In dieser Arbeit werden deshalb dezentrale Schedulingstrategien für Computational Grids entwickelt und unter Einsatz von Methoden der Computational Intelligence realisiert und optimiert. Dabei werden einzelne virtuelle Organisationen als autonome Einheiten betrachtet, die über eine Annahme oder Abgabe sowohl von eigenen als auch von extern eingereichten Jobs entscheiden. Durch die Beachtung einer restriktiven Informationspolitik werden die Autorität und Sicherheit virtueller Organisationen gewahrt und zugleich wird die Skalierbarkeit in größeren Umgebungen durch den dezentralen Aufbau sichergestellt. Zunächst werden verschiedene dezentrale Strategien entwickelt und simulatorisch untersucht. Die Ergebnisse geben dann Aufschlüsse über die Dynamik und Eigenschaften eines derartigen Verbunds. Auf Basis der so gewonnenen Erkenntnisse werden die Mechanismen zur Entscheidungsfindung verfeinert und in einer neu entworfenen modularen Schedulingarchitektur umgesetzt. Mittels evolutionär optimierter Fuzzy-Systeme wird anschließend die Entscheidungsfindung optimiert. Die Interaktion zwischen virtuellen Organisationen wird dann alternativ mittels co-evolutionärer Algorithmen angepasst. Die auf Basis realer Arbeitslastaufzeichnungen durchgeführten Evaluationen zeigen, dass die so erstellten Grid-Schedulingstrategien für alle am Grid teilnehmenden Communities deutlich verkürzte Antwortzeiten für die jeweiligen Nutzergemeinschaften erreichen. Gleichzeitig wird eine große Robustheit der Verfahren sowohl gegenüber veränderlichen Grid-Umgebungen als auch gegenüber verändertem Nutzerverhalten bewiesen. Die Ergebnisse sind als Motivation für die stärkere Community-übergreifende Kooperation im Sinne eines Computational Grid zu sehen, da dies bei Nutzung entsprechend optimierter Verfahren in einer Win-win Situation für alle Teilnehmer resultiert. | de |
| dc.description.abstract | The ever-growing need for universally available computing and storage capacity is more and more satisfied by new architectures for networked interaction between users and providers of computing resources. Today, research and industry have realized an infrastructure for the coordinated use of globally distributed computing resources. The so-called grid computing infrastructure is assumed to be an integral part of the future global resource landscapes. In such an environment, submitted computing jobs are no longer bound locally, but can be flexibly migrated between different resource providers. In the context of community grids, different users are organized into virtual organizations, which typically share---in addition to a joint research---various computing resources. However, cooperation among different virtual organizations at the moment occurs only very rarely as---besides technical issues---this requires more advanced decentralized grid scheduling concepts. In order to fully utilize the capabilities of a federated grid, it is essential to promote a cross-community cooperation in the sense of a global grid infrastructure. At the same time, however, it is most important that the local autonomy is maintained, as no virtual organization would voluntarily cede the control of their local resources. Thus, the interaction among different communities in the grid brings both opportunities and challenges: The newly formed flexibility makes users even more demanding with respect to computing result delivery and wait times. The efficient operation of future computational grids highly depends on the development of viable architectures and strategies for scheduling, i.e. the allocation of jobs to resources and powerful methods for the negotiation of job migrations. In this work, we therefore develop distributed scheduling strategies for computational grids using various methods from computational intelligence. Different virtual organizations are seen as autonomous entities that decide on the acceptance or decline of jobs. Here, jobs can be offered by other schedulers or by the local user communities. The authority and security of virtual organizations will be maintained by following a restrictive information policy that strongly limits the exchange of system state information. The fully decentralized grid structure guarantees that the scheduling concepts are also applicable in large-scale environments. Initially, several decentralized strategies are developed and tested by extensive simulations with real-world workload traces. The results give first insights into the dynamics and characteristics of the assumed grid federations. Based on these findings, the mechanisms for decision-making is refined and implemented in a newly designed modular scheduling architecture. Using an evolutionary fuzzy system, the decision-making and interaction between virtual organizations is realized and further optimized. In a last step, also a coevolutionary algorithm is applied to improve the scheduling decisions. The evaluation based on real workload recordings reveals that it is possible to achieve significantly shorter response times for all respective user communities. At the same time, we demonstrate a strong robustness of the procedures, both to changing grid environments and changed user behavior. The results can be seen as a motivation for the increased cross-community cooperation in terms of a global computational grid, as this results in a win-win situation for all participants. | de |
| dc.identifier.uri | http://hdl.handle.net/2003/27681 | |
| dc.identifier.uri | http://dx.doi.org/10.17877/DE290R-8778 | |
| dc.language.iso | de | de |
| dc.subject | Scheduling | de |
| dc.subject | Computational intelligence | de |
| dc.subject | Evolutionäre Fuzzy-Systeme | de |
| dc.subject.ddc | 004 | |
| dc.title | Dezentrales grid scheduling mittels computational intelligence | de |
| dc.type | Text | de |
| dc.type.publicationtype | doctoralThesis | de |
| dcterms.accessRights | open access |