Peer-to-Peer-Netzwerke: Algorithmen und Methoden

existieren noch Kanten zwischen benachbarten Segmenten, also eine Ringstruktur. Auf these Weise kann man jeden Pfad im kontinuierlichen Graphen auf einen gleich langen Pfad im diskreten Graph abbilden.

    Durch die gerade beschriebene Diskretisierung des oben beschriebenen kontinuierlichen Graphen entsteht das so genannte Distance-Halving-Netzwerk. Abbildung 7.4 veranschaulicht den Vorgang der Diskretisierung an einem kleinen BeispielNetzwerk mit Sieben Peers. Es sei an dieser Stelle erwahnt, dass man das CAN- Netzwerk auf die gleiche Art and Weise als die Diskretisierung des zweidimensionalen Quadrats [0, 1)2 betrachten kann.
    Abb. 7.4. Durch die Diskretisierung eines kontinuierlichen Graphen entsteht das DistanceHalving-Netzwerk.
    Aus der Distanzeigenschaft folgt sofort, dass der Grad des Distance-HalvingNetzwerks konstant ist, falls das Verhaltnis aus groBtem and kleinstem Intervall konstant ist. Die Kamen eines Segments zeigen auf ein Intervall I, das fur jeden Kantentyp hochstens doppelt so groB wie das Segment selbst ist. Sei

    das Verhaltnis aus der maximalen SegmentgroBe and der minimalen SegmentgroBe. Dann kann sich das Intervall I nur mit 2p + 1 vielen Segmenten uberschneiden.
    Ein konstantes Verhaltnis p = 4 kann beim Einfugen durch das im Folgenden vorgestellte Prinzip der vielfachen Auswahl (principle of multiple choice) erreicht werden. Damit ergibt sich durch die Diskretisierung eine Graderhohung um den Faktor neun and somit ein konstanter Grad fur das Distance-Halving-Netzwerk.
7.2.2 Einfugen von Peers and das Prinzip der vielfachen Auswahl
    Statt beim Einfugen eine zufallige Position im [0, 1) Ring zu wahlen, betrachtet jeder Peer zunachst k = clog it zufallige Positionen Y1, Y2, ... , yk E [0, 1), wobei c eine geeignet gewahlte Konstante ist. Fur jede dieser Positionen yj wird die GroBe a(yz) des den Punkt yz umgebenden Segmentes s(x*) gemessen, also der Abstand zwischen den potenziellen linken and rechten Nachbarn im [0, 1) Intervall. Nun wird das groBte der gefunden Segmente ausgewahlt and der neue Peer in der Mitte dieses Segmentes platziert.

    Auf these Weise wird immer ein relativ groBes Segment gewahlt, was letztendlich zur Folge hat, dass die Abstande zwischen den Peers relativ gleichmaBig sind (siehe auch Abbildung 7.5). Das folgende Lemma trifft eine genauere Aussage uber die zu erwartenden minimalen and maximalen SegmentgroBen.
    Abb. 7.5. Das Prinzip der vielfachen Auswahl beim Einfugen eines Peers.

    Lemma 7.10. Habe das groBte Segment die Grof3e g/n (g kann von n abhangig sein). Dann sind nach dem Einfugen von 2n/g Peers alle Segmente kleiner als g/(2n).
    Beweis. Wir betrachten ein Segment der GroBe g/n. Werden beim Einfugen jedes Peers clog n mogliche Positionen betrachtet and 2n/g Peers eingefugt, so ist die erwartete Anzahl von Treffern X in ein solches Intervall gerade

    Ist nun b2c > 2, werden all diese Intervalle mindestens 2(1 - b)clog n-mal getroffen. Hier muss jedoch berucksichtigt werden, dass jedes Mal, wenn ein Intervall von einem Peer geteilt wird, die (c log n) - 1 weiteren Treffer dieses Peers (in moglicherweise andere groBe Intervalle) keine Teilung mehr bewirken konnen.
    Fur 2(1 - b) > 1 gilt, dass jedes der Intervalle der Mindestlange gin mit hoher Wahrscheinlichkeit geteilt wird. ❑ (Lemma 7.10)

    Es bleibt zu zeigen, dass keine Segmente kleiner als 1/(2n) entstehen. Die Gesamtlange aller Segmente der GroBe 1/(2n) ist vor jedem EinfUgen hochstens n/2. Damit ist die Wahrscheinlichkeit, dass bei clog n Versuchen nur solche Segmente gewahlt werden, hochstens 2-ologn = n o. Somit wird fur c > 1 ein Segment der GroBe 1/(2n) nur mit polynomiell kleiner Wahrscheinlichkeit weiter unterteilt. Damit ist der Beweis von Lemma 7.9 abgeschlossen. ❑

    Beim EinfUgen werden die clog n zu uberprufenden Segmente jeweils durch eine Suche lokalisiert. HierfUr werden, wie wir gleich sehen werden, jeweils O(log n) Schritte benotigt. Nachdem das groBte Segment ausgewahlt wurde, wird der ein- zufugende Peer zunachst in die Ringstruktur eingebunden and baut dann seine weiteren Verbindungen zu anderen Peers mit Hilfe der auf dem Ring benachbarten Peers auf. Entsprechend aktualisieren auch these ihre Nachbarschaft im Netzwerk.
7.2.3 Routing im Distance-Halving-Netzwerk
    Wir werden in diesem Abschnitt einen Routing-Algorithmus fur das DistanceHalving-Netzwerk vorstellen, der obgleich des konstanten Grades lediglich 0(log n) Schritte benotigt and zugleich die beim Routing entstehende Last