Content Addressable Network

CAN (acrónimo de Content Addressable Network) es un sistema peer-to-peer estructurado que provee funcionalidades de tabla de hash distribuida (DHT) y permite realizar búsquedas eficientes ya que la información se organiza agrupando el contenido similar en la red. CAN fue una de las primeras cuatro DHTs.

Historia

CAN fue propuesto por primera vez en el año 2001 en la Universidad de California en A scalable content-addressable network escrito por Sylvia Ratnasamy, Paul Francis, Mark Handley,Richard Karp y de Scott Shenker.

Surgió por la popularización de internet entre la población lo que promovió la utilización de diferentes sistemas peer-to-peer. Hasta la fecha los únicos sistemas peer-to-peer existentes eran Napster para redes centralizadas y Gnutella para redes descentralizadas

Introducción

CAN es una Tabla Hash Distribuida utilizada para implementar redes peer-to-peer estructuradas. La topología de red es un espacio cartesiano multidimensional. CAN especifica la información que cada nodo del sistema debe almacenar, también regula la comunicación y el intercambio de mensajes entre los nodos. Algunos sistemas de gestión de almacenamiento tales como OceanStore, Farsite y Publiu utilizan CAN.
El algoritmo de encaminamiento de CAN está diseñado para proporcionar las siguientes características:

Escalable - cada parte del sistema mantiene sólo una pequeña cantidad de estado de control.
Distribuido - el sistema no requiere ningún tipo de control centralizado.
La eficiencia y la tolerancia a fallos- una ruta debe ser óptima.
Carga equilibrada

Estructura

Asignación de claves a nodos

Can es un sistema distribuido que proporciona funcionalidad de tabla hash, lo que supone que la red no se organiza por su contenido ni por sus servicios, sino que se divide todo el espacio mediante unos identificadores que le son signados a los pares que utilizan la red, haciéndoles responsables de una pequeña parte del espacio. Se puede decir que cada nodo es un servidor dedicado a proporcionar la información que él contiene. Esta información es guardada en parejas (clave, valor). A cada clave (k) se le asigna una zona Z en el espacio de coordenadas usando una función hash (SHA-1), por lo que cada par de la pareja (clave, valor) guardará en vez de la clave su hash. La zona Z corresponderá a un nodo, el cual será el nodo que almacene dicha clave. Para poder asignar la pareja (clave, valor) a cada nodo correctamente, solo debemos seguir una regla, una vez calculado el hash de la clave se debe asignar al nodo cuyo identificador sea el más cercano. Si dicho hash es mayor que los identificadores se usara el módulo 2n.

Tabla de encaminamiento

Ejemplo 2d

Vecinos

El diseño básico de su arquitectura es un espacio de coordenadas cartesianas virtual d-dimensional donde d indica la dimensión del espacio. Es un espacio de coordenadas lógicas que es cíclico en todas sus dimensiones. CAN sigue una topología de hiper-rectángulos llamados '“zonas” ', en donde a cada nodo se le asigna una zona única y diferenciada. Este espacio de coordenadas virtuales es independiente de la localización física y conectividad física de los nodos. El sistema se compone de muchos nodos individuales donde cada nodo almacena un trozo de la tabla hash. Las zonas pueden tener diversos tamaños pero deben tener una forma cuadrada. Cada nodo ofrecerá acceso a la zona que contenga para todos los usuarios conectados a él. Pero lo normal, es que la mayoría de datos solicitados por los usuarios se encuentren en un nodo al que no están conectados; para poder solventar dichas peticiones el nodo debe reenviar la petición a uno de sus nodos vecinos. Un nodo solo puede enviar consultas a sus nodos vecinos. Dos nodos son vecinos si de entre sus d coordenadas coinciden todas menos una, con la utilización de vecinos creamos un red virtual para el reenvió de consultas, por lo que cada nodo mantendrá una lista de sus vecinos que contendrá sus direcciones IP y su zona de coordenadas. Con estas coordenadas un nodo es capaz de enviar un mensaje hacia el destino usando un simple algoritmo que reenvía el mensaje al nodo vecino más próximo al destino en el sistema de coordenadas. Todos los mensajes que se envían contienen el destino final al que va dirigido y el nodo al que se envía el mensaje. Cuando un nodo recibe un mensaje que no va dirigido a él, éste lo reenvía al nodo cuyas coordenadas sean las más próximas a las del nodo destino. El número de vecinos que posee un nodo depende del número d de dimensiones que posea el sistema (2*d).

