Hey
Kann mir jemand erklären wie das Chord Netz funktioniert bzw wie man da beim Suchen eines Keys vorgeht und wann man abbricht??
Ich verstehe überhaupt nicht was die dan in der Groß ÜÜbung machen!!
Also es gehts um die letzte Aufgabe in der Groß Übung 13.4
wie kommt man z.B. auf i=5 beim Knoten 1 und was passiert eigentlich danach??
Wäre echt nett wenn mir jemand helfen könnte, bin total am Verzweifeln!!
Danke im Voraus
Chord Netz
Moderator: Moderatoren
Re: Chord Netz
Hallo,
zum Thema Chord-Netz gibt es zwei hilfreiche Quellen:
Kurz zum Thema der Suche mit FingerTable:
Diese besteht für jeden Knoten p aus m Einträgen (m = Länge der IDs). Für jeden i-ten Eintrag wird zunächst ein Startwert nach der Formel mod 2^m)
berechnet und von da aus der nächste Knoten gesucht mit einer ID größer dem Startwert und dessen ID dann in die FingerTable geschrieben.
Das beschreibt etwas kryptisch die Formel![[math]](http://www.forkosh.com/mathtex.cgi?[math])
FTp = succ(p+2^{i-1})[/math], die auf den Vorlesungsfolien zu finden ist.
Bei einer Suchanfrage an Knoten n nach Schlüssel k wird nun zunächst der nächstgelegene Vorgänger des Schlüssels gesucht, den Knoten n kennt. Dabei wird die Fingertable so lange von unten nach oben durchsucht, bis der erste Eintrag i gefunden wird, dessen Knoten nicht zwischen n und k liegt. Der Eintrag i+1 ist damit der nächstgelegene Vorgänger von k, den n kennt. Die Suche wird dann mit Hilfe dieses Knotens fortgesetzt. Das wiederholt sich, bis der Knoten gefunden ist, dessen Successor (= direkter Nachfolger, erster Eintrag in der Fingertable) für k zuständig (jeder Knoten ist für die Schlüssel, die unterhalb von ihm bis zum nächsten Knoten liegen) ist.
zum Thema Chord-Netz gibt es zwei hilfreiche Quellen:
- eine kurze, verständliche Einführung
ausführlich zum Prinzip des Chord-Netzes und der Suchfunktionen
Kurz zum Thema der Suche mit FingerTable:
Diese besteht für jeden Knoten p aus m Einträgen (m = Länge der IDs). Für jeden i-ten Eintrag wird zunächst ein Startwert nach der Formel
Das beschreibt etwas kryptisch die Formel
Bei einer Suchanfrage an Knoten n nach Schlüssel k wird nun zunächst der nächstgelegene Vorgänger des Schlüssels gesucht, den Knoten n kennt. Dabei wird die Fingertable so lange von unten nach oben durchsucht, bis der erste Eintrag i gefunden wird, dessen Knoten nicht zwischen n und k liegt. Der Eintrag i+1 ist damit der nächstgelegene Vorgänger von k, den n kennt. Die Suche wird dann mit Hilfe dieses Knotens fortgesetzt. Das wiederholt sich, bis der Knoten gefunden ist, dessen Successor (= direkter Nachfolger, erster Eintrag in der Fingertable) für k zuständig (jeder Knoten ist für die Schlüssel, die unterhalb von ihm bis zum nächsten Knoten liegen) ist.
Re: Chord Netz
Hey danke dir ich habe glaube ich den Aufgabe jetzt verstanden nur eins verstehe ich nicht ganz, wenn der Eintrag i den Schlüssel enthält, der nicht zwischen k und n liegt, welche bedeutung hat wenn k<n bzw k>n (also am Start) und was ist die Abbruchbedingung bzw woran erkennt man sie??#
UNd wofür steht die Bedingung : Knoten 18 wählt Knoten 20 = FT18[2] < k ≤ FT18[2].
UNd wofür steht die Bedingung : Knoten 18 wählt Knoten 20 = FT18[2] < k ≤ FT18[2].
Re: Chord Netz
Ich verstehe die erste Frage nicht so ganz.
Die Abbruchbedingung ergibt sich einfach, wenn der erste Knoten mit einer ID oberhalb des gesuchten Schlüssels erreicht wurde (Der verwaltet jeweils diese(n) Schlüssel).
Zur zweiten Frage kann ich nichts sagen, da ich die Aufgabe nicht kenne.
Die Abbruchbedingung ergibt sich einfach, wenn der erste Knoten mit einer ID oberhalb des gesuchten Schlüssels erreicht wurde (Der verwaltet jeweils diese(n) Schlüssel).
Zur zweiten Frage kann ich nichts sagen, da ich die Aufgabe nicht kenne.