Peer-to-Peer-Netzwerke: Algorithmen und Methoden

Phase mit hoher Wahrscheinlichkeit hochstens O(log2 n) Schritte entlang des Rings vom Ziel entfernt sind.

7.1.6 Einfiigen eines Peers
    Betritt ein neuer Peer p mittels eines Peers pa, das Viceroy-Netzwerk, so wahlt er zunachst zufallig seine ID u E [0, 1) and erhalt von pa, eine Schatzung n' der Peer- Anzahl n, mittels welcher er ebenfalls zufallig eine Ebene aus i E {0, ... , [log n'] } wahlt. Peer p wird dann uber Peer pa eine Suche nach dem fur seine eigene ID u verantwortlichen Peer pz durchfuhren. Zur Einbindung in das Netzwerk wird p dann zunachst in die Ringstruktur integriert and einen Teil der von pz verwalteten Daten ubernehmen. Darauf wird p in den Ring der Ebene i eingebunden and seine den Butterfly-Kanten entsprechenden Nachbarn wahlen. Ebenso werden die entsprechenden Peers der benachbarten Ebenen informiert, ihre Zeiger neu zu justieren.
    Die Anzahl der Schritte and Nachrichten fur das Einfigen eines Peers besteht damit im Wesentlichen aus der Zeit fur die Suche nach der eigenen ID mit O(log n) and das Aufbauen der Routing-Tabelle mit Zeit O(1og n).

7.1.7 Diskussion
    Viceroy war das erste Peer-to-Peer-Netzwerk mit konstantem Ausgrad. Mittels weiterer (hier nicht vorgestellter) Techniken, kann auch der Eingrad mit hoher Wahrscheinlichkeit konstant gehalten werden. Diese Techniken verursachen jedoch zusatzlichen Aufwand. Des Weiteren ist die Netzwerktopologie durch die mehrfache Ringstruktur vergleichsweise kompliziert and erschwert die praktische Umsetzung des Netzwerks.
    Letzteres war wohl einer der Grunde, warum einer der drei Entwickler des Viceroy-Netzwerks selbst ein anderes Peer-to-Peer-Netzwerk als Nachfolger von Viceroy vorschlug, das er Distance-Halving-Netzwerk nannte.
7.2 Distance-Halving
    Im Jahre 2003 stellten Moni Naor and Udi Wieder das Distance-Halving-Netzwerk vor [45]. Ziel der Autoren war nicht lediglich ein weiteres Peer-to-Peer-Netzwerk zu entwerfen, sondern es wurde besonderer Wert auf das im Folgenden vorgestellte Prinzip der kontinuierlichen Graphen gelegt. Dieses liegt eigentlich schon den Netzwerken CAN and Chord zu Grunde, von Naor and Wieder wurde das Prinzip jedoch erstmals formalisiert.
7.2.1 Kontinuierliche Graphen
    Genauso wie man diskrete Graphen als Kantenmenge uber einer endlichen Knotenmenge definiert, kann man auch kontinuierliche Graphen fiber einer unendlichen Menge von Knoten definieren. Als Beispiel eines kontinuierlichen Graphen betrachten wir direkt den im Distance-Halving-Netzwerk verwendeten. Die Knotenmenge V ist das kontinuierliche Intervall der reellen Zahlen [0, 1). Die Kantenmenge E C V x V bildet eine unendlich grofe Paarmenge zwischen diesen Knoten. Der Graph des Distance-Halving-Netzwerks besteht aus vier Grundtypen von Kanten (siehe Abbildung 7.3):

    Abb. 7.3. Links- and Rechtskanten des kontinuierlichen Graphen des Distance-Halving-Peerto-Peer-Netzwerks.
    Der Ubergang vom kontinuierlichen zum diskreten Graphen
    Kontinuierliche Graphen lassen sich wegen der unendlichen Knotenanzahl nicht direkt als Netzwerkstruktur verwenden. Fur den Ubergang zum diskreten Graphen mussen wir die unendliche Knotenmenge V in endlich viele Teilintervalle partitio- nieren, welche im diskreten Graph als Knoten dienen and von uns fortan als Segmente bezeichnet werden. In unserem Fall entsprechen die Knoten bzw. Segmente des diskreten Graphen gerade den Peers des Netzwerks. Die Peers warden im ein- fachsten Fall wie schon in den zuvor vorgestellten Netzwerken eine zufallige Position im [0, 1) Intervall wahlen and waren dann fur die Daten ab ihrer Position his zur Position des Nachfolgers im [0, 1) Intervall verantwortlich. Tatsachlich wird im Distance-Halving-Netzwerk eine modifizierte Methode zur Platzierung der Peers verwendet, wie wir in Abschnitt 7.2.2 sehen werden. Um den Ubergang vom kontinuierlichen zum diskreten Graphen zu beschreiben, gehen wir jedoch zunachst von der zufalligen Wahl der Positionen im [0, 1) Intervall aus and bezeichnen im Folgenden mit xt, X 2 ,.. , x,,, die von den it Peers gewahlten Positionen in aufsteigender Sortierung, d.h., xi < xj fur alle i < j. Dem Peer an Position xi, 1 < i < n, wird das Segment s(xi) = [xi, xi+t) zugeordnet.
    Nachdem wir nun die Knoten des diskreten Graphen definiert haben, definieren wir die Menge der Kanten nun wie folgt: Eine Kante zwischen zwei Segmenten s (x2) and s (xj) existiert genau dann, falls es Punkte u E s (xi) and v E s (xj) gibt, so dass (u, v) eine Kante des kontinuierlichen Graphen ist. Zusatzlich