Peer-to-Peer-Netzwerke: Algorithmen und Methoden

diesem Grund werden wir im folgenden Abschnitt zunachst das Butterfly-Netzwerk vorstellen and dann sehen wie dieses in Viceroy eingesetzt wird.
7.1.1 Das Butterfly-Netzwerk
    Das Butterfly-Netzwerk ist ein sehr bekanntes Netzwerk mit hervorragenden Kom- munikationseigenschaften, das schon lange vor der Zeit der Peer-to-Peer-Netzwerke eingesetzt wurde. Im Gegensatz zu Peer-to-Peer-Netzwerken, welche wie wir inzwischen wissen sehr dynamisch sind, handelt es sich bei dem Butterfly-Netzwerk um ein statisches Netzwerk, d.h., es ist nicht so konzipiert, dass wahrend des Betriebs weitere Netzwerkknoten eingefdgt werden konnen. Ein typisches Anwendungsbei- spiel fur das Butterfly-Netzwerk ist zum Beispiel die Verbindung der Prozessoren eines Parallel-Rechners.
    Wir kommen nun zur formalen Definition des Butterfly-Netzwerks. Bezeichne von nun an u(i) fur ein Binirwort u E {0,1}* das Binarwort, das sick lediglich im i-ten Bit von u unterscheidet. Dann ist das Butterfly-Netzwerk wie folgt definiert.
    Definition 7.1 (Butterfly-Netzwerk). Das Butterfly-Netzwerk der Dimension k wird als BF(k) = (Vk, Ek) bezeichnet. Knotenmenge Vk and Kantenmenge Ek sind wie folgt definiert:

    Die Kanten der ersten Mengen bezeichnen wir dabei als Kreiskanten and die Kanten der zweiten Menge als Kreuzkanten.

    Die Knoten (i, u) des Butterfly-Netzwerks sind in Ebenen eingeteilt, wobei i jeweils die Ebene angibt. Abbildung 7.1 zeigt das Butterfly-Netzwerk BF(3). Man beachte, dass dieses lediglich aus drei Ebenen besteht, denn die Knoten der Ebene 0 werden in Abbildung 7.1 zweimal dargestellt, um das Einzeichnen der Kreuzkanten zwischen den Ebenen 0 and k - 1 zu vereinfachen.
    Abb. 7.1. Das Butterfly-Netzwerk BF(3).
    Das folgende Theorem fasst einige grundlegenden Eigenschaften des ButterflyNetzwerks zusammen.
    Theorem 7.2. Das Butterfly-Netzwerk BF(k) der Dimension k besitzt die folgenden Eigenschaften:
    1. BF(k) besitzt k2k Knoten and 4k2k-t = k2k+1 Kanten.
    2. BF(k) ist 4 regular.

    Beweis. Die Anzahl der Knoten folgt direkt aus der Definition des Netzwerks. Der regulare Grad 4 entsteht, da jeder Knoten jeweils eine Kreiskante and eine Kreuzkante zum nachst hoheren and niedrigeren Level besitzt. Aus diesen beiden Eigenschaften lasst sich nun leicht die Anzahl der Kamen bestimmen, indem die Anzahl der Knoten mit dem Grad multipliziert and durch 2 geteilt wird, da jede Kante zu zwei Knoten adjazent ist.

    Daruber hinaus besitzt das Butterfly-Netzwerk eine ganze Reihe weiterer positiver Eigenschaften, auf die wir hier allerdings nicht naher eingehen mochten. Beispielhaft sei die hohe Fehlertoleranz erwahnt, d.h., ein Butterfly-Netzwerk bleibt auch beim Ausfall vieler Knoten zusammenhangend. Wir halten also test, dass viele Grunde dafur sprechen ein Butterfly-Netzwerk als Verbindungsstruktur zu wahlen - auch fur Peer-to-Peer-Netzwerke.
7.1.2 Ubersicht
    Die Zielsetzungen von Viceroy waren neben der Skalierbarkeit die Bewaltigung von dynamischen Lastanforderungen and die gleichmaBige Verteilung des Nachrichten- aufkommens (Traffic). Diese gleichmaBige Verteilung misst man mit dem Begriff der Congestion. Die Congestion fur einen bestimmten Routing-Algorithmus and ein bestimmtes Routing-Problem (in unserem Fall eine bestimmte Menge von Routing- Operationen) ist definiert als die maximale Anzahl von Paketen, die ein Peer trans- portieren muss. Es ist offensichtlich, dass die Congestion eine untere Schranke fur die Zeit, die zur Beforderung aller Nachrichten benotigt wird, darstellt.
    Neben der Congestion sollen naturlich sowohl die Kosten fur das Einfugen and das Entfernen von Peers gering gehalten werden als auch die Lange der Suchpfade. All these Eigenschaften erfullt Viceroy. Zugleich war Viceroy das erste Peer-to-PeerNetzwerk mit optimalem Verhaltnis zwischen Grad and Durchmesser.
7.1.3 Netzwerkstruktur von Viceroy
    Wie bereits erwahnt, basiert Viceroy auf verteilten Hash-Tabellen nach Chord- Vorbild. Der einzige Unterschied zur Umsetzung in Chord ist, dass der Raum fur das Hashing hier nicht aus den ganzen Zahlen 0, ... 2'n - 1, sondern aus dem reellen [0, 1) Intervall besteht.

    Der Aufbau der Netzwerkstruktur von Viceroy ist etwas komplexer als der vergleichbarer Netzwerke. Vom Prinzip her wird in Viceroy versucht die Peers auf die Knoten eines Butterfly-Netzwerks zu setzen. So wahlt jeder Peer eine zufallige ID u aus dem Intervall [0, 1) sowie eine zufallige Ebene i, 1 < i < [log n]. Im Gegensatz zur Ebene, wird die ID eines Peers wahrend seiner