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 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

= 1011 = 11

= 1000 = 8

= 0110 = 6

= 0011 = 3

= 0111 = 7

Métrica de distancia con respecto al peer E

= 1100 (binario) = 12 (decimal)

= 1111 (binario) = 15 (decimal)

= 0001 (binario) = 1 (decimal)

= 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