Artigo-Chord Protocol

Più simili a questo

Redes de Computadores

da Alan Manzato

Arquitetura e Redes

da MIKAEL GARCIA DA COSTA

Património Cultural

da Henrique Branco

Middleware2

da Yuji Negoro

Desenvolvimento

Análise Mais Realista

O trabalho [16] mostra que uma rede volátil pode funcionar num estado "quase estável" se a rotina de estabilização é executada com certa frequência. Nesse caso, os lookups são rápidos e corretos

Operações Dinâmicas e Falhas

Saída Voluntária de um Nó

O nó que sai pode comunicar seu sucessor e seu predecessor e distribuir suas chaves de forma controlada.

Falhas e Replicação

Mesmo em caso de falha, o tempo para encontrar um sucessor é O(log N)

De qualquer modo, há uma alta probabilidade de um lookup encontrar o nó certo ou um muito próximo dele em caso de falha

Para utilizar esta nova tabela, os pseudo-códigos apresentados precisam ser pouco modificados

O valor r é escolhido estatisticamente (qual a chance de uma falha simultânea que queremos). r = U(log N)

Chord mantém também uma lista de tamanho r contendo todos os r sucessores de um nó n. Para haver falha, todos o r sucessores de n devem falhar simultaneamente.

Em caso de falha, a informação sobre um sucessor pode ser inválida (ver exemplo considerando a Figura 4)

Impacto da Chegada de Nós Sobre as Buscas

Só haveria problema se um grande número de nós fosse inserido entre 2 outros de uma vez.

Se N cresce, após a estabilização o acréscimo de N não muda os passos de lookup (a Finger Table tem no máximo m entradas)

Correção: 1 de 3 casos

3 - As chave estão imprecisas porque ainda não migraram para o servidor correto: um lookup pode falhar. O lookup pode ser repetido após algum tempo pela camada de software que usa o Chord. A espera é curta.

2 - Finger Table desatualizada: um lookup ainda é correto, mas mais lento

1 - Informação razoavelmente atualizada: um lookup encontra corretamente o sucessor

Chegada de Nós e Estabilidade

A operação do protocolo leva a formação de um círculo lógico - o Chord Ring

Exemplo página 23, abaixo da Figura 6

Pseudo-código na Figura 6

Protocolo de estabilização - cada nó executa periodicamente para atualizar as Finger Tables e informações sobre o sucessor

Localização escalável da Chave

O número de nós que devem ser contactados para encontrar um sucessor com a Chave buscada numa rede de N nós é O(log N)

Pseudo-código na Figura 5

Mesmo a Finger Table não tem informação para determinar todos os nós, mas apenas um número O(log N)

Cada nó mantém pouca informação na Finger Table

A i-ésima entrada contém a identidade do primeiro nó s sucessor de n por pelo menos 2(i-1) no Chrod Ring - s = sucessor(n+2(i-1)) - explicação completa no texto, exemplo na Fig. 4(a)

Cada nó n mantém uma tabela de roteamento com até m entradas - finger table

m - número de bits do identificador de chaves/nós

Não importante para a correção - cada Nó precisa saber apenas seu sucessor

Apresenta informação adicional de roteamento

Localização simples da Chave

Número de mensagens é linear

Pseudo-código na Fig. 3(a)

Queries são repassadas pelo anel até chegarem ao Nó certo ou falharem

Um Nó só precisa saber seu sucessor

Buscas no Chord Ring precisam de pouco estado por Nó

Relacionar Chaves com Nós

Quando um Nó X deixa a rede, suas Chaves são repassadas a sucessor(X)

Quando um Nó X entra na rede, algumas Chaves mantidas por sucessor(X) são repassadas a X

Círculo de IDs = Chord Ring

Este Nó é o sucessor de K - sucessor(K)

A Chave K é relacionada ao 1o. Nó cujo ID seja igual ou maior que K

Ordena IDs no "Círculo de IDs" módulo 2**m (fig. 2)

m deve ser grande o suficiente para não ocorrer colisões

ID Key = Hash(Key)

ID Node = Hash(End. IP)

Cada Nó/Chave possui um identificador de m-bits produzido com SHA-1

