Tapestry

Tapestry

Usando apenas ligações ponto-a-ponto e recursos descentralizados, o Tapestry é uma infra- estrutura de roteamento e de cobertura de posição que fornece um roteamento independente da localização de mensagens diretamente a uma cópia mais próxima de um objeto ou serviço. O tapestry pode ostentar características como o balanceamento de carga, fault-resilience, robustez, escalabilidade e auto-organização.
Arquitetura de roteamento
Usando a localização Plaxton as metas do mecanismo de roteamento do Tapestry são adaptativas, auto-gerenciáveis e fault-resiliance. A arquitetura de roteamento do Tapestry eficientemente “roteia” requisições mesmo na presença de falhas nos nós ou uma carga alta na rede. Através do uso de aleatoriedade ele realiza o roteamento localmente e carrega a distribuição. O Tapestry vai lidar com os problemas da rede desviando se das rotas com falhas, removendo nós sobrecarregado por um serviço, transparentemente mascarando componentes com falhas e rapidamente adaptando a topologia de comunicação às circunstâncias que dependem dos tipos de problemas encontrados.
Por ter suas rotas fortemente ligadas ao mecanismo Plaxton, é apropriado discutir o que é basicamente o método Plaxton para que se possa entender o mecanismo de roteamento do Tapestry.
Arquitetura de roteamento do Plaxton
O mecanismo de roteamento do Plaxton possui em cada nó mapas de roteamento locais chamados mapas de vizinhança (neighborhood maps) que incrementalmente “roteiam” as mensagens cobertas ao local de destino (destination ID). Cada nó possui um mapa de vizinhaça com múltiplas camadas. Cada camada possui um número de entradas igual à base do ID, onde uma de i entradas de uma das j camadas é a ID e o local mais próximo do nó. Na intenção de achar o próximo nó, procura-se nos n+1 níveis do mapa, e verifica-se a entrada correspondente ao valor do próximo dígito no local de destino. Usando este método de roteamento num “namespace” de tamanho n e usando ID de base b pode-se garantir que em no máximo hops lógicos um nó pode ser achado no sistema, assumindo que cada nó tenha um mapa de vizinhança consistente.
Como todos os mapas de vizinhança em cada nó assumem que a predição de dígitos de cada nó sempre “casa” com o sufixo do nó atual, ele só precisa manter um tamanho constante b de entradas em cada nível da rota:
NeighborMapSize = (entries/map) * (# of maps) = b *


Esse trecho sobre Tapestry foi tirado do link abaixo. Um link muito bom que descreve um visão geral dos algoritmos de implementação DHT, além de diversas seções a respeito de várias áreas da tecnologia e arquitetura Peer-to-Peer (P2P).

http://www.gta.ufrj.br/grad/04_1/p2p/