MO818/MC953 Tópicos Especiais em Redes de Computadores:
"Roteamento em redes Peer-to-Peer" - 1º Sem 2007

Prof. Célio Guimarães IC - Unicamp

Atualizado em: 06 Junho 2007

Próximos Seminários

Sistemas híbridos: busca por palavras chaves via DHT:
  1. Freenet: freenet.pd     Diego 28 Maio
  2. li-feasibility-2003
  3. The case for hybrid...(2004) Loo et al Diego 6 Junho
  4. Semantic Social Overlay Networks     Fernando 13 Junho
  5. Hybrid global-local.. (2004) esearch     Christian
  6. Gossip based search ...2006 Zaharia & Keshav     Marcelo 18 Junho
  7. Arpeggio-2005       Douglas 20 Junho
  8. Continuação do Gnutella estruturado (2005): Myths about structured and unstructured   Mauricio
Sistema DHT baseado em rede DeBruijn: De Bruijn - Koorde     Sérgio 25 Junho
Pastry otimizado para seleção de vizinhos usando localidade: MS Pastry     Vitor 27 Junho

Bibliografia

Artigos e tutoriais (surveys) publicados na Internet e disponibilizados nas diversas pastas do diretório http://www.ic.unicamp.br/~celio/peer2peer/.
Dois tutoriais abrangentes: Risson & Moors: redes peer-to-peer, Li & Wu: Searching Techniques in Peer-to-Peer Networks e Barabasi: redes complexas (este último sob o ponto de vista da Física).

Programa da disciplina:

(*) Artigos complexos: as idéias básicas serão apresentadas em aula.

Avaliação

  1. Duas provas de conhecimentos gerais após ~1/3 e 2/3 das aulas.
  2. Um ou dois seminários aprofundados / aluno
  3. Cerca de duas listas de exercícios

Tópicos iniciais para Seminários:

Obs: deverão ser apresentados na ordem indicada, exceto Freenet que é independente dos demais.

  1. kalogeraki-local-search.pdf     Douglas 23-04
  2. search&replic-lv.pdf     Suzete 25-04
  3. making-gnutella-like-scalable-Chawatte
  4. gnutella-structured-castro.pdf    Mauricio 02-05
  5. kumar-scalableqr2005.pdf Marcelo
  6. Freenet: freenet.pd     Diego
    mais: freenet_small.pdf
  7. Superpeers:                     Fernando
  8. De Bruijn - Koorde

Exercicios

  1. Re-escreva o procedimento n.join(n') de Chord (p. 23)de forma a agilizar a reconstrução do anel quando um nó n entra na rede, satisfazendo:
  2. O número esperado de nós num intervalo  I  qualquer do anel Chord é igual a (Balls into bins):  N* | I | /2m onde m é o número de bits da função de hashing utilizada. O comprimento do intervalo coberto pela entrada i da finger table de um nó qualquer é igual a 2 i-1 e o número esperado de nós nesse intervalo é maior que 0 se e somente se:
     N*2i-1/2m  >=1 
    ou seja,  i>= m+1-log N
    
    Isto mostra que para i < m + 1 - log N espera-se que as entradas em finger[i] apontem para o sucessor do nó no anel, (uma análise semelhante, usando Balls into bins mostra que para i < m+1- 2log N as entradas em finger[i] apontam para o sucessor do nó com alta probabilidade, ou seja, com alta probabilidade apenas 2logN entradas de uma finger table não apontam para o sucessor do nó). Estes argumentos nos dão uma boa indicação de como agilizar o procedimento fix-fingers() usando o ponteiro circular next.
    Re-escreva fix_fingers() levando estas dicas em consideração.

  3. Prove a asserção acima, "com alta probabilidade se i < m+1- 2log N as entradas em finger[i] apontam para o sucessor do nó corrente"
    Sugestão: em aula foi demonstrado que "a probabilidade de 1 ou mais nós estarem localizados num intervalo de comprimento 2m/N2 a partir de um nó qualquer, é <= 1/N" usando argumentos de "Balls into bins", ou seja, se N pontos são escolhidos aleatoriamente no intervalo 0 - 2m - 1, a probabilidade de 1 ou mais pontos cairem num intervalo qualquer I de comprimento 2m / N2 é menor ou igual a 1/N