Peer-to-Peer-Netzwerke: Algorithmen und Methoden

entsprechenden Knoten.
    Abb. 8.1. Ein Beispiel eines Tries.
    Da P-Grid auf solchen Binar-Tries aufbaut, muss fur die Beschreibung von Schlusselwortern der Daten eine Umkodierung auf das Binaralphabet stattfinden. Denkbar ware die Standardkodierung mit ASCII oder Unicode. Weitaus besser ist aber eine Huffman-Kodierung, da dadurch die Baumstruktur balanciert ist: Haufig vorkommende Zeichen werden auf kurze Binarstrings abgebildet.

    Abb. 8.2. Der Morse-Code als Beispiel fiir einen Binar-Trie.
    Es ist nicht empfehlenswert, einen Baum direkt in ein Peer-to-Peer-Netzwerk umzusetzen, indem man auf jeden Knoten einen Peer setzt. Als erstes ware es ein ungewohnlicher Zufall, wenn die Anzahl der Peers der Knotenanzahl entsprache. Zweitens ist die resultierende Netzwerkstruktur nur einfach zusammenhangend. Das heiBt, geht ein interner Knoten oder irgendeine Kante verloren, so verliert der Graph and damit das Netzwerk seinen Zusammenhang. Ein solches Verhalten ist nicht akzeptabel fur ein Peer-to-Peer-Netzwerk, das andauernd den plotzlichen Ausfall von Peers verkraften muss.
8.1.1 Netzwerkstruktur von P-Grid
    Daher wird in P-Grid eine andere Zuordnung zwischen Peers and Knoten des Baums durchgefuhrt. Peers sind den internen Knoten des Baumes so zugeordnet, dass kein Peer auf dem Pfad eines anderen Peers liegt. Ferner gehen wir davon aus, dass die Daten (oder die Zeiger auf die Daten) so tief im Trie abgespeichert werden, dass niemals ein Peer unterhalb der Daten liegt. Das kann zum Beispiel dadurch erreicht werden, dass man sehr lange Schlusselworter durch Anhangen von Kontrollinformationen, wie Erzeugungsdatum, Hersteller etc. erstellt. Zuletzt wird sichergestellt, dass jeder Pfad im Baum zwischen Wurzel and den Blattern wenigstens einen Peer besitzt, siehe Abbildung 8.3.
    So gesehen formen die Peers die Blatter eines Baumes, der oberhalb der Peers mit dem Suchbaum Ubereinstimmt. Die internen Knoten dieses Baums werden durch die Peers des darunter liegenden Teilbaums mit ubernommen. Ein Peer hat in seiner Routing-Tabelle fur jeden, der zu seinem eigenen Pfad benachbarten Teilbaume, einen Eintrag, der auf einen Peer des Teilbaums verweist. AuBerdem wird vorausgesetzt, dass these Nachbarn gleichwahrscheinlich aus den jeweiligen benachbarten Teilbaumen gewahlt werden.
    Naturlich besteht nun wiederum die Gefahr, dass ganze Teilbaume wegfallen, wenn sich nur ein Peer aus dem Netzwerk entfernt. Daher geht man davon aus, dass sich staff eines Peers eine bestimmte Mindestanzahl von k Peers die Aufgaben teilen, die mit der Ubernahme eines Teilbaums entstehen.

    Abb. 8.3. Beispiel eines P-Grid-Netzwerks.
    Der Hauptgrund, warum in anderen Peer-to-Peer-Netzwerken Hash-Funktionen verwendet werden, ist die Balancierung der Daten. Die Verteilung der Daten ist namlich typischerweise nicht gleichmaBig. So sind beispielsweise in der Deutschen Sprache die Buchstaben N and E viel haufiger als die Buchstaben x and Y. Auch fur Kombinationen von Buchstaben gibt es groBe Abweichungen. So erscheint z.B. nach einem Q fast immer ein U. Kodiert man Q binar, dann wird der Pfad, der zu u fuhrt, zu fast alle Daten fuhren. Wurde man die Peers also wahllos auf die Teilbaume verteilen, so warden die Peers, die in diesem Teilbaum sind, ein deutlich hohere Last haben.

    Da Peers nur in den Blattern des Netzwerkbaums liegen, sind die Pfadlangen des Baumes dynamisch. Im Idealfall ist die Anzahl der Peers proportional zu der Anzahl der Dateneintrage. Das wird durch P-Grid nicht garantiert. AuBerdem mussen samtliche Peers fortwahrend uberprufen, inwieweit sich die Baumstruktur geandert hat. Um die Balancierung zu sichern, wird auBerdem eine kontinuierliche Rebalancierung durchgefUhrt. Hierzu hat jeder Peer eine Minimal- and eine Maximalaus- lastung. Peers, die Uberlastet sind, versuchen die Daten auf den Nachbarbaum ab- zuwalzen. Wie bei der Defragmentierung von CAN wird dadurch der Baum an dieser Stelle kurzer.
    Die freien oder freigewordenen Peers suchen fortwahrend nach uberlasteten Peers. Ist ein solcher gefunden worden, so teilen sie bei diesem Peer den Baum weiter auf.
8.1.2 Einfiigen von Peers
    Beim EinfUgen von Peers entscheidet jeder Peer selbststandig, in welchen der Teilbaume er sich einordnet. Hierzu initiiert er eine Interaktion mit einem zufallig ausgewahlten Peer (den er aus der Routing-Tabelle des in der Baumstruktur gelegenen nachsthoheren Peers erhalten hat). Mit Hilfe dieses Peers erhalt er evtl. weitere Zeiger auf Peers in diesem Teilbaum. Nun