Fachbereich Informatik  Abteilung
Betriebssysteme und Verteilte Systeme 		Universität Oldenburg   

Publications: Details

Document Description

Author: Maria Susanne Steiner
Title: Lastverteilung in heterogenen Systemen
Kind of Publication: Report (dissertation). Berichte aus dem Fachbereich Informatik 08/98, Universität Oldenburg, December 1998
Date: December 1998
Institution: Universität Oldenburg; Abteilung Betriebssysteme und Verteilte Systeme
Pages, Language 307, German
Keywords: Load sharing, load balancing, object migration, distributed system, heterogeneous systems, modeling
CR Classification: D.4.7 [Operating Systems]: Organization and Design - distributed systems; C.2.4 [Computer-Communication Networks]: Distributed Systems
General Terms (ACM): Algorithms, Design, Experimentation
up

Abstract

The goal of this thesis is the design of simple and efficient load distribution strategies for heterogeneous systems such as those used by locally connected workstations within a university environment. To this end, an investigation and evaluation is conducted to determine the extent of how heuristics and specific criteria already proven in homogeneous systems are transferable to heterogeneous systems with the target of minimizing the load units' mean system delay. It is shown that load distribution strategies for heterogeneous systems require strategies which fundamentally differ from those designed for homogeneous systems. This is also indicated by the fact that it seems sensitive to extend the canon of established strategies by more focussed limit strategies. During the selection of a focussed and meaningful strategy canon, the class of nonpreemptive dynamic load distribution strategies with initial placement is selectively investigated for suitable limit strategies. To reach the design target, it is particularly attractive to concentrate on this set of strategies, since other dynamic strategies are more complex, adaptive strategies are too expensive, and the sensitive static strategies too inefficient - even in the case of optimal parameter adjustment. For this selected class of strategies a basic model is prepared. This model reduces the more general problem of looking for the best load distribution strategy to the search for the best global scheduling policy. A cost function is defined to aid in the decision where a process is initially placed socially optimal. The transfer decision and location selection of the policy is approximated by simple threshold strategies. Following this the transfer decision policy is separated. For the selection of location an asymmetric policy, P, and a symmetric one, S, are proposed. Both policies are based on new heuristics extracted during setting up the focussed comparative strategy canon. With the modelling tool MACOM these new location policies are subsequently analyzed, optimized, and evaluated in comparison to the limit strategies while restricted to smaller scenarios under heavily varying load and speed heterogeneity. Results from these experiments lead to the design of a hierarchical load distribution policy, where separateness is expanded to the group level. Questions related to the grouping within the hierarchy and partial aspects are again investigated and evaluated by using MACOM. The question raised at the beginning of the thesis, how suitable criteria might and should look like for the evaluation of load distribution strategies in heterogeneous systems, is finally picked up again. The existing mathematical analysis of the algorithms employed in this thesis are compiled and partially completed by new ones generated as a part of this work. In particular, the matrix-geometric analysis of the policy P is attached. A wide collection of several load distribution strategies, including short descriptions and evaluations as well as a short discussion of the modelling tool MACOM are attached in the Appendix.

Kurzfassung

Ziel dieser Arbeit ist der Entwurf effizienter, einfacher Lastverteilverfahren für heterogene Systeme, wie sie z.B. lokal vernetzte Arbeitsplatzrechner im universitären Bereich bilden. Hierzu wird untersucht und bewertet, inwieweit sich Heuristiken und Kriterien, die sich in homogenen Systemen für Lastverteilverfahren bewährt haben, auf heterogene Systeme unter der Zielsetzung der Minimierung der mittleren Verweilzeit der Lasteinheiten übertragen lassen. Es wird gezeigt, daß Lastverteilverfahren in heterogenen Systemen Strategien erfordern, die sich grundlegend von solchen, die für homogene Systeme konzipiert wurden, unterscheiden. Dies äußert sich auch darin, daß es sich als sinnvoll erweist, den Kanon der etablierten Vergleichsstrategien um schärfere Grenzstrategien zu erweitern. Bereits bei der Aufstellung des verschärften Strategiekanons wird für die Klasse der nichtunterbrechenden dynamischen Lastverteilverfahren mit Erstplazierung gezielt nach geeigneten Grenzstrategien gesucht. Die Konzentrierung auf diese Verfahrensklasse ist für das Entwurfsziel besonders attraktiv, da andere dynamische Verfahren komplexer, adaptive Verfahren zu aufwendig und die sensiblen statischen Verfahren selbst bei optimaler Parametereinstellung zu ineffizient sind. Für diese ausgewählte Verfahrensklasse wird ein Grundmodell erarbeitet. Dieses Modell reduziert das allgemeinere Problem der Suche nach dem besten Lastverteilverfahren auf die Suche nach der besten globalen Vergabestrategie. Es wird eine Kostenfunktion definiert, mit der entschieden werden kann, wo ein Prozeß sozial optimal erstplaziert ist. Die Verlagerungsentscheidung und Ortswahl der Strategie wird durch einfache Schwellwertverfahren approximiert. Die Verlagerungsentscheidungsstrategie ist in der Folge separiert. Für die Ortswahl werden, basierend auf den bei der Aufstellung des verschärften Vergleichsstrategiekanons gewonnenen neuen Heuristiken, zunächst die asymmetrische Strategie P und die symmetrische Strategie S vorgeschlagen. Diese neuen Ortswahlstrategien werden anschließend mit dem Modellierungswerkzeug MACOM beschränkt auf kleinere Szenarien für sehr stark variierende BeIastungs- und Bedienratenheterogenität analysiert, optimiert und mit den Grenzstrategien vergleichend bewertet. Aus diesen Experimenten werden Erkenntnisse gewonnen, die zum Entwurf einer hierarchischen Lastverteilungsstrategie führen, deren Separiertheit auf Gruppenebene ausgedehnt ist. Fragestellungen der Gruppeneinteilung innerhalb der Hierarchie, werden in Teilaspekten ebenfalls mit MACOM untersucht und bewertet. Die bereits zu Beginn der Arbeit aufgeworfene Frage, wie geeignete Kriterien für die Bewertung von Lastverteilverfahren in heterogenen Systemen aussehen könnten und sollten, wird abschließend erneut aufgegriffen. Die mathematischen Analysen, der im Verlauf der Arbeit eingesetzten Verfahren, werden, soweit bekannt, zusammengesteIlt und zum Teil auch durch neue ergänzt. Hinzugefügt wird insbesondere auch die matrix-geometrische Analyse der Strategie P. Eine umfangreiche Sammlung vieler Lastverteilverfahren, ihrer kurzen Definition und Bewertung findet sich ebenso im Anhang, wie eine kurze Diskussion und Beschreibung des verwendeten Modellierungswerkzeugs MACOM.
up

Download

up

Remarks

None.
up


Last change: Apr 2 1998 stiege