Peer-to-Peer-Netzwerke: Algorithmen und Methoden

Storage-Server liegen, bei der Suche schnell auf Abkurzungen durch Links treffen and mussen nicht his zum Storage-Server routen.
    In Abbildung 6.14 wird der gerade beschriebene Routing-Vorgang dargestellt. Der Peer mit ID 197E sucht nach dem Datum mit ID 4378 and schickt die Anfrage an den zustandigen Root-Server 4377. Auf dem Weg zum Root-Server wird beim Peer mit ID 4361 ein Link der vorangegangenen Publikation fur das gesuchte Datum gefunden. Das Routing wird daraufhin abgebrochen and es wird direkt zu demjenigen verlinkten Peer mit ID 39AA gesprungen, der das gesuchte Datum bereitstellt, and somit werden zwei Hops bis zum Root-Server eingespart.
6.3.3 Surrogate-Routing
    Ein bislang vernachlassigtes Problem ist, dass die von MapRoots(b) gelieferten Peer IDs unter Umstanden gar nicht im Netzwerk existieren. Dies ist sogar wahrscheinlich, da der Namensraum nur Behr dunn besetzt ist, um Kollisionen zu vermeiden. Ein anderes Problem sind die dadurch entstehenden Locher in den Routing-Tabellen.
    Die Losung fur dieses Problem wurde von den Tapestry-Autoren SurrogateRouting genannt (ubersetzt etwa: Ersatz-Wegewahl) and funktioniert wie folgt: Wie zuvor wird schrittweise versucht, den Root-Server zu erreichen. Stoat man dabei auf ein Loch an der Stelle (z, j) der Routing-Tabelle eines Peers, so wird stattdessen nach (z, j + 1) weitergeleitet. Handelt es sich auch dabei um ein Loch in der Routing-Tabelle, wird jeweils das nachst hohere j E B gewahlt and nach dem Erreichen der groBten Ziffer aus B wird mit der Ziffer 0 fortgefahren. Dieser Vorgang wird so lange wiederholt, his der gesuchte Peer erreicht wurde oder der aktuelle Peer keine Eintrage in hoheren Levels and nur den einen, uber den er erreicht wurde, im aktuellen Level seiner Routing-Tabelle hat. Es gilt nun folgendes Theorem Ober das Verhalten des Surrogate-Routing:
    Theorem 6.4. Wenn Eigenschaft 1 (Konsistenz) gilt, dann wird durch SurrogateRouting ein eindeutiger Peer erreicht, egal von wo im Netzwerk das Routing starter.

    Wir halten an dieser Stelle test, dass Surrogate-Routing fur insgesamt n Peers hochstens O(log n) Hops benotigt, um das gewUnschte Ziel zu erreichen, da mit jedem Schritt eine Ziffer an die gesuchte ID angepasst wird and mit hotter Wahrscheinlichkeit lediglich die ersten O(log n) Level der Routing-Tabellen mit Eintragen besetzt sind. Letzteres folgt aus dem Beweis des Lemma 6.2.
6.3.4 Einfiigen neuer Peers
    Wird ein neuer Peer in ein bestehendes Netzwerk eingefugt, so soil das resultierende Netzwerk demjenigen gleichen, das entstanden ware, wenn das Netzwerk von Grund auf mit diesem Peer entstanden ware. Um dies zu gewahrleisten, muss folgende Eigenschaft gelten, welche schon im Plaxton-Routing sichergestellt wurde.
    Abb. 6.14. Routing im Tapestry -Netzwerk.

    Eigenschaft 4: Objekt-Links auf dem Publikations Pfad. Liegt ein Peer p auf dem Pfad zwischen dem publizierenden Peer von Objekt 0 and dessen Root-Server, dann besitzt p einen Link auf den Peer der 5 bereitstellt.
    Daten bleiben jedoch auch erreichbar, wenn diese Eigenschaft nicht erfUllt ist. Im schlimmsten Fall benotigt die Suche etwas Langer Oedoch immer noch hochstens O(log n) Schritte). Deshalb verzichten wir an dieser Stelle darauf zu zeigen, wie diese Eigenschaft sichergestellt werden kann. Wir halten hier lediglich fest, dass ein einfacher Algorithmus hierfur existiert (siehe [12]).
    Kommen wir nun zum Einf ige-Algorithmus fur neue Peers. Dieser besteht aus drei wesentlichen Schritten, die wir im Folgenden naher erlautern werden:
    1. Suchen nach der eigenen ID im Netzwerk and Kopieren der Routing-Tabelle des so gefundenen Surrogate-Peers.
    2. Kontaktieren derjenigen Peers, die Locher in ihren Routing-Tabellen haben, die durch den neuen Peer gefullt werden konnen.
    3. Aufbauen and Optimieren der eigenen Routing-Tabelle.
    Schritt 1 lasst sich einfach mit dem zuvor beschriebenen Surrogate-Routing umsetzen and benotigt lediglich O(log n) Hops, so dass wir bier nicht auf weitere Details dieses Schritts eingehen.
    Schritt 2 ist erforderlich, um Eigenschaft 2 (Konsistenz) gewahrleisten zu konnen. Um dies zu erreichen, wird der so genannte Acknowledged-Multicast-Algorithmus verwendet. HierfUr wird zunachst das langste gemeinsame Prafix z von dem neuen Peer and des beim EinfUgen gefundenen Surrogate-Peers bestimmt. Daraufhin geht man wie folgt vor:
    • Der neue Peer sendet eine Multicast-Nachricht an seinen Surrogate-Peer. Diese besteht aus dem gemeinsamen Prafix and einer Funktion.