Peer-to-Peer-Netzwerke: Algorithmen und Methoden

Methode wird als statisches Routing bezeichnet. Es wird also explizit eingetragen, welche Pakete wohin geleitet werden sollen. Daher ist statisches Routing nur fur kleine, stabile Netze sinnvoll.
    In der Regel werden Routing-Tabellen jedoch automatisch erzeugt, was dann analog als dynamisches Routing bezeichnet wird. Die Routing-Tabelle wird hierbei fortwahrend an neue Gegebenheiten angepasst, wie z.B. an den Ausfall von Rechnern oder das Erscheinen neuer Router. Beispiele fur dynamische RoutingAlgorithmen sind RIP (Routing Information Protocol) and OSPF (Open Shortest Path First).
    Das Prinzip der Paketweiterleitung durch Routing-Tabellen ermoglicht nur die Beforderung eines Pakets auf einem gleichbleibenden Weg vom Startknoten zum Zielknoten. Dieser sehr intuitive Ansatz kann in der Praxis die Performanz eines Netzwerks beeintrachtigen: Wenn zum Beispiel zwei unabhangige Wege zwischen zwei Rechnern moglich sind, so konnte man mit einer alternierenden Benutzung dieser Wege den Datendurchsatz vergroBern. Die Frage des groBtmoglichen Da- tendurchsatzes wird beim Routing im Internet bereits bei der Wahl der Routing- Tabellen-Eintrage vernachlassigt. Hier wird der kurzeste Weg grundsatzlich allen anderen Moglichkeiten vorgezogen.
    So versuchen alle Routing-Algorithmen das so genannte kurzeste-Wege-Problem in Graphen zu losen (siehe auch Anhang zum Begriff Graph auf Seite 263):

    Wir verwenden im Folgenden Kantengewicht and Entfernung synonym. Im Internet wird hier fur jede Verbindung e zwischen Rechnern der Wert w(e) = 1 gesetzt. Fur manche Probleminstanzen gibt es mehrere Losungen. Man kann aber leicht zeigen, dass unter den Losungen immer eine Menge von Pfaden existiert, die in einen gerichteten Baum eingebettet sind, der den Startknoten als Wurzel hat and dessen Kanten zu den Blattern hin gerichtet sind.

    Abb. 2.4. Dijkstras Algorithmus.
    Eine sehr effiziente Losung fiir das Kdrzeste-Wege-Problem ist der in Abbildung 2.4 dargestellte Algorithmus von Edsger Wybe Dijkstra [19]. Das Ergebnis dieses Algorithmus, angewendet auf einen Graphen, der Wege von s zu alien anderen Knoten beinhaltet, ist die Tabelle Vorganger. Diese Tabelle beschreibt den KurzesteWege-Baum mit den Kanten (Vorganger(u), u) fur alle Knoten u E V \ {s}. In Abbildung 2.5 ist der Ablauf von Dijkstras Algorithmus an einem Beispiel beschrieben.
    Der Dijkstra-Algorithmus baut den Kurzeste-Wege-Baum sukzessive ausgehend vom Startknoten auf. Hierzu wird in jedem Durchlauf der While-Schleife der Knoten ausgewahlt, der dem Startknoten am nachsten and noch nicht Teil des Baumes ist. Daraus ergibt sich die Korrektheit des Algorithmus. Liefe der kurzeste Weg zu diesem Knoten uber einen anderen, noch nicht aufgenommenen Knoten, dann ware dieser andere Knoten naher am Startknoten. Das widerspricht der Bedingung, dass der aufzunehmende Knoten dem Startknoten am nachsten war.
    Algorithmen wie der Dijkstra-Algorithmus, die die Losungsmenge sukzessive durch das am besten geeignete Element erweitern, nennt man Greedy-Algorithmen. Dijkstras Algorithmus besitzt eine enge Verwandtschaft zur Breitensuche im Baum. Wenn alle Kantengewichte den Wert Eins haben, entspricht die Reihenfolge in der die Knoten ausgewahlt werden gerade derjenigen bei einer Breitensuche im Baum. Zudem ist Dijkstras Algorithmus sehr effizient: Fur in Kanten and n Knoten muss der Algorithmus n-mal den nachsten minimalen Knoten bestimmen. Verwendet man fur diesen Auswahlprozess eine geeignete Datenstruktur wie den Fibonacci-Heap [20], betragt die Laufzeit des Algorithmus lediglich O(Tn + nlog(n)), da die Aktualisierung der Distanzen in amortisierter konstanter Zeit moglich ist and nur die Auswahl and das Entfernen der Knoten logarithmische Zeit benotigen.

    Abb. 2.5. Ablauf des Disjkstra-Algorithmus. Der resultierende Kurzeste-Wege-Baum wird durch gestrichelte Pfeile dargestellt.

Link-State-Routing
    Eine praktische Umsetzung von Dijkstras-Algorithmus ist das so genannte LinkState-Routing. Bei diesem werden die Routing-Tabellen der Knoten bzw. Router analog zum Verfahren in Dijkstras Algorithmus bestimmt. Allerdings muss hierfur jeder Knoten alle Verbindungen des Netzwerks kennen. Dieses Problem wird dadurch gelost, dass alle Knoten ihre Verbindungsinformation durch das Netzwerk fluten, was auch als Broadcast bezeichnet wird. Hierzu sendet jeder Knoten seine Informationen an alle seine Nachbarn. Diese reichen sie wieder an alle Nachbarn weiter usw. Somit erreicht jeden Rechner die gesamte Information