Wie funktioniert die Routing-Tabelle zum Bestücken von Gebäck?

Ich versuche, die Pastry Distributed Hash Table zu implementieren, aber einige Dinge entziehen sich meinem Verständnis. Ich hatte gehofft, jemand könnte das klären.

Haftungsausschluss : Ich bin kein Informatikstudent. Ich habe in meinem Leben genau zwei Informatikkurse belegt und mich auch nicht mit irgendetwas entfernt Komplexem befasst. Ich habe jahrelang mit Software gearbeitet und fühle mich der Implementierungsaufgabe gewachsen, wenn ich mich nur mit den Ideen beschäftigen könnte. Vielleicht fehlt mir einfach etwas Offensichtliches.

Ich habe das Papier gelesen, das die Autoren veröffentlicht haben [1], und ich habe einige gute Fortschritte gemacht, aber ich bin immer wieder auf dem neuesten Stand, wie die Routingtabelle funktioniert:

Das Papier behauptet das

Die Routing-Tabelle eines Knotens ist in Zeilen mit jeweils Einträgen organisiert. Die Einträge in Zeile der Routing-Tabelle beziehen sich jeweils auf einen Knoten, dessen Knoten-ID die Knoten-ID des aktuellen Knotens in den ersten n Ziffern teilt, dessen te Ziffer jedoch einen der möglichen Werte hat anders als die te Ziffer in der ID des aktuellen Knotens.2 log 2 b N ⌉ 2 b - 1 2 b - 1 n n + 1 2 b - 1 n + $R$$\lceil \log_{2^b} N\rceil$$2^b - 1$$2^b - 1$$n$$n + 1$$2^b - 1$$n + 1$

Das steht für eine anwendungsspezifische Variable, normalerweise . Verwenden wir der Einfachheit halber . So ist das Obige4 b = $b$$4$$b=4$

Die Routing-Tabelle eines Knotens ist in Zeilen mit jeweils Einträgen organisiert. Die Einträge in Zeile der Routing-Tabelle beziehen sich jeweils auf einen Knoten, dessen Knoten-ID die Knoten-ID des aktuellen Knotens in den ersten n Ziffern teilt, dessen Ziffer jedoch einen der möglichen Werte außer Stelle in der ID des aktuellen Knotens.≤ log 16 N ≤ 15 15 n n + 1 2 b - 1 n + $R$$\lceil \log_{16} N\rceil$$15$$15$$n$$n + 1$$2^b - 1$$n + 1$

Ich verstehe das sehr. Außerdem ist die Anzahl der Server im Cluster. Das verstehe ich auch.$N$

Meine Frage ist, wenn die Zeile, in die ein Eintrag eingefügt wird, von der gemeinsamen Länge des Schlüssels abhängt, warum die scheinbar zufällige Begrenzung der Anzahl der Zeilen? Jede NodeId hat 32 Ziffern, wenn (128-Bit-NodeIds, unterteilt in Ziffern von b Bits). Was passiert also, wenn hoch genug ist, dass ? Mir ist klar, dass es 340.282.366.920.938.463.463.374.607.431.768.211.457 (wenn meine Mathematik stimmt) Server braucht, um dieses Szenario zu erreichen, aber es scheint nur eine seltsame Einbeziehung zu sein, und die Korrelation wird nie erklärt.N ⌈ log 16 N ⌉ > $b=4$$N$$\lceil\log_{16} N\rceil > 32$

Was passiert außerdem, wenn Sie eine kleine Anzahl von Servern haben? Wenn ich weniger als 16 Server habe, habe ich nur eine Zeile in der Tabelle. Außerdem würde unter keinen Umständen jeder Eintrag in der Zeile einen entsprechenden Server haben. Sollen die Einträge leer bleiben? Mir ist klar, dass ich den Server in der Blattsammlung finden kann, egal was passiert, da nur wenige Server vorhanden sind. Für die zweite Zeile wird jedoch dasselbe Problem ausgelöst - was passiert, wenn ich keinen Server mit einer NodeId habe so, dass ich jede mögliche Permutation der n-ten Ziffer ausfüllen kann? Wenn ich beispielsweise vier Server und zwei Knoten habe, die beispielsweise 20 ihrer 32 Ziffern teilen, sollte ich zufällig 20 Tabellenzeilen für diesen Knoten füllen, auch wenn dies der Fall ist weit mehr Reihen, als ich überhaupt füllen könnte?

Folgendes habe ich mir ausgedacht und versucht, mich hierdurch zurechtzufinden:

