Bibliographic Metadata

Title
Self-organization for load balancing and information retrieval based on shared coordination spaces / Vesna Čavić
AuthorČavić, Vesna
CensorKühn, Eva ; Mitrovic, Slobodanka
Published2011
Description224 Bl. : Ill., graph. Darst.
Institutional NoteWien, Techn. Univ., Diss., 2011
LanguageEnglish
Bibl. ReferenceOeBB
Document typeDissertation (PhD)
Keywords (DE)self-organization / swarm intelligence / adaptive algorithms / space based computing / autonomous agents
Keywords (EN)self-organization / swarm intelligence / adaptive algorithms / space based computing / autonomous agents
Keywords (GND)Softwaresystem / Selbstorganisation / Algorithmus / Adaptives System / Autonomer Agent / Softwaresystem / Lastteilung / Information Retrieval / Selbstorganisation / Schwarmintelligenz / Ameisenalgorithmus
URNurn:nbn:at:at-ubtuw:1-44669 Persistent Identifier (URN)
Restriction-Information
 The work is publicly available
Files
Self-organization for load balancing and information retrieval based on shared coordination spaces [1.45 mb]
Links
Reference
Classification
Abstract (German)

Die erhöhte Komplexität in heutigen Softwaresystemen (speziell in verteilten Systemen) stellt eine riesige Hürde in der weiteren Entwicklung von Softwaresystemen dar. Die große Anzahl von unvorhersehbaren Abhängigkeiten von interagierenden Komponenten kann nicht mehr auf traditionelle Weise bewältigt werden und daher muss durch die Verwendung von fortschrittlicheren, intelligenten Ansätzen behandelt werden. Weil sich Softwaresysteme schnell entwickeln und ständig ändern, können bestehende Methoden in heutigen dynamischen Umgebungen veraltet oder unpassend sein. Deshalb wird Selbstorganisation, welche einen relativ neuen Ansatz mit derzeit wenigen praktischen Anwendungen darstellt, in dieser Dissertation als eine vielversprechende Methode vorgestellt um Komplexität zu bewältigen. Die Dissertation zeigt eine neue Auffassung einer selbstorganisierenden Koordinationsinfrastruktur als eine Kombination von verschiedenen Methoden: Koordinationsräumen, Selbstorganisation, adaptiven Algorithmen und Multiagenten-Technologien.

Der Fokus liegt auf zwei wichtigen IT-Problemen: dynamische Lastverteilung in heterogenen verteilten Systemen und Informationswiedergewinnung im Internet. Diese Probleme werden auf neue Weise unter Verwendung von Selbst-Mechanismen behandelt. Für jedes dieser Probleme, wird ein selbst organisierendes Framework entwickelt, z.B. eine Software-Architektur. Diese Architekturen wurden modelliert und deren Richtigkeit wird durch die Verwendung der PlusCal Algorithmus Sprache bewiesen. Sie sind flexibel und generisch, unabhängig von Netzwerkstruktur, verwendete Algorithmen, Problem-Spezifikation, etc.

Bienen-Algorithmen und zwei adaptierte Ameisen-Algorithmen werden für die identifizierten IT-Szenarien entwickelt. Diese Algorithmen sind inspiriert von Selbstorganisation in der Natur. Sie beschreiben auf mathematische Weise biologische Selbst-Mechanismen und lösen die komplexen Probleme erfolgreich durch komplett autonome und vollständig verteilte Kommunikation der Systemkomponenten. Die Resultate werden in zwei unterschiedlichen Umgebungen erlangt: in Cluster und in Amazon EC2 Cloud . Der Benchmarking-Teil bietet Möglichkeiten der Auswahl und der Feinabstimmung einer enormen Zahl von Parametern, die in den Algorithmen verwendet werden. Der Vergleich wurde gemacht unter Berücksichtigung der anderen Ansätzen: Gnutella Lookup Mechanismen für die Informationssuche im Internet und verschiedene unintelligente (random, sender) und intelligente (angepasste genetische Algorithmen) Ansätze für dynamische Lastverteilung. Die Auswertung erfolgt durch Leistung und Skalierbarkeit. Die erhaltenen Resultate zeigen die Vorteile der angewandten Methodik und der erzeugten Algorithmen, da die Leistung und die Skalierbarkeit des Systems erhöht werden. Zum Beispiel zeigten die Ergebnisse des ersten betrachteten Szenario, erhalten auf der Amazon EC2 Cloud, dass die zufällige/Bienen Kombination auf 80 Knoten mit 50 Schwärmen und durch Behandeln 5 Anfragen, um 0,5% besser waren als zufällige/ AntNet Kombination, um 7,8% besser waren als zufällige/MMAS Kombination und um 61,3% besser waren als Gnutella. Die Ergebnisse des ersten betrachteten Szenario, erhalten auf der Amazon EC2 Cloud zeigten, dass in der Ketten-Topologie, das beste Ergebnis von beiden BeeAlgorithm/Sender und MMAS/MMAS erhalten wird. Sie waren gleich gut, und um 5,4% besser als die Kombination "nahm den zweiten Platz", GA/Bee-Algorithmus. Die Kombination RoundRobin/BeeAlgorithm zeigte die besten Ergebnisse in der vollen Topologie. Diese Kombination war um 1,3%. besser als die Kombination, "nahm den zweiten Platz", RoundRobin/AntNet. Beide BeeAlgorithm/Sender und MMAS/RoundRobin waren gleich gut in Ring-Topologie. Sie waren um 1,4% besser als die Kombination "nahm den zweiten Platz", MMAS/RoundRobin. In der Stern-Topologie, die Kombinationen BeeAlgorithm/BeeAlgorithm und GA/AntNet waren die besten mit dem gleichen Ergebnis. Die waren um 6,1% besser als Kombination "nahm den zweiten Platz", AntNet/MMAS.

