Peer-to-Peer-Netzwerke: Algorithmen und Methoden

abschlieBend den Aufwand des Einfiige-Algorithmus. Hierbei konzentrieren wir uns wieder auf die benotigten Schritte im Netzwerk and ver- nachlassigen lokale Berechnungen. In Schritt 1 kann der Surrogate-Peer mit O (1og n) Hops gefunden werden. Der Acknowledged-Multicast-Algorithmus (Schritt 2) benotigt 0(m) Hops, wobei m die Zahl der erreichten Peers ist. Hierbei ist m klein im Vergleich zu n and konstant. Der Aufbau der Nachbarschaftsmengen kann mit O(log2 n) Hops geschehen. Da jeder Peer eine konstante Anzahl Nachbarn je Level hat, betragt die Laufzeit des Algorithmus zum Aufbau der Nachbarschaftsmengen O(k) = O(log n) pro Level and somit insgesamt O(1og2 n) fur alle Level. Insgesamt ergibt sich somit:
    Theorem 6.6. Das Einfiigen eines neuen Peers in Tapestry kann mit O(log2 n) Hops geschehen.
6.4 Zusammenfassung
    Pastry and Tapestry werden gerne in einem Atemzug genannt. Tatsachlich beruhen beide Peer-to-Peer-Netzwerke auf demselben Routing-Prinzip von Plaxton, Rajara- man and Richa [13]. Dieses stellt eine Verallgemeinerung von Routing auf dem Hypercube dar, wobei die entstehende Kommunikationslatenz nur konstant groBer ist als die auf dem schnellsten Pfad.
    Tapestry ist nicht vollstandig selbstorganisierend, achtet aber stark auf die Konsistenz der Routing-Tabelle. Des Weiteren ist Tapestry sehr nahe am Originalverfahren von Plaxton et al. gehalten and daher analytisch gut verstanden: Tapestry hat nach- weisbare Performanzeigenschaften, wenn die Annahmen zutreffen.
    In Pastry werden statt analytischer Methodik viele heuristische Methoden bei der Umsetzung vom Plaxton-Routing eingesetzt. Die eigentliche algorithmische Beschreibung ist ungenau (zum Beispiel die Bestimmung der Menge M latenznaher Peers), and experimentelle Verifikation ersetzt hier analytische Untersuchungen. Dagegen lasst sich Pastry praktisch besser umsetzen and ist durch die EinfUhrung der Leaf-Sets sehr robust.

7

Gradminimierte Netzwerke
    In Paderborn entspringt die nur 4 km lange Pader - der kurzeste Fluss Deutschlands!
    www.paderborn-ueberzeugt.de
    Es gab einige Zeit lang einen Wettlauf, den Grad and Durchmesser von Peer-toPeer-Netzwerken zu minimieren. Der Grad eines Netzwerks ist die maximale Anzahl von Nachbarn eines Peers and der Durchmesser ist die Lange des langsten aller kurzesten Pfade zwischen zwei Peers im zugehorigen Verbindungsgraphen des Netzwerks.
    Bezeichne im Folgenden d den Grad eines Netzwerks. Somit besitzt ein Peer hochstens d direkte Nachbarn and hochstens d' Nachbarn in Distanz kleiner gleich i. Damit ein Netzwerk den Durchmesser IT besitzt, muss
    d h > n

    Aus dieser Sicht ist das in in Kapitel 4 vorgestellte CAN mit einem polyno- miellen Durchmesser and einem konstanten Grad nicht sonderlich effizient. Auch Chord, Pastry and Tapestry sind mit logarithmischem Grad and Durchmesser nicht optimal. Wir stellen in diesem Kapitel drei gradminimierte Netzwerke vor, die es schaffen, ein effizientes Peer-to-Peer-Netzwerk mit konstantem Grad and logarithmischem Durchmesser zu organisieren. Viceroy war das erste Peer-to-Peer-Netzwerk, das mit konstantem Ein- and Ausgrad einen logarithmischen Durchmesser erreicht hat. Kurze Zeit spater folgten dann das Distance-Halving Netzwerk and Koorde. Beide reduzieren nochmals den Grad and verwenden eine einfachere Netzwerkstruktur als Viceroy.
    Die drei in diesem Kapitel vorgestellten Netzwerke verwenden alle verteilte Hash-Tabellen fur die Zuordnung von Daten zu Peers. Die Umsetzung der verteil ten Hash-Tabellen geschieht dabei weitgehend wie im Chord-Netzwerk, d.h., Peers and Daten werden eindeutige Positionen in einem eindimensionalem Raum zugewiesen, welcher als Ring betrachtet wird. Ein Datum wird jeweils von demjenigen Peer verwaltet, das der Position des Datums in aufsteigender Zahlrichtung auf dem Ring folgt. Wir verweisen an dieser Stelle fur weitere Details lediglich auf Kapitel 5.1 and werden bei den drei in diesem Kapitel vorgestellten Netzwerken nicht nochmals auf die Umsetzung der verteilten Hash-Tabellen eingehen, es sei denn es existieren Unterschiede zu Chord.

7.1 Viceroy
    Viceroy ist ein von Dahlia Malkhi, Moni Naor and David Ratajczak entwickeltes Peer-to-Peer Netzwerk and wurde im Jahr 2001 vorgestellt. Viceroy ist das englische Wort fur Vizekonig and bezeichnet zugleich eine Schmetterlingsart. Letzteres weist auf die Grundstruktur des Netzwerks hin: Viceroy stellt eine skalierbare and dynamische Emulation des Butterfly-Netzwerks in einem Peer-to-Peer-Netzwerk dar. Aus