Peer-to-Peer-Netzwerke: Algorithmen und Methoden

des Netzwerks and er kann den Dijkstra-Algorithmus verwenden, um fur jeden Rechner denjenigen Nachbarn zu bestimmen, der auf dem kurzesten Weg liegt. Bei diesem Verfahren muss jeder Knoten anfangs nur seine aktuellen Verbindungen verbreiten. Spater genugt es, alle Teilnehmer uber Anderungen zu informieren. Damit ist der Kommunikationsaufwand im laufenden Betrieb relativ gering.
Distance-Vector Routing
    Der Distance-Vector-Routing-Algorithmus verwendet fur jede bestehende Verbindung einen Entfernungseintrag fur jeden Knoten. Diese Entfernungseintrage werden in so genannten Distance-Vector-Tabellen gespeichert. In der Distance-VectorTabelle eines Knotens H steht an der Position (A, B) (im Idealfall) die Lange des kurzesten Pfades von H zu A, der die Kante (H, B) als erste Kante verwendet. Distance-Vector-Tabellen fur ein kleines Beispielnetzwerk linden sich in Abbildung 2.6.
    Somit kann der Knoten H aus dieser Tabelle den kurzesten Weg bestimmen, indem er die Verbindung wiihlt, die den kleinsten Wert besitzt. Wenn H diese Information an alle Nachbarn weitergibt, konnen diese ihre Tabellen aktualisieren, da sie einfach die Entfernung zu H fur den Eintrag hinzuaddieren mussen. Dieser verteilte Aktualisierungsprozess konvergiert zu den korrekten Eintragen.
    Ein Problem, das beim Distance Vector Routing auftritt, ist das so genannte Count-to-Infinity-Problem. Dieses trill zum Beispiel im folgenden Szenario auf: Wir betrachten drei Router A, B and C wobei Verbindungen zwischen A and B sowie B and C bestehen (siehe auch Abbildung 2.7 oben). Fallt nun der Router C aus, kann B ihn nicht mehr direkt erreichen. Router B meint jedoch, er konne C noch uber den Router A erreichen and sendet seine geanderte Distance-Vector-Tabelle an A. Das hat zur Folge, dass auch Router A seine Tabelle anpasst (also den Eintrag fur Routing nach C uber B erhoht) and diese Information im Netzwerk verbreitet. Wenn Router B diese Nachricht erhalt, wird er wiederum die Kosten erhohen usw. Hier wird deutlich, class sich schlechte Nachrichten, wie z.B. der Ausfall eines Routers, nur langsam verbreiten. Dagegen breiten sich gute Nachrichten sehr schnell aus. Das Count-to-Infinity-Problem lasst sich z.B. mit den im Folgenden kurz beschriebenen Poisoned Reverse oder Split Horizon Verfahren losen.

    Abb. 2.6. Distance-Vector-Tabellen.
    Abb. 2.7. Das Count-to-Infinity-Problem beim Distance-Vector-Routing.

    Poisoned Reverse Wenn ein Router die Verbindung zu einem anderen Router verliert, teilt er dies den anderen Routern mit, indem er die verlorene Verbindung mit Lange unendlich angibt. So verbreitet sich die Information, class der ausgefallene Router nicht mehr erreichbar ist, Behr schnell.
    Split Horizon Bei diesem Verfahren wird ein Router daran gehindert, eine Route zu einem bestimmten Ziel zuruck an den Router zu ubermitteln, von dem er these Route gelernt hat. Dadurch kann ein Router B, der die Verbindung zu einem anderen Router C verloren hat, nicht seinen Nachbarn A fragen, wie man nach C kommt, solange A davon ausgeht, dass dies uber B geht.
    Beide Verfahren haben jedoch das Problem, dass sie bei langeren Kreisen im Netzwerk nicht mehr zuverlassig arbeiten.
2.2.2 Autonome Systeme
    Sowohl Link-State-Routing als auch Distance-Vector-Routing benotigen fur jeden teilnehmenden Rechner mindestens einen Eintrag. Bei Link-State-Routing musste jeder Rechner/Router sogar jede Verbindung im Netzwerk kennen. Nun gibt es Millionen von Router-Knoten im Internet, and die Anzahl der Endgerate ist noch wesentlich hoher. Daher ist es einfach nicht moglich, Routing-Tabellen nach diesen Verfahren zu erstellen. Auch statisches Routing ist kein gangbarer Weg.
    Dieses Problem wird durch die EinfUhrung von Hierarchien gelost. Hierzu wird das Internet in so genannte Autonome Systeme (AS) partitioniert. Ein Autonomes System ist ein Teilnetz im Internet, das unter einer dedizierten Verwaltung steht. Dieses Netz wiederum kann sich aus Teilnetzen zusammensetzen. Ublicherweise gehort ein autonomes System einem Internetdienstanbieter, einer Universitat, z.B. uni-freiburg. de, oder einem Unternehmen, das mit den ubrigen Rechnern des Internets moglicherweise mehrfach verbunden ist. Diese Autonomen Systeme besitzen so genannte Boundary Router, die verschiedene Autonome Systeme verbinden, siehe Abbildung 2.8. Der Vorteil dieser Netzwerkstruktur ist, dass die GroBe der Routing-Tabelle nur noch von der GroBe des eigenen Autonomen Systems abhangt. Anderungen von Eintragen in den