Protocolo de enrutamiento

Enrutamiento

El algoritmo de enrutamiento define el tiempo de respuesta para la consulta. La distancia cartesiana es utiliza como una métrica de enrutamiento para calcular caminos más cortos.En el algoritmo de enrutamiento CAN se debe definir el punto de destino para lo que un usuario envía una petición, que puede ser añadir, borrar o buscar, al nodo que está conectado a él. El nodo mapea la clave solicitada usando la función hash en el punto del espacio de coordenadas cartesianas. La solicitud será enviada al nodo que posee la zona que contiene el punto de destino. Se pueden dar dos opciones: que el nodo conectado directamente al usuario contenga la zona solicitada con lo que el nodo iniciara una conexión directa con el usuario para enviarle el resultado o que el nodo conectado directamente al usuario no contenga la zona deseada con lo que dicho nodo reenviara la solicitud al nodo vecino con coordenadas cartesianas más cercanas a las del nodo destino. El algoritmo de enrutamiento debe comprobar la disponibilidad de los vecinos antes de reenviar la solicitud, ya que puede fallar el nodo vecino más cercano al destino y producirse un error si se envía la solicitud a dicho vecino. Esto puede suponer que el camino utilizado no sea el óptimo.

Latencia media de la ruta

Es importante estimar una longitud media del camino. El número de zonas es la misma para todas las dimensiones y es igual a la ^d√n, donde n es el número total de zonas y d la dimensión del espacio de coordenadas. La longitud máxima de cada dimensión es ^d√n/2. Con lo que la longitud máxima es la suma de la trayectoria máxima en cada dimensión y es igual d*^d√(n)/2. Por tanto la longitud media del camino es O(d*^d√n)

Construcción de la red

Algoritmo de arranque o bootstrapping

El primer paso de la iteración entre el usuario y el sistema P2P es conseguir el acceso al sistema. CAN proporciona un mecanismo de arranque para la primera iteración entre el usuario y el sistema per-to-peer. Este mecanismo está formado por nodos bootstrap que mantienen una lista parcial de los nodos que se encuentran en el sistema. Existe un mecanismo de DNS que permite localizar nodos del sistema mediante un nombre DNS. Se le asigna a CAN un nombre de dominio DNS que se resuelve con la dirección IP de uno de sus nodos bootstrap. Si un usuario envía una solicitud utilizando la dirección de dominio de CAN, el cliente obtiene una respuesta de uno de los nodos bootstrap y establece automáticamente la conexión a cualquier nodo disponible.

CAN se asemeja a una tabla hash y proporciona tres operaciones básicas: inserción, eliminación y búsqueda.

Búsqueda

Cuando se desea buscar una clave K, el identificador de la clave es el que determina la zona del espacio de coordenadas en la que se encuentra. Cuando un nodo X desea buscar una clave K el nodo comprueba si el identificador corresponde con la zona de la que él es responsable, si no es así el nodo reenvía la petición de búsqueda al nodo vecino cuyas coordenadas sean las más cercanas a las del identificador de la clave, el resto de nodos realizarán el mismo proceso hasta llegar al nodo encargado de la zona buscada. La complejidad de este algoritmo de búsqueda es del orden de O (d ∗ N^1/d), siendo n el número de nodos y d la dimensión del espacio de coordenadas.

Inserción

Inserción de un nodo en P

Insertado un nodo en la zona de P

