Kad

KAD es un protocolo pensado para ser desplegado sobre redes P2P basado en una red estructurada y que usa como método de ordenamiento y búsqueda las DHT (Distributed Hash Tables).​

Es una implementación del protocolo Kademlia, el cual aporta la base teórica al protocolo y por tanto, hay muchas partes de Kademlia que KAD hereda y reutiliza. KAD desarrolla la base en forma práctica siguiendo las pautas genéricas de Kademlia y las especificaciones propias del mismo KAD.

Se aplica a proyectos P2P del tipo Open Source y soportado por las aplicaciones cliente para compartir archivos como eMule, aMule, eDonkey2000 o Lphant.

No lleva mucho tiempo de uso, pero a pesar de ello tiene alrededor de 1 millón de usuarios simultáneos.

KAD usa para el transporte de sus mensajes el protocolo UDP, lo que permite el envío de paquetes de manera rápida, además sin implicar considerablemente a los demás peers. También usa UDP debido a que no necesita establecer sesiones entre los peers, pues se suele enviar una sola petición de un peer a otro; cuando obtiene la respuesta es cuando repite la operación con el siguiente peer.

Debido a la naturaleza de los nodos, normalmente suelen unirse o abandonar la red KAD cuando quieren, y la aplicación cliente debe ser consciente de ello; para lo cual se utilizan temporizadores que define el tiempo de las operaciones.

Los usuarios tienen dos puertos estándar definidos:

• Puerto UDP (4672): Para el intercambio de mensajes de operaciones de servicio.
• Puerto TCP (4662): Para el intercambio (subida o bajada) de ficheros. Aunque este puerto también se usa para comprobar reglas de Firewall por otros servicios.

Cabe destacar que el número de los puertos puede personalizarse por el usuario.

Clientes

Sólo cuatro grandes clientes admiten actualmente la implementación de la red Kad. Sin embargo, comprenden más del 80% de la base de usuarios y probablemente cerca del 95% de los clientes de la red eDonkey. Dichos clientes son:

• aMule: Un fork multiplataforma de lMule y xMule enfocado a sistemas UNIX.
• MLDonkey: Un cliente de software libre que funciona en varios sistemas y soporta varios protocolos de intercambio más.
• eMule: Un cliente de código abierto para Windows. Es el más popular, con un 80% de usuarios. También funciona en GNU/Linux a través de Wine.
• Lphant: Un cliente que soporta también BitTorrent. Tiene acceso a la red Kad a partir de la versión 3.50.

Existen cierto número de variantes menores o forks de eMule que soportan las mismas funciones básicas que eMule.

Estructura

Espacio de trabajo

Una de las cosas que KAD hereda de Kademlia es el espacio de objetos virtual y el ordenamiento basado en árbol binario.

El protocolo Kademlia posee un espacio de 128 bits, es decir, en este espacio puede existir 2¹²⁸ objetos/peers distintos. Cada uno de estos objetos posee un ID de cliente que determina la posición dentro del espacio Kademlia.

Es importante destacar que a pesar de que en el árbol dos peers estén cercanos, como el cálculo de distancias se calcula mediante la operación XOR, pueden encontrarse más lejos de lo que aparentan físicamente en el árbol. Las diferencias de bits en las posiciones más altas implicarán distancias mayores que si existe diferencias en los bits de menor peso.

Al contrario que otras implementaciones y protocolos, en KAD la distancia entre dos nodos es la misma en ambos sentidos, es decir es bidireccional.

El árbol de peers en el que se basa KAD no es un árbol perfecto, pues no todos los peers deben tener el mismo nivel de profundidad.

Ejemplo de árbol binario con IDs de 4 bits

Esto es un ejemplo simplificado de lo que sería KAD con tan solo 4 bits.

Espacio de números

ID_A = 1011 = 11

ID_B = 1000 = 8

ID_C = 0110 = 6

ID_D = 0011 = 3

ID_E = 0111 = 7

Métrica de distancia con respecto al peer E

ID_A $\oplus$ ID_E = 1100 (binario) = 12 (decimal)

ID_B $\oplus$ ID_E = 1111 (binario) = 15 (decimal)

ID_C $\oplus$ ID_E = 0001 (binario) = 1 (decimal)

ID_D $\oplus$ ID_E = 0100 (binario) = 4 (decimal)

Tablas de rutas

Las tablas de rutas de un peer se organiza mediante K buckets, que son las hojas del árbol. Cada uno de los K buckets representa un subárbol con K peers.

