Tapestry DHT
Tapestry DHT[editar]
Es una red de superposición P2P que proporciona DHT para aplicaciones distribuidas.[1]
Es un sistema escalable, tolerante de fallos y descentralizado, con una infraestructura adaptable de localización y enrutamiento.
Al ser descentralizado emplea una jerarquía virtual con referencias de ubicación en caché.
Breve Historia[editar]
Tapestry fue creado en el año 2000 como un informe técnico por un grupo de desarrolladores de la universidad de Berkeley, en california.
En 2004 fue publicado como artículo de una revista.
Muchos proyectos de seguimiento realizados en tapestry. Por ejemplo, es la capa de red de OceanStore.
Usos Potenciales[editar]
Tapestry proporciona una red de enrutamiento superpuesta que es estable bajo una gran variedad de estados de la red, consiguiendo una eficiencia óptima. Por ello, proporciona una infraestructura ideal para aplicaciones distribuidas.
Algunas aplicaciones basadas en Tapestry son:
- Spamwatch: es una implementación de un filtro de spam descentralizado.
- Mnemosyne: es un sistema de archivos esteganográfico (un método para ocultar datos).
- Bayeux: es una aplicación de multidifusión autoorganizada.
Enrutamiento y localización[editar]
El espacio de nombres de nodos y objetos es de 160 bits, 280 nombres, usando la función hash SHA-1. Cada objeto tiene una o más raíces.
Eligiendo la raíz.
, se establece a través de una función de mapeo dinámico.
Con la función anterior se intenta enrutar a este nodo sin saber si existe (que debería de ser la raíz). Si existe se convierte en la raíz.
De otra manera, si se encuentra una entrada nula, se elige la siguiente entrada de puntero no nulo o una entrada secundaria.
Si el nodo actual es solo un puntero no nulo, se elige como raíz.
Para realizar una inserción:
El nuevo nodo envía un mensaje de unión a un sustituto.
Se establecen los punteros desde los nodos sustitutos hasta el nodo nuevo.
Se notifica a los nodos que deben saberlo.
Se crean las tablas de enrutamiento y se notifica a otros nodos.
Eliminar un nodo[editar]
El nodo que se va a eliminar notifica a sus vecinos lejanos de que ya no los está apuntando.
A los nodos cercanos también los notifica y propone al menos un reemplazo.
El nodo que va a ser eliminado publica todos los objetos que almacena.
Los objetos que tuvieran este nodo como raíz obtienen nuevas raíces.
Enrutamiento mediante sufijos[editar]
Siempre se enruta por el nodo que esté más cerca del objetivo.
En el salto (x), se llega al nodo más cercano, salto (x).
Salto(x) comparte la longitud de x dígitos con el sufijo del nodo destino.
Por ejemplo, el nodo 7543 llega al nodo 1849 a través de 7543 – 2639 – 4549 –9849 – 1849.
Otro ejemplo, el nodo 5324 llega al nodo 0629 a través de 5324 – 2349 – 1429 – 7629 – 0629.
No se muestran todos los nodos y enlaces.
El objeto raíz[editar]
El objeto raíz es el encargado de almacenar la ubicación del objeto.
Las rutas de publicación y enrutamiento se pasan incrementalmente a la raíz.
Propiedades[editar]
Nodo responsable de los objetos que tienen el mismo id.
Es muy improbable que encuentre ese nodo para cada objeto.
Este nodo también es responsable de los objetos cercanos.
Publicación de objetos[editar]
Los nodos responsables solo almacenan punteros. Existen varias copias del objeto, y cada copia debe publicarse.
Los punteros se guardan en caché a lo largo de la ruta de publicación.
Las consultas están dirigidas hacia el nodo responsable. Las consultas para el mismo objeto van a los mismos nodos.
Tapestry se centra en el almacenamiento de objetos.
Dos copias del objeto “.torrent” con ID 4377 creadas en AA93 y 4228.
AA93 y 4228 publican objeto “.torrent”, los mensajes van enrutados a 4377.
La ruta de publicación de mensajes crea punteros de ubicación en el camino.
Cualquier consulta posterior puede usar estos punteros y la consulta será más rápida.
Para ello se deben mantener actualizados los punteros de ubicación.
Enrutamiento tolerante a errores[editar]
Tapestry mantiene la malla conectada con mensajes keep-alive.
Para ello utiliza tiempos de espera TCP y mensajes UDP, requiere información adicional de estado en cada nodo.
En la tabla de enrutamiento, Tapestry tiene nodos vecinos de respaldo. Para cada entrada tiene dos nodos vecinos de respaldo. Si el primero falla usa el secundario.
Funciona bien para fallos no relacionados. Cuando el nodo detecta un nodo fallido, lo marca como no válido.
La mayoría de los fallos de conexión duran poco tiempo. Hay un periodo de segunda oportunidad, durante el cual un nodo inválido puede regresar a la ruta anterior y vuelve a ser válida de nuevo.
Si el nodo inválido no regresa a la ruta, se propone un nodo vecino de respaldo.
Ubicación tolerante a errores[editar]
Un nodo responsable es un único punto de fallo.
La solución consiste en asignar múltiples raíces por objeto.
-Añadir un “salt” al nombre del objeto y un hash.
Este proceso hace que los datos estén más disponibles, incluso si la red esta particionada.
Con la asignación de múltiples raíces la disponibilidad es de:
P=1-(1/2)S.
Depende de la partición.
Estos dos mecanismos garantizan la tolerancia a fallos en la mayoría de los casos.
Enrutamiento sustituto[editar]
Cuando no hay una entrada que coincida con la tabla de rutas vecina para reenviar un mensaje, el nodo selecciona la siguiente entrada de la tabla de su vecino.
Si esa entrada tampoco existe se prueba con la siguiente y así sucesivamente.
La idea consiste en que, si los enlaces perdidos se seleccionan determinísticamente, cualquier mensaje para esa id terminara en el mismo nodo.
Este nodo es el sustituto.
Si se unen nuevos nodos, el nodo sustituto puede cambiar. Un nodo nuevo es vecino del sustituto.
Ejemplo:
El nodo 2716 busca el 4666.
2716 – 4233 – 4899 – 4860
En el nivel 1 el dígito 4 coincide. En el nivel 2 el 6 no existe y pasa al siguiente enlace, el 8.
En el nivel 3 coincide el 6, pero el nodo 4860 no tiene vecinos de nivel 6.
Rendimiento[editar]
Mensajes enrutados en O(logb N) saltos.
En cada paso se resuelve un dígito de la id.
N es el tamaño del espacio de nombres.
El enrutamiento sustituto agrega un bit a esto, pero no significativamente.
Referencias[editar]
Enlaces externos[editar]
https://cs.gmu.edu/~setia/cs699/lecture2.pdf
| Control de autoridades |
|
|---|
Datos: Q56324129