Peer-to-Peer-Netzwerke: Algorithmen und Methoden

der neue Peer den fur diesen Punkt z zustandigen Peer. Das ist der Besitzer des z umgebenden Rechtecks. Diese Kontaktaufnahme geschieht durch die Suchfunktion, die wir spater erlautern. Nun wird dieses Rechteck halbiert. Wenn es sich um ein Quadrat handelt, dann zuerst vertikal entlang der y-Achse and bei einem Rechteck entlang der x-Achse. In Abbildung 4.3 wird dargestellt, wie dieser Prozess das Quadrat immer weiter in kleinere Rechtecke unterteilt.

    Nach der Unterteilung wird auch die Netzwerkstruktur entsprechend der neuen Nachbarschaft angepasst. Wir wenden uns zunachst der Frage zu, wie gleichmaBig die Daten durch diese EinfUgeoperation auf die Peers verteilt werden.
    Der Anteil der Daten eines Peers ist erwartungsgemaB proportional zur Flache des von ihm verwalteten Rechtecks. Zwar ist jeder Eintrittspunkt gleichwahrscheinlich, so dass groBe Rechtecke beim EinfUgen weiterer Peers mit hoherer Wahrscheinlichkeit geteilt werden als kleine, eine vollkommen gleichmaBige Aufteilung ist jedoch sehr unwahrscheinlich.
    Wir betrachten einen Peer p mit Rechteck R(p) in CAN. Sei A(p) die Flache dieses Rechtecks. Das folgende Lemma liefert eine obere Schranke fur die Wahrscheinlichkeit, class das Rechteck R(p) nicht weiter unterteilt wird, wenn n weitere Peers eingefiigt werden.
    Lemma 4.1. Sei PR,n, die Wahrscheinlichkeit, dass ein Rechteck R mit Flache A(R) nach dem Einfugen von n Peers ungeteilt bleibt. Dann gilt

    Beweis. Wir betrachten ein Rechteck R mit der Flache q = A(R). Die Wahrscheinlichkeit, dass ein bestimmter Peer diese Flache im Zuge des Einfugens nicht weiter unterteilt, also zufallig keinen Punkt innerhalb von R wahlt, ist 1 - q. Das geschieht unabhangig vom Verhalten anderer Peers. Somit ist die Wahrscheinlichkeit, dass n Peers keinen Punkt aus R wahlen, das Produkt aller n Einzelwahrscheinlichkeiten 1 - q and damit (1 - q)n. Nun gilt fur alle m >

    Daraus folgt

    and somit das Lemma. ❑
    So ist es zum Beispiel extrem unwahrscheinlich, dass eine Flache der GroBe z nach dem Eintreffen von n weiteren Peers ungeteilt bleibt. Die Wahrscheinlichkeit ist nach Lemma 4.1 hochstens e-n/2 (tatsachlich sogar hochstens 2-n).
    Mit Hilfe von Lemma 4.1 konnen wir nun eine Aussage daruber treffen, wie groB die Rechtecke in einem CAN hochstens sein werden.

    Beweis. Bezeichne Rz ein Rechteck mit Flache A(Rj) = 2-'. Mit Hilfe von Lemma 4.1 konnen wir die Wahrscheinlichkeit PRi,c2i Inn, dass ein Rechteck der GrMe Ri von c2' In n Peers nicht geteilt wird, abschatzen:

    Abb. 4.3. EinfUgen von Peers in das CAN.

    Wie schon erwahnt, ist die erwartete Anzahl von Daten, die ein Peer verwalten muss, proportional zur Flache seines Rechtecks. Im Durchschnitt hat diese Flache die GroBe 1/n. Theorem 4.2 zeigt, dass die Flache eines Peers mit hoher Wahrscheinlichkeit kleiner als (2cln n) /n ist. Anders formuliert bedeutet dies, dass ein Peer mit hoher Wahrscheinlichkeit hochstens 2c(ln n) mal mehr Daten als der Durchschnitt verwalten muss.
4.3 Netzwerkstruktur and Routing
    Die Netzwerkstruktur von CAN ergibt sich aus der Lage der Rechtecke der Peers. Ein Peer unterhalt Verbindungen zu allen Peers, die fur ein orthogonal benachbar- tes Rechteck verantwortlich sind. Beim Einfugen kann jeder Peer diese Information von dem Peer erfragen, dessen Rechteck hierbei geteilt wird. Naturlich mussen die Nachbar-Peers diese Information dann auch anpassen. Sind alle Rechtecke gleich groB and jeder Peer nur fur ein Rechteck verantwortlich, dann ist der Grad des Netzwerk-Graphen konstant groB (siehe Abbildung 4.1). Tatsachlich ist es jedoch unwahrscheinlich, dass alle Rechtecke gleich groB sind. Ein Grund hierfur ist der eben beschriebene EinfUgeprozess. So ist eher eine Netzwerkstruktur wie in Abbildung 4.4 zu erwarten.

    Zusatzlich werden so genannte Torus-Kanten zwischen den Peers der Rechtecke am rechten Rand mit den Peers der Rechtecke am linken Rand gleicher Hohe unterhalten. Analog werden die Zeiger zwischen Peers in Rechtecken des unteren and oberen Randes, die genau ubereinander liegen, angelegt. In Abbildung 4.1, 4.4 and 4.5 wurde aus GrUnden der Ubersichtlichkeit auf die Darstellung der TorusKanten verzichtet. Die Torus-Kanten verringern die durchschnittliche Entfernung im Netzwerk-Graphen um den Faktor Zwei. Bei einer vollig gleichmaBigen Unterteilung des Quadrats Q ergibt sich ein Netzwerk-Durchmesser von O( n) fur rn Peers.
    Das Routing bzw. die Suche nach einem Peer, der fur einen Punkt in Q verantwortlich ist, verwendet nun die