Peer-to-Peer-Netzwerke: Algorithmen und Methoden

Datums numerisch am nachsten ist. Abbildung 6.5 zeigt Pastrys Routing-Algorithmus als Pseudo-Code. Wird dieser Algorithmus beispielsweise fur die Suche nach einem Datum im Netzwerk verwendet, wird zunachst die ID des gesuchten Datums (im Folgenden auch als Ziel-ID bezeichnet) mit Hilfe der Hash-Funktion berechnet and dann der Algorithmus mit eben dieser aufgerufen.
    Wird der Algorithmus von einem Peer p aufgerufen, wird zunachst uberpruft, ob die Ziel-ID innerhalb der Grenzen des eigenen Leaf-Sets liegt. Ist dies der Fall, wird die Anfrage an denjenigen Peer des Leaf-Sets weitergeleitet, dessen ID numerisch am nachsten an der Ziel-ID liegt. Dieser Peer wird dann in der Lage sein, die Anfrage bzw. Nachricht zu beantworten, da er fur die Ziel-ID verantwortlich ist. War die Suche im Leaf-Set hingegen erfolglos, wird in der Routing-Tabelle ein Peer p' gewahlt, dessen gemeinsames Prafix mit der Ziel-ID um mindestens eine Ziffer Langer ist als das gemeinsame Prafix von p and der Ziel-ID. Dieser Peer p' wird das Routing dann mit demselben Algorithmus fortsetzen.

    Es kann, wie bereits erwahnt, vorkommen, dass die Routing-Tabelle fehlerhafte oder fehlende Eintrage besitzt. In diesem Fall wird die Suche an einen Peer p' aus alien benachbarten Peers weitergeleitet, dessen gemeinsames Prafix mit der Ziel-ID mindestens so lang ist wie dasjenige des aktuellen Peers p and dessen ID numerisch naher an der Ziel-ID liegt als diejenige von p. Ein solcher Peer p' muss zumindest im Leaf-Set existieren, es sei denn die Nachricht ist bereits beim Empfanger, also dem fur die Ziel-ID verantwortlichen Peer, angekommen. Ferner muss einer dieser Peers im Leaf-Set aktiv and erreichbar sein, wenn nicht gerade der unwahrscheinli- che Fall des simultanen Ausfalls von ILI/2 auf der Ring-Struktur benachbarten Peers eingetreten ist.
    Es ist offensichtlich, dass dieser einfache Routing-Algorithmus sein Ziel immer erreichen wird: In jedem Schritt wird die Nachricht entweder an einen Peer weitergeleitet, dessen gemeinsamer Prafix mit der Ziel-ID mindestens eine Ziffer Langer ist, oder an einen Peer, dessen ID zumindest numerisch naher an der Ziel-ID liegt.
    Betrachten wir nun die Anzahl der benotigten Nachrichten bzw. involvierten Peers unter der Annahme korrekt gefuhrter Routing-Tabellen and Leaf-Sets.
    Abb. 6.3. Die drei Nachbarschaftsklassen eines Pastry Peers.

    Abb. 6.4. Die Nachbarschaft eines Pastry Peers mit ID 001 als Netzwerkgraph. Schwarze Pfeile entsprechen den Eintragen der Routing-Tabelle R and grau gestrichelte Pfeile den Eintragen des Leaf-Sets L.

    Beweis. Fur den Beweis der Sprunganzahl O(n/l) nehmen wir an, class lediglich die Leaf-Sets fur das Weiterreichen einer Nachricht verwendet werden. In diesem Fall wurde sich die Distanz zur Zie1-ID mit jedem Schritt um I L I = f Peers verringern, so dass das Ziel nach spatestens nach n/f Schritten erreicht wird.

    Es kannjedoch vorkommen, class kein passender Eintrag fur den nachsten Schritt des Routings in einer Routing-Tabelle vorhanden ist and die Ziel-ID noch nicht innerhalb des Leaf-Sets liegt. Unter der Annahme korrekter Routing-Tabellen bedeutet dies, dass sich kein Peer mit passendem Prafix im Netzwerk befindet. Dieser Fall ist jedoch bei adaquater Wahl von ILI, z.B. 2b, sehr unwahrscheinlich. Des Weiteren wdrde dadurch mit hoher Wahrscheinlichkeit lediglich ein zusatzlicher Schritt im Netzwerk benotigt [11]. ❑
    Die in Theorem 6.3 angegebenen Schranken gelten lediglich unter der Voraussetzung korrekter Routing-Tabellen. Durch die in einem Peer-to-Peer-Netzwerk standig wechselnden Teilnehmer wird es jedoch zumeist auch Peers mit fehlerhaften Routing-Tabellen Eintragen geben. So kann Routing aus theoretischer Sicht in ex- tremen Situationen naturlich auch it Schritte benotigen oder gar scheitern, falls das Netzwerk den Zusammenhang verloren hat. Tatsachlich wird das Routing jedoch selbst bei durchgehend stark beschadigten Routing-Tabellen so gut wie niemals n/f oder gar it Schritte benotigen, da bereits wenige korrekte Routing-Tabelleneintrage eine erhebliche Reduzierung der Hop-Anzahl ermoglichen. Wir werden spater in Abschnitt 6.2.5 experimentelle Resultate betrachten, die zeigen wie sich ausfallende Peers auf den Zustand der Routing-Tabellen auswirken.

    Abb. 6.5. Routing-Algorithmus fur Pastry. Rr bezeichnet den Eintrag der Routing-Tabelle R in Spalte i and Zeile r, L_f/2 bzw. L_C/2 bezeichnen die IDs der beiden auBeren Peers des lokalen Leaf-Sets L, id, bezeichnet die r-te Ziffer