Peer-to-Peer-Netzwerke: Algorithmen und Methoden

auf DHT basierender Peer-to-Peer-Netzwerke zwei einfache, effiziente Peerto-Peer-Netzwerke kennengelernt. Kombiniert man Koorde mit dem Prinzip der vielfachen Auswahl, so hat es wie das Distance-Halving-Netzwerk and Viceroy mit hoher Wahrscheinlichkeit konstanten Ein- and Ausgrad and logarithmischen Durchmesser. Alle drei Netzwerke erlauben Methoden zur Lastbalancierung and logarithmischen Routing. Die Einfugeoperation von Peers benotigt dann jeweils O(log2 n) Schritte and Nachrichten.
    Ferner wurde hier erstmals das Prinzip des Ubergangs von kontinuierlichen zu diskreten Graphen vorgestellt. Dieses Prinzip wird implizit in Chord, Koorde, Viceroy and CAN verwendet.
    Das Prinzip der vielfachen Auswahl kann auch auf andere Peer-to-Peer-Netzwerke angewendet werden. So kann man damit bei Chord den Ein- and Ausgrad auf O(log n) optimieren. Trotzdem wird die Einfugeoperationen weiterhin Aufwand O(log2 n) benotigen. Wie bereits gesagt, kann dieses Prinzip auch bei Koorde angewendet werden. Dann ist dort der Ein- and Ausgrad konstant and der fur die EinfugeOperationen benotigte Aufwand 0(log2 n). Bei naherer Betrachtung verschwinden zunehmend die Unterschiede zwischen Koorde and dem Distance-HalvingNetzwerk. Die Komplexitat von Viceroy dagegen zeigt, dass das Butterfly-Netzwerk als Konstruktionsprinzip fur Peer-to-Peer-Netzwerke kaum geeignet sind.

8

Geordnete Indizierung
    Ordnung ist das halbe Leben. ... aber die andere Hdlfte ist schoner.
    Volksmund
    Bis jetzt haben wir hauptsachlich Peer-to-Peer-Netzwerke kennengelernt, deren Indizierung durch verteilte Hash-Tabellen vorgenommen wird. Damit werden die Peers gleichmaBig belastet and kleine Anderungen im Datenbestand oder in der Menge der anwesenden Peers haben nur lokale Auswirkungen. Leider verliert man Beziehungen zwischen den Daten. So werden zum Beispiel die Indizes von „Peerto-Peer-Netzwerke" and „Peer-to-Peer Netzwerke" durch das Hashing wahrscheinlich an vollig verschiedenen Orten abgelegt, obgleich sich die beiden Zeichenketten nur wenig unterscheiden. Eine Suche nach irgend einem Stichwort, das mit „Peer" anfangt, ist also in verteilten Hash-Tabellen nicht effizient moglich.
    In diesem Kapitel stellen wir Methoden vor, die es Peer-to-Peer-Netzwerken ermoglichen, die Beziehungen der Daten im Netzwerk zu erhalten. In den folgenden Netzwerken werden ahnliche Daten auf denselben oder wenigstens leicht erreichbaren Peers abgelegt.
8.1 P-Grid
    Das P-Grid-Netzwerk [47, 48] wurde 2001 an der EPFL (Ecole Polytechnique Federale de Lausanne) von Karl Aberer entwickelt. Es beruht auf der Verwendung eines bindren Suchbaums and der geeigneten Verteilung der Peers in dieser Datenstruktur.
    Ein Suchbaum ist eine klassische Datenstruktur zur effizienten Speicherung and Suche von Daten. Wir beschreiben den Suchbaum als gerichteten Graphen mit einem Wurzelknoten and Kanten, die in Richtung der Blatter des Baums zeigen. P-Grid betrachtet den Spezialfall eines Binarbaums. Alle Kanten sind mit 0 oder 1 nummeriert. Es geht also von jedem inneren Knoten hochstens eine Null- oder Einskante aus.

    Mit Hilfe dieser Kanten erhalt man zu jedem Knoten des Baums einen eindeutigen Pfad. Die Konkatenation (Aneinanderreihung) der Ziffern an den zugehorigen Kanten weist jedem Knoten eine eindeutige Bitfolge zu. Die Wurzel erhalt die leere Zeichenkette E. Umgekehrt kann man so auch jeder Zeichenkette einen Pfad in dem Binarbaum zuordnen, indem man geeignete Knoten and Kanten einfugt, wobei es vorkommen kann, dass man in einem Blatt endet, bevor man die Bitfolge abgearbeitet hat, oder dass die Bitfolge zu kurz ist and man in einem inneren Knoten endet. Solch einen Binarbaum nennt man einen Trie.
    Der Begriff Trie (manchmal ausgesprochen wie das englische Wort „tree", manchmal wie das englische Wort „try") entstand aus den Begriffen reTRIEval TREE. Diese Baume werden unter anderem zur effizienten Suche in Texten and zur Textkompression verwendet. Normalerweise stehen in einem Trie nicht binare Ziffern, sondern die Buchstaben des lateinischen Alphabets auf den Kanten, siehe Abbildung 8.1. Jeder Knoten bezeichnet dann ein Wort eines Worterbuchs. Die WOrter eines Textes werden auf den internen Knoten and den Blattern des Baums (Trie) gespeichert. Manch einer kennt vielleicht die Darstellung des Morse-Codes als Trie, welche hier zur Veranschaulichung des Prinzips des Tries angefuhrt wird, siehe Abbildung 8.2. Statt 0 and 1 stehen hier - and • auf den Kanten and die Buchstaben auf den