Kommunikation in parallelen Rechnernetzen?

Friedhelm Meyer auf der Heide und Rolf Wanka

Fachbereich Mathematik/Informatik

und Heinz Nixdorf Institut

Universit?at-GH Paderborn

33095 Paderborn

e-mail: ffmadh,wankag@uni-paderborn.de

Zusammenfassung

Effiziente Kommunikationsmethoden in Netzwerken sind Grundvoraussetzung, um die Leistungsf?ahigkeit grosser paralleler Rechnersysteme auszusch?opfen. Aus diesem Grund wurden und werden erhebliche Forschungs- und Entwicklungsanstrengungen unternommen, derartige Kommunikationsmechanismen, sogenannte Router, zu analysieren und herzustellen. In diesem Aufsatz beschreiben wir die Grundideen der Beitr?age der theoretischen, algorithmisch orientierten Forschung zur Entwicklung solcher Kommunikationsmethoden.

1 Das Routingproblem

Telefonnetze, Rechnernetze in Unternehmen und Hochschulen oder das Internet sind Beispiele f?ur Netzwerke, die die Aufgabe haben, viele Kommunikationsanfragen (Telefonate, e-mail-Kontakte innerhalb einer Hochschule oder zwischen Hochschulen oder Unternehmen, Geldtransfers zwischen Banken, : : : ) gleichzeitig zu verarbeiten. Woher weiss eine Botschaft, wohin sie gehen muss, und welchen Weg sie zu benutzen hat? Beim Verschicken einer email ?uber das Internet schaut das System f?ur einen Teil der Adresse in einer Tabelle nach, tr?agt in der Botschaft einen Teil des Weges ein, den die Botschaft zur?ucklegen muss, und verschickt sie an den ersten Rechner auf diesem Weg. Dieser wertet dann die mitgegebene Weginformation aus und gibt die e-mail weiter oder bestimmt selbst einen Weg oder ein Wegst?uck f?ur die Botschaft. Unter Umst?anden werden auch Priorit?atsberechnungen durchgef?uhrt. Dieser Vorgang wiederholt sich, bis die Botschaft beim Adressaten angekommen ist. Diesem Verfahren liegt also ein Netzwerk, d. h. ein Graph zugrunde, dessen Knoten die einzelnen Rechner sind. Die Kanten geben an, zwischen welchen Knoten direkte Leitungen,

?Diese Arbeit wird im Rahmen des Sonderforschungsbereichs 376 "Massive Parallelit?at durch die Deutschen Forschungsgemeinschaft gef?ordert.