Peer-to-Peer-Netzwerke: Algorithmen und Methoden

Anwesenheit im Netzwerk niemals geandert. Wie wir in Abschnitt 7.1.4 sehen werden, wird die Ebene unter Umstanden neu gewahlt, wenn sich die Anzahl n der Peers im Netzwerk verandert.
    Bei der Umsetzung des Butterfly-Netzwerks entstehen jedoch unter anderem die folgenden Probleme. Zunachst ist es notwendig, den Logarithmus der Anzahl der Peers im Netzwerk (also log n) zu kennen um die Anzahl der Ebenen festzulegen. Des Weiteren entstehen offensichtlich Probleme durch die zufallige Wahl der IDs sowie Ebenen and insbesondere dann, wenn die Anzahl der Peers nicht von der Form n = k • 2k mit k E N ist, da das statische Butterfly-Netzwerk nur fur ebensolche n definiert ist. Aus diesen Grunden stellt Viceroy keine Eins-zu-eins-Umsetzung des Butterfly-Netzwerks, sondern eher eine Approximation eben dieses dar.
    Fur die dynamische Approximation des Butterfly-Netzwerk werden in Viceroy die drei im Folgenden beschriebenen Klassen von Kamen verwendet.
    Ring. Dieser Ring verbindet ahnlich wie der Chord-Ring alle Peers. So ist z.B. ein Peer mit ID u mit den Peers mit nachst groBerer sowie kleinerer ID zu u verbunden. Der Ring sorgt fur einen elementaren Zusammenhalt, erlaubt Routing im Fall fehlerhafter Kanten in den beiden anderen Mengen von Kanten and bestimmt letztendlich fur welchen Teil des Hash-Raumes, also fur welchen Bereich der Daten-IDs, ein Peer verantwortlich ist.
    Ebenen-Ringe. Diese Ringe verbinden jeweils die Peers derselben Ebenen. So ist ein Peer mit Ebene i and ID a mit den Peers mit nachst groBerer sowie kleinerer ID zu u derselben Ebene verbunden.
    Butterfly-Kanten. SchlieBlich kommen noch die eigentlichen Butterfly-Kanten hinzu. Hat ein Peer Ebene i and ID u gewahlt, so unterhalt er die folgenden drei Verbindungen zu anderen Peers:
    Linke Abwartskante: Eine Verbindung zu dem Peer auf Ebene i + 1, dessen ID der Position u in aufsteigender Zahlrichtung folgt.
    Rechte Abwartskante: Eine Verbindung zu dem Peer auf Ebene i + 1, dessen ID der Position u + 1/2' in aufsteigender Zahlrichtung folgt.
    Aufwartskante: Eine Verbindung zu dem Peer auf Ebene i - 1, dessen ID der Position u in aufsteigender Zahlrichtung folgt.
    Ausnahmen bilden hier die Peers der ersten Ebene, die keine Aufwartskanten besitzen, and die Peers der letzten Ebene, die keine Abwartskanten besitzen.
    Der Zusammenhang zwischen Butterfly-Kanten and IDs der Peers wird in Abbildung 7.2 dargestellt. Wir halten test, dass der Ausgrad jedes Peers im Vieceroy- Netzwerk gerade 7 ist and sich aus zwei Zeigern fur den Ring, zwei Zeigern fur den Ebenen-Ring and drei Zeigern fur die Butterfly-Kanten zusammensetzt. Gleiches gilt fur den erwarteten Eingrad. Allerdings ist der Eingrad nur dann konstant, wenn die Peers auf den Ebenen des Netzwerks perfekt verteilt werden, d.h., der Abstand zum Nachbarn entspricht dem erwarteten Abstand bis auf einen konstanten Faktor. Da die Positionen auf dem Ring jedoch zufallig gewahlt werden, kommt mit konstanter Wahrscheinlichkeit auch ein um den Faktor log n erhohter Abstand vor. Daraus ergibt sich, dass mit konstanter Wahrscheinlichkeit auch Peers mit logarithmischem Eingrad existieren. Dieses Problem, dass ein Peer mit groBem Abstand auf seinem Ebenen-Ring viele eingehende Kamen anzieht and die Nachbarn in der vorigen Ebene mit kleineren Abstanden den Eingrad erhohen, kann man nur losen, indem man die Peers nicht rein zufallig einordnet. Um mit hoher Wahrscheinlichkeit auch einen konstanten Eingrad fur Peers zu erreichen schlagen die Autoren von Viceroy einen so genannten Bucket-Mechanismus vor, dessen Details wir hier jedoch nicht beschreiben werden (siehe [44]). Viel eleganter erhalt man aber eine gleichmaBige Verteilung mit dem Prinzip der vielfachen Auswahl [45], das wir auf Seite 138 vorstellen werden.

    Es bleibt zu zeigen, wie ein Peer eine ganzzahlige Ebene aus 1, ... , [log n] wahlen kann, oder anders formuliert: wie ein Peer die Anzahl n der sich im Netzwerk befindlichen Peers abschatzen kann.
    Abb. 7.2. Die Butterfly-Kanten von Viceroy [44]. Auf die Darstellung der Aufwartskanten wurde aus Grunden der Ubersichtlichkeit verzichtet.

7.1.4 Bestimmung der erforderlichen Ebenen
    Da in Viceroy mit steigender Anzahl n an Peers auch die Anzahl [log n] der erforderlichen Ebenen steigt, ist es notwendig, die GroBe von n oder zumindest einen Naherungswert n' von n zu kennen. In einem Peer-to-Peer-Netzwerk handelt es sich hierbei keineswegs um eine triviale Aufgabe. SchlieBlich verlassen and betre- ten standig Peers das