Tapiz (DHT)
Tapestry es una red superpuesta de igual a igual que proporciona una tabla hash distribuida , enrutamiento e infraestructura de multidifusión para aplicaciones distribuidas. [1] El sistema Tapestry peer-to-peer ofrece enrutamiento eficiente, escalable, autorreparable y con reconocimiento de ubicación a recursos cercanos.
La primera generación de aplicaciones peer-to-peer, incluida Napster , Gnutella , tenía limitaciones restrictivas, como un directorio central para Napster y consultas de difusión con alcance para Gnutella, que limitaban la escalabilidad. Para abordar estos problemas, se desarrolló una segunda generación de aplicaciones P2P que incluyen Tapestry, Chord , Pastry y CAN . Estas superposiciones implementan un mecanismo de enrutamiento básico basado en claves. Esto permite el enrutamiento determinista de los mensajes y la adaptación a las fallas de los nodos en la red superpuesta. De las redes nombradas, Pastry está muy cerca de Tapestry, ya que ambas adoptan el mismo algoritmo de enrutamiento de Plaxton et al.
Tapestry es una infraestructura extensible que proporciona ubicación y enrutamiento de objetos descentralizados que se enfocan en la eficiencia y minimizan la latencia de los mensajes. Esto se logra ya que Tapestry construye tablas de enrutamiento óptimas a nivel local desde la inicialización y las mantiene para reducir la extensión del enrutamiento. Además, Tapestry permite determinar la distribución de objetos de acuerdo con las necesidades de una aplicación determinada. De manera similar, Tapestry permite que las aplicaciones implementen multidifusión en la red superpuesta.
A cada nodo se le asigna un ID de nodo único distribuido uniformemente en un gran espacio de identificación. Tapestry usa SHA-1 para producir un espacio de identificación de 160 bits representado por una llave hexadecimal de 40 dígitos. Los GUID de puntos finales específicos de la aplicación se asignan de manera similar identificadores únicos. Los ID de nodo y los GUID se distribuyen aproximadamente de manera uniforme en la red superpuesta y cada nodo almacena varios ID diferentes. A partir de experimentos, se muestra que la eficiencia de Tapestry aumenta con el tamaño de la red, por lo que varias aplicaciones que comparten la misma red superpuesta aumentan la eficiencia. Para diferenciar entre aplicaciones, se utiliza un identificador de aplicación único. Tapestry hace todo lo posible para publicar y enrutar objetos.
Cada identificador se asigna a un nodo en vivo llamado raíz. Si el ID de nodo de un nodo es G, entonces es la raíz; de lo contrario, utilice los ID de nodo y las direcciones IP de la tabla de enrutamiento para encontrar los nodos vecinos. En cada salto, un mensaje se enruta progresivamente más cerca de G mediante el enrutamiento de sufijo incremental. Cada mapa vecino tiene varios niveles donde cada nivel contiene enlaces a nodos que coinciden con una cierta posición de dígito en el ID. La entrada i- ésima primaria en el nivel j- ésimo es el ID y la ubicación del nodo más cercano que comienza con el prefijo (N, j-1) + i. Esto significa que el nivel 1 tiene enlaces a nodos que no tienen nada en común, el nivel 2 tiene el primer dígito en común, etc. Debido a esto, el enrutamiento toma aproximadamentesaltos en una red de tamaño N e ID de base B (hexadecimal: B = 16). Si no se puede encontrar una ID exacta, la tabla de enrutamiento se enrutará al nodo coincidente más cercano. Para la tolerancia a fallas, los nodos mantienen enlaces secundarios de manera que la tabla de enrutamiento tenga un tamaño .
Los participantes de la red pueden publicar objetos enrutando periódicamente un mensaje de publicación hacia el nodo raíz. Cada nodo a lo largo de la ruta almacena un puntero que mapea el objeto. Varios servidores pueden publicar punteros al mismo objeto. Los enlaces redundantes se priorizan por latencia y / o localidad.