Seite 1 von 1

Kademlia?

Verfasst: 29. Jan 2013 10:29
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?

Re: Kademlia?

Verfasst: 29. Jan 2013 17:20
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.

Re: Kademlia?

Verfasst: 30. Jan 2013 11:15
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?

Re: Kademlia?

Verfasst: 30. Jan 2013 15:37
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.

Re: Kademlia?

Verfasst: 31. Jan 2013 08:03
von theday
vielen Dank, ich habe es jetzt verstanden.