Peer-to-Peer-Netzwerke: Algorithmen und Methoden

gleichmaBig auf die Peers verteilt. Um zunachst die grundlegende Idee des Routings in diesem Netzwerk zu vermitteln, betrachten wir zunachst eine vereinfachte Variante, die die Last nicht so gleichmaBig verteilt, jedoch auch nur eine logarithmische Anzahl an Schritten benotigt. Dieser einfache Routing-Algorithmus arbeitet rekursiv and ist in Abbildung 7.6 dargestellt.

    Abb. 7.6. Routing mittels Linkskanten and Ruckwiirts-Linkskanten im Distance-HalvingNetzwerk.

    Abb. 7.7. Ein alternativer Routing-Algorithmus mit Rechtskanten and RuckwartsRechtskanten fur das Distance-Halving-Netzwerk.
    Dieser Algorithmus verwendet nur die Linkskanten. Hierzu berechnet der StartPeer zwei Zwischenstationen and reduziert das Routing-Problem auf eines mit der halben Entfernung. Dies geschieht solange, his Start- and Zielknoten benachbart sind. Man konnte den Eindruck gewinnen, dass der Zielknoten sich an der Suche beteiligt, was aber nicht korrekt ist. SchlieBlich ,weiB" dieser nicht, dass er gesucht wird. Die Berechnung der ersten Zwischenstationen wird vom Startknoten durch- gefiihrt. Diesen Zwischenstationen muss nun noch mitgeteilt werden, auf welchem weiteren Weg die Nachricht zu befordern ist. In Abbildung 7.8 ist ein typischer Routing dutch Verwendung von Linkskanten dargestellt. NatUrlich funktioniert das Routing auch dutch die Verwendung von Rechtskanten, siehe Abbildung 7.7.

    Abb. 7.8. Routing im Distance-Halving-Netzwerk mit Linkskanten.
    Fur beide Algorithmen wird die Distanz zwischen Start and Ziel mit jedern Rekursionsschritt halbiert and jeder Rekursionsschritt benotigt zwei Schritte. Da rich alle Intervallgrof3en nur urn den Faktor p = 4 unterscheiden, benotigt der RoutingAlgorithmus hochstens 1 + log n Rekursionen urn eine Nachricht auszuliefern. Es ergibt sich somit als Routing-Aufwand 2 log n + 3:
    Lemma 7.11. Mit hoher Wahrscheinlichkeit benotigt das Routing im Distance-Halving-Netzwerk hochstens 2 log n + 3 Nachrichten and Schritte.
    Da die Links- and Rechtskanten in diesen Algorithmen beliebig ausgetauscht werden konnen, ergibt rich auch die Moglichkeit, die Orientierung (paarweise) durch Munzwurf zu bestimmen. So erhalt man den in Abbildung 7.9 dargesteliten Algorithmus, der ebenfalls hochstens 2 log n + 3 Schritte benotigt.

    Abb. 7.9. Congestion-optimierter Suchalgorithmus fur das Distance-Halving-Netzwerk.
    Abb. 7.10. Routing im Distance-Halving-Netzwerk mit Links- and Rechtskanten.

    Wahrend die ersten beiden Algorithmen dazu tendieren, den Verkehr in die auBerste linke oder rechte Ecke des Intervalls zu senden, sorgt dieser Algorithmus fur eine sehr gute Verteilung der Datenlast. Man kann hier zeigen, dass die Belastung (Congestion) sehr gering ausfallt.
    Es stellt sich heraus, dass das Distance-Halving-Netzwerk eine elegante and einfache Alternative zum komplizierten Butterfly-Graph-basierten Viceroy ist. Wir werden jetzt noch eine weitere einfache Alternative diskutieren.
7.3 Koorde
    Das Peer-to-Peer-Netzwerk Koorde von David Karger and M. Frans Kaashoek [46] ist eine Verbesserung des Ansatzes von Chord hinsichtlich des Grades der Knoten and dem Aufwand fur die Einfugeoperationen. Wir haben bei Chord einen Grad von O(log n) (mit hoher Wahrscheinlichkeit) and einen Durchmesser von O(log n) be- obachtet. Einen wesentlich kleineren Grad kann man bei diesem Durchmesser nicht erwarten, denn wir haben bereits zu Beginn dieses Kapitels festgestellt, dass bei Grad d in It Schritten hochstens dh Knoten erreicht werden konnen.

7.3.1 Das De-Bruijn-Netzwerk
    Das De-Bruijn-Netzwerk ist benannt nach seinem Entdecker Nicolaas Govert de Bruijn and kommt zum Beispiel in Parallelrechnern zum Einsatz. Das Netzwerk besitzt zudem die besondere Eigenschaft so genannte De-Bruijn-Sequenzen durch den Ablauf eines Hamiltonschen Kreises' im Netzwerk erzeugen zu konnen. Eine De-Bruijn-Sequenz B(k, n) ist eine zyklische Folge von Zeichen uber einem Alphabet A der GroBe k, in der jede mogliche Teilfolge der Lange it aus A exakt einmal vorkommt. Diese Eigenschaft sei hierjedoch nur am Rande erwi hnt.

    Bevor wir zur eigentlichen Definition des De-Bruijn-Netzwerks kommen, definieren wir zunachst drei einfache Operationen auf Binarwortern. Bezeichne im Folgenden S = (sl, 82, ... , S n) mit si E {0, 1} ein Binarwort der Lange m.
    Definition 7.12 (Shuffle-Operation). Die Shuffle-Operation shuffle(S) rotiert die Bits eines Bindrworts S um eine Stelle nach links, d.h.

    Abb. 7.11. Die Shuffle-Operation.
    Definition 7.13