Algunos de los atributos de estos otros peers que guardamos en los buckets son: la dirección IP, el puerto UDP y/o TCP, el ID, la distancia, y algunos más.

Otro de los atributos que se guardan en estas tablas son los tiempos de expiración en el cual se deben mantener estas filas en la table de rutas.

El contenido de estas tablas se refresca cada cierto tiempo. Por ejemplo en la implementación de KAD para eMule, el tiempo de refresco es de 24 horas.

Formato y Tipo de Mensajes

Formato de los mensajes

Los paquetes UDP que utiliza KAD tiene el siguiente formato:

• ID: El primer byte especifica el identificador del protocolo específico.
• OPCODE: El segundo byte determina el código de operación. Suele definir los diferentes tipos de peticiones y respuestas del protocolo KAD.
• PAYLOAD: Datos útiles con tamaño determinado por el datagrama UDP.

Tipo de mensajes

Existen cuatro tipos de mensajes: PING, STORE, FIND_NODE y FIND_VALUE.

PING

Este mensaje se envía de un peer a otro, que suponemos nos contestará. Se utiliza para actualizar el bucket del receptor con los datos del peer emisor del mensaje PING; pero también si es respondido este mensaje, el emisor también actualizará su bucket con la información recibida.

STORE

El emisor proporciona una clave y un bloque de datos. Esta operación requiere que el receptor almacene los datos y los marque como disponibles para su posterior acceso mediante la clave especificada por el emisor. Como el protocolo de transporte suele ser UDP, debemos especificar en el mensaje también el ID del peer (el ID del emisor en el mensaje STORE, y en el mensaje de respuesta a este, el receptor del mensaje STORE).

FIND_NODE

Este mensaje primitivo (no iterativo) incluye una clave de 160 bit. El receptor del mensaje devuelve k triadas de datos a los contactos más cercanos a la clave. Esta triada de la que hablamos se compone de la siguiente información: la dirección IP, el puerto, y el ID del peer. El receptor deberá devolver k triadas a no ser que el receptor no conozca más contactos y devuelva todos los que conoce. Si la clave que busca el emisor es la clave de uno de los contactos, o del mismo peer al que se le está enviando este mensaje; aun así el receptor debe devolver k triadas. Y nunca deberá devolver una triada con los datos del emisor del mensaje FIND_NODE original.

FIND_VALUE

Este mensaje primitivo (no iterativo) incluye una clave de 160 bit. Si el valor buscado se encuentra en el receptor del mensaje FIND_VALUE original, este devuelve el dato sin más. Pero si no este mensaje actúa como un mensaje FIND_NODE y se devuelve k triadas al emisor para continuar la búsqueda.

Inicialización y Configuración de un Nuevo Peer

Cuando un nuevo peer se conecta a la red KAD, es necesario configurar esta nueva conexión para que la red siga siendo consistente. Cada nodo en la red KAD debe tener un identificador único, así que si no se ha asignado uno a un cliente, lo genera él mismo de manera aleatoria.

Bootstrapping o Proceso de Arranque

El proceso de bootstrapping debe realizarse ante un nuevo peer, pues un nodo cliente debe tener en su tabla de rutas al menos un nodo activo de la red KAD.

El nuevo peer envía el mensaje de bootstrap, que es respondido por otro peer con una lista de nodos de la red; esta lista será una porción aleatoria de la tabla de rutas del peer que recibe el mensaje de bootstrap. Tras esto, el cliente bootstrap verifica las direcciones IP y puerto obtenidas, y si son correctas podremos poblar nuestra tabla de rutas con estos datos. Y en un futuro poder buscar tanto otros nodos en la red, como contenido que tenga alguno de esos nodos.

Además de este intercambio de datos, el peer que recibe el mensaje de bootstrap, reconoce al emisor como un nuevo peer, y le añade a su lista.

Después de añadir un nuevo contacto, el emisor inicia un nuevo proceso para asegurarse que el receptor sigue allí, enviando una petición a este. Si el receptor sigue activo responderá al emisor. Una vez llegue este mensaje al emisor, se envía una comprobación de firewall (si este proceso ocurrió tras el bootstrapping) o un paquete del tipo ‘HELLO’ (en cualquier otro caso) en cuya ocasión se responderá con un ‘HELLO RESPONSE’.

Comprobación Tipo Firewall

