Universidade Federal do Paraná
Redes P2P: CHORD
Nuno Manuel Ferreira Gonçalves
Resumo

História

Classificação

Estrutura

Mapeamento de chaves

Roteamento

Pesquisa

Estabilização

Endereçamento

Vantagens/Problemas

Implementações

Referências
História



Criado em 2001
Instituto de Tecnologia de
Massachusetts(MIT)
Investigadores:

Ian Stoica

Robert Morris

David Karger

M. Frans Kaashoek

Hari Balakrishnan
01/09/2010
Nuno Manuel Ferreira Gonçalves -
3
Classificação

Arquitetura de 3ª geração

Modelo Descentralizado e Estruturado

Pesquisa através de DHT
01/09/2010
Nuno Manuel Ferreira Gonçalves -
4
Estrutura




Anel – direcionado
sentido horário com ID's
de m bits usado tanto
para os nodos como para
as chaves.
SHA-1 - Função de
HASH(Secure Hash
Standart)
Nó ID = SHA-1(endereço
IP)
Chave ID = SHA-1(chave)
01/09/2010
Nuno Manuel Ferreira Gonçalves -
5
Mapeamento de Chaves

Uma chave é mapeada para o primeiro
nodo cujo ID é igual ou superior ao da
chave.


Cada nó é responsável por um conjunto de
chaves(variável)
As chaves devem ser re-distribuídas após uma
entrada ou saída do sistema.
01/09/2010
Nuno Manuel Ferreira Gonçalves -
6
Roteamento

Finger table – contém m entradas. Definidas através
da função (n+2k-1)mod 2m, 1≤k≤m
01/09/2010
Nuno Manuel Ferreira Gonçalves -
7
Pesquisa Simples
01/09/2010
Nuno Manuel Ferreira Gonçalves -
8
Pesquisa Escalável
01/09/2010
Nuno Manuel Ferreira Gonçalves -
9
Pesquisa Escalável

O(log N) – N é o número de nodos
01/09/2010
Nuno Manuel Ferreira Gonçalves -
10
Estabilização


Quando um nó
entra na rede
somente corrige o
seu sucessor.
Executa a função
stabilize() e a
função fix_fingers()
periodicamente.
Somente O(1/N)
das chaves são
mudadas para
outra localização.
01/09/2010
Nuno Manuel Ferreira Gonçalves 
11
Entrada na rede

Entrada na rede através de um nodo
conhecido
01/09/2010
Nuno Manuel Ferreira Gonçalves -
12
Endereçamento


Não disponibilizada informação sobre como
ultrapassar barreiras de
endereçamento/protecção.
Paper original somente assume que a
comunicação na rede física é simétrica e
transitiva.
01/09/2010
Nuno Manuel Ferreira Gonçalves -
13
Principais vantagens

Balanceamento de carga

Descentralizado

Escalável

Alta disponibilidade

Simples

Boa performance
01/09/2010
Nuno Manuel Ferreira Gonçalves -
14
Problemas

Pesquisa no Chord não atende apropriamente:

Semântica mais complexa

Meta-informação

Buscas incompletas

Erros léxicos
Ex: Se for armazenado o video “o meu pé de meia” e a
procura for por “o meu pé” a pesquisa falha.

Possíveis problemas de segmentação do anel

Somente trata de chaves e ID's
01/09/2010
Nuno Manuel Ferreira Gonçalves -
15
Implementações

P2P XWIKI

Macedon (C++).

i3/Chord (C).

P2 (A custom declarative language).

The Circle (Python).

Open Chord (Java).

Overlay Weaver (Java).

nchord (C#)

chordjerl (Erlang)
01/09/2010
Nuno Manuel Ferreira Gonçalves -
16
Referências

Ion Stoica, Robert Morris, David Karger, M. Frans
Kaashoek, and Hari Balakrishnan. Chord: A scalable
peer-to-peer lookup service for internet applications.
In Proc. ACM SIGCOMM 2001, August 2001. An early
version appeared as LCS TR-819 available at
http://www.pdos.lcs.mit.edu/chord/papers.

http://pdos.csail.mit.edu/chord/

http://www.itl.nist.gov/fipspubs/fip180-1.htm(SHA-1)

Ion Stoica, Robert Morris, David Liben-Nowell, David R.
Karger, M. Frans Kaashoek, Frank Dabek, Hari Balakrishnan,
Chord: A Scalable Peer-to-peer Lookup Protocol for Internet
Applications. IEEE/ACM Transactions on Networking,
February 2003
01/09/2010
Nuno Manuel Ferreira Gonçalves -
17
Perguntas?
01/09/2010
Nuno Manuel Ferreira Gonçalves -
18