Peer-to-Peer-Netzwerke: Algorithmen und Methoden

vorgestellt. Die Idee ist, einen Multicast-Verteilungsbaum auf einem Overlay-Netzwerk, hier Pastry [11], zu implementieren. Zwar entsteht im Internet immer noch der Mehrfachaufwand durch wiederholtes Senden der Nachrichten durch die Router, es hat sich aber herausgestellt, dass fur den einfachen In- ternetbenutzer der letzte Link in das Netzwerk hinein der Flaschenhals ist. Der Grund ist, dass die weitverbreiteten DSL-, ISDN- oder analogen Modemverbindungen der Endkunden mit den Glasfaserverbindungen der Internet-Service-Provider nicht mit- halten, selbst wenn eine Vielzahl der Benutzer these Dienste verwendet.
    Ahnliche Ansatze fur andere Peer-to-Peer-Netzwerke wurden mit CAN-Multicast [102], basierend auf CAN [8], and Bayeux [103], basierend auf Tapestry [12], vorgestellt. Wir greifen hier Scribe beispielhaft auf, ohne die anderen Ansatze abwerten zu wollen.
    Daneben gibt es mit Overcast [104] and Narada [105] altere Ansatze zur Verwendung von Unicast-Verbindungen zum Aufbau eines Multicast-Baumes. In diesen Netzwerken ist es aber notwendig, alle Abstandsinformationen zwischen den Endknoten zu sammeln and auszuwerten. Wie wir bereits wissen, ist die optimale Losung dieses Problems AfP-vollstandig. Aber allein das Sammeln der Information ubersteigt die Moglichkeiten eines Peer-to-Peer-Netzwerks. SchlieBlich konnen in Peer-to-Peer-Netzwerke mehrere Millionen Peers anwesend sein. Damit gilt es fur jeden Peer, den Abstand zu Millionen anderen Peers zu sammeln. Auch Scribe findet keinen optimalen Multicast-Baum. Aber Scribe (wie CAN-Multicast and Bayeux) vermeidet es, solche Mengen an Informationen zu sammeln and auszuwerten.
Create
    Scribe vergibt fur jede Empfangergruppe eine so genannte Gruppen-ID (Group-ID). Diese wird per Hash-Funktion auf einen Peer abgebildet. Ansonsten ist die Funktionsweise von Scribe der von IP-Multicast sehr ahnlich.
Join
    Jeder Peer, der sich einer Gruppe anschlieBen mochte, sendet einen Lookup zu dem Root-Peer, der die Group-ID verwaltet. Sobald auf dieser Route ein Peer gefunden wird, der zum Multicast-Baum dieser Gruppe gehort, wird der Pfad zu diesem Peer zum Multicast-Baum dieser Gruppe hinzugefugt. Die Information wird dann mittels dieses Baumes verteilt, siehe auch Abbildung 12.3.

Download
    Die Nachrichten werden jetzt durch diesen Baum verteilt. Hierzu duplizieren die Knoten die Informationen.
    Scribe benutzt eine Besonderheit des Pastry-Protokolls: Die Zeiger in den nied- rigen Leveln fuhren zu naheren Knoten im Netzwerk, als Zeiger in hohen Leveln. Je groBer der Baum wird and je mehr Knoten im Multicast-Baum sind, desto kurzere Kanten werden eingefugt.
    Abb. 12.3. Funktionsprinzip von Scribe.
Reparatur and Kontrolle
    Da der Multicast-Baum wie der Rest des Peer-to-Peer-Netzwerks den dauernden Veranderungen durch hinzukommende oder verschwindende Peers ausgesetzt ist, bedarf es einer standigen Kontrolle, ob der Multicast-Baum noch intakt ist.
    Hierzu werden so genannte Herzschlage ausgesandt, das Sind Kontrollnachrichten, die der Knoten, der die Group-ID verwaltet, an alle weiteren Knoten des Baums verschickt and weiterleitet. Wurde also ein Teil des Baums abgetrennt, so kann dies durch das Ausbleiben dieser regelmaBigen Kontrollnachrichten festgestellt werden. Der Multicast-Baum wird dann dadurch repariert, dass der Aufbaualgorithmus erneut ausgefUhrt wird.

Bottleneck-Remover
    Wenn ein Knoten uberlastet ist, dann wird die Gruppe mit der groBten Last ausgewahlt. In dieser Gruppe wird das in der Netzwerkmetrik am weitesten entfernte Kind gewahlt, welches dann den Delay zwischen sich and den anderen Kindern misst. Daruthin wird das Kind unter den nachsten der hierbei gefundenen Knoten gehangt, siehe Abbildung 12.4.
    Abb. 12.4. Entfernen von Engpassen in Scribe.
    Durch these Mechanismen erhalt man mit Scribe eine uberraschend gute Bandbreite, die mit IP-Multicast vergleichbar ist.
12.3 Splitstream
    Splitstream ist eine Verbesserung von Scribe von Castro, Druschel, Kermarrec, Nandi, Rowstron and Singh [106]. Die Struktur eines Multicast-Baumes bevorzugt die Blatter and benachteiligt die inneren Knoten. Diese mussen namlich die empfangenen Daten mindestens zweimal wieder versenden. Die Blatter dagegen erhalten die Daten and haben keinerlei weiteren Aufwand.
    Das Verhaltnis der benachteiligten Peers in einem Binarbaum ergibt sich aus dem folgenden Lemma:
    Lemma 12.1. In jedem Binarbaum ist die Anzahl der Bldtter b um eins groj3er als die Anzahl k der internen Knoten, d.h. b = k +