red direccionable por contenido

La red direccionable por contenido ( CAN ) es una infraestructura P2P distribuida y descentralizada que proporciona funcionalidad de tabla hash a una escala similar a la de Internet . CAN fue una de las cuatro propuestas originales de tablas hash distribuidas , presentadas simultáneamente con Chord , Pastry y Tapestry .

Al igual que otras tablas hash distribuidas, CAN está diseñada para ser escalable , tolerante a fallos y autoorganizada . Su diseño arquitectónico consiste en un espacio de coordenadas cartesianas multidimensional virtual , un tipo de red superpuesta , sobre un multitoro . Este espacio de coordenadas n -dimensional es una dirección lógica virtual , completamente independiente de la ubicación física y la conectividad física de los nodos. Los puntos dentro del espacio se identifican con coordenadas. Todo el espacio de coordenadas se particiona dinámicamente entre todos los nodos del sistema, de manera que cada nodo posee al menos una zona distinta dentro del espacio total. ^{[ 1 ]}

Un nodo CAN mantiene una tabla de enrutamiento que almacena la dirección IP y la zona de coordenadas virtuales de cada uno de sus vecinos. Un nodo enruta un mensaje hacia un punto de destino en el espacio de coordenadas. El nodo primero determina qué zona vecina está más cerca del punto de destino y luego busca la dirección IP del nodo de esa zona a través de la tabla de enrutamiento. ^{[ 1 ]}

Para unirse a una CAN, un nodo que se une debe:

1. Encuentra un nodo que ya esté en la red superpuesta.
2. Identificar una zona que pueda dividirse
3. Actualizar las tablas de enrutamiento de los nodos vecinos de la zona recién dividida. ^{[ 1 ]}

Para encontrar un nodo que ya se encuentra en la red superpuesta, se pueden utilizar nodos de arranque para informar al nodo que se une sobre las direcciones IP de los nodos que actualmente se encuentran en la red superpuesta. ^{[ 1 ]}

Después de que el nodo que se une recibe la dirección IP de un nodo que ya está en la CAN, puede intentar identificar una zona para sí mismo. El nodo que se une elige aleatoriamente un punto en el espacio de coordenadas y envía una solicitud de unión, dirigida a dicho punto aleatorio, a una de las direcciones IP recibidas. Los nodos que ya están en la red superpuesta enrutan la solicitud de unión al dispositivo correcto a través de sus tablas de enrutamiento de zona a IP. Una vez que el nodo que administra la zona del punto de destino recibe la solicitud de unión, puede aceptarla dividiendo su zona por la mitad, asignándose la primera mitad y la segunda al nodo que se une. Si no acepta la solicitud de unión, el nodo que se une continúa eligiendo puntos aleatorios en el espacio de coordenadas y enviando solicitudes de unión dirigidas a estos puntos aleatorios hasta que se une correctamente a la red. ^{[ 1 ]}

Una vez completada la división y asignación de zonas, los nodos vecinos se actualizan con las coordenadas de las dos nuevas zonas y las direcciones IP correspondientes. Las tablas de enrutamiento se actualizan y las actualizaciones se propagan por toda la red. ^{[ 1 ]}

Para gestionar la salida de un nodo, el CAN debe

1. identificar un nodo que está saliendo
2. que la zona del nodo saliente se fusione o sea tomada por un nodo vecino
3. Actualizar las tablas de enrutamiento en toda la red. ^{[ 1 ]}

La detección de la salida de un nodo puede realizarse, por ejemplo, mediante mensajes de latido que transmiten periódicamente información de la tabla de enrutamiento entre vecinos. Tras un período predeterminado de silencio por parte de un vecino, este se considera que ha fallado y se le considera un nodo que se está desconectando. ^{[ 1 ]} Alternativamente, un nodo que se desconecta voluntariamente puede transmitir dicho aviso a sus vecinos.

Una vez identificado un nodo saliente, su zona debe fusionarse o tomar el control. Primero, se analiza la zona del nodo saliente para determinar si la zona de un nodo vecino puede fusionarse con la zona del nodo saliente para formar una zona válida. Por ejemplo, una zona en un espacio de coordenadas 2D debe ser cuadrada o rectangular y no puede tener forma de L. La prueba de validación puede recorrer todas las zonas vecinas para determinar si se puede producir una fusión exitosa. Si una de las fusiones potenciales se considera válida, las zonas se fusionan. Si ninguna de las fusiones potenciales se considera válida, el nodo vecino con la zona más pequeña toma el control de la zona del nodo saliente. ^{[ 1 ]} Después de una toma de control, el nodo que toma el control puede intentar periódicamente fusionar sus zonas adicionales controladas con las zonas vecinas respectivas.

Si la fusión se realiza correctamente, las tablas de enrutamiento de los nodos de las zonas vecinas se actualizan para reflejarla. Tras la fusión, la red considerará la subsección de la red superpuesta como una única zona y gestionará todo el enrutamiento desde esta perspectiva. Para efectuar una toma de control, el nodo de toma de control actualiza las tablas de enrutamiento de los nodos de las zonas vecinas, de modo que las solicitudes a cualquiera de las zonas se resuelvan en el nodo de toma de control. Por lo tanto, la red seguirá considerando la subsección de la red superpuesta como dos zonas separadas y gestionará todo el enrutamiento desde esta perspectiva.

Sylvia Ratnasamy , Paul Francis, Mark Handley , Richard Karp , Scott Shenker

• Acorde
• Almacenamiento direccionable por contenido
• Pasteles
• Tapiz