Un cliente P2P puede ser afectada por las reglas de control de tráfico de dos formas: un firewall o un NAT(Network Address Translation). El firewall bloqueará todas las conexiones entrantes que no hayan sido previamente especificadas por defecto. Por eso, cuando un host con una IP privada intenta enviar un mensaje a otro peer, no podrá ser alcanzado por ser un host desconocido e inalcanzable.

Una solución es enviar los puertos deseados del cliente al router o abrir los puertos correspondientes en el firewall directamente. A pesar de que el cliente Kad se lanza tras un router con un NAT, este puede obtener el estado del firewall aun cuando el router encamina paquetes hacia el puerto UDP por defecto (puerto 4672 como dijimos anteriormente).

KAD posee una implementación específica que averigua si un puerto de un cliente P2P tiene conectividad directa o no, y siempre que se establece la conexión de un peer con la red KAD, se ejecuta este proceso.

Procedimiento de Búsquedas

A continuación explicaremos el algoritmo utilizado por este protocolo para localizar sus k nodos más cercanos (cercanía en cuanto a métrica XOR) a una clave. Este algoritmo basado en DHTs es similar a los que implementan otros protocolos como Pastry (enlace en inglés), Tapestry (enlace en inglés) o Toplus.

La búsqueda comienza seleccionando α contactos (Si no hay α contactos se elige otro bucket) de los k bucket que contengan algún nodo más cercano al bucket adecuado a la clave que se busca. El contacto más cercano a la clave buscada (llamado closestNode) de destino, se guarda.

Los primeros α contactos alfa seleccionados se utilizan para crear una lista preliminar para la búsqueda. El nodo envía de forma paralela mensajes asíncronos del tipo FIND (FIND_NODE o FIND_VALUE) a los α contactos de la lista. Cada contacto activo devolverá k triadas, y cada contacto inactivo se borrará de la lista preliminar que generamos anteriormente. Con estos contactos cada vez nos acercaremos más (de nuevo en cuanto a métricas XOR) al nodo objetivo, puesto que cada búsqueda actualiza el closestNode para continuar buscando hasta el nodo deseado.

Alpha and Parallelism

En cuanto al parámetro α, Kademlia de forma predeterminada usa un valor de α=3.

Hablando del paralelismo de las búsquedas, establecemos tres aproximaciones diferentes de modelado de paralelismo:

• La primera es enviar las α peticiones y esperar hasta que todas hayan resultado con éxito o que el tiempo de espera (timeout) antes de la operación haya terminado. Esto se denomina paralelismo estricto.
• La segunda es la de limitar el número de peticiones en vuelo; cada vez que una petición nos devuelve un resultado, se hace una nueva petición de búsqueda. Podríamos llamar a este tipo: paralelismo acotada.
• Y el tercero es enviar de nuevo las α peticiones después de un tiempo razonable (indeterminado), por lo que el número de sondas en vuelo es un poco baja, y múltiplo de alfa. Este se llama paralelismo amplio y es el usado por Kademlia.

iterativeStore

Esta es la operación de almacenamiento de este protocolo. El nodo emisor envía esta petición recogiendo un conjunto de los k contactos más cercanos, y luego envía a cada uno un mensaje del tipo STORE.

Las peticiones iterativeStores se usan para la publicación de datos o replicarlos en la red KAD.

iterativeFindNode

Esta es la operación básica de búsqueda de nodos. Como se explicó en el apartado anterior, el nodo que busca crea una lista con los k contactos más cercanos utilizando de forma iterativa mensajes del tipo FIND_NODE.

iterativeFindValue

Se trata de la operación de búsqueda de datos. Se lleva a cabo como una búsqueda de nodo, y por lo tanto genera una lista con los k contactos más cercanos. Sin embargo, esto se hace usando mensajes del tipo FIND_VALUE en lugar de los FIND_NODE. Si en cualquier momento durante las operaciones de búsqueda de nodo el valor se devuelve en lugar de un conjunto de k contactos, la búsqueda se interrumpe y se devuelve el valor. De lo contrario, si no se ha encontrado ningún valor, la lista de los k contactos más cercanos se devuelve al nodo que inició la búsqueda del dato.

Cuando una petición iterativeFindValue se completa de forma correcta, el nodo emisor debe almacenar el par clave-valor en el nodo más cercano al que preguntamos y que no nos devolvió el valor buscado.

Publicación de contenidos

En esta sección se explica el proceso de publicación en detalle tanto de las referencias de metadatos, como de la publicación del contenido real en las fuentes reales de los datos. Además se explicará brevemente la publicación de notas para almacenar otros tipos de información que ya veremos.

