Peer-to-Peer-Netzwerke: Algorithmen und Methoden

uber dem Ring {0,.. . , 2' -1}. Fur die Operationen gilt:

    Tatsachlich werden in einem Koorde-Netzwerkjedoch niemals alle Peer-IDs vergeben sein, da der Parameter m gross genug gewahlt wird um Kollisionen bei der Zuweisung von Peer-IDs unwahrscheinlich zu machen (typischerweise wird m = 128 oder in = 160 gewahlt). Des Weiteren wird die Anzahl der Peers auch nur selten eine zweier Potenz sein (und nur fur these ist das De-Bruijn-Netzwerk definiert).
    Abb. 7.17. Transformation des De-Bruijn-Graphen in ein Koorde-Peer-to-Peer-Netzwerk.
    In Koorde wird dieses Problem folgendermaBen gelost. In einem Netzwerk mit n Peers sind naturlich auch n (zufallige) Positionen des Rings durch Peers besetzt. Die nicht besetzten 2' - n Positionen bezeichnen wir fortan auch als virtuelle DeBruijn-Knoten. So werden die De-Bruijn-Kanten der Peers mit hoher Wahrscheinlichkeit auf virtuelle De-Bruijn-Knoten zeigen. Ist dies der Fall, wird fur these Kante der dem virtuellen De-Bruijn-Knoten auf dem Ring vorangehende Peer p' gewahlt (dieser wird auch als fur den virtuellen Knoten verantwortlicher Peer bezeichnet). Da die De-Bruijn-Kanten auf benachbarte Positionen auf dem Ring zeigen, wird ein Peer p zudem nur die 2p mod 2" entsprechende Verbindung unterhalten. Dies ist sinnvoll, da die Shuffle- and die Shuffle-Exchange-Kante mit hoher Wahrscheinlichkeit ohnehin auf denselben Peer zeigen. So besitzt ein Peer also drei Nachbarn im Netzwerk: zwei Ring-Nachbarn and einen Nachbarn fur die De-Bruijn-Kante (siehe auch Abbildung 7.17). Der Eingrad eines Peers kann hingegen hoher sein. Um auch einen konstanten Eingrad zu erreichen, konnte z.B. das Prinzip der vielfachen Auswahl bei der Wahl der Peer-IDs bzw. dem Einfugen verwendet werden.

    Um im Folgenden das Routing im Koorde-Netzwerk zu beschreiben, bezeichnen wir fortan fur einen Peer p seinen Nachfolger auf dem Ring mit p.Nachfolger and seinen entsprechend der De-Bruijn-Kante gewahlten Nachbarn mit p.db. Des Weiteren fuhren wir folgende Notation ein: Fur ein Bin irwort x ist x o 0 := 2x mod 2' und x o 1 := (2x + 1) mod 2"n. Die entstehenden Werte entsprechen also den Shuffle bzw. Shuffle-Exchange-Kanten. Zudem liefere topBit(S) das am weitesten links stehende Bit eines m-stelligen Binarwortes S.
    Beim Routing bzw. der Suche nach einem Datum mit der ID id im KoordeNetzwerk muss zu dem Peer mit nachsthoherer ID als id geroutet werden. Da die meisten Knoten in Koorde virtuelle De-Bruijn-Knoten sind, simuliert Koorde den Weg in einem vollstandigen De-Bruijn-Netzwerk,2 indem fur jeden virtuellen Knoten i jeweils durch den Peer geroutet wird, der fur diesen verantwortlich ist (also dem letzten Peer vor der Position i des Rings).
    Der Pseudo-Code des Routing-Algorithmus wird in Abbildung 7.18 dargestellt. Der momentane virtuelle Knoten wird im Algorithmus als Parameter i ubergeben. In einem Routing-Schritt simuliert Koorde den Sprung vom virtuellen Knoten i zum Knoten i o topBit(id) and uberfuhrt i so schrittweise in id. Dies geschieht durch einen Sprung von p, dem aktuellen Peer, nach p.db. Durch diesen Sprung wird ein Peer p' mit ID nahe 2p erreicht. Ist p' Vorganger der Position i o topBit(id), kann direkt die nachste De-Bruijn-Kante verwendet werden.
    Wenn in jedem Routing-Schritt De-Bruijn-Kanten verwendet werden konnen, d.h. p' ist jeweils Vorganger der Position i o topBit(id), so werden insgesamt m Schritte benotigt, da mit jedem Schritt ein Bit an die Ziel-ID angepasst wird.
    Dies anzunehmen ware jedoch sehr optimistisch. Auch wenn p' = p.db per Definition der der Position 2p vorangehende Peer des Rings ist, muss dies nicht zugleich der Vorganger der Position i o topBit(id) sein. Der Grund hierfur ist die zufallige Wahl der Peer-IDs. Deshalb uberpruft jeder Peer, ob er tatsachlich der Vorganger der Position i o topBit(id) ist and routet, falls dies der Fall ist, entlang der De-BruijnKante, and andernfalls an seinen Nachfolger auf dem Ring.
    Das folgende Lemma trifft eine Aussage uber die erforderlichen Schritte beim Routing in Koorde.

    Abb. 7.18. Routing-Algorithmus fur Koorde. Variablen wie De-Bruijn-Kanten and Nachfolgern ist jeweils der betreffende Peer vorangestellt. So bezeichnet z.B. p.db den De-Bruijn- Nachbarn des Peers p.
    Lemma 7.18. Sei 2'"z die Ring-Grof3e eines Koorde-Netzwerks. Dann benotigt das Routing mittels des Algorithmus aus Abbildung 7.18 mit hoher Wahrscheinlichkeit 0(m) Schritte.
    Beweis. Wir haben bereits gesehen, dass m Schritte genUgen, falls nur De-BruijnKanten