Kademlia?

theday
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 6. Apr 2006 12:14

Kademlia?

Beitrag von theday »

Hallo,
Im Skript 3 auf S.83 wird erklärt wie Knoten u Knoten v in seiner Routing Tabelle einträgt. Könnte mir einer dieses Verfahren erklären?
Warum wird in einem Schritt überprüft ob das entsprechende Bucket den Knoten u enthält?

Soll auch dieses Verfahren in der Aufgabe G7.1 c) erklärt werden.
Weil ich habe in einem Paper im Internet gelesen dass erstmal der alte Knoten mit einer Ping nachricht überprüft wird ob er aktiv ist. wenn nicht, wird er durch dem Neuen ersetzt. Was ist also das Richtige?

Benutzeravatar
AlexPi11
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 154
Registriert: 18. Apr 2009 15:32

Re: Kademlia?

Beitrag von AlexPi11 »

Warum wird in einem Schritt überprüft ob das entsprechende Bucket den Knoten u enthält?
Man sucht sich erstmal den Bucket mit gleichem Prefix raus. Ist da noch Platz, wird der neue Knoten einfach hinzugefügt. Falls der Bucket schon voll ist, wird der Bucket nur dann aufgesplittet und die Knoten samt dem Neuen aufgeteilt, wenn man selbst in diesem Bucket ist. Das führt im Endeeffekt dazu, dass man seine eigene "Region" (langer gemeinsamer Prefix -> kurze Distanz) recht gut kennt, und man für weit entfernte Regionen nur ein paar stellvertretende Knoten speichert.
Weil ich habe in einem Paper im Internet gelesen dass erstmal der alte Knoten mit einer Ping nachricht überprüft wird ob er aktiv ist. wenn nicht, wird er durch dem Neuen ersetzt. Was ist also das Richtige?
Ja, das macht man, da Knoten mit hoher Uptime mit größerer Wahrscheinlichkeit auch später noch länger online sein werden. Man zieht also alte Knoten neuen Knoten vor; vorrausgesetzt der alte Knoten ist noch aktiv.
Das hat aber erstmal nichts mit dem Bucket aufsplitten zu tun. Also beides richtig.

theday
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 6. Apr 2006 12:14

Re: Kademlia?

Beitrag von theday »

danke dir.
Aber ich habe noch eine kleine Frage: wann genau wird mit der Ping Nachricht überprüft ob noch der Knoten aktiv ist? Bevor das aufsplitten des Buckets?

Benutzeravatar
AlexPi11
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 154
Registriert: 18. Apr 2009 15:32

Re: Kademlia?

Beitrag von AlexPi11 »

Aber ich habe noch eine kleine Frage: wann genau wird mit der Ping Nachricht überprüft ob noch der Knoten aktiv ist? Bevor das aufsplitten des Buckets?
Beim Aufsplitten des Bucket wird der neue Knoten in einen der beiden Buckets hinzugefügt, ohne das ein alter Knoten gelöscht wird. Hier ist kein Ping notwendig. Wie schon gesagt sind das Bucket-Aufsplitten und das Prüfen eines Knotens (via PING) zwei unabhängige Sachen.

Wann genau ein PING benutzt wird, um zu Prüfen ob der Knoten noch aktiv ist, hängt von der Implementierung ab. In der "Basisversion" des Papers sieht die Sache folgendermaßen aus:
  • Man erhält (irgendeine) Nachricht und lernt somit einen neuen Knoten kennen.
  • Der Bucket in dem der Knoten hinzugefügt werden würde, ist voll und ist auch nicht der eigene Bucket (sprich kein Aufsplitten)
  • Da man alte Knoten bevorzugt, würde man den Neuen einfach vergessen. Aber um sicher zu gehen, dass die alten Knoten noch aktiv sind, überprüft man zumindest den am längsten nicht mehr gesehenen Knoten (LRU), der sich im Bucket befindet. Sprich hier wird der PING gesendet. Falls man keine Antwort erhält, wird der überprüfte Knoten gelöscht und man hat wieder Platz für den neuen Knoten.
Das kann jedoch zu vielen unnötigen PING Nachrichten führen. Eine vorgeschlagene Optimierung ist deshalt, zu warten bis man eine sinnvolle Nachricht hat (kein simples PING), die man an den zu überprüfenden Knoten schicken kann. Neue Knoten werden dabei erstmal in einer Warteliste vorgehalten.

theday
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 6. Apr 2006 12:14

Re: Kademlia?

Beitrag von theday »

vielen Dank, ich habe es jetzt verstanden.

Antworten

Zurück zu „Archiv“