Peer-to-Peer-Netzwerke: Algorithmen und Methoden

orthogonalen Zeiger der Netzwerkstruktur. Ausgehend von einem Peer im CAN wird die Suchanfrage an einen Nachbar-Peer weitergeleitet, dessen Rechteck bezUglich der x- oder y-Koordinate naher am gesuchten Punkt liegt. Dies wird wiederholt, bis der Peer gefunden worden ist, der das den Punkt umschlieBende Rechteck besitzt. Diese Suchfunktion wird auch beim Einfugen eines Peers verwendet.
    Die Suche nach einem Datum geschieht in zwei Schritten. Zuerst werden aus dem Schlussel des Datums mit Hilfe der Hash-Funktion die Koordinaten des zugehorigen Punkts berechnet. Dann wird mit dem eben beschriebenen Algorithmus die Anfrage an den Peer weitergeleitet, der den Punkt and damit das Datum verwaltet.
    Abb. 4.4. Ein CAN mit typischer Struktur.

    Wir wenden uns nochmals dem Grad des Netzwerk-Graphen zu. Ist jeder Peer nur fur ein Rechteck verantwortlich', so ist der durchschnittliche Grad konstant. Das ergibt sich aus folgendem Gedankenexperiment: Wir richten jede Kante zwischen zwei Peers so aus, class sie von dem Peer mit dem kleineren zu dem Peer mit dem groBerem Rechteck zeigt. Zwischen Peers mit gleich groBen Rechtecken wahlen wir eine zufallige Richtung. Nun gehen von jedem Rechteck hochstens vier Kanten aus, da these immer zum GroBeren oder Gleich-GroBen zeigen. Insgesamt kann es also hochstens 4n Kanten geben. Somit hat jeder Peer durchschnittlich hochstens acht Kanten, da eine Kante zwei Peers verbindet. Jeder Peer muss daher im Durchschnitt hochstens acht Verbindungen verwalten.
    Der maximale Grad eines Peers hangt sehr stark von der Anzahl kleiner Rechtecke ab. Der schlimmste Fall ist, wenn um ein groBes Rechteck lauter kleine Rechtecke liegen. Wir haben schon gesehen, dass die groBten Rechtecke hochstens um einen logarithmischen Faktor groBer sind als der Durchschnitt. Es ist jedoch nicht ausgeschlossen, dass ein uberdurchschnittlich groBes Rechteck von unterdurchschnittlich kleinen Rechtecken umgeben ist. Eine genaue mathematische Analyse dieses Grades wurde bislang noch nicht durchgefuhrt.
    Im CAN wird durch die unterschiedlich groBen Rechtecke also nicht vermieden, dass einige Peers viel weniger (oder mehr) Daten speichern als der Durchschnitt. Auch wenn der durchschnittliche Grad des Netzwerks konstant ist, werden einige Peers durch die unterschiedlich groBen Rechtecke einen nicht konstanten Grad auf- weisen. Dies kann nicht nur bei Peers mit groBen Rechtecken auftreten. Hiervon konnen ebenfalls Peers mit durchschnittlich groBen Rechtecken betroffen sein, wenn sie von unterdurchschnittlich kleinen Rechtecken umgeben sind. Es handelt sich hierbei allerdings um Ausnahmen, and die meisten Peers besitzen einen konstanten Grad and verwalten einen (his auf einen konstanten Faktor) fairen Anteil des Datenvolumens.
4.4 Defragmentierung nach dem Entfernen von Peers
    Die CAN-Netzwerkstruktur erlaubt es Peers, fur mehr als ein Rechteck verantwortlich zu sein. Das wird notwendig, wenn ein Peer das Netzwerk verlasst. In einem Peer-to-Peer-Netzwerk kann nicht davon ausgegangen werden, dass ein Peer, der das Netzwerk verlasst, seine Nachbarn rechtzeitig daruber informiert. Daher uberpruft jeder Peer regelmaBig, ob seine Nachbarn noch erreichbar sind. Meldet sich ein Nachbar nicht zuruck, so ubernimmt der erste Peer, der dies bemerkt, das Gebiet des abwesenden Peers nach Ablauf eines Wartezeitraums (siehe Abbildung 4.5).
    So wird das fortlaufende Einfugen and Loschen von Peers zu einer immer starkeren Fragmentierung des Netzwerks in kleine Rechtecke fuhren. Auf Dauer ist es nicht hinnehmbar, dass ein Peer ein Konglornerat aus benachbarten Flachen verwaltet. Daher wird von Zeit zu Zeit eine Defragmentierung im CAN vorgenommen.

    Abb. 4.5. Entfernen von Peers im CAN. Verlasst ein Peer das Netzwerk (a), ubernimmt ein Nachbar sein Gebiet (b).

    Um den Defragmentierungsprozess zu verstehen, ist es hilfreich, das CAN als Binarbaum zu betrachten. Jedes CAN besitzt eine aquivalente Darstellung als Binarbaum. Abbildung 4.6 zeigt zum Beispiel die Binarbaumdarstellung des CANs aus Abbildung 4.5(b). Die Wurzel des Baumes reprasentiert das gesamte Quadrat [0, 1) x [0, 1) des Netzwerks. Die beiden Kind-Knoten der Wurzel reprasentieren jeweils die rechte Halfte [0, 0.5) x [0, 1) bzw. linke Halfte [0.5, 1) x [0, 1) dieses Quadrats. Deren Kinder reprasentieren dann jeweils die obere and untere Halfte ihrer Vater-Knoten. Diese Aufteilung wird fortgesetzt, bis ein Knoten genau den Zustandigkeitsbereich eines Peers beschreibt. So entspricht jedes