View
11
Download
0
Category
Preview:
Citation preview
8/1/2008
1
Redes Peer to PeerRedes Peer to Peer
Compartilhamento e localização de t údconteúdo
Hubert FonsecaAlgoritmos Distribuídos – PUC‐Rio
Junho de 2008
Redes P2P
Sistemas Sistemas distribuídos capazes de se distribuídos capazes de se organizar em topologias que permitem organizar em topologias que permitem o o
compartilhamento compartilhamento de recursosde recursos
[1] STEPHANOS ANDROUTSELLIS‐THEOTOKIS AND DIOMIDIS SPINELLIS, A Survey of Peer‐to‐Peer Content Distribution Technologies, Athens University of Economics and Business, ACM Computing Surveys, Vol. 36, No. 4, December 2004
8/1/2008
2
Recursos
•• Espaço em Espaço em discodisco
•• ProcessamentoProcessamento
•• BandaBanda
•• ConteúdoConteúdo
Compartilhamento de conteúdo
InserçãoInserçãoL li ãL li ãLocalizaçãoLocalizaçãoLeituraLeituraAtualizaçãoAtualizaçãoDeleçãoDeleçãoControle de versãoControle de versãoControle de versãoControle de versãoGerenciamento de espaço em disco Gerenciamento de espaço em disco Gerenciamento de taxa de transmissãoGerenciamento de taxa de transmissão
8/1/2008
3
Classificação de sistemas
Puramente Puramente descentralizadodescentralizadoTodos os nós têm a mesma função
Parcialmente Parcialmente centralizadocentralizadoAlguns nós assumem funções específicas
HíbridoHíbridoExistem nós específicos mas interação é direta
Redes overlay
• Redes formadas pelas conexões entre os nós
EstruturadasEstruturadasConteúdo depende da localização
NãoNão estruturadasestruturadasNãoNão‐‐estruturadasestruturadasConteúdo não depende da localização
8/1/2008
4
Redes estruturadas
Conteúdo relacionado com l li ãlocalização
Redes estruturadas
Conteúdo dos arquivos (ou ponteiros) são Conteúdo dos arquivos (ou ponteiros) são d d t d l li ãd d t d l li ãdependentes da localizaçãodependentes da localização
Favorece Busca por exact matchFavorece Busca por exact match
Desfavorece redes com nós transientesDesfavorece redes com nós transientes
8/1/2008
5
Exemplo: Chord
• Baseado em DHTs (Distributed Hash Tables)
Redes não‐estruturadas
Conteúdo independente da l li ãlocalização
8/1/2008
6
Redes não‐estruturadas
•• Nem sempre queries são respondidas Nem sempre queries são respondidas ( l t ã ti t d d )( l t ã ti t d d )(normalmente não atingem toda a rede)(normalmente não atingem toda a rede)
•• Buscas por floodingBuscas por flooding
•• Diferenças entre buscas por conteúdos Diferenças entre buscas por conteúdos populares ou rarospopulares ou raros
•• Alto volume deAlto volume de tráfegotráfego•• Alto volume de Alto volume de tráfegotráfego
FastTrack
•• ProprietárioProprietário
•• Kazaa, Grokster e iMeshKazaa, Grokster e iMesh
•• Continuação de downloads interrompidosContinuação de downloads interrompidos
•• Download de partes de arquivos de diferentes Download de partes de arquivos de diferentes peerspeers
•• Algoritmo de hashing UUHash Algoritmo de hashing UUHash –– checksum checksum rápido mas não detecta corrupção de arquivosrápido mas não detecta corrupção de arquivos
XX
8/1/2008
7
Gnutella
• Ao iniciar, o servent deve conhecer ao menos h tum host
• Ao conectar, recebe lista com outros hosts e cria conexões com estes (em média 5)
Gnutella ‐ Descritores
•• PingPingDescoberta de outros serventsDescoberta de outros servents
•• PongPongResposta a um ping
•• QueryQueryConsulta
•• HitHitHitHitResposta de sucesso ao requisitante
•• PushPushMecanismo para download através de firewalls e NATs
8/1/2008
8
Gnutella ‐ Busca
• Requisitante envia query a todos os vizinhos
• Query tem um TTL (time to live)
• Cada nó que encontra um resultado envia um hit ao requisitante pelo caminho inverso
• Posteriormente a query passou a levar o endereço do requisitanteendereço do requisitante
Gnutella – Download
• Se o servent estiver atrás de um firewall ou NATNAT:
• Requisitante envia push request para o detentor do conteúdo para que a conexão seja iniciada pelo mesmo
8/1/2008
9
Gnutella ‐ Ultrapeers
• Push proxies – a rota original pode não existir imais
• Ultrapeers não têm firewall e se ligam em média a 75 nós folha
• Folhas estabelecem conexões através dos ultrapeersultrapeers
Mecanismos de busca
Métodos e algoritmos para d b t d t úddescoberta de conteúdo
8/1/2008
10
Mecanismos de busca
Em 2003, 60% do tráfego da Internet era Em 2003, 60% do tráfego da Internet era d d t õ d P2P ãd d t õ d P2P ãdado por transações em redes P2P nãodado por transações em redes P2P não‐‐estruturadas [1]estruturadas [1]
[2] Tsoumakos, D., Roussopoulos, N., A Comparison of Peer‐to‐Peer Search Methods, International Workshop on the Web and Databases (WebDB). June 12‐13, 2003, San Diego, California
Mecanismos de busca ‐ métricas
•• Taxa Taxa de sucesso de sucesso (acurácia)– Relação entre buscas bem sucedidas e total de
buscas
•• Hits Hits por requisiçãopor requisição
•• Mensagens Mensagens por requisiçãopor requisição
8/1/2008
11
Mecanismos de busca
• Nós podem guardar informações sobre t úd d d d i i hconteúdo da rede ou de seus vizinhos
Mecanismos de busca
•• Blind searchesBlind searchesNós não guardam informação
•• Informed searchesInformed searchesNós guardam informação sobre conteúdo
8/1/2008
12
Blind searches
Busca sem conhecimento
Modified‐BFS
Diminuição no tráfegoDiminuição no tráfego
Semelhante ao Gnutella, porém a cada hop escolhe aleatoriamente somente alguns de seus vizinhos para propagar a busca
Ainda conecta a um grande número de nós desnecessariamente
8/1/2008
13
Random Walks
Diminuição do tráfego de mensagesDiminuição do tráfego de mensages
• Nó requisitante envia k walkers a seus vizinhos.
• A cada hop, um vizinho é escolhido l t i taleatoriamente.
• Condição de terminação: TTL ou checking.
Random Walks
•• VantagensVantagenso Reduz em até uma ordem de grandeza o número de mensagens
em relação ao BFS
o Implica num balanceamento de carga, visto a aleatoriedade das escolhas
D tD t•• DesvantagensDesvantagenso Impossibilidade de adaptação a buscas por conteúdos populares
o Acurácia depende da topologia da rede
8/1/2008
14
Informed searches
Busca com conhecimento
Intelligent‐BFS
AcuráciaAcurácia
Ambientes dinâmicosAmbientes dinâmicos
• Suposição:– Se um nó tem um determinado conteúdo, deve
também ter conteúdo similartambém ter conteúdo similar
8/1/2008
15
Intelligent‐BFS
• Cada nó guarda tuplas relacionando vizinhos a i tpesquisas recentes
• Um ranking é formado para cada busca com a probabilidade de encontrar o conteúdo em cada vizinho, baseado em buscas antigas
• A requisição é repassada a um conjunto dosA requisição é repassada a um conjunto dos vizinhos com maior ranking
Intelligent‐BFS
•• VantagensVantagenso Entrada e saída de nós não implica em mensagens
excedentes
•• DesvantagensDesvantagenso Atualização constante dos rankings implica em aumento doo Atualização constante dos rankings implica em aumento do
tráfego em função do número de buscas
8/1/2008
16
Adaptative Probabilistic Search (APS)
AcuráciaAcurácia
Diminuição do tráfegoDiminuição do tráfego
• Baseia‐se no aprendizado com os acertos e erros ao longo do tempo
• Utiliza o conceito de walkers
Adaptative Probabilistic Search (APS)
• Cada nó mantém um índice com o número de i i õ d bj trequisições a cada objeto
• O índice é incrementado em hits e decrementado em falhas (walkers fazem feedback a cada nó)
• O índice representa a probabilidade deO índice representa a probabilidade de encontrar o conteúdo em cada nó
8/1/2008
17
Adaptative Probabilistic Search (APS)
•• Abordagem otimistaAbordagem otimista– Atualização depois de uma falha
•• Abordagem pessimistaAbordagem pessimista– Atualização depois de um sucesso
Adaptative Probabilistic Search (APS)
•• VantagensVantagensEficiência no uso da banda (semelhante ao Random Walks)o Eficiência no uso da banda (semelhante ao Random Walks)
o Entrada e saída de nós sem overhead
o s‐APS adapta a abordagem entre otimista e pessimista adaptativamente
o Objetos mais próximos são encontrados com mais frequência
•• DesvantagensDesvantagenso Peers têm que prover grande quantidade de conteúdo
o Grande armazenamento e processamento
o Implementação mais complicada
8/1/2008
18
Routing indices
Diminuição do tráfegoDiminuição do tráfego
• Suposição:– Conteúdos podem ser separados em categorias
Routing indices
• O índice é baseado na quantidade de d t d l ddocumentos que podem ser alcançados por cada link de saída para determinada categoria
• Cada nó encaminha a busca pelo seu link de saída com maior índice para a categoriasaída com maior índice para a categoria daquela busca
8/1/2008
19
Routing indices
•• VantagensVantagenso Buscas são eficientes em utilização de banda
•• DesvantagensDesvantagenso Criação e atualização de índices requer inundação na rede
o Ineficiente para ambientes dinâmicos
o Índices podem estar incorretos devido a loops na redeo Índices podem estar incorretos devido a loops na rede, partição de documentos ou correlação entre categorias
Distributed Resource Location Protocol (DRLP)
AcuráciaAcurácia
Diminuição do tráfego ao longo do tempoDiminuição do tráfego ao longo do tempo
• Cada nó mantém o endereço de uma provável localização do arquivo procurado
8/1/2008
20
Distributed Resource Location Protocol (DRLP)
• Inicialmente baseado em blind searches
• Quando um arquivo é encontrado, requisição percorre caminho inverso, gravando provável localização em cada nó
• Futuras buscas por conteúdo semelhante serão feitas diretamente ao detentorserão feitas diretamente ao detentor
• Caso essa busca direta não tenha resultado, outra blind search é iniciada
Distributed Resource Location Protocol (DRLP)
•• VantagensVantagenso Número de mensagens diminui ao longo do tempo
•• DesvantagensDesvantagenso Ineficiente para ambientes dinâmicos: Quando há mudanças na
topologia da rede, o algoritmo executa blind searches
o Modelo é dependente da aplicação, pois índice de acurácia para um blind search é maior (uma busca retorna muitos resultados)um blind search é maior (uma busca retorna muitos resultados) do que para uma busca direta (retorna um resultado)
o No início, o custo de mensagens é alto, diluindo‐se ao longo do tempo
8/1/2008
21
Comparação
Resultados obtidos para cada l italgoritmo
Hits por requisição
8/1/2008
22
Mensagens por requisição
Taxa de sucesso
8/1/2008
23
Referências• STEPHANOS ANDROUTSELLIS‐THEOTOKIS AND DIOMIDIS SPINELLIS, A Survey of Peer‐to‐Peer Content Distribution
Technologies, Athens University of Economics and Business, ACM Computing Surveys, Vol. 36, No. 4, December 2004.
• Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan, Chord: A Scalable Peer‐to‐peer Lookup Service for Internet Applications, SIGCOMM’01, August 27‐31, 2001, San Diego, California, USA
• KARGER, D., LEHMAN, E., LEIGHTON, F., LEVINE, M., LEWIN, D., AND PANIGRAHY, R. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (El Paso, TX, May 1997), pp. 654–663.
• LEWIN, D. Consistent hashing and random trees: Algorithms for caching in distributed networks. Master’s thesis, Department of EECS, MIT, 1998. Available at the MIT Library, http://thesis.mit.edu/
• Gnutella, http://www.gnutella.com
• Why Gnutella Can't Scale. No, Really. http://www.darkridge.com/~jpr5/doc/gnutella.html
• The Gnutella Protocol Specification v0.41, http://www.gnutella.com
• Tsoumakos, D., Roussopoulos, N., A Comparison of Peer‐to‐Peer Search Methods, International Workshop on the Web and Databases (WebDB). June 12‐13, 2003, San Diego, California.
Recommended