Chord

Chord es un protocolo sencillo y escalable de búsqueda distribuida en redes P2P que relaciona claves (keys) con nodos. Está diseñado para funcionar en redes descentralizadas (es decir, sin nodos privilegiados), y su funcionamiento permite concluir con un resultado exhaustivo de la búsqueda.

Funcionamiento general

Se considera una red formada por 2^m nodos, que pueden estar activos o ausentes de la red. Dado un conjunto de claves en esa red, el protocolo Chord se encarga de asignar las claves existentes a los nodos activos y mantener esas asignaciones dinámicamente, es decir, a medida que los nodos van entrando y saliendo de la red. El resto de tareas vinculadas a la red -autenticación, almacenamiento de datos, interficie, etc.- son responsabilidad de los niveles superiores de la arquitectura.

La asignación de identificadores a nodos y claves se realiza mediante una función de hash consistente. En efecto, cuando un nodo o una clave entran en la red, reciben una identificación (id) que se obtiene calculando el hash (SHA-1) de la IP del nodo o del valor de la clave. Con este hashing se aleatorizan los accesos al sistema, de forma que para un atacante resulte difícil nodos o claves consecutivas o de posición estratégica en la red.

Una clave de id k se asigna al nodo de id k si éste está activo en la red. Si k no está, se busca el primer nodo posterior a k que esté activo y se le asigna a la clave: este nodo sustituivo se denomina sucesor de k (successor(k)).

Cuando k se conecte a la red, su nodo sucesor le transferirá las claves que estuvieran destinadas a él. Cuando un nodo abandona la red, transfiere las claves de las que se hacía cargo a su sucesor, es decir, al nodo con id siguiente a la suya. Con estos mecanismos, se garantiza la autorregulación de la red y el mantenimiento de las claves aun en un contexto de movilidad de los nodos participantes.

Procedimiento de búsqueda

El correcto mantenimiento de los nodos sucesores ya garantiza que las búsquedas se procesan de forma exhaustiva. Sin embargo, cada nodo almacena una cierta información adicional sobre la red que permite acelerar las búsquedas.

Esta información adicional se reduce a unos pocos nodos activos de la red, y se refleja en una tabla de rutas (finger table) interna. En la i-ésima fila de esta tabla consta el sucesor del nodo situado a distancia 2^{(i − 1)} del nodo correspondiente (en dirección negativa en el círculo). De esta forma, cada nodo tiene un conocimiento más exhaustivo de sus homólogos más cercanos (aproximadamente, si N es el número de nodos totales, almacena información sobre O(log(N))).

Cuando un nodo solicita una clave j, examina su propia tabla de rutas; si encuentra el nodo responsable de j, envía la petición directamente al nodo afectado. En caso contrario, pregunta al nodo cuya id sea más cercana (menor) a j, que devolverá la id del nodo más cercano a j (menor) que encuentre en su tabla de rutas. De esta manera, el nodo remitente obtiene en cada nueva iteración un nodo más cercano a k, hasta llegar a k o a su sucesor. Todo este mantenimiento requiere el desarrollo de una señalización (mensajes entre nodos para mantener actualizadas las tablas de rutas) del orden de (log(N))².

Escalabilidad

Chord está diseñado para ser altamente escalable, es decir, para que los cambios en las dimensiones de la red no afecten significativamente a su rendimiento. En particular, si N es el número de nodos de la red, su coste es proporcional a log(N).