Peer-to-Peer-Netzwerke: Algorithmen und Methoden

(Exchange-Operation). Bezeichne -s die Negation eines Bits s. Die Exchange-Operation exchange(S) negiert das am weitesten rechts stehende Bit eines Bindrworts S, d.h.

    Abb. 7.12. Die Exchange-Operation.
    Definition 7.14 (Shuffle-Exchange-Operation). Bei einer Shuffle-Exchange-Operation (auch als SE bezeichnet) wird zuerst eine Shuffle- and dann eine ExchangeOperation auf S angewendet, d.h.

    In der Bit-Darstellung von S ergibt sich:

    Abb. 7.13. Die Shuffle-Exchange-Operation.
    Die drei Operation werden in den Abbildungen 7.11, 7.12 and 7.13 veranschaulicht. Wir halten zunachst folgende Beobachtung fest.
    Lemma 7.15. Ein Binarwort A der Lange m ldsst sich durch m faches Anwenden von Shuffle- and Shuffle-Exchange-Operationen in jedes beliebige Binarwort B gleicher Lange transformieren.
    In Abbildung 7.14 wird eine solche Transformation beispielhaft fur die Binar- worter A = 0111011 and B = 1001111 durchgefuhrt. Man sieht hier, dass jedes der m Bits sukzessive auf den korrekten Wert gesetzt wird. Die notwendige Folge der Operationen erhalt man, indem man A and B bitweise durch XOR (Ex- klusives Oder) verknUpft. Ein 1-Bit in der XOR Verknupfung zeigt dann an, dass eine Shuffle-Exchange-Operation anzuwenden ist and ein 0-Bit zeigt an, dass eine Shuffle-Operation anzuwenden ist.
    Das De-Bruijn-Netzwerk lasst sichjetzt leicht mit Hilfe von Shuffle- and ShuffleExchange-Operationen definieren. Das Netzwerk besteht aus n = 2k Knoten, die jeweils eine k-stellige Binarzahl darstellen. Jeder Knoten v besitzt zwei ausgehende Kanten, wobei die erste Kante von v auf den Knoten shuffle(v) and die zweite Kante auf den Knoten shuffle-exchange(v) zeigt.
    Definition 7.16 (De-Bruijn-Netzwerk). Das DeBruijn-Netzwerk der Dimension k wird als DB(k) = (Vk, Ek) bezeichnet. Knotenmenge Vk and Kantenmenge Ek sind wie folgt definiert:

    Die Kanten der ersten Mengen sind die Shuffle-Kanten and die Kanten der zweiten Menge sind die Shuffle-Exchange-Kanten.

    Abb. 7.14. Anwendung der Shuffle- and Shuffle-Exchange-Operation. Jedes Binarwort der Lange m (asst sich durch m Shuffle- oder Shuffle-Exchange-Operationen in jedes andere Binarwort gleicher Lange uberfiihren.
    Zur Veranschulichung wird in Abbildung 7.15 das De-Bruijn-Netzwerk DB(4) mit 16 Knoten dargestellt. Es ist gut zu erkennen, dass die gestrichelten ShuffleKanten Kreise im Netzwerk bilden. Das folgende Lemma fasst einige Eigenschaften des De-Bruijn-Netzwerks zusammen.
    Lemma 7.17. Das De-Bruijn-Net.werk DB(k) der Dimension k besitzt die folgenden Eigenschaften:
    1. DB(k) besteht aus 2k Knoten and 2k+1 Kanten.
    2. Jeder Knoten des DB(k) hat Eingrad and Ausgrad 2.
    3. DB(k) hat Durchmesser k.
    Beweis. Die Aussagen Uber die Anzahl der Knoten, die Anzahl der Kamen sowie den Ausgrad der Knoten folgen direkt aus der Definition von DB(k). Die Aussage uber den Eingrad 2 der Knoten gilt, da sowohl die Shuffle- als auch die ShuffleExchange-Operationen Permutationen uber den Binarzahlen sind.

    Dass der Durchmesser hochstens k = log it ist, folgt direkt aus Lemma 7.15. Am Beispiel der Knoten 0 ... 0 and 1...1 lasst sich leicht einsehen, dass auch tatsachlich Knoten mit dieser Entfernung existieren. ❑
    Das De-Bruijn-Netzwerk besitzt also ahnlich gute Eigenschaften wie das von Viceroy verwendete Butterfly-Netzwerk. Die Umsetzung des Butterfly-Netzwerks in ein Peer-to-Peer Netzwerk war im Fall von Viceroy jedoch vergleichsweise kompliziert. Wie wir jetzt sehen werden, lasst sich die Struktur des De-Bruijn-Netzwerks eleganter in ein Peer-to-Peer-Netzwerk umsetzen.
    Abb. 7.15. Das De-Bruijn-Netzwerk DB(4). Die Shuffle-Kanten werden gestrichelt dargestellt.

7.3.2 Netzwerkstruktur and Routing
    Wie erwahnt, kombiniert das Koorde-Netzwerk das De-Bruijn-Netzwerk mit einer Ringstruktur. Die Ringstruktur wird wiederum fur das verteilte Hashing verwendet and hat die GrOBe 2r" . Somit werden auch die Peer-IDs zufallig aus den Zahlen 0, ... , 2" - 1 gewahlt. Wurde man m = 4 wahlen and ware tatsachlich die somit maximale Anzahl von 16 Peers im Netzwerk vorhanden, so wurde sich die in Abbildung 7.16 dargestellte Netzwerkstruktur ergeben. Wie in der Abbildung zu sehen ist, besitzt jeder Peer zwei Ringkanten and zwei De-Bruijn-Kanten.
    Abb. 7.16. Das De-Bruijn-Netzwerk fur 16 Knoten. Die Knoten sind sortiert auf dem Ring aufgetragen.
    Um these scheinbar verwirrende Struktur besser zu verstehen, betrachten wir noch einmal die Shuffle- and Shuffle-Exchange-Operationen and interpretieren die Peer-IDs als game Zahlen