Protocolo

Um Nó não precisa saber sobre todos os outros - escalabilidade

Quando um Nó entra ou sai da rede, só O(1/N) das Chaves são movidas - mínimo para manter a rede balanceada

Alta probabilidade de carga balanceada pela função hash

Hash consistente [12] [14]

Mapeia Chaves para os Nós que as mantém

Cálculo distribuído rápido de função hash

Produto

Chord facilita funções da aplicação

Outras: caching, nomes user-friendly, etc.

Replicação: a aplicação mantém informação sob 2 Chaves Chord derivadas de identificadores dos níveis de aplicação dos dados

Autenticação: a aplicação mantém informações com uma chave Chord derivada de um hash criptografado dos dados

P. ex. a aplicação pode mover objetos para novos hosts quando um novo Nó entra na rede

2 - Chord informa a aplicação sobre alteração do conjunto de chaves que o Nó está mantendo

1 - função lookup(Key) devolve End. IP do Host que mantém Key

2 formas de interação:

Chord é uma biblioteca lincada na aplicação que usa o protocolo

Aplicações

CAN

Um Nó contém O9d) estados - custo O(d.N**(1/d))

Tabela hash distribuída (mapeia chaves para valores)

Espaço de coordenadas cartesianas de d-dimensões

Oceanstore / Plaxton

Subtopic

Uma query não viaja mais que a distância do Nó onde a Chave está

Distribuição de chaves balanceada

Query viaja por log(No. saltos)

GLOBE

Objetos divididos por vários servidores Root físicos (hash)

Trabalha com altas cargas no nó raiz lógico

Usa ponteiros para caches como atalhos

Informações sobre os objetos ficam nas folhas

Árvore estática da Internet

Organiza a Internet como uma hierarquia de domínios

Administrativos

Topológicos

Geográficos

Mapeia ID de objetos para localização de objetos

Serviço de localização em WAN

Archival Intermemory [4]

Mapeia endereços lógicos para as máquinas que mantém objetos

Árvore de busca montada offline

Ohaha [20]

Possui as fraquezas do Freenet

Consulta informações de roteamento como Freenet

Função hash mapeia documentos para os nós que os mantém

Freenet [5] [6]

Previne danos/exclusão de objetos

Garantia de anonimato

Lookup ocorre em cópias mantidas em cache

Objetos não são responsabilidade dos seus servidores

Adapta-se automaticamente a mudanças na rede

Simétrico (cada nó é balanceado com os outros)

Sistema descentralizado

DNS baseado em Chord

Também encontra objetos não ligados a máquinas específicas

Não impõem padrões de nomenclatura

Mantém informação de roteamento correta automaticamente

Servidores não são necessários

Chave ~ hash(Host name) [7]

DNS

Lookup: nomes de hosts são Chaves; Endereços IP são valores

Especializado em encontrar nomes de hosts e serviços

Nomes de hosts devem refletir limites administrativos

Gerência manual da informação de roteamento

Usa servidores Root

Chord Protocol

CFS

Chord localiza os blocos

Arquivos armazenados numa rede P2P

Chord File System

Implementação

Mapeia Nós num espaço undimensional virtual

Algoritmo de roteamento similar ao Grid [15]

Armazena e acha valores no Nó mapeado pela Chave

Dabek [9]

Hashing

[12]

Carga balanceada

Chaves associadas a Nós

Lookup

Busca correta e robusta mesmo se a informação de roteamento esteja parcialmente incorreta

O(log N) mensagens

Cada nó se comunica com outros

Roteamento

Algoritmo Dinâmico: a rede se altera com frequência

Tabela de roteamento distribuída

Cada Nó possui informações sobre poucos Nós - O(log N)

Inicialiazação

Total de Chaves / No. de Nós (N)

Características

Flexibilidade de nomes - não há restrições

Disponibilidade - novos Nós e falhas são ajustados automaticamente

Custo de busca O(log N) - barato para redes grandes

Totalmente distribuído

Balanceamento de carga natural

Requisitos

Pelo menos 1 informação de roteamento correta

Desempenho

As alterações da rede dificultam manter dados atualizados, mesmo sobre O(log N) nós!