5 nomeacao

Prévia do material em texto

Nomeação
Recurso
Ponto de 
Acesso
Entidade
Endereço
Nomes Identificadores
‣ Como resolvemos nomes e 
identificadores em endereços?
Resolução de nomes
Roteamento de mensagens
Nomeação 
Simples
Nomeação 
Estruturada
Nomeação 
Baseada em 
Atributos
Broadcasting e 
Multicasting
(Ex. ARP)
Localização Nativa
(Ex. Mobile IP)
DHTs
Abordagens 
Hierárquicas
(Ex. Domínios)
Espaço de Nomes
(Ex. DNS, NFS)
Serviços de 
Diretórios
(Ex. LDAP, AVTree)
(id, endereço) (nome, endereço) (atributo, valor)
DNS
‣ Abordagem decentralizada para resolução de 
nomes estruturados
- Resolução iterativa
- Resolução recursiva
ftp://ftp.cs.vu.nl/pub/globe/index.txt
InetAddress.getByName(“ftp.cs.vu.nl");
Distributed Hash Tables (DHT)
‣ Tabelas Hash Distribuídas
‣ Exemplo: Sistema Chord
Chord
‣ Identificadores são associados aleatoriamente aos nós
‣ Chaves são associadas aleatoriamente a entidades 
(arquivos, processos, etc)
‣ Cada identificador/chave é formado por m bits
- m = 128 ou m = 160 (depende da função de hash)
‣ Uma entidade com chave k é associada ao nó que tenha o 
menor identificador maior ou igual a k (id ≥ k)
- Este nó é denominado sucessor de k e denotado por succ(k)
‣ Como encontrar o endereço do nó 
que contém um recurso identificado 
pela chave k?
‣ Como resolver com eficiência uma chave 
k para um endereço de succ(k)
Primeira Solução
‣ Cada nó p monitora seu sucessor succ(p) e seu predecessor 
pred(p)
‣ Quando p recebe um requisição para resolver a chave k, ele:
- retorna seu próprio endereço p, se pred(p) < k ≤ p
- repassa a requisição para succ(p), se k > p
- repassa a requisição para pred(p), se k ≤ pred(p)
Problema de escalabilidade!
Tabela de Derivação
‣ Cada nó mantém uma tabela de derivação (FT - finger 
table), de no máximo m entradas
‣ Cada registro i dado por
- FT[i] = succ(p+2i-1)
- atalhos para nós sucessores 
- a distância para o atalho aumenta exponencialmente
‣ FT[j] ≤ k ≤ FT [j+1] O(log(N))
m = 5
‣ Custo: manter as tabelas de derivação atualizadas
- chega e saída e nós na rede
- falha de nós
‣ Ações:
- Monitoramento do predecessor
- Envio periódico de requisições