Todas las referencias se distribuyen en varias veces, este proceso se llama replicación de contenido. Esto es necesario, debido a la rotación y naturaleza de los peers, además la publicación de una referencia a un único peer es un alto riesgo y un peligroso punto de ataque de la red KAD; ya que la referencia se perdería cuando un peer sale de la red o contiene información obsoleta que no refresca… Así que el protocolo KAD envía la misma referencia a unos 10 pares diferentes.

Publicación de Metadatos

La publicación de metadatos está en el segundo nivel del sistema de publicación descrito en el apartado anterior. Por lo que hace referencia a la información de ubicación de la primera capa. Pero ya contiene la información sobre el archivo real: nombre de archivo, tamaño, tipo, ID hasheado del archivo y del peer, fuentes, etc. ; esto facilita la búsqueda al usuario.

Por supuesto, para que un contenido pueda ser publicado, el cliente debe tener el archivo listo para ser publicado.

Existe un proceso cada 24 horas de publicación de archivos, que publica los archivos que aún no lo han hecho y verifica y modifica la fecha de última publicación de todos los archivos del peer.

Publicación de Fuentes

Lo que llamamos fuentes, son los peers que contienen la ubicación de la información que apunta directamente al peer que posee el archivo real. Se publica una fuente por archivo. Sin embargo, la replicación de contenido hace que la publicación se haga en varios peers diferentes. El proceso de publicación es similar al de metadatos. Existe un proceso cada 5 horas de republicación que publicará la información que no lo haya hecho anteriormente.

Las fuentes las guardamos en una tabla que contendrá la información conveniente para ello: ID hasheada de la fuente y cliente de la información, tipo IP y puerto de la fuente, y más atributos menos destacables. Todos los atributos de la entrada de esta tabla son los que se enviarán en el mensaje de publicación para identificar el contenido. Cabe destacar que las fuentes con IDs más altos, serán los peers que no pasan por Firewall y no envían información alguna.

Cuando se supone que una fuente va a ser publicada, entonces el peer enviará una solicitud de búsqueda que encontrará el peer adecuado donde publicar este contenido; y finalmente publica este contenido.

Cuando un peer recibe un contenido de publicación de una fuente también guarda información sobre esa transacción, como puede ser la dirección IP y puerto entrante, por ejemplo. Además confirma al peer que publicó la fuente con un mensaje y añadirá a su lista de fuentes la información de los datos actuales.

Publicación de Notas

Estas notas son unos comentarios que se usan a modo de calificación del contenido, de manera que si un supuesto peer malicioso intentase contaminar la red publicando contenidos corruptos o no legítimos, el cliente peer que recibe ese archivo lo detecta evitando publicarlo o compartirlo de nuevo al resto de la red, y evitar así su masificación por la red KAD.

Dichas notas no solo sirven para esto, sino que además se utilizan para almacenar otros tipos de información relativa a contenidos de la red KAD.

Como el objetivo principal de estas notas es el de evaluar los contenidos en la red se provee de un rango de calificación entre 1 y 5 llamado FILERATING, donde 5 es el mejor y 1 la peor. La calificación sólo debe notificarse un archivo está dañado o evaluar la calidad técnica como el sonido o vídeo. Aunque a veces los usuarios lo usan para validar el contenido del archivo y no el propio archivo. Si este FILERATING se establece en 0, significa que la nota es un mero comentario. Las notas además poseen un campo de descripción opcional donde puede escribirse un texto a modo de comentario.

El cliente que recibe la nota la añade al ID de la fuente correspondiente. Existe una limitación de 50 notas por archivo.

Intercambio de Archivos

El intercambio de archivos en la red KAD, requiere que cada fichero se publique en el espacio de la red KAD poblando los buckets de ciertos nodos para que el contenido sea accesible. Los nodos que contienen la información de cierto contenido se llaman ‘host peer’ y son responsables de responder las peticiones de los peers que busquen el contenido de los que ellos poseen información. Estos host peer solo mantendrán la información durante un periodo determinado de tiempo preestablecido, para evitar referencias corruptas que no apunten a ningún contenido. Como hemos presentado anteriormente, lo que los host peers almacenan son referencias al contenido publicado anteriormente y no el fichero completo. Esto mejora el rendimiento y además evita sobrecarga de tráfico en la red.

Es importante destacar que los peers más cercanos a palabras clave populares reciben más palabras clave y/o referencias a fuentes, así como los peers con métricas XOR más altas.

