Chord Protocol

Simples

Escalável

Busca de dados distribuídos pelos N nós da rede

Nós entram e deixam a rede frequentemente - o tratamento é simples

Entrada: uma Chave K

Função Hash: mapeia K para um valor

Saída: Nó que mantém K

Valor: Endereço, Documento, Dado

Sem anonimato

Lookup em tempo previsível

Resultado definido: sucesso ou falha

Não faz hierarquias por classes de objetos

Armazena dados (objetos)

Chaves mapeadas para valores

Degrada quando a informação de roteamento está desatualizada

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

Pelo menos 1 informação de roteamento correta

Balanceamento de carga natural

Totalmente distribuído

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

Escalável

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

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

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

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

Tabela de roteamento distribuída

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

Cada nó se comunica com outros

O(log N) mensagens

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

Chaves associadas a Nós

Carga balanceada

[12]

Dabek [9]

Armazena e acha valores no Nó mapeado pela Chave

Algoritmo de roteamento similar ao Grid [15]

Mapeia Nós num espaço undimensional virtual

Chord File System

Arquivos armazenados numa rede P2P

Chord localiza os blocos

Usa servidores Root

Gerência manual da informação de roteamento

Nomes de hosts devem refletir limites administrativos

Especializado em encontrar nomes de hosts e serviços

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

Chave ~ hash(Host name) [7]

Servidores não são necessários

Mantém informação de roteamento correta automaticamente

Não impõem padrões de nomenclatura

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

Sistema descentralizado

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

Adapta-se automaticamente a mudanças na rede

Objetos não são responsabilidade dos seus servidores

Lookup ocorre em cópias mantidas em cache

Garantia de anonimato

Previne danos/exclusão de objetos

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

Consulta informações de roteamento como Freenet

Possui as fraquezas do Freenet

Árvore de busca montada offline

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

Serviço de localização em WAN

Mapeia ID de objetos para localização de objetos

Organiza a Internet como uma hierarquia de domínios

Geográficos

Topológicos

Administrativos

Árvore estática da Internet

Informações sobre os objetos ficam nas folhas

Usa ponteiros para caches como atalhos

Trabalha com altas cargas no nó raiz lógico

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

Query viaja por log(No. saltos)

Distribuição de chaves balanceada

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

Subtopic

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

Tabela hash distribuída (mapeia chaves para valores)

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

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

2 formas de interação:

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

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

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

Chord facilita funções da aplicação

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

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

Outras: caching, nomes user-friendly, etc.

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

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

Hash consistente [12] [14]

Alta probabilidade de carga balanceada pela função hash

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

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

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

ID Node = Hash(End. IP)

ID Key = Hash(Key)

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

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

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

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

Círculo de IDs = Chord Ring

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

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

Buscas no Chord Ring precisam de pouco estado por Nó

Um Nó só precisa saber seu sucessor

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

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

Número de mensagens é linear

Apresenta informação adicional de roteamento

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

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

Cada nó n mantém uma tabela de roteamento com até m entradas - 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ó mantém pouca informação na Finger Table

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

Pseudo-código na Figura 5

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)

Chegada de Nós e Estabilidade

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

Pseudo-código na Figura 6

Exemplo página 23, abaixo da Figura 6

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

Impacto da Chegada de Nós Sobre as Buscas

Correção: 1 de 3 casos

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

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

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.

Desempenho

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)

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

Falhas e Replicação

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

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.

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

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

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

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

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.

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