Gnutella
Flavio Vinicius Diniz de Figueiredo
[email protected]
Universidade Federal de Campina Grande
Departamento de Sistemas e Computação
Sistemas Distribuı́dos, 2006.1
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
1 / 43
Roteiro
1
Introdução
2
Protocolo Base
Mensagens
Bootsrap
Busca e Download
3
A Rede Gnutella
Free-riding
Mapeando a Rede Gnutella
Problemas de escala
4
Novo Protocolo
Query Routing Protocol
Ultrapeers
Outras Melhorias
5
Conclusão
6
Referências
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
2 / 43
Roteiro
1
Introdução
2
Protocolo Base
Mensagens
Bootsrap
Busca e Download
3
A Rede Gnutella
Free-riding
Mapeando a Rede Gnutella
Problemas de escala
4
Novo Protocolo
Query Routing Protocol
Ultrapeers
Outras Melhorias
5
Conclusão
6
Referências
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
3 / 43
Introdução
Como surgiu o Gnutella
Em meados do ano 2000 Justin Frankel e Tom Pepper desenvolveram um
software P2P de compartilhamento de arquivos chamado de Gnutella. A
Nullsoft, empresa no qual o software estava sendo desenvolvido, é uma
subsidiaria da AOL, que temendo problemais legais cancelou o
desenvolvimento do software.
O programa foi divulgado pela Nullsoft um dia antes do seu cancelamento,
neste pouco milhares de copias do software foram baixadas. Pouco tempo
depois clones do cliente Gnutella foram surgindo pela internet, graças à
engenharia reversa feita no protocolo.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
4 / 43
Introdução
Um protocolo aberto que evolui de maneira distribuı́da
Com o surgimento de vários clientes Gnutella o protocolo evoluiu de uma
maneira descentralizada, alguns clientes fornecem o serviço utilizando
otimizações do protocolo mas sendo compatı́vel com a versão original.
Este modo-operando distribuı́do levou ao surgimento do Gnutella
Developers Forum CITE, onde a evolução do protocolo é discutida e
padronizada por diversos desenvolvedores.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
5 / 43
Introdução
Qual o motivo de tanto interesse no Gnutella?
Diferente de outras redes P2P de compartilhamento de arquivos, como o
Napster, o Gnutella não depende de um servidor central. Com o
fechamento do Napster e ataques sendo feitos ao o Kazaa (Rede
Fasttrack) a rede Gnutella cresceu em popularidade.
Caracterı́sticas
Usa um protocolo em sua maioria aberto.
O protocolo Gnutella forma uma rede P2P completamente
descentralizada.
Clientes precisam conhecer somente um outro cliente para fazer parte
da rede.
Isto dificulta o fechamento da rede, pois é muito difı́cil desconectar
todos clientes.
Alta tolerância a falhas de clientes pelo mesmo motivo anterior.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
6 / 43
Roteiro
1
Introdução
2
Protocolo Base
Mensagens
Bootsrap
Busca e Download
3
A Rede Gnutella
Free-riding
Mapeando a Rede Gnutella
Problemas de escala
4
Novo Protocolo
Query Routing Protocol
Ultrapeers
Outras Melhorias
5
Conclusão
6
Referências
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
7 / 43
Mensagens
Como todos os nós da rede fazem o papel de cliente e servidor o Gnutella
utiliza o termo servent (server + client para definir um software que roda
o protocolo Gnutella.
O protocolo base do Gnutella utiliza de cinco tipo de mensagens básicas.
Mensagens
Ping: Utilizado para descobrir outros servents da rede.
Pong: Resposta que um servent envia quando recebe um Ping.
Query: Utilizado para fazer pesquisa de arquivos na rede.
QueryHit: Resposta quando uma pesquisa foi feita com sucesso em
um servent.
Push: Utilizado para iniciar uma transferência de arquivo, que usa
HTTP.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
8 / 43
Mensagens
Todas mensagens contém campos de TTL que é decrementado a cada
salto, como também um campo Hops que é incrimentado a cada salto.
Onde: TTL(i) = TTL(0) + Hops(i).
Toda mensagem também contém informação suficiente para serem
identificadas (ID e Descritor).
Servents ignoram mensagens com TTL muito alto ou com identificação de
uma mensagem já recebida.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
9 / 43
Bootstrap
Servent A quer fazer parte de rede
O servent A precisa conhecer algum outro servent para fazer parte da rede.
A maneira que este conhecimento é adquirido não faz parte do protocolo,
geralmente este conhecimento é obitido usando um cache na WWW.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
10 / 43
Bootstrap
Envio de Pings
Antes de iniciar qualquer comunicação uma conexão deve ser iniciada para
criar o enlace de A para os servent B e C. Agora o servent A deve
propagar sua existência para a rede.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
11 / 43
Bootstrap
Encaminhamento de Pongs
Servents que recebem um ping do servent A devem propagar este Ping
entre os outros enlaces e responder com um Pong.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
12 / 43
Bootstrap
Recebimento de Pongs
Um servent que recebe um Ping responde o Pong somente para o servent
do qual este recebeu o Ping. Assim servents devem encaminhar Pings
devolta para o servent que originou o Ping, neste caso o servent A.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
13 / 43
Busca e Download
Supondo agora que o servent A quer fazer uma busca na rede. Neste caso
vamos supor que A ja é parte da rede mas conhece somente os servents B
e C.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
14 / 43
Busca e Download
Envio de Query
A inicialmente manda uma mensagem do tipo Query para os servents
conhecidos, B e C neste caso. O query contém informações para busca de
arquivos.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
15 / 43
Busca e Download
QueryHits
Os servents que recebem um Query propagam este pelos outros enlaces,
como foi feito com a mensagem de Ping. Caso a busca tenha sucesso um
QueryHit é enviado devolta para quem originou a Query.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
16 / 43
Busca e Download
QueryHits
Como no caso do Pong, QueryHits devem ser retornadas pelo mesmo
caminho que elas foram propagadas.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
17 / 43
Busca e Download
Obtendo o arquivo
Caso o servent A decida inicia uma transferência ao receber QueryHits,
este vai propagar uma mensagem de Push pelo mesmo caminho qu
recebeu o QueryHit. Quando o servent dono do arquivo (neste caso o F)
receber o Push este envia o arquivo fora da rede Gnutella.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
18 / 43
Roteiro
1
Introdução
2
Protocolo Base
Mensagens
Bootsrap
Busca e Download
3
A Rede Gnutella
Free-riding
Mapeando a Rede Gnutella
Problemas de escala
4
Novo Protocolo
Query Routing Protocol
Ultrapeers
Outras Melhorias
5
Conclusão
6
Referências
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
19 / 43
A Rede Gnutella
Por causa de sua natureza descentralizada e popularidade a rede Gnutella
acabou se tornando uma boa fonte de estudos na área de P2P. Vários
estudos foram feitos na rede no tempo de 2000-2002, estes mostram
problemas que existente na rede como assim seu comportamento de dos
usuários desta.
Alguns destes trabalhos explicitam o problema de escala que existe no
Gnutella CITE, outros mostram que a rede também tem pouca tolerãncia
a free-riders CITE.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
20 / 43
Free-riding
Um dos principais estudo de free-riding na rede Gnutella foi feito em 2000
CITE. Este mostra resultados em que a maioria da rede são free-rider. Os
free-rider são dı́vididos em dois tipos:
Tipos de Free-riders
Não compartilham arquivos
Compartilham arquivos que não são desejados.
Principais resultados
70% dos nós rede Gnutella não compartilham arquivos.
Dos que compartilham arquivos, 1% responde a 50% das buscas.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
21 / 43
Mapeando a Rede Gnutella
Um estudo interessante foi feito pelo Ripenau CITE onde ele monitorou a
rede Gnutella por alguns meses (entre 2000-2001), durante este tempo foi
análisado do trafego da rede como sua topologia. Este estudo mostra que
o Gnutella tem comportamento parecido com a distribuição power-law e
que a rede Gnutella não utiliza bem a estrutura da internet.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
22 / 43
Mapeando a Rede Gnutella
Comportamento da rede
O estudo mostra resultados de como os nós da rede se comportaram
durante o perı́odo analisado. Também indica o crescimento da rede.
Crescimento da rede
Durante o estudo o nó mais conectado cresceu (em número de conexões)
em 25%. Mostrando o crescimento da rede neste perı́odo.
Tempo de vida nós
40% dos nós ficam ativos por menos de 4 horas.
Apenas 25% dos nós ficam ativos por mais de 24 horas.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
23 / 43
Mapeando a Rede Gnutella
Distribuição power-law e o Gnutella
Várias redes locais como moléculas em uma célula, pessoas em um grupo
social, aeroportos, a Internet, etc. Seguem uma distribuição power-law.
Caracterı́sticas da power-law
Alguns poucos nós são altamente conectados.
A maioria dos nós são fracamente conectados.
Estes tipos de redes são altamente tolerântes a falhas (nós com poucas
conexões podem falhar sem afetar a rede), mas são fracas em relação a
ataques (caso os nós altamente conectado sejam identificados e atacados).
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
24 / 43
Mapeando a Rede Gnutella
Gnutella segue esta distribuição?
No inicio do estudo a rede Gnutella aparentava seguir a distribuição
power-law. Com o passar do tempo a rede não apresentava mais
caracterı́sticas puramente power-law.
Os autores do artigo mostram isto como uma vantagem pois a distribuição
apresentada aparenta ter a vantagem da power-law e sua desvantagem
amortizada.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
25 / 43
Mapeando a Rede Gnutella
Analisando o trafego da rede
O estudo também mostra o overhead gerado pelas mensagens de controle
(Ping e Pong) da rede. Outros tipos de mensagens são as geradas pelos
usuários (Query e QueryHit) e outras (Push e mensagens não
identificadas).
Trafego da rede - Primeira Análise
55% para mensagens de controle.
36% para mensagens de usuário.
9% para outros tipos de mensagens.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
26 / 43
Mapeando a Rede Gnutella
Novamente analisando o trafego da rede
Perto do fim do estudo mostrou resultados bem diferentes dos
apresentados anteriormente. Talvez isto seja devido a evolução dos
servents e do protocolo, ou simplesmente por causa da variação da rede.
Trafego da rede - Segunda Análise
92% para mensagens de controle.
8% para mensagens de usuário.
Valor desprezı́vel para outros tipos de mensagens.
Estudo também mostra que quantidade de trafego gerado é proporcional
ao número de nós.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
27 / 43
Problemas de escala
Vários textos comentam sobre os problemas de escalabilidade no Gnutella.
Mensagens de Ping-Pong podem causar um grande overhead na rede como
mostrado anteriormente. Outro problema que afeta a escala são os nós
com pouca banda, estes obviamente não conseguem lidar com o tanto
mensagens que circulam na rede criando bottlenecks.
Alguns destes estudos mostram que o Gnutella precisa de alguns gigabytes
de bandas para fazer buscas e é ineficiente quando comparada a redes
como o antigo Napster.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
28 / 43
Roteiro
1
Introdução
2
Protocolo Base
Mensagens
Bootsrap
Busca e Download
3
A Rede Gnutella
Free-riding
Mapeando a Rede Gnutella
Problemas de escala
4
Novo Protocolo
Query Routing Protocol
Ultrapeers
Outras Melhorias
5
Conclusão
6
Referências
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
29 / 43
Novo Protocolo
Principalmente devido ao problema de escala alguns desenvolvedores de
clientes Gnutella começaram a desenvolver melhorias para o protocolo. O
Gnutella Developers Forum é um local onde desenvolvedores discutem e
padronizam estas melhorias.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
30 / 43
Query Routing Protocol
Direcionando buscas
Uma das melhorias existentes é o Query Routing Protocol (QRP). A
motivação por trás deste é minimizar a quantidade de mensages query
propagadas pela rede. O QRP faz com que servents troquem informações
sobre os arquivos que compartilham para sers vizinhos, assim um Query
pode ser direcionado.
QRP
Servents indicam para os vizinhos metadados (palavras chaves) de
árquivos compartilhados.
Nós encaminham seus metadados e metadados recebidos até a
mensagem ter TTL=0.
Cada servent mantém uma tabela com palavra chaves e distância em
hops do servent que propagou a informação.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
31 / 43
Query Routing Protocol
Troca de mensagens - 1
Supondo o caso abaixo onde os nós B, C e D contém arquivos com
palavras chaves {x, y}, {z, w} e {q, p} respectivamente.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
32 / 43
Query Routing Protocol
Troca de mensagens - 2
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
33 / 43
Query Routing Protocol
Troca de mensagens - 3
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
34 / 43
Query Routing Protocol
Troca de mensagens - 4
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
35 / 43
Ultrapeers
TODO
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
36 / 43
Ultrapeers
Estrutura de rede com Ultrapeers
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
37 / 43
Outras Melhorias
Existem outras melhorias que foram introduzidas no protocolo Gnutella.
Algumas destas visam otimizar a descoberta de nós para fazer bootstrap
(GWebCaches) ou a transferência de dados (Swarming), assim como
outras.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
38 / 43
Roteiro
1
Introdução
2
Protocolo Base
Mensagens
Bootsrap
Busca e Download
3
A Rede Gnutella
Free-riding
Mapeando a Rede Gnutella
Problemas de escala
4
Novo Protocolo
Query Routing Protocol
Ultrapeers
Outras Melhorias
5
Conclusão
6
Referências
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
39 / 43
Conclusão
Com isto damos uma introdução ao protocolo utilizado no Gnutella e na
sua rede. Não foram encontrado estudos para verificar as melhorias nas
otimização que foram feitas no protocolo, mas algumas fontem que
proponhem estas indicam melhorias.
Um outro estudo realizado sobre free-riding CITE mostra que o Gnutella
tem problemas neste aspecto.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
40 / 43
Fim
Alguma pergunta?
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
41 / 43
Roteiro
1
Introdução
2
Protocolo Base
Mensagens
Bootsrap
Busca e Download
3
A Rede Gnutella
Free-riding
Mapeando a Rede Gnutella
Problemas de escala
4
Novo Protocolo
Query Routing Protocol
Ultrapeers
Outras Melhorias
5
Conclusão
6
Referências
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
42 / 43
Referências
Brito A. and Brasileiro F.
Programando um Subsistema Sı́ncrono para Suporte a Mecanismos
Eficientes de Tolerância a Falhas
Workshop de Tolerância a Falhas / Simpósio Brasileiro de Redes de
Computadores, 2004.
Flavio V. D. de Figueiredo (DSC)
Gnutella
sisdist 2006.1
43 / 43