Modelo de publicación en 2 capas

Un archivo compartido siempre se mantiene en un peer hasta que comienza el proceso de descarga de ese contenido.

Este modelo divide los archivos en dos tipo: los metadatos y los de ubicación de la información.

Los metadatos son identificados mediante una palabra clave cifrada mediante hash del tipo MD4. Cada fichero tiene tantas referencias de metadatos apuntando a la ubicación del archivo, como palabras clave válidas tenga el nombre del contenido.

Un ejemplo de publicación de contenido en la red KAD se podría plantear como lo mostramos en la imagen anterior, donde podemos ver los peers implicados con la información que contiene cada uno del contenido almacenado.

Se puede apreciar que el contenido a publicar tiene por título una serie de 3 palabras, por tanto como se explicó anteriormente tendremos 3 hashes de las referencias al peer que almacena el contenido real.

Para que un nodo pueda encontrar un archivo en la red KAD, es necesario que conozca al menos una de las palabras clave del contenido que está buscando. Calcula el hash de esa clave y busca en sus tablas nodos cercanos a esa clave, e iterativamente realiza los procesos de búsqueda explicados en apartados anteriores, hasta recibir la lista de fuentes que contienen el archivo buscado. De esta lista de fuentes se elegirían varias de las que se procederá a descargar el contenido y así hasta completar el contenido; si con estas fuentes elegidas el contenido está incompleto, se eligen fuentes diferentes de la lista recibida en el proceso anterior.

El esquema de 2 niveles o capas tiene ventajas frente al modelo de la publicación de 1 capa; especialmente en redes con una alta tasa de duplicación de archivos, necesita el esquema de 2 niveles pues se usarán menos referencias. Otra de las ventajas del modelo en 2 capas es que el promedio de palabras clave por archivo es de 7; aunque la separación entre palabra clave y la ubicación real del contenido equilibra la sobrecarga de la red en diferentes peers.

Vamos a contar el número de referencias en cada una de las implementaciones:

• 2 niveles: (archivosDistintos x réplicasPorArchivo) + (archivosDistintos x palabrasClavePorArchivo) = archivosDistintos x (réplicasPorArchivo + palabrasClavePorArchivo)

• 1 nivel: (archivosDistintos x réplicasPorArchivo x palabrasClavePorArchivo)

Como vemos el modelo de 2 niveles es inferior (en número de referencias) que en el de 1 nivel, otra ventaja más por la que un modelo en dos capas es mejor.

Proceso de Descarga

El proceso de descarga comienza cuando el peer que quiere descargar un contenido encuentra un peer con el contenido que pretende descargar. Para poder encontrar a estos peers, el nodo que desea conseguir un contenido anuncia a todos los contactos de su lista la información de la ubicación del contenido que busca, el peer se añade a la lista de espera de bajada de ese contenido, hasta que es elegido para la descarga de este contenido. La descarga del contenido se realiza mediante partes del contenido y no el contenido completo, estas partes se llaman chunks. De tal manera que una vez descargado esta porción del contenido que deseamos, ya podemos compartirla nosotros y que otros peers se la descarguen de nosotros.

Sistema de Crédito

Los clientes P2P implantan un sistema de crédito para incitar a los usuarios a compartir más archivos y así recibir mejor prestaciones y mejores contenidos que otros usuarios. Este crédito se traduce en el tiempo de espera que un usuario espera en cola para poder descargar un contenido de otro peer.

El crédito de un usuario que intenta descargar un contenido, también llamado ratio, dependerá de la cantidad de contenido que estemos compartiendo y que estamos requiriendo a la red KAD.

Este crédito se calculará en un intervalo de tiempo definido por el cliente P2P, y mediante este se decidirá quien es el que conseguirá ser el peer que descargará el contenido en ese momento, siendo el de mayor rating el elegido.

Véase también

• Tabla de Hash Distribuido
• Kademlia

Enlaces externos

• Brunner, R., 2006, A performance evaluation of the Kad-protocol, Institut Eurécom (France) ⇒ Evaluación del protocolo KAD (en inglés)
• Especificación de Kademlia (en inglés)
• Especificación formal de las tablas de rutas de Kademlia y KAD en Maude (en inglés)
• Mejoras para el proceso de búsqueda sobre algoritmos DHT (en inglés)
• Estudio de ataques y vulneravilidades de la red KAD (en inglés)
• Especificación del protocolo Kad (en inglés)

• Datos: Q2620547