# Novas Tecnologias de Internet/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)

## Mecanismo de busca do Plaxton

Este mecanismo permite um cliente localizar e enviar mensagens para um objeto encontrado num servidor. Isto é realizado pelo servidor anunciando que ele possui o objeto. O servidor faz isto “roteando” a mensagem para o nó raiz, um nó único na rede que é usado para guardar a raiz do objeto. De acordo com a finalidade crítica do nó raiz e sendo o único nó deste tipo faz com que haja no sistema um ponto único de falha. A publicação (publishing) é o processo no qual uma mensagem é enviada ao nó raiz e a cada nó ao longo do caminho entre os locais onde se encontram armazenados o Object-ID (O) e Server-ID (S).
Por outro lado um local de consulta permite o cliente enviar mensagem para objetos. Como as mensagens percorrem um determinado caminho, então é verificado o nó por onde a mensagem passar. A mensagem é redirecionada ao servidor contendo o objeto se a mensagem encontrar um nó que possua a informação de localização para o objeto procurado. Senão, a mensagem é encaminhada um passo mais próximo da raiz. A informação de localização ou mapeamento (mapping) para um objeto é a garantia de que este objeto será achado uma vez que a mensagem atinja a raiz. O mecanismo de roteamento do Plaxton escolhe nós raiz usando um algoritmo determinístico e globalmente consistente.

## O mecanismo de roteamento e localização do tapestry

As características principais do mecanismo Tapestry são baseadas fortemente no mecanismo Plaxton. Como o roteamento Plaxton, todos os nós da rede possuem um mapa de vizinhança com múltiplos níveis de roteamento e cada entrada descreve a localização do seu vizinho mais próximo. O mecanismo de localização do Tapestry é similar o do Plaxton.
No método Plaxton cada nó armazena apenas informação de localização: <Object-ID (O), Server (S)> armazena o objeto mais próximo do nó. O Tapestry por outro lado armazena a informação de localização de todos os objetos. Isto tem um efeito de aumento da flexibilidade semântica.
A seção seguinte explica como o mecanismo Tapestry detecta, opera e se recupera de falhas (faults) que afetam o roteamento e a funcionalidade da localização.
* Em cada nó ao longo do caminho de
publicação armazena o mesmo mapeamento
* Quando um nó tem vários mapeamentos para
o mesmo GUID, ele ordena pela distância da rede

## Fault Handling

Uma decisão desenvolvida pelo Tapestry foi que componentes que lidam com o problema de falha de adaptatividade usando de um estado suave para manter armazenado um conteúdo para uma recuperação mais tranqüila, ao invés de um estado pesado que pudesse necessitar de providências de segurança. O conteúdo armazenado é atualizado através de mensagens regulares. Ao invés de tratar as falhas como um caso especial, o Tapestry lida como se elas fossem partes de uma operação normal.

### Fault-tolerant Routing

Tabelas corrompidas de mapas de vizinhança, falhas de servidores e de “links” são tipos de faltas esperadas que necessitam ser cuidadas pela rede. O sistema deveria, idealmente, detectar essas faltas rapidamente, operá-las por baixo e recuperar o estado do roteador quando elas forem corrigidas. O Tapestry confia no “timeout” do TCP para detectar falhas nos “links” e servidores durante uma operação normal. Cada nó da rede contém ponteiros de retorno que enviam pacotes UDP´s regularmente para o vizinho mais próximo. Isto é feito para garantir que o roteamento pode ser realizado através daquele nó. Tabelas corrompidas podem ser facilmente e rapidamente detectadas usando se uma mensagem para verificar a ID de cada nó que ela passar. O mapa de vizinhança de um nó armazena dois vizinhos de “backup” em resposta ao vizinho mais próximo. Se o vizinho primário de um nó falhar então o nó utiliza um dos seus vizinhos de “backup” no lugar. Quando um nó falha, ele é geralmente encontrado e reparado rapidamente. Ao invés do nó remover o nó falhado do seu mapa de vizinhança este nó é indicado como inválido. O roteamento é então realizado através de uma rota alternativa até que o nó seja restaurado. Entretanto o nó permanecerá como inválido na rede apenas por um período fixo de tempo para dar uma chance de ele ser reparado. Mensagens de uma rota falhada são verificadas para observar o momento em que esta rota foi reparada. Se após um tempo específico o reparo do nó não for realizado então o nó é removido do mapa de vizinhança. Este processo é realizado a fim de que se possa evitar uma cara reinserção dos nós recuperados.

### Fault-tolerant Location

No mecanismo do Plaxton o nó raiz é vulnerável no sentido de que ele se torna um ponto único de falha. No Tapestry múltiplos nós raiz são usados. Cada objeto terá agora várias raízes atribuídas a ele. Durante o processo de publicação (publishing) descrito anteriormente os nós raízes são usados para inserir informações de localização nos nós. Os objetos armazenados em intervalos regulares têm suas informações de localização republicadas por servidores de armazenamento.

## Surrogate Routing

O Tapestry utiliza um mecanismo de roteamento substituto, que é na realidade apenas um algoritmo distribuído que incrementalmente computa um único nó raiz. Este algoritmo é determinístico, escalável, e pode chegar a resultados consistentes de qualquer ponto na rede. O roteamento substituto opera escolhendo um objeto do nó raiz que tem o mesmo nome da sua ID. Isto é, entretanto, improvável devido à natureza escassa do “namespace” dos nós. O Tapestry funciona como se o nó não existisse tentando “rotear” para ele. Uma rota para um identificador não existente irá encontrar entradas de vizinhos vazia em várias posições ao longo do percurso. Aqui, o algoritmo seleciona um “link” existente que aja como uma alternativa a um link desejado. Esta seleção é feita através de uma seleção determinística entre ponteiros de vizinhos existentes. O roteamento termina uma vez que um mapa de vizinhança foi alcançado onde a única entrada não nula pertence ao nó atual. Aquele nó é então designado como uma raiz substituta para o objeto.
* Esta página é somente um esboço. Ampliando-a você ajudará a melhorar a Wikiversidade.

## Bibliografia e referências

* - www.edeyson.com.br
* - www.gta.ufrj.br
* -www.gta.ufrj.br/ftp/gta/TechReports