B.Sc./M.Sc. Elektrotechnik an der RWTH

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

Hallo,

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

Dort steht eigentlich alles nötige, wohl auch etwas verständlicher als in der ComNets-Version.

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 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 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.

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].

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.