Cuando un nuevo peer se conecta a la red CAN, es necesario configurar esta nueva conexión para que la red siga siendo consistente. Un ejemplo, si un nodo X quiere unirse al sistema debemos encontrar una nueva zona para él. Lo primero que debe hacer es conectarse a un nodo del sistema, esto se realiza ejecutando el algoritmo de arranque. Una vez que el nodo tiene la dirección IP de algún nodo I del sistema, se pone en contacto con él para indicarle su deseo de entrar al sistema. Ahora X debe elegir un punto P al azar del espacio de coordenadas y debe enviárselo al nodo I encontrado, dicho nodo utiliza el algoritmo de enrutamiento para calcular la ruta desde él al punto P elegido al azar (p, q), para descubrir al nodo J. El nodo J encargado de dicho punto P divide su espacio de coordenadas en 2 partes iguales quedando él al cargo de una de ellas y el nodo X a cargo de la otra parte. Una vez que X está conectado al nodo J, el nodo J debe comunicar a X su tabla de vecinos, para que 'X pueda construir su propia tabla de vecinos. Esta zona del sistema debe actualizar su estado, por lo que el nodo J notifica a sus vecinos la existencia de un nuevo nodo vecino. El nodo X crea su tabla y notifica a sus vecinos. La inserción de un nuevo nodo solo afecta a un único nodo y sus vecinos inmediatos.

Eliminación

En el caso de que un nodo X abandone el sistema o tenga un fallo, surge la necesidad de reparar el espacio. Se crea un algoritmo de reestructuración, encargado de que alguno de los vecinos de X se haga cargo del control sobre la zona antes controlada por X. Una vez realizado esto, el nuevo encargado informará a sus vecinos del cambio para que estos puedan actualizar su tabla de vecinos.

En el caso de que el nodo X quiera abandonar el sistema de una manera normal, se debe indicar al sistema sobre su salida. Por lo que entrega su zona y la información de su tabla de encaminamiento a uno de sus vecinos, generando una nueva zona que puede ser válida si la zona del nodo que abandona el sistema es posible combinarla con la zona del nodo vecino e invalida si las zonas no se pueden combinar, por lo que se selecciona al nodo vecino con la zona más pequeña para que se encargare temporalmente de la zona del nodo que abandona el sistema. Reasignada la zona a un nodo vecino informa a sus vecinos del cambio para que actualicen sus tablas de encaminamiento.

En el caso de que un nodo X falle genera una zona inalcanzable ya que se marchara del sistema sin notificarlo y los datos (clave, valor) propiedad del nodo que ha fallado se perderán. Para evitar esta situación, cada nodo envía mensajes de actualización periódicas a cada uno de sus vecinos dando sus coordenadas y una lista de sus vecinos y su zona. Si un nodo no responde a los mensajes durante un cierto periodo de tiempo, se asume que dicho nodo ha fallado y se activa el protocolo de reestructuración (takeover). Este mecanismo es iniciado por los vecinos que detentan que un nodo ha fallado, por tanto dicho protocolo puede iniciarse a la vez por varios nodos diferentes. Este protocolo asegura que uno de los nodos vecinos del nodo fallido tomará el control de la zona. Reasignada la zona a un nodo vecino informa a sus vecinos del cambio para que actualicen sus tablas de encaminamiento.

Mecanismo de reestructuración:

El nodo inicia un temporizador.
Si el temporizador expira envía un mensaje takeover a los vecinos del nodo fallido que el conocía.
Los vecinos que reciben el mensaje comparan el tamaño de su zona con la del nodo que envió el mensaje, si su zona es menor que la del nodo que envía el takeover este nuevo nodo envía un mensaje takeover.

Las dos ventajas principales de este mecanismo son, que permite asignar la zona del nodo que ha fallado al nodo más pequeño lo que supone un equilibrado de carga y que funciona sin ningún tipo de control centralizado.

También se pueden producir fallos más complejos como son: fallos simultáneos en nodos adyacentes. En estas circunstancias es posible que CAN se vuelva inconsistente, por lo que antes de activar el mecanismo de reestructuración el nodo realiza una búsqueda en anillo de expansión y reconstruye el sistema.

Reasignación de zonas

