Comment comprendre le protocole Kademlia (KAD)

Question

Récemment, j'ai lu un document du protocole Kademlia, j'ai essayé de comprendre le protocole, mais j'ai encore une question: Pourquoi un nœud doit trouver un autre nœud quand il connaît son identité, mais IP ou le port? Pourquoi il a l'ID alors qu'il ne connaît pas l'adresse IP ou le port, où est-il obtenir l'ID? Je pense que la « distance » entre deux différents nœuds n'est pas une distance de routage ou de la distance réelle, il est seulement une distance virtuelle qui peut être utilisé l'algorithme pour trouver le nœud rapidement, il est vrai?

Peut-être que mon anglais est pas très clair parce que l'anglais n'est pas ma langue maternelle, mais je vais essayer de me exprimer clair si vous avez besoin. Merci beaucoup!

Answer 1

Comme dit chao, la nature distribuée des moyens de réseau que les noeuds doivent publier leurs papiers d'identité et leurs coordonnées à d'autres nœuds, ils parlent. Il n'y a pas lieu central où les ID sont mis en correspondance de contact, de sorte que chaque nœud doit garder cette correspondance pour un sous-ensemble des noeuds du réseau dans sa propre table de routage.

tables de routage Kademlia sont structurés de telle sorte que les nœuds auront une connaissance détaillée de la proximité du réseau pour eux, et les connaissances de façon exponentielle décroissante plus loin.

L'utilisation de XOR au niveau du bit en tant que mesure de la distance théorique entre les ID présente l'avantage que, pour un ID cible donné, aucun deux identifiants peuvent avoir la même distance à la cible.

Imaginez un exemple simple où les ID sont compris entre 00 et 63. Si Kademlia utilisé par exemple différence mathématique pure comme une mesure de la distance, 15 et 35 serait la même distance à 25 - les deux auraient une distance de 10. En utilisant XOR, la distance entre 15 et 25 est 22, et entre 25 et 35, il est 58

De cette façon, le groupe de k ID les plus proches à un ID cible peut être calculé sans ambiguïté.

La constante k a deux utilisations dans Kademlia, mais il est surtout le facteur de réplication. En d'autres termes, un morceau de données sont stockées sur les k plus proches nœuds à l'ID de données.

Le processus de recherche est conçu pour renvoyer soit un groupe de noeuds k (avant le stockage de données sur chacun d'entre eux) ou retourner une pièce unique de données (à partir du premier noeud tenant au cours des itérations de consultation).

En raison de cela, pur Kademlia n'est pas le mieux adapté pour trouver un seul noeud, donc je ne suis pas sûr qu'une partie de votre question est trop pertinente. Si vous ne souhaitez utiliser Kademlia pour trouver un seul nœud, il serait sans doute la peine de modifier le processus de recherche pour terminer plus tôt dès que les déclarations de noeud les détails de contact de noeud cible (de la même manière que les finitions de consultation précoce si une valeur cible se trouve au cours du procédé).

Answer 2

Étant donné que le réseau est distribué, par définition, il n'y a pas une table de maître de Id-> mappage d'adresses. Les nœuds ne sont pas (et généralement ne) connaissent tous les autres nœuds. Le processus de « trouver » un nœud est essentiellement demander des noeuds connus « le plus proche » à la cible non pas tant sur le nœud cible directement, mais de quels noeuds sont plus proches à la cible. Le résultat de cette requête vous donne le prochain groupe de noeuds à la requête, et le processus se répète - et parce qu'un noeud retournerait des résultats qui sont plus proches qu'il est, chaque itération tend à trouver des nœuds plus proches et plus proche de la cible jusqu'à ce que vous finalement atteindre un nœud qui peut dire « Oh, noeud X? Il est juste là-bas. »

Au moins c'est ce que je comprends cela.