Ant-inspired load-balancing

Der Lastenausgleich ist ein wichtiger Gesichtspunkt bei der Administration von Telephonnetzen, beim Internetworking, wie auch in verteilten Systemen. In den ersten beiden Fällen betrifft der Lastenausgleich das Routing, d.h. das Bestimmen der günstigsten Verbindung zwischen zwei Knoten. Dabei sollte vermieden werden, daß einzelne Vermittlungsknoten überlastet werden, während andere völlig unausgelastet sind. In verteilten Systemen, die auf das Internet aufgesetzt sind, spielt dieser Aspekt zwar auch eine Rolle, entscheidender ist dort jedoch der Lastenausgleich in Hinblick auf die Zuteilung der Rechenlast an die einzelnen Knoten, was als Scheduling bezeichnet wird. Auch hier liegt eine Optimierungsaufgabe vor, die darin besteht, die Rechenlast auf die Knoten entsprechend deren Kapazität zu verteilen. Es ist offensichtlich, daß die Rechenleistung eines Grids nur bei einem optimalen Scheduling zur vollen Geltung kommt, und im schlechtesten Falle das Grid nur die Leistung eines einzelnen Rechners erbringt.

Ein zentral organisierter Lastenausgleich begrenzt die Skalierbarkeit eines Grids und erfordert einen hohen Verwaltungsaufwand aufgrund einer dynamischen und nicht-deterministischen Netzwerkstuktur. Der inhärent dezentrale Ansatz von Organic Computing bedeutet für das Routing, wie für das Scheduling eine Selbstregulierung durch die Interaktion selbständiger Einheiten. In diesem Vortrag werden Konzepte des Lastenausgleichs beim Routing auf der Grundlage autonomer Agenten vorgestellt, die durch das Kollektivverhalten von Ameisen inspiriert sind. Selbstorganisiertes Scheduling ist Gegenstand des nächsten Vortrags.

Zuzuordnen in den Fachbereich: Informatik

Mathematische Voraussetzungen: keine

Literatur und Links:

[Dij59] DIJKSTRA, E.W. : A Note on Two Problems in Connexion with Graphs. Numerische Mathematik. Vol 1, 1959

[LK99] LIPPERTS, S. ; KRELLER, B.: Mobile Agents in Telecommunications Networks A Simulative Approach to Load Balancing, 1999. pdf

[SHB97] SCHOONDERWOERD, R. ; HOLLAND, O. ; BRUTEN, J. : Ant-like agents for load balancing in telecommunications networks. Proceedings of the first international conference on Autonomous agents table of contents. 209 – 216, 1997. pdf

[Wh97] WHITE, T : Routing with Swarm Intelligence. SCE Technical Report SCE-97-15, 1997. pdf

[Wh99] WHITE, T ; PAGUREK, B, : Artificial Life, Adaptive Behavior, Agents Application Oriented Routing with Biologically-inspired Agents. In Proc. Genetic and Evolutionary Computation Conference (GECCO 1999), Orlando, Florida, USA, July 1999

Last modified: Wed Nov 12 20:33:52 CET 2005