El algoritmo de reestructuración puede causar que a un único nodo se le asignen varias zonas. Lo ideal sería una asignación distribuida entre todos los nodos de la zona, ya que esto evita que el espacio de coordenadas se fragmente excesivamente. Para lograr que se haga una asignación distribuida se utiliza un algoritmo de reasignación de zonas.

Mejoras

La arquitectura básica de CAN es un poco limitada, por lo que surge la necesidad de realizar algunas mejoras. El objetivo principal de estas mejoras es reducir la latencia de enrutamiento, donde tenemos la latencia de ruta (número medio de saltos por ruta) y la latencia por salto (tiempo medio necesario para realizar un salto) .Algunas de las mejoras posibles son las siguientes:

Coordenadas del espacio multi-dimensional

La forma más sencilla para mejorar la latencia de ruta es aumentar el número de dimensiones. Para un pequeño aumento del tamaño de dimensiones, se reduce la latencia de ruta ya que aumentamos la tabla de enrutamiento y por tanto, el número de vecinos. La tolerancia ante fallos también mejora, ahora un nodo tiene más posibles saltos para enviar un mensaje en el caso de que algún nodo falle.

Múltiples realidades

Esta mejora se basa en mantener múltiples espacios de coordenadas independientes, cada uno de estos espacios de coordenadas se llamara realidad. Cuando un nuevo nodo quiere unirse al sistema enviará r join solicitudes, una por cada realidad. Por lo que en cada realidad elegirá un punto diferente al azar. Esto supone que cada nodo debe guardar r tablas diferentes de vecinos, una por cada realidad. Con esto se mejora la latencia media de la ruta y la disponibilidad de los datos con un factor r

Técnicas de almacenamiento en caché y replicación

Habrá pares (clave, valor) que sean más utilizadas, para no sobrecargar tanto los nodos que contienen están claves de datos populares, utilizamos técnicas de almacenamiento en caché y replicación.

Almacenamiento en caché

CAN mantiene una caché de las claves de datos usadas recientemente. Antes de enviar una solicitud de un clave hacia su destino, el nodo comprueba primero si el dato de la clave está en su propia caché y si es así puedo satisfacer dicha solicitud sin reenviarlo más. Por lo tanto, el número de cachés de un dato de una clave crece en proporción a su popularidad y el hecho de que se solicite una clave hace dicha clave más accesible. Las claves guardadas en caché tienen un cierto tiempo de vida pasado ese tiempo se eliminará dicha clave.

Replicación

Si un nodo determina que está sobrecargado por request de una clave de datos puede replicar dicha clave en cada uno de sus vecinos. De este modo la replicación se produce dentro de la región que rodea al nodo de almacenamiento original. Un nodo que tiene una réplica de una clave de datos puede elegir entre satisfacer la solicitud o avanzar en el camino, lo que provoca que la carga se reparta por la región. Las claves de datos replicadas tienen un cierto tiempo de vida pasado dicho tiempo la clave será eliminada.

Múltiples funciones hash

Para mejorar la disponibilidad de los datos se puede utilizar k diferentes funciones hash para asignar una sola clave en k puntos diferentes del espacio de coordenadas y en consecuencia replicar un solo par (clave, valor) en k diferentes nodos en el sistema. Esta mejora conlleva el aumento de las bases de datos de las claves, pero mejora la latencia ya que una consulta del usuario se puede reenviar a un nodo más cercano que contenga la clave.

Particiones más uniformes

La partición uniforme es muy importante para CAN, la longitud media del camino es mínima cuando el espacio de coordenadas se divide en zonas iguales. En CAN básico un nuevo nodo elige una zona al azar para insertarse y esta se divide por la mitad, como el nodo que posee la zona elegida al azar conoce las zonas de sus vecinos. Con el fin de mejorar la partición este nodo puede la unión del nuevo nodo al vecino cuya zona es la más grande.

Véase también

Referencias

^[1]A scalable content addressable network

Enlaces externos

Datos: Q3408069

↑ «http://conferences.sigcomm.org/sigcomm/2001/p13-ratnasamy.pdf».

[1] «http://conferences.sigcomm.org/sigcomm/2001/p13-ratnasamy.pdf».

[1]