Die Selbstorganisation wird durch den Einsatz einer speziell erzeugten Funktion (der sogenannten Suitability-Funktion) gemessen. Der Hauptbeitrag und Innovation dieser Dissertation ist: die Identifikation von Problemarten, für die Selbst-* nützlich sein kann, Bau einer neuen selbstorganisierenden/koordinierenden Infrastrukturen, die Adaption eines Ameisen-Algorithmen für die gefundenen IT-Probleme, die Erstellung eines neuen Algorithmentyps (Bienen-Algorithmen) für diese IT-Probleme, das Finden der besten Parameterabstimmung in jedem der behandelten Szenarien zusammen mit dem besten Algorithmus bzw. der besten Kombination von Algorithmen.

Abstract (English)

The increased complexity in nowadays information technology (especially in distributed systems) presents a huge obstacle in the further development of software systems. The huge number of unpredictable dependencies on interacting components cannot be coped with any more in a traditional way. It implies the necessity of finding more advanced, intelligent approaches. As software systems develop rapidly and change constantly, the existing methods are obsolete or inadequate in today's dynamic environments. Therefore, self-organization that is a relatively new approach with a lack of real applications is proposed in the dissertation as a promising approach in coping with complexity. The dissertation presents a new conception of a self-organizing coordination infrastructure as a combination of different methods: coordination spaces, self-organization, adaptive algorithms and multi-agent technologies. The focus is put on two important IT problems: dynamic load balancing in heterogeneous distributed systems and information retrieval in the Internet. These problems are treated in a new way by using self-mechanisms. For each of these problems, a self-organizing framework, i.e., software architecture is developed. These architectures are modeled and their correctness is proven by using the PlusCal algorithm language. They are flexible and generic, undependable of the network topology, algorithms used, problem specification, etc. A bee algorithm and two adapted ant algorithms are developed for the located IT scenarios. These algorithms are inspired by self-organization from nature. They mathematically describe bio-self-mechanisms and successfully solve these complex problems through autonomy and fully distributed communication of components in a system. These algorithms are plugged in the frameworks. The results are obtained by benchmarking in two different environments: a cluster and the Amazon EC2 Cloud. The benchmarking part presents a way of selecting and fine-tuning of a huge number of parameters used in the algorithms.

The comparison is done taking into account the other approaches:

Gnutella lookup mechanisms for the information retrieval in the Internet, and different unintelligent (Random, Sender) and intelligent (adapted genetic algorithms) approaches for dynamic load balancing. The evaluation is carried out by performance and scalability. The obtained results prove the benefits of the used methods and constructed algorithms as the performance of the system and scalability are improved. For example, the results of the first considered scenario obtained on the Amazon EC2 Cloud, showed that the random/bee combination on 80 nodes with 50 swarms and by treating 5 queries was 0.5% better than the random/AntNet combination, 7.8% better than the random/MMAS combination and 61.3% better than Gnutella. The results of the first considered scenario obtained on the Amazon EC2 Cloud, showed that: in the chain topology, the best result is obtained by both BeeAlgorithm/Sender and MMAS/MMAS. They were equal good, and better than the combination that "took the second place", GA/Bee Algorithm, for 5.4%. The combination RoundRobin/BeeAlgorithm showed the best results in the full topology. This combination was better than the combination that "took the second place", RoundRobin/AntNet, for 1.3%. Both BeeAlgorithm/Sender and MMAS/RoundRobin were equal good in the ring topology. They were better than the combination that "took the second place", MMAS/RoundRobin, for 1.4%. In the star topology, the combinations BeeAlgorithm/BeeAlgorithm and GA/AntNet were the best with the same resulting value. They were better than the combination that "took the second place", AntNet/MMAS, for 6.1%. The self-organization is measured through the usage of specially constructed functions (so-called the suitability function). The main innovation and contribution of this dissertation is: location of problem types where self-* can be useful, construction of a new self-organizing coordination infrastrucutre, adaptation of Ant Algorithms for the located IT problems, specification of a new type of algorithm, Bee Algorithms for the located IT problems, finding the best parameters tuning in each of the considered scenarios as well as the best algorithm/combination of algorithms.

Stats
The PDF-Document has been downloaded 31 times.