Tapestry es una red superpuesta peer to peer que proporciona una tabla hash distribuida , enrutamiento e infraestructura de multidifusión para aplicaciones distribuidas. [1] El sistema peer to peer Tapestry ofrece enrutamiento eficiente, escalable, autorreparable y consciente de la ubicación a recursos cercanos.
La primera generación de aplicaciones peer-to-peer, incluyendo Napster y 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 incluía Tapestry, Chord , Pastry y CAN . Estas superposiciones implementan un mecanismo de enrutamiento básico basado en clave. Esto permite el enrutamiento determinista de mensajes y la adaptación a fallas de nodos en la red superpuesta. De las redes nombradas, Pastry es muy similar a 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, centrándose en la eficiencia y minimizando la latencia de los mensajes. Esto se logra porque Tapestry construye tablas de enrutamiento óptimas localmente desde la inicialización y las mantiene para reducir el estiramiento del enrutamiento. Además, Tapestry permite determinar la distribución de objetos según 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 identificador de nodo único distribuido de manera uniforme en un gran espacio de identificadores. Tapestry utiliza SHA-1 para producir un espacio de identificadores de 160 bits representado por una clave hexadecimal de 40 dígitos. Los GUID de los puntos finales específicos de la aplicación también reciben identificadores únicos asignados. Los identificadores de nodo y los GUID se distribuyen de manera aproximadamente uniforme en la red superpuesta y cada nodo almacena varios identificadores diferentes. Los experimentos demuestran que la eficiencia de Tapestry aumenta con el tamaño de la red, por lo que el hecho de que varias aplicaciones compartan la misma red superpuesta aumenta la eficiencia. Para diferenciar entre aplicaciones, se utiliza un identificador de aplicación único. Tapestry utiliza el máximo esfuerzo para publicar y enrutar objetos.
Cada identificador se asigna a un nodo activo llamado raíz. Si el nodeID de un nodo es G , entonces es la raíz; de lo contrario, se utilizan los nodeID 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 enrutamiento de sufijo incremental. Cada mapa de vecinos tiene múltiples niveles donde cada nivel contiene enlaces a nodos que coinciden hasta una determinada posición de dígito en el ID. La entrada i primaria en el nivel j 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 aproximadamente saltos en una red de tamaño N e ID de base B (hexadecimal: B=16). Si no se puede encontrar un ID exacto, la tabla de enrutamiento enrutará al nodo coincidente más cercano. Para la tolerancia a fallas, los nodos mantienen enlaces secundarios de modo que la tabla de enrutamiento tenga 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 asigna el objeto. Varios servidores pueden publicar punteros al mismo objeto. Los enlaces redundantes se priorizan por latencia o localidad.
Los objetos se localizan enrutando un mensaje hacia la raíz del objeto. Cada nodo a lo largo de la ruta verifica la asignación y redirige la solicitud de manera adecuada. El efecto del enrutamiento es la convergencia de rutas cercanas que se dirigen al mismo destino.
El nuevo nodo se convierte en la raíz de su ID de nodo. La raíz encuentra la longitud del prefijo más largo de la ID que comparte. Luego envía un mensaje de multidifusión que llega a todos los nodos existentes que comparten el mismo prefijo. Luego, estos nodos agregan el nuevo nodo a sus tablas de enrutamiento. El nuevo nodo puede asumir el rol de raíz para algunos de los objetos de la raíz. Los nodos se comunicarán con el nuevo nodo para proporcionar una lista de vecinos temporal. Luego, el nuevo nodo realiza una búsqueda iterativa del vecino más cercano para completar todos los niveles en su tabla de enrutamiento.
Para abandonar la red, un nodo transmite su intención de abandonarla y transmite el nodo de reemplazo para cada nivel en las tablas de enrutamiento de los otros nodos. Los objetos en el nodo que abandona se redistribuyen o se reponen a partir de copias redundantes.
La falla inesperada de un nodo se maneja mediante redundancia en la red y punteros de respaldo para restablecer los enlaces dañados.
Tapestry proporciona una red de enrutamiento superpuesta que es estable en diversas condiciones de red. Esto proporciona una infraestructura ideal para aplicaciones y servicios distribuidos. Las aplicaciones basadas en Tapestry son:
Tapestry fue desarrollado por Ben Y. Zhao, Ling Huang, Jeremy Stribling, Sean C. Rhea, Anthony D. Joseph y John D. Kubiatowicz.
