Peer-to-Peer-Netzwerke: Algorithmen und Methoden

von id and die Funktion pfxl(p, id) liefert die Lange des gemeinsamen Prafix von p and id.

6.2.3 Einfugen von Peers
    Das Einfugen eines neuen Peers in Pastry unterscheidet sich vom Einfugen neuer Peers in CAN and Chord, da bei Pastry unter anderem in der Routing-Tabelle jeweils latenznahe Peers aus vielen moglichen Kandidaten ausgesucht werden sollen.
    Will ein neuer Peer p in das Pastry-Netzwerk aufgenommen werden, so muss er natUrlich zunachst einen Peer pa,, der bereits Teil des Netzwerks ist, kontaktieren. Bei Pastry wird jedoch abweichend von den bisher vorgestellten Peer-to-PeerNetzwerken angenommen, dass der Peer pa im Underlay-Netzwerk einen geringen Abstand zu p hat, d.h. latenznah ist. Ausgehend von pa, wird dann mit einer speziellen join-Nachricht nach dem Peer pz mit dem langsten gemeinsamen Prafix zu p gesucht, indem pa im Netzwerk nach der ID von p sucht.
    Die Peers pa and pz sowie alle weiteren Knoten auf dem Weg der join-Nachricht von pa nach pz senden als Antwort auf diese jeweils ihre drei Nachbarschaftsklassen an den Peer p. Peer p initialisiert seine Routing-Tabelle, das Leaf-Set and die Nachbarschaftsmenge M anhand dieser Nachrichten auf die im nachsten Absatz beschriebene Art and Weise. Zugleich informiert p diejenigen der ihm nun bekannten Peers, die p in ihre Routing-Tabelle, ihr Leaf-Set oder ihre Menge M latenznaher Peers aufnehmen mussen.
    Wir widmen uns nun der Frage, wie Peer p aus den erhaltenen Nachbarschaftsinformationen seine eigene Nachbarschaft unter Berucksichtigung der Netzwerklokalitat aufbauen kann. Da Peer pa, latenznah zu p ist, kann p die Menge Al latenznaher Peers von pa, Ubernehmen. Des Weiteren hat Peer pz das langste gemeinsame Prafix zu p, so class p sein Leaf-Set leicht aus demjenigen von pz aufbauen kann.
    Es bleibt zu zeigen, wie Peer p seine Routing-Tabelle aufbauen kann. Wir gehen dabei vom allgemeinen Fall aus, dass die IDs von p and pa keinen gemeinsamen Prafix besitzen. Die Level 0-Eintrage der Routing-Tabelle sind jedoch unabhangig von der ID. Somit kann Peer p diese Eintrage vom Peer pa ubernehmen. Die anderen Level der Routing-Tabelle von pa sind fur p uninteressant, da die IDs von p and pa keinen gemeinsamen Prafix besitzen. Die Level 1-Eintrage der Routing-Tabelle konnen jedoch von dem zweiten Peer auf dem Weg der join-Nachricht von pa nach pz ubernommen werden. Dies ist moglich, da in jedem Schritt die Lange des gemeinsamen Prafix um mindestens eine Ziffer anwachst. Auf die gleiche Art and Weise wird fur die weiteren Level der Routing-Tabelle bzw. Peers auf dem Weg von pa nach pz verfahren. Der beschriebene Vorgang wird in Abbildung 6.6) veranschaulicht. Dass hierbei auch tatsachlich latenznahe Nachbarn ausgewahlt werden, werden wir spater zeigen.

Reparaturmechanismus
    Die Einfugeoperation von Pastry ist sehr einfach, wenn man bedenkt, dass beim Aufbau der Nachbarschaft Netzwerklokalitat beriicksichtigt wird. Allerdings stellt sie nicht sicher, dass dabei stets korrekte Routing-Tabellen entstehen. Es kann durchaus vorkommen, dass notwendige Nachbarschaftseintrage nicht aktualisiert werden. Ein einfaches Beispiel hierfiir ist der folgende Fall: Ist der neu eingefugte Peer p zum Beispiel der erste Peer im Netzwerk, dessen ID mit der Ziffer 1 E B beginnt, so reicht es nicht aus, alle Peers aus den teilweise ubernommenen Nachbarschaftslisten der Peers po, bis pz zu informieren. Tatsachlich mussten namlich alle Peers des Netzwerks Peer p in ihre Routing-Tabelle aufnehmen.

    Nun ist aber das korrekte Routing bzw. die Suche im Netzwerk selbst dann sichergestellt, wenn Eintrage in der Routing-Tabelle fehlen, solange die Leaf-Sets der Peers korrekt sind. Der fur ein Datum zustandige Peer kann also in jedem Fall gefun den werden. Jedoch werden dann unter Umstanden erheblich mehr Schritte fur die Suche im Netzwerk benotigt.

    Abb. 6.6. Einfugen eines Peers in das Pastry Netzwerk.

    Um dem Problem der fehlenden Routing-Tabelleneintrage entgegenzuwirken, gibt es einen Reparaturmechanismus in Pastry. Angenommen, der Eintrag fur Level j and Ziffer i E B fehlt einem Peer p in seiner Routing-Tabelle. Peer p bemerkt diesen fehlenden Eintrag zum Beispiel dadurch, dass eine Nachricht an oder von einem Peer mit diesem Prafix durch p befordert wird. Es kann aber auch vorkommen, class ein Peer das Netzwerk verlasst and dadurch alte Eintrage in der Routing-Tabelle falsch oder uberflussig werden.
    Bemerkt ein Peer p, dass er einen fehlenden Eintrag in seiner Routing-Tabelle hat,