Peer-to-Peer-Netzwerke: Algorithmen und Methoden

(Dazu gleich mehr.)

    • Empfangt ein Peer eine solche Nachricht, die er nicht mehr weiterleiten kann, fuhrt er die in der Nachricht enthaltene Funktion aus.
    • Die mitgesendete Funktion transferiert Links auf Daten zum neuen Peer, falls dieser einen alten Surrogate-Peer ersetzt, and entfernt nicht mehr benotigte Links. Auf diese Weise wird verhindert, dass Daten unerreichbar werden.
    • Jeder Peer, der Multicast-Nachrichten verschickt hat, erwartet eine Ruckmeldung (Acknowledgement) von alien Empfangern. Sind alle Ruckmeldungen eingetroffen, so benachrichtigt er den im Aufrufbaum „uber" ihm liegenden Peer.
    Wir werden nun zeigen, dass der Acknowledged-Multicast-Algorithmus tatsachlich alle Peers mit Prafix z im Netzwerk erreicht.
    Theorem 6.5. Wenn der Empfdnger einer Multicast-Nachricht mit Pri fix z sein Acknowledgement versendet, dann haben zuvor alle Peers mit Prdfix z eine MulticastNachricht erhalten.

    Beweis. Wir zeigen die Korrektheit des Theorems durch Induktion uber die Lange des Prafix z.
    Induktionsanfang: Wir nehmen an, class Peer p eine Multicast-Nachricht mit Prafix z erhalt and p der einzige Peer mit Prafix z ist. In diesem Fall ist die Behauptung offensichtlich korrekt.
    Induktionsschritt: (z j = i z j = i - 1): Angenommen, die Behauptung gilt fur ein Prafix z mit I z I = i. Des Weiteren nehmen wir an, dass Peer p eine MulticastNachricht mit Prafix z erhalt. Dann sendet p Multicast-Nachrichten an jeweils einen Peer mit den moglichen Erweiterungen von z (also z o j, fur alle j E B). Sobald p von jedem dieser Peers Acknowledgment-Nachrichten erhalten hat, wurden alle Peers mit Prafix z erreicht. Da p auf diese Acknowledge-Nachrichten wartet, bevor die eigene Acknowledge-Nachricht gesendet wird, haben bereits alle Peers mit Prafix z eine Multicast-Nachricht erhalten, wenn p sein Acknowledgement sendet.
    Dies beweist das Theorem. ❑
    Wir kommen nun zu Schritt 3 des Einfuge-Algorithmus fur neue Peers. In diesem mussen die Nachbarschaftsmengen des neuen Peers aufgebaut and optimiert werden, um die Eigenschaften I (Konsistenz) and insbesondere Eigenschaft 2 (Lokalitat) zu erfullen. Dies kommt dem Loten des Nachste-Nachbarn-Problems fur viele verschiedene Prafixe gleich.
    Der Aufbau der Nachbarschaftsmengen geschieht Level fur Level. Aus dem vor- hergehenden Schritt (Multicast) kennen wir bereits alle Peers, die das langste gemeinsame Prafix z, I z I = i, mit dem neuen Peer p teilen. Somit sind alle potenziellen Level i-Nachbarn bekannt, and es mUssen nur noch fur jede der Mengen Nz j, j E B, die jeweils k nachsten von diesen ausgewahlt werden.
    Anschliel3end werden sukzessive die Level (i -1)-Nachbarn mit Hilfe der zuvor berechneten Level i-Nachbarn berechnet, bis Level 0 erreicht wurde. Dies geschieht mit Hilfe des folgenden Algorithmus:
    1. Fordere von allen Level i-Nachbarn Listen ihrer Level (i - 1)-Nachbarn an.
    2. Messe die Entfernung zu jedem der in Schritt I erhaltenen Peers gemaB einer gewahlten Metrik (z.B. durch die RTT - Round Trip Time).
    3. Wahle die k nachsten Elemente fur jedes j aus and speichere diese in der entsprechenden Nachbarschaftsmenge.
    Schritt 2 des Algorithmus ist von elementarer Bedeutung fur die Lokalitatseigenschaft des Netzwerks. Damit der oben stehende Algorithmus tatsachlich eine Routing-Tabelle generiert, die der Lokalitatseigenschaft genugt, muss gelten, dass mit Hilfe der k nachsten Level i-Nachbarn mit hoher Wahrscheinlichkeit die k nachsten Level (i - 1)-Nachbarn gefunden werden konnen. Dies ist tatsachlich mit hoher Wahrscheinlichkeit moglich, wenn zum einen k E O(log n) gewahlt wird, d.h., jede der Nachbarschaftsmengen enthalt O(log n) Elemente, and fur den durch die Latenzzeiten definierten metrischen Raum die folgende Restriktion gilt:
    Wachstumsrestriktion: Bezeichne B,(r) die Menge aller Peers, die sich im Ball mit Radius r um Peer p befinden. Dann muss fur eine Konstante c

    and c2 < 2b gelten. Die Konstante c wird auch als Expansionskonstante des Netzwerks bezeichnet.
    Diese Restriktion ahnelt derjenigen im Plaxton-Routing. Man kann sich dies etwa als eine gleichmaBige Verteilung der Peers im Raum vorstellen, die gelten muss. Gilt these Annahme nicht, so ist nicht mehr garantiert, class der Algorithmus mit hoher Wahrscheinlichkeit die Lokalitatseigenschaft der Nachbarschaftsmengen aufrechterhalten kann. Wir werden auf den Beweis der Korrektheit des Algorithmus an dieser Stelle verzichten. Dieser kann in [12] nachgelesen werden.
    Betrachten wir