Tapestry
Henrique Denes Hilgenberg Fernandes
Agenda
•
•
•
•
Introdução
Estado da arte
A API DOLR
Malha de roteamento
– Da perspectiva de um único nó
– Caminho da mensagem
• Localização e publicação de objetos
– Publicação de objeto no Tapestry
– Rotas para objetos em Tapestry
• Algoritmos
• Arquitetura do Tapestry
– Camadas funcionais do nó Tapestry
Introdução
• Tapestry é um protocolo que provê infraestrutura para roteamento em redes P2P
sobrepostas
• Altamente escalável
• Bom para réplicas de objetos
• Provê DOLR (Decentralized Object Location
and Routing)
Estado da arte
• 1as. P2P
– Foco no compartilhamento de arquivos
– Napster (Serviço de diretório centralizado)
– Gnutella
• Totalmente distribuído, escalabilidade limitada
– Freenet
• Projetada para sobreviver à censura
• Gnutella e Freenet não garantem a localização dos
arquivos
Estado da arte
• Gerações posteriores (redes P2P sobrepostas)
– Tapestry
– Chord
– Pastry
– CAN
– Implementam KBR (key-based routing)
– Suportam interfaces de mais alto nível: DHT
A API DOLR
• Cada nó é designado por um nodeID
– Um host pode abrigar mais de um nó
• Pontos de aplicações específicas são chamados GUID
(Globally Unique Identifiers)
• O espaço de endereçamento Tapestry possui 160 bits (40
dígitos hexa)
• NodeID’s e GUID’s podem ser obtidos usando-se hash, por
exemplo, SHA-1
• Nós têm nodeID’s e objetos têm GUID’s
• Cada mensagem tem um identificador específico de
aplicação Aid
– Usado para selecionar o processo que recebe a mensagem,
como se fosse uma porta do TCP
A API DOLR
• A API DOLR possui 4 operações:
– PUBLISHOBJECT(OG, Aid)
• Publica o objeto O no nó local
– UNPUBLISHOBJECT(OG, Aid)
• Tenta remover os mapeamentos de O
– ROUTETOOBJECT(OG, Aid)
• Encaminha mensagem para a localização do objeto com GUID OG
– ROUTETONODE(N, Aid, Exact)
• Encaminha mensagem para aplicação Aid no nó N.
• Exact diz se o destino deve bater exatamente para efetuar a
entrega (não pode ser um surrogate)
• Como o Tapestry tira proveito do tamanho da rede,
sugere-se o uso de uma única rede universal
A malha de roteamento
• O Tapestry mantém tabelas de rotas locais, em
cada nó, chamadas neighbor links
– São ordenados por prefixos
– Roteiam bit a bit (4*** → 42** → 42A* → 42AD)
– Cada nó tem um mapa com múltiplos níveis
A malha de roteamento
(Da perspectiva de um único nó)
A malha de roteamento
(Da perspectiva de um único nó)
• Os links saindo apontam para um prefixo em
comum
• Rotas de maior nível possuem mais dígitos em
comum
• Todos os links juntos formam a tabela de rotas
local
A malha de roteamento
(Caminho da mensagem)
A malha de roteamento
(Caminho da mensagem)
• Mensagem originada em 5230 e com destino
a 42AD
• Se o destino não for encontrado, a mensagem
poderá ser entregue a um nó similar
– Surrogate node
Localização e publicação de objetos
• Um servidor S, armazenando um objeto O
(com GUID OG e raiz OR), periodicamente o
publica via mensagem PUBLISH em direção à
OR
• O que é raiz?
– Se existe um nó com Nid = G, então esse nó é raiz
de G
Publicação de objeto no Tapestry
Publicação de objeto no Tapestry
• Duas cópias de um objeto (4378) são
publicadas para o seu nó raiz (4377)
• Mensagens publish roteiam para a raiz,
deixando um ponteiro para a localização em
cada hop
• Quando houverem réplicas em mais de um
servidor, cada servidor publica sua cópia
Rota para objeto em Tapestry
Rota para objeto em Tapestry
• Vários nós enviam mensagens para 4378, de
diferentes pontos da rede
• As mensagens são roteadas para a raiz de 4378
• Ao atingir o caminho do "publish", as mensagens
são roteadas para a cópia do objeto mais próxima
• Cada nó, no caminho, checa se ele possui um
mapeamento para O
– Caso positivo, encaminha para S
– Caso contrário, encaminha a mensagem em direção à
raiz
Algoritmos
• Inserção de nós
– A inserção de um nó N, começa no surrogate node
do seu ID, S
– S encontra p, maior prefixo compartilhado com
Nid
– S envia uma mensagem Acknowledged Multicast
que chega a todos os nós com o mesmo prefixo p
– Os nós que recebem a mensagem adicionam N às
suas tabelas
Algoritmos
• Remoção de nós:
– Quando um nó deseja deixar o Tapestry, ele avisa
sua intenção a todos os nós que apontam para
ele, junto com um "next hop", em sua
substituição, para cada nível da tabela de
roteamento
Arquitetura do Tapestry
Camadas funcionais do nó Tapestry
• Camada de transporte
– Provê um canal de comunicação entre dois nós
sobrepostos
– Corresponde a camada 4 do modelo OSI
• Neighbor Link
– Estabelece uma conexão com um nó remoto
– Pode prover um canal seguro
– Corresponde a sessão no modelo OSI
• Roteador
– Nessa camada estão a tabela de rotas e os ponteiros
para objetos locais
Referências
• B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph
and J. D. Kubiatowicz, “Tapestry: A Resilient GlobalScale Overlay for Service Deployment”, IEEE Journal on
Selected Areas in Communications, vol. 22, no. 1,
january 2004, pp. 41-53.
• B. Y. Zhao, J. D. Kubiatowicz, and A. D. Joseph,
“Tapestry: An infrastructure for fault-tolerant widearea location and routing,” Univ. California, Berkeley,
CA, Tech. Rep. CSD-01-1141, Apr. 2001.
• K. Hildrum, J. D. Kubiatowicz, S. Rao, and B. Y. Zhao,
“Distributed object location in a dynamic network,” in
Proc. SPAA, Winnipeg, Canada, Aug. 2002, pp. 41–52.