1. Einträge müssen auf einen Nullwert gesetzt werden, wenn es keinen Knoten gibt, der genau mit diesem Präfix übereinstimmt.
2. Leere Zeilen müssen hinzugefügt werden, bis genügend Zeilen vorhanden sind, um der gemeinsamen Länge der NodeIds zu entsprechen.
3. Wenn und nur wenn es keinen passenden Eintrag für eine gewünschte Nachrichten-ID gibt, greifen Sie auf eine Suche in der Routing-Tabelle nach einer Knoten-ID zurück, deren gemeinsame Länge größer oder gleich der aktuellen Knoten-ID ist und deren Eintrag mathematisch näher als die aktuelle ist NodeId's auf die gewünschte ID.
4. Wenn in Nr. 3 kein geeigneter Knoten gefunden werden kann, nehmen Sie an, dass dies das Ziel ist, und übermitteln Sie die Nachricht.

Halten alle vier dieser Annahmen? Gibt es irgendwo anders, wo ich nach Informationen suchen sollte?

1. Gebäck: Skalierbare, dezentrale Objektlokalisierung und Routing für große Peer-to-Peer-Systeme von A. Rowstrong und P. Druschel (2001) - hier herunterladen

Die Idee einer Routing-Tabelle in Pastry (und allen strukturierten P2P-Netzwerken) besteht darin, ihre Größe zu minimieren und gleichzeitig ein schnelleres Routing zu gewährleisten.

Der Routing-Algorithmus von Pastry sieht folgendermaßen aus:

Schritt A. Ein Knoten u sucht nach einem Objekt A, indem er es zuerst in seinem Blattsatz nachschlägt. Schritt B. Wenn es nicht verfügbar war, wird die Abfrage an einen bekannten Knoten weitergeleitet, der "eine Anzahl von Präfixen mit teilt , die mindestens größer ist als der Knoten, den u mit A teilt". Schritt C. Wenn ein solcher Datensatz nicht gefunden wird, wird die Abfrage an einen Knoten in der Blattsammlung weitergeleitet, der numerisch am nächsten an .$A$$A$

$u$

$i$$u$$i$$u$

$(i + 1)^{th}$$i$$\{0, …, 2^{b} – 1\}$

Beispiel in einem typischen Szenario: Wenn u-Adresse 1111 ist und Objekt den Bezeichner 4324 hat, geschieht Folgendes: 4] [1-4] [1-4]).$A$

Knoten Anteile 0 - Präfix mit dem Objekt . Daher sieht es in Zeile 0 aus. Gemäß der obigen Regel 2 speichert der Knoten Adressen der Knoten 1XXX, 2XXX, 3XXX, 4XXX, wobei X ein Wert ist, der sich nicht darum kümmert. Die nächstgelegene unter diesem Knoten ist 4XXX. - Lassen Sie uns sagen , dass dies 4XXX tatsächlich 4013. Dann ist vorwärts mit Adresse 4013. Jetzt werden Sie die gleiche Sache wieder am Knoten wiederholen mit Adresse 4013.A u A u u 1 u $u$$A$$u$$A$$u$$u _1$$u _1$

Zur Vereinfachung hier noch einmal ein Beispiel für 4013. sucht zuerst nach dem gemeinsamen Präfix für die Größe zwischen 4013 und 4324 (1). Also geht es zu Zeile 1, die Werte wie 41XX enthält. 42XX, 43XX, 44XX. Der Schlusskurs von ist 43XX. - Wenn dies 4331 war, wird es darauf zu gerichtet sein.$u _1$$A$

Die maximale Anzahl von Hops hier in ist 4 Hops (XXXX)! in Konditorei-Begriffen ist es . So wird es reduziert, wenn zunimmt. Aber die Größe der Zeilen, die sind, nimmt zu! - so sagten die Autoren, dass = 4 eine gute Balance ist! b 2 b$log_{2^b}$$b$$2^b$$b$

Praktische Szenarien sind in der Regel nicht so typisch. Es kann Situationen geben, in denen sich nicht viele Knoten im Netzwerk befinden. Aus diesem Grund folgen wir dem obigen Schritt C. - Um sicherzustellen, dass dieser Algorithmus korrekt ist, müssen Sie jedoch sicherstellen, dass jeder Knoten mit den beiden nächstgelegenen Knoten verbunden ist (in Bezug auf die Bezeichner). Dies wird einen Ring geordneter Knoten bilden [zB 1-> 3-> 4-> 9-> 10-> 11-> 1]