Peer-to-Peer-Netzwerke: Algorithmen und Methoden

Blatt der Baumdarstellung genau einem Peer.
    Abb. 4.6. Baumdarstellung des CANs aus Abbildung 4.5(b).
    Wir beschreiben nun den Defragmentierungsprozess. Dieser kann von jedem Peer angestoBen werden, der fur mehr als ein Rechteck verantwortlich ist. Dabei versucht ein Peer das kleinste von ihm verwaltete Rechteck an einen anderen Peer zu ubergeben. Sei A dieses kleinste Rechteck. In der Biniirbaumdarstellung entspricht A einem Blatt. Der Peer betrachtet gemaB der oben beschriebenen Binarbaumdarstellung den Bruderbaum von Blatt A. Besteht dieser ebenfalls nur aus einem Blatt B, also aus einer ungeteilten Zone, so kann der Peer das Rechteck A an den Peer ubergeben, der B verwaltet. Dieser Peer wird dann die Rechtecke A and B vereini- gen, so dass ein einziges Rechteck mit doppelter Flache entsteht and die Fragmentierung des Netzwerks verringert wird.

    Dieser Vorgang ist beispielhaft in Abbildung 4.7 dargestellt. Peer p4 verwaltet zwei Zonen and startet die Defragmentierung. Der Nachbarbaum des kleinsten von p4 verwalteten Rechtecks besteht nur aus einem Blatt, fur das Peer P16 verantwortlich ist. Peer P16 Ubernimmt das kleinste Rechteck von p4 and vereinigt die beiden nun von ihm verwalteten Rechtecke zu einem einzigen mit doppelter Flache. Der Baum besitzt nun ein Blatt weniger, and das Netzwerk ist weniger fragmentiert.
    Abb. 4.7. Der einfache Fall der Defragmentierung.
    Die Defragmentierung gestaltet sichjedoch nicht immer so einfach. Sei wieder A das kleinste Rechteck eines Peers, der fur mehrere Rechtecke verantwortlich ist. Besteht der Nachbarbaum B des Blattes, das A reprasentiert, jetzt nicht nur aus einem Blatt, kann das gerade beschriebene Verfahren nicht angewendet werden. Stattdessen wird der Peer, der die Defragmentierung durchfuhrt, im Nachbarbaum B nach zwei benachbarten Blattern suchen.2 Diese werden dann zu einem Rechteck doppelter Flache vereinigt. Der dabei frei gewordene Peer ubernimmt nun die Verantwortlich- keit fur das Rechteck A.
    Abbildung 4.8 veranschaulicht den schwierigeren Fall der Defragmentierung. Peer p6 verwaltet zwei Rechtecke and versucht das kleinere abzugeben. HierfUr wird eine Tiefensuche im Nachbarbaum durchgefuhrt, bei der zwei benachbarte Blatter gefunden werden, die von p11 and p13 verwaltet werden. Diese beiden Blatter werden vereinigt and von p13 ubernommen. Der nun frei gewordene Peer p11 iibernimmt das kleinere Rechteck von P6. Wieder wurde die Anzahl der Blatter des Baumes and somit die Fragmentierung des Netzwerks verringert.
4.5 Weitere Konzepte in CAN
    Es existieren mehrere Konzepte, um die Effizienz von CAN zu steigern. Diese werden wir nun kurz vorstellen.

    Abb. 4.8. Der schwierige Fall der Defragmentierung.
Dimensionen
    Bis jetzt haben wir den Fall eines zweidimensionalen Quadrats vorgestellt. Wenn man zu einem dreidimensionalen Warfel ribergeht, erhoht sich der durchschnittliche Grad auf sechs, and der Durchmesser verringert sich auf 0(nt/3). Natiirlich kann man das auf d Dimensionen verallgemeinern, wodurch man einen Durchmesser von o(nt/d) and einen Grad von 0(d) erhalt (vorausgesetzt, der Zufallsprozess zum Einfugen erzeugt ungefahr gleich groBe Hyper-Rechtecke). Abbildung 4.9 zeigt, wie sich der Durchmesser eines CANs verrndert, wenn die Anzahl der Dimensionen erhoht wird.
Realitaten
    Ein weiteres Konzept ist die Verwendung von mehreren Netzwerken zugleich, die einzelnen Netzwerke werden dann als Realitaten bezeichnet (siehe Abbildung 4.10). Jeder Peer and jedes Datum nimmt gleichzeitig in alien r Realitaten (CAN-Netz- werken) teil. In jedem der r CANs wird eine andere Hash-Funktion gewahlt, so class die Peers and Daten in alien r Realitaten verschieden an- and zugeordnet werden.
    Dadurch erhoht sich der Grad um den Faktor r, wahrend die verschiedenen Realitaten sowohl die Zuverlassigkeit erhohen als auch den Durchmesser des Netzwerks verringern. Die erhohte Zuverlassigkeit ergibt sich allein aus der Tatsache, dass man r - 1 Ersatznetzwerke hat. Der Durchmesser verringert sich erheblich. Man kann zeigen, dass dieser mit hotter Wahrscheinlichkeit nur noch 0 (log n) ist. Das Routing profitiert davon aber nur bis zu einem gewissen MaB, denn den einzelnen Peers ist der kurzeste Weg zu einem Rechteck nicht bekannt.
    Eine gewisse Verkurzung des Weges ist dennoch moglich. Hierzu wahlt das Routing den jeweils nachsten Peer aus der Realitat, in der der Abstand zum Ziel gemaB der jeweiligen Koordinaten am kleinsten ist. Dadurch wird am Anfang haufig zwischen den