Usuario:Silvia.hernandez.uah/Taller

CAN 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. Sistemas de gestión de almacenamiento tales como OceanStore, Farsite y Publiu utilizan CAN.

HISTORIA

Can fue propuesta 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

TABLA DE ENCAMINAMIENTO

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

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 y es independiente de la cantidad de piezas.
  

• 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
  

Vecinos

El sistema se compone de muchos nodos individuales donde cada nodo almacena un trozo de la tabla hash. Cada chunk (trozo) de la tabla se denomina “zona” . 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, cada nodo poseerá una zona distinta. Pero lo normal es que la mayoría de datos solicitados por los usuarios estén 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 asociados. 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).

CONSTRUCCIÓN DE LA RED.

AlGORITMO DE ARRANQUE o bootstrapping

El primer paso de la interacció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 asica 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

BUSQUEDA

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 reenviara 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 ∗ N1/d), siendo n el número de nodos y d la dimensión del espacio de coordenadas.

INSERCIÓN

Cuando un nodo X quiere unirse al sistema deberemos encontrar una nueva zona para él. Lo primero que debe hacer es conectarse a un nodo del sistema, esto se realizará 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 utilizará 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 dividirá 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 deberá comunicar a X su tabla de vecinos, para que 'X pueda construir su propia tabla de vecinos. La inserción de un nuevo nodo solo afecta a un único nodo y sus vecinos inmediatos.

ELIMINACIÓN

En el cada 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 entregará 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 y se encargará temporalmente de la zona del nodo que abandona el sistema.

En el caso de que un nodo X falle generará una zona inalcanzable. Para evitar esta situación, cada nodo envía periódicamente un mensaje a sus nodos vecinos para notificarles que sigue activo. 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 portocolo de restauración, el cual asegura que uno de los nodos vecinos del nodo fallido tomará el control de la zona. Reasignada la zona a un nodo vecino este informa a sus vecinos del cambio para que actualicen sus tablas de encaminamiento

También se pueden producir fallos más complejos como son: fallos simultáneos en nodos adyacentes e inundaciones para descubrir vecinos, pero suelen ser eventos muy raros.