A.o. Univ. Prof. Dr. Dipl.-Ing. eva Kühn
TU Wien

Vesna Sesum-Cavic

Self-Organization for Load Balancing and Information Retrieval Based on Shared Coordination Spaces


Dissertation, TU-Vienna, 2011


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.





top | XHtml 1.0 strict | last update: Jun 2015