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

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

Bibliografia

Programa da disciplina:

• Introdução a redes Peer-to-Peer: histórico, características básicas; o conceito de "overlay network"; taxonomia básica: redes "não estruturadas" e "redes estruturadas". Noções de busca e roteamento. O conceito de "hashing consistente".
• Propriedades elementares de grafos conexos: grau, diâmetro, caminho médio, bipartição, etc. Os limites de Moore.
• Topologias de redes determinísticas para processamento paralelo: hipercubos, butterflies, grafos "shuffle exchange", grafos de DeBruijn: grau, diâmetro, caminho médio, (Ref: F. T. Leighton, "introduction to Parallel Algorithms and Architectures", Morgan Kaufmann, 1992)(*);
• Modelagem de redes reais complexas: topologia, diâmetro, clusterização, características dinâmicas, resistências a falhas/ataques. Características básicas das "redes aleatórias" do modelo de Erdös-Rényi.
  Dois trabalhos seminais sobre redes complexas: o modelo do "mundo pequeno" (small world) de Watts e Strogatz e o modelo "livre de escala" (scale free) de Barabasi
  Exemplos e características de redes complexas do mundo real de diferentes áreas da ciência: física, biologia, ciências sociais, ciências naturais, a rede mundial WWW, a Internet, etc.
  Outro trabalho seminal é o modelo de redes "small world" de Kleinberg(*)
• As notações matemáticas O(), o(), Θ(), Ω(), ω();
• Modelos probabilisticos: noção de eventos com "alta probabilidade". Os limites de Chernoff; aplicações ao problema de "balls into bins"(*). A extensão "ovo de Colombo" ao problema "balls into bins": "power of two"(*).
• Algoritmos de roteamento em redes não estruturadas. Estudo de casos: Gnutella, mais Gnutella, Melhorias propostas aos algoritmos básicos de roteamento de Gnutella; Freenet.
• As redes clássicas estruturadas: Chord, CAN, Pastry, Tapestry, Kademlia, Ulysses
• Redes estruturadas baseadas nos grafos de DeBruijn:
  • Koorde,
  • o modelo "contínuo-discreto" de Wider-Naor
  • análise matemática(*) mostrando as vantagens de redes baseadas em grafos de DeBruijn sobre Chord, CAN, Butterflies,etc
• Redes peer-to-peer híbridas
• Redes não determinísticas: skip graph, Skip Net e variantes.
• Redes hierárquicas.
• Replicação e balanceamento de carga em redes peer-to-peer.

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:

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:
   • introduza novas mensagens (procedimentos remotos) ou modifique os existentes, se preciso, porém
   • (óbvio)apenas o próprio nó pode alterar os seus links successor e predecessor,
   • conte quantas mensagens são enviadas como consequencia dos novos procedimentos e verifique se correspondem ao mínimo necessário.
2. O número esperado de nós num intervalo  I  qualquer do anel Chord é igual a (Balls into bins):  N* | I | /2^m 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 2^m/N² 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 - 2^m - 1, a probabilidade de 1 ou mais pontos cairem num intervalo qualquer I de comprimento 2^m / N² é menor ou igual a 1/N