Peer-to-Peer-Netzwerke: Algorithmen und Methoden

verwendet werden. Es verbleibt also zu zeigen, dass in den Fallen wo p' = p.db nicht zugleich der Vorganger der Position i o topBit(id) ist, jeweils nur konstant viele and insgesamt maximal 0(m) Schritte entlang des Rings gemacht werden.
    Um von einem virtuellen Knoten i zum Vorganger der Position i o topBit(id) zu gelangen (was gerade der Simulation eines Schrittes im statischern De-BruijnNetzwerk entspricht) routen wir zunachst von Peer p (dem Vorganger von i auf dem Ring) zum Knoten p' = p.db and dann entlang des Rings von p' bis zum Vorganger der Position i o topBit(id). Die Peers, die wir dabei benutzen, sind diejenigen mit IDs zwischen 2p and 2i. Die erwartete Anzahl u von Peers in diesem Bereich des Rings ist gerade

    and somit neben n auch von p and i abhangig. Um die Abhangigkeit von p and i zu entfernen betrachten wir den Wert i - p, also den Abstand auf dem Ring. Dieser ist durch die zufallige Platzierung der Peers gerade 2m/n. Dadurch ergibt sich

    Anders formuliert bedeutet das, dass im Erwartungswert nur jeweils 2 Schritte entlang des Rings gemacht werden, was eine erwartete Schrittanzahl von 3m fur das Routing ergibt. (Verwendet werden m De-Bruijn-Kanten and 2m Ring-Kanten.) Um eine Schranke mit hoher Wahrscheinlichkeit zu erhalten kann gezeigt werden, dass die Anzahl Schritte entlang des Rings jeweils mit hoher Wahrscheinlichkeit konstant ist, wodurch sich dann immer noch 0(m) Schritte ergeben. ❑
    Wir Sind nun in der Lage mit 0(m) Schritten in Koorde zu routen. Dies sind jedoch noch vergleichsweise viele Schritte, wenn wir bedenken, dass in den zuvor vorgestellten Netzwerken O(log n) Schritte genugten. Jedoch lasst sich auch in Koorde durch die Verwendung eines einfachen Tricks mit O(log n) Schritten routen.

    Die Idee ist die Folgende: Da der Startknoten p fur alle virtuellen De-BruijnKnoten bis zu seinem Nachfolger auf dem Ring verantwortlich ist, konnen wir den virtuellen Startknoten i des Routings frei aus diesem Bereich wahlen. Auf diese Weise konnen bereits einige Bits an die Ziel-ID des Routings angepasst werden. Genauer gesagt werden so viele der unteren Bits des Startknotens wie moglich (ohne den Zustandigkeitsbereich von p zu verlassen) auf den Wert der oberen Bits der Ziel-ID gesetzt and erst dann mit dem Routing begonnen. Wenn wir auf diese Weise k Bits anpassen konnen, benotigt das Routing nur noch O(m - k) Schritte.
    Wie viele Bits wir anpassen konnen, hangt von der GroBe des Zustandigkeitsbereichs des Start-Peers p ab. Dieser ist mit hoher Wahrscheinlichkeit groBer als 2f`/n° fur eine Konstante c. Das bedeutet wiederum, dass wir mit hoher Wahrscheinlichkeit

    Bits wie zuvor beschrieben wahlen konnen. Auf diese Weise mussen nur noch c log it Bits an die Ziel-ID angepasst werden, was lediglich O(log n) Schritte im Netzwerk benotigt. Wir halten dieses Ergebnis im folgenden Theorem test.
    Theorem 7.19. Routing in einem Koorde-Netzwerk mit n Peers kann mit hoher Wahrscheinlichkeit mit O(log n) Schritten geschehen.
    Damit liegt uns mit Koorde eine einfache Netzwerkstruktur vor, die mit konstantem Ausgrad auBerst effiziente Operationen zur Verfugung stellt. SchlieBlich folgt aus dem logarithmischen Aufwand zum Suchen einer Position (Routing), dass das EinfUgen oder Loschen eines Peers ebenfalls in logarithmischer Zeit vorgenommen werden kann.
    Somit ist Koorde ebenso einfach wie Chord, nur effizienter. Negativ ist, dass fur Koorde, im Gegensatz zu Chord, noch keine Stabilisierungsstrategie bekannt ist. Der kleine Grad bringt auBerdem nicht nur Vorteile. So ist der Zusammenhang des Netzwerks entsprechend geringer. Damit nimmt die Gefahr zu, dass das Netzwerk bei Ausfallen von Peers auseinanderfallt.
    Will man dieses Problem losen, dann kann man den Grad des Graphen erhohen, indem man so genannte Grad k-De-Bruijn-Graphen verwendet. Hierfur betrachten wir ein Alphabet aus k (statt zwei) Buchstaben, z.B. fur k = 3, m = 2. Jeder k-De- Bruijn-Knoten x hat nun die Nachfolger (kx mod km), (kx+l mod k'), (kx+2 mod km), . . . , (kx + k -1 mod km). Dadurch verkurzt sich der Durchmesser auf (log m)/ log k, wahrend sick der Grad auf 0(k) erhoht. Diese Konstruktion stellt eine naturliche Verallgemeinerung von Koorde dar, and die Ergebnisse lassen sich hier weitestgehend ubertragen. AuBerdem bewegt sich diese Losung fur alle k entlang des eingangs beschriebenen Trade-Offs zwischen Grad and Durchmesser.

7.4 Zusammenfassung
    Mit Koorde and dem Distance-Halving-Netzwerk haben wir zum Abschluss einer Reihe