Exercise 4 - Join of a Chord Node

Benutzeravatar
BadTaste
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 181
Registriert: 18. Apr 2005 16:40
Wohnort: Darmstadt
Kontaktdaten:

Exercise 4 - Join of a Chord Node

Beitrag von BadTaste »

Hi all,

Just wanted to give you a clarification concerning the messages sent during a node join in Chord.
As discussed during the lecture, the current successor sends a message to the joining node.
Since this fact is not reflected in the image on the slides, i created a versions that does.

http://www.p2p.tu-darmstadt.de/fileadmi ... d-join.pdf


greets
benni

Benutzeravatar
Maeher
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 282
Registriert: 14. Okt 2007 23:02
Kontaktdaten:

Re: Exercise 4 - Join of a Chord Node

Beitrag von Maeher »

Ist das wirklich korrekt?

Welchen Zweck erfüllt die SUCC 6 Nachricht so wirklich? Ich würde verstehen, wenn die Nachricht SUCC 0 lauten würde.
Also nach dem Motto "Dein Nachfolger ist die 0".
Aber so ist der Informationsgehalt der Nachricht sehr gering. Wenn der Knoten 6 die ID seines Nachfolgers durch aus dem Absender der Nachricht extrahieren kann, dann würde auch SUCC reichen.

Einem Knoten seine eigene ID mitzuteilen kommt mir relativ seltsam vor.

Benutzeravatar
BadTaste
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 181
Registriert: 18. Apr 2005 16:40
Wohnort: Darmstadt
Kontaktdaten:

Re: Exercise 4 - Join of a Chord Node

Beitrag von BadTaste »

Danke für den Hinweis.
Natürlich muss der Inhalt der Nachricht im Beispiel "SUCC 0" sein!
Ich habe die Datei dementsprechend aktualisiert.

Benutzeravatar
blackcomb
Mausschubser
Mausschubser
Beiträge: 70
Registriert: 1. Okt 2007 15:48
Wohnort: Darmstadt

Re: Exercise 4 - Join of a Chord Node

Beitrag von blackcomb »

In dem Zusammenhang habe ich noch eine Frage zur Lösung der Aufgabe 4.1 b) (exercise5-slides.pdf, S. 6):

Warum leitet 49 die JOIN-Nachricht an 55 weiter und nicht direkt an 60? Um den Nachfolger des neuen Knotens (58) zu finden, müsste es ja ausreichen, die JOIN-Nachricht an succ( 49 + 8 ) = succ(57) = 60 weiterzuleiten...

Vielen Dank schon einmal, falls jemand hierzu eine Idee hat.

Benutzeravatar
BadTaste
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 181
Registriert: 18. Apr 2005 16:40
Wohnort: Darmstadt
Kontaktdaten:

Re: Exercise 4 - Join of a Chord Node

Beitrag von BadTaste »

Hi,

Die Finger in Chord spannen jeweils Intervalle auf, wobei Finger i dem Intervall zwischen Finger i und Finger i+1 zugeordnet wird (siehe dazu Folie 28 in Lecture_3-1.pdf). Wenn man nun zu einer ID routen will, wird die Nachricht immer an den Finger weitergeleitet, in "dessen" Intervall (ausgehend vom aktuellen Knoten) die ZielID liegt, d.h. es wird immer der Finger mit der größten ID gewählt, dessen ID <= Ziel-ID ist. Somit wird verhindert, dass man über das Ziel hinausschießt und man z.B. über die Predecessor Links rückwärts routen müsste. In der Übung wäre das ja z.B. aufgetreten, wenn es einen Knoten mit ID 59 gegeben hätte.

Würden die Peers in Ihren Routing Tabellen nicht nur die echte ID des Fingers speichern, sondern auf die ihrer Vorgänger bzw. das Intervall für das der Finger zuständig ist, könnte man natürlich in einem solchen Fall diese <= Regel "verletzen" und direkt an den zuständigen Knoten routen. Dieses Vorgehen wäre dann aber quasi eine Erweiterung des "normalen" Routing Protokolls.
(Im Beispiel aus der Übung hätte 49 natürlich ohne zusätzliche Informationen gewusst, dass 60 zuständig für 58 ist, weil es ja wie von dir beschrieben der vierte Finger ist. Es wäre aber ein Spezialfall, der wie gesagt gesondert behandelt werden müsste.)

Ich hoffe, dass ich deine Frage damit beantworten konnte.

Benutzeravatar
BadTaste
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 181
Registriert: 18. Apr 2005 16:40
Wohnort: Darmstadt
Kontaktdaten:

Re: Exercise 4 - Join of a Chord Node

Beitrag von BadTaste »

Ok, mir ist gerade noch mal aufgefallen, dass es schon von der Implementierung abhängt.
In dem von mir beschriebenen Verfahren schaut man quasi nur auf die IDs der Finger.

Wenn man aber die zugewiesenen Intervalle nicht von den echten IDs der Finger sondern von der TargetID des Fingers abhängig belegt würde 49 in der Tat direkt an 60 weiterleiten, weil dieser Laut Finger Table von 49 für den Bereich ab 49+8 = 57 zuständig ist.

Ein guter Grund, warum man das von mir beschriebene auf IDs bezogene Verfahren anwenden sollte ist, dass die Einträge der Finger Table natürlich veraltet sein können und wirklich mittlerweile ein Node 59 hinzugekommen ist, von dem 49 noch nicht weiß und seine Finger Table dementsprechend noch nicht aktualisiert hat. Wenn man sich also nach den IDs und nicht der Position in der Finger Table richtet, geht man auf Nummer Sicher, dass man nicht zurücklaufen muss, falls die Finger Table Einträge veraltet sind. In dem Beispiel hier wäre das natürlich nur ein Hop, kann sich bei hoher Dynamik in einem größeren Netz natürlich viel stärker bemerkbar machen.

So, jetzt sollte die Frage aber wirklich und richtig beantwortet sein :oops:

Benutzeravatar
blackcomb
Mausschubser
Mausschubser
Beiträge: 70
Registriert: 1. Okt 2007 15:48
Wohnort: Darmstadt

Re: Exercise 4 - Join of a Chord Node

Beitrag von blackcomb »

Ok, vielen Dank für die ausführliche Erklärung, das hat meine Frage beantwortet. :wink:

Antworten

Zurück zu „Archiv“