Cómo entender el protocolo de Kademlia (KAD)

Question

Recientemente he leído un documento del Protocolo de Kademlia, traté de entender el protocolo, pero todavía tengo alguna pregunta: ¿Por qué un nodo debe encontrar otro nodo cuando sabe que es ¿ID pero ip o puerto? ¿Por qué tiene la identificación mientras no conoce la dirección IP o el puerto, donde obtuvo la identificación? Creo que la "distancia" entre dos nodos diferentes no es una distancia de enrutamiento o distancia real, solo es una distancia virtual que puede usar el algoritmo para encontrar el nodo rápidamente, ¿verdad?

Quizás mi inglés no sea muy claro porque el inglés no es mi lengua materna, pero intentaré expresarme claramente si lo necesita. ¡Muchas gracias!

Answer 1

Como dijo cHao, la naturaleza distribuida de la red significa que los nodos necesitan publicar sus identificaciones y sus detalles de contacto en otros nodos con los que hablan. No hay un lugar central donde los ID se mapeen a la información de contacto, por lo que cada nodo debe mantener esta asignación para un subconjunto de los nodos en la red en su propia tabla de enrutamiento.

Las tablas de enrutamiento de Kademlia están estructuradas de manera que los nodos tengan un conocimiento detallado de la red cerca de ellos y disminuyan exponencialmente el conocimiento más allá.

El uso de XOR bit a bit como una medida de la distancia teórica entre ID tiene la ventaja de que para una ID de objetivo determinada, no hay dos ID que puedan tener la misma distancia al objetivo.

Imagine un ejemplo simple donde los ID están en el rango de 00 a 63. Si Kademlia usó, p. diferencia matemática pura como medida de distancia, 15 y 35 sería la misma distancia a 25 - ambos tendrían una distancia de 10. Usando XOR, la distancia entre 15 y 25 es 22, y entre 25 y 35 es 58.

De esta forma, el grupo de k identificadores más cercanos a una ID de destino puede calcularse sin ambigüedades.

La constante k tiene un par de usos en Kademlia, pero es principalmente el factor de replicación. En otras palabras, una parte de los datos se almacena en los k nodos más cercanos a la identificación de los datos.

El proceso de búsqueda está diseñado para devolver un grupo de k nodos (antes de almacenar datos en cada uno de ellos) o devolver un único dato (desde el primer nodo que lo contiene durante las iteraciones de búsqueda).

Debido a esto, Kademlia pura no es la más adecuada para encontrar un solo nodo, por lo que no estoy seguro de que una parte de su pregunta sea demasiado relevante. Si desea utilizar Kademlia para encontrar un solo nodo, probablemente valga la pena modificar el proceso de búsqueda para finalizar temprano tan pronto como un nodo devuelva los detalles de contacto del nodo de destino (de la misma manera que la búsqueda finaliza anticipadamente si el valor objetivo es se encuentra durante el proceso).

Answer 2

Como la red se distribuye, por definición, no hay una tabla maestra de asignaciones de ID-> direcciones. Los nodos no tienen que (y generalmente no lo hacen) conocer todos los otros nodos. El proceso de "encontrar" un nodo es básicamente preguntar nodos conocidos "más cercanos" al objetivo no tanto sobre el nodo objetivo directamente, sino sobre qué nodos están más cerca del destino. El resultado de esa consulta le da el siguiente grupo de nodos para consultar, y el proceso se repite, y como un nodo devolverá resultados que están más cerca de lo que es, cada iteración tiende a encontrar nodos más y más cerca del objetivo hasta que finalmente llegar a un nodo que pueda decir "Oh, nodo X". Está justo allí ".

Al menos eso es lo que entiendo.