Implementação de um Algoritmo para Busca em Redes Peer-to-Peer

Implementação de um Algoritmo para
Busca em Redes Peer-to-Peer
André Panisson, Maria Janilce Bosquiroli Almeida,
Liane Margarida Tarouco, Lisandro Zambenedetti Granville
Universidade Federal do Rio Grande do Sul - UFRGS
Instituto de Informática – Bloco IV – Bairro Agronomia
Caixa Postal 15.064, CEP: 91.501-970 - Porto Alegre, RS
{panisson, janilce, liane, granville}@inf.ufrgs.br
Abstract. This paper investigates strategies for traffic distribution on peer-topeer network throughout the implementation of a search algorithm. The search
strategies are verified taking into account, mainly, the capacity of the network
nodes. The implementation was done changing some structures of the JXTA
architecture. According to the strategy used in a search operation on a JXTAbased network, a more proper distribution of search messages can be achieved.
Resumo. Este artigo investiga estratégias para distribuição de tráfego em redes
peer-to-peer através da implementação de um algoritmo de busca. As
estratégias de busca são consideradas levando-se em conta, principalmente, a
capacidade de processamento dos nós da rede. A implementação foi realizada
através da alteração das estruturas da arquitetura JXTA. De acordo com a
estratégia utilizada na busca em redes baseadas em JXTA, pode-se ter uma
distribuição mais adequada das mensagens.
1. Introdução
O uso de redes Peer-to-Peer (P2P) tem crescido substancialmente nos últimos anos e
cada vez mais aplicações são construídas sobre essas estruturas. Com a popularização de
sistemas para compartilhamento de arquivos como Napser [Napster 2004], Gnutella
[Ripeanu 2001] e Kazaa [Kazaa 2004], a pesquisa em redes P2P tornou-se imprescindível
não apenas para melhorar esses sistemas, mas também para compreender e controlar o
uso dos recursos da infra-estrutura (tipicamente redes IP) utilizada por essas redes. O
impacto do tráfego P2P pode ser entendido pela seguinte estatística: em algumas
situações, a banda consumida pelo seu tráfego pode chegar a mais de 50% da banda total
disponível pelos provedores [Sen 2002].
Em uma rede P2P, os recursos compartilhados estão distribuídos entre os seus nós
[Sen 2002], diferentemente do que acontece em redes cliente-servidor convencionais,
onde os recursos são armazenados de forma centralizada nos servidores. Um dos serviços
críticos de uma rede P2P é o serviço de busca de recursos. Tal serviço permite que um
usuário localizado em um nó solicite à rede a localização de um conteúdo de interesse. A
resposta gerada a uma solicitação de busca é, normalmente, uma lista de nós onde o
recurso pode ser encontrado. O nó solicitante pode então ter acesso direto aos nós que
disponibilizam o recurso para proceder com seu respectivo acesso.
Em redes P2P, os recursos são sempre acessados de forma distribuída entre os
nós, mas o serviço de busca não é necessariamente realizado de forma distribuída. Nas
primeiras redes P2P existentes, o serviço de busca exigia a existência de um servidor
central para indexação dos conteúdos distribuídos nos nós. Um usuário solicitava a busca
ao servidor central, e este devolvia a lista de nós que disponibilizavam o recurso de
interesse. A abordagem centralizada, apesar de simples, possui um ponto único de falha:
se o servidor de indexação falhar, o serviço inteiro é interrompido. Além disso, essa
abordagem não é escalável porque o processamento do servidor de busca é dependente do
volume de recursos compartilhados, do número de nós da rede P2P e do número de
consultas que tais nós podem gerar. Em virtude dos problemas de escalabilidade e
tolerância a falhas gerados pelas abordagens centralizadas, torna-se necessário recorrer a
abordagens não centralizadas, tais como: modelo de inundação, utilizado pelo Gnutella,
DHT (Distributed Hash Tables), e outros algoritmos similares a algoritmos de
roteamento, utilizados, por exemplo, pelo sistema FreeNet.
Atualmente, uma das abordagens importantes utilizadas na implementação do
serviço de busca é o emprego de algoritmos DHT (Distributed Hash Tables) [Ratnasamy
2002]. Tais algoritmos permitem que se tenha uma busca distribuída estruturada e
eficiente. Os conteúdos a serem disponibilizados recebem um valor associado (hash) e os
nós da rede são distribuidamente consultados passando-se o valor associado. Entretanto,
o algoritmo não permite busca por similaridade. Para os algoritmos baseados em DHT, o
sistema tem um desempenho melhor quando a rede é bastante homogênea, dado que a
distribuição de recursos é feita de forma igual a todos os nós da rede.
Neste artigo é apresentada a análise realizada, através de uma implementação, de
um algoritmo de busca alternativo proposto por Lv et al [Lv et al 2002]. Também propõese o aperfeiçoamento desse algoritmo, somando a ele características de distribuição de
tráfego adaptativa e gerenciável, através da avaliação de funções de distribuição de
mensagens. O algoritmo resultante é escalável, descentralizado e baseado em controle de
fluxo e adaptação da topologia de busca da rede P2P. O algoritmo também considera que
a rede P2P é uma rede heterogênea, onde os nós têm capacidades diferenciadas de
processamento, armazenamento e banda disponível. Para uma análise prática, o algoritmo
foi implementado dentro da plataforma de código aberto JXTA da Sun [Gong 2001] que
possui uma arquitetura de protocolos para a implementação de aplicações P2P. Os
resultados obtidos pela implementação permitem observar que o algoritmo proposto
possui vantagens sobre as outras abordagens porque considera uma distribuição da
consulta que leva em conta as características particulares de cada nó da rede.
O restante deste artigo está assim dividido. A Seção 2 apresenta os fundamentos
da arquitetura JXTA, discute os algoritmos de busca em redes P2P, apresenta o algoritmo
proposto por Lv et al e os aperfeiçoamentos propostos. A Seção 3 introduz a modelagem
do algoritmo na plataforma JXTA. Na Seção 4 é apresentada a implementação do
algoritmo de busca, enquanto na Seção 5 as estratégias de distribuição de mensagens
desse algoritmo são discutidas. A Seção 6 apresenta os resultados obtidos a partir dos
testes realizados com a implementação. Finalmente, na Seção 7 são apresentados as
conclusões e os trabalhos futuros.
2. Trabalhos Relacionados
As duas funções importantes que um sistema P2P deve desempenhar são a descoberta de
recursos e o acesso a estes. O fato de os sistemas P2P serem descentralizados faz com
que o processo de acesso seja inerentemente escalável. A dificuldade, entretanto, está no
processo de descoberta dos recursos de interesse. Essa operação deve ser escalável de
forma que o processo de busca não seja afetado pelas dimensões da rede P2P.
2.1. Soluções para descoberta de recursos
Soluções centralizadas são vulneráveis porque implementam ponto único de falha, além
de serem de difícil expansão em sistemas da ordem de milhões de usuários. Porém,
serviços de procura como Yahoo e Google, apesar de não serem sistemas P2P,
demonstraram que é possível construir tais soluções centralizadas. Isso, no entanto,
demanda investimentos significativos em infra-estrutura, em servidores e em alta largura
de banda. Em redes P2P, também há a existência de alta volatilidade dos peers e a
constante entrada e saída de informações no sistema. Isso torna o modelo P2P de busca
completamente diferente do modelo utilizado para pesquisa em páginas Web.
Tais problemas levaram à adoção de soluções descentralizadas. Essas soluções
envolvem tipicamente a organização dos peers em redes sobrepostas, sobre as quais as
requisições de procura são passadas de peer para peer. Dessa maneira, os sistemas atuais
criam novos e diferentes problemas de escalabilidade. Por exemplo, no Gnutella
[Ripeanu 2001], as mensagens de busca são repassadas por inundação. Neste processo,
um peer, quando precisa encontrar algum recurso na rede, envia uma mensagem de busca
aos seus vizinhos. Estes, por sua vez, repetem o processo, passando adiante as
mensagens. Esse processo de inundação em cada requisição não é escalável, pois o
número de mensagens circulando na rede cresce exponencialmente.
Motivados pelos problemas de escalabilidade nos sistemas P2P, muitos grupos de
pesquisa investigam a viabilidade de uma solução escalável para o problema de
localização de recursos em redes P2P. Como resultado, têm sido propostos sistemas
altamente estruturados. Um exemplo desses sistemas, descrito por Helder [Helder et al.
2002], é um modelo próximo a um algoritmo de roteamento, e tem grandes aplicações em
comunicação multicast. Nesses sistemas altamente estruturados, a topologia da rede é
extremamente controlada, e os recursos da rede (ou referências aos recursos) são
distribuídos em lugares específicos. Esses sistemas fornecem um mapeamento entre os
identificadores de recursos e sua localização, de forma que as buscas sejam
eficientemente roteadas até os peers com os recursos desejados. Esses sistemas, dessa
forma, oferecem uma solução escalável para pesquisas de busca.
Muitos sistemas altamente estruturados utilizam algoritmos DHT (Distributed
Hash Table), e vários projetos estão propondo a construção de facilidades na Internet
feitas sobre algoritmos DHT. Os algoritmos mais conhecidos de roteamento baseado em
DHTs são: Tapestry [Zhao et al. 2001], Pastry [Rowstron et al. 2001], Chord [Stoica et al.
2001] e CAN (Content Adressable Networks) [Ratnasamy 2002]. Porém é preciso
considerar que as buscas podem ser feitas via DHT se for possível fazer uma busca exata.
Essas buscas são as chamadas exact match query, que diferem consideravelmente das
buscas feitas por aproximação, comuns em sistemas de bancos de dados modernos.
Sistemas altamente estruturados são também caracterizados por serem menos flexíveis
em um ambiente com população de usuários muito transitória, pois há um custo alto para
manter a estrutura necessária para seu funcionamento.
Considerando todas estas questões, Lv, Ratnasamy e Shenker [Lv et al 2002]
propõem um algoritmo de busca que visa resolver esses problemas. Esta solução utiliza
caminhamento aleatório, onde cada nó escolhe aleatoriamente um vizinho e envia as
mensagens a ele. O algoritmo aproveita bem as características de heterogeneidade
reveladas por redes P2P. Nas implementações do presente trabalho propõe-se um
aperfeiçoamento desse algoritmo, aproveitando as suas características de adaptabilidade
da rede, e somando características de distribuição de tráfego adaptativa através da
avaliação de funções de distribuição de mensagens.
2.2. A plataforma JXTA
O projeto JXTA [Gong 2001] é um projeto de código aberto concebido inicialmente pela
Sun Microsystems e atualmente sob a responsabilidade de um grupo independente. O
principal objetivo do JXTA é definir uma rede P2P genérica que possa ser usada para a
implementação de uma grande variedade de aplicações e serviços P2P.
Os peers da rede JXTA se organizam em grupos chamados peergroups,
compostos por peers com interesses e serviços comuns. Além disso, todo e qualquer
recurso da rede JXTA é representado por um anúncio, ou advertisement, e identificado
por um ID. Através de anúncios, o problema de encontrar peers e recursos da rede se
reduz ao problema de encontrar anúncios que os descrevem. Os peers guardam, publicam
e trocam anúncios a fim de descobrir e alocar os recursos disponíveis.
O projeto JXTA define um conjunto de seis protocolos [JXTA 2003] para o
desenvolvimento de aplicações P2P (Figura 1). Esses protocolos estabelecem uma rede
virtual sobre a rede física, e fornecem primitivas simples que permitem que um peer se
comunique com qualquer outro peer da rede.
O Endpoint Routing Protocol (ERP) fornece mecanismos para determinar rotas
até um peer, permitindo que haja comunicação através de camadas de transporte
incompatíveis. O Peer Resolver Protocol (PRP) trata do envio e recebimento de
mensagens através de queries, definindo um protocolo para o envio de queries e para o
processamento de queries recebidas. Pipes são construções que enviam ou recebem dados
de um peer remoto. Os serviços da plataforma JXTA utilizam tipicamente o PRP ou
pipes a fim de comunicar-se com outros peers. O Pipe Binding Protocol (PBP) define um
conjunto de mensagens (queries e responses) que um peer pode usar a fim de relacionar
um pipe a um peer remoto.
O Rendezvous Protocol (RVP) é responsável pela propagação de mensagens via
peers especiais chamados rendezvous. O RVP fornece o serviço de rendezvous a outros
peers da rede, o que forma o serviço de propagação de mensagens. Atualmente, o
algoritmo de busca definido no JXTA encontra-se no RVP. A propagação de mensagens
na rede através do RVP original é feita através de inundação e o escopo das mensagens é
controlado através do controle de loops e TTL. O Peer Information Protocol (PIP)
permite que os peers possam obter informações sobre o estado de outros peers (ex.:
tempo de funcionamento, quantidade de conexões, tráfego, etc.). O Peer Discovery
Protocol (PDP) é um protocolo que define como é feita a requisição de anúncios
(advertisements) de outros peers, e como cada peer responde às requisições recebidas.
Peer Local
Peer Remoto
Peer Discovery Protocol
Peer Discovery Protocol
Peer Information Protocol
Peer Information Protocol
Pipe Binding Protocol
Pipe Binding Protocol
Peer Resolver Protocol
Peer Resolver Protocol
Rendezvous Protocol
Rendezvous Protocol
Endpoint Routing Protocol
Endpoint Routing Protocol
Camada de Transporte
Camada de Transporte
Figura 1. A pilha de protocolos JXTA
Há projetos para modificação do RVP, como o algoritmo apresentado por Bernard
Traversat [Traversat 2003]. Em seu artigo, é proposto um algoritmo baseado em DHT,
em que cada rendezvous possui uma lista interna de todos os outros rendezvous do grupo,
ordenados por seu identificador. Esta lista é atualizada periodicamente através de troca de
mensagens, de forma a manter uma consistência entre todas as listas existentes. A partir
desta lista, é gerada então a tabela de hash distribuída (DHT), e cada peer é responsável
por manter um subconjunto das mensagens anunciadas. Quando um peer qualquer faz
uma busca por um anúncio A, o serviço rendezvous faz então uma busca direta no peer
responsável pelo anúncio, via função de hash H(A). Desta forma, escapa-se do modelo de
inundação e assegura-se a disponibilidade das informações através da duplicação dos
anúncios. Porém, esta solução não é totalmente escalável, pois o custo para a manutenção
da consistência da DHT é alto, e o custo para armazenamento da DHT em sistemas com
um número grande de peers também é alto. Além disso, todos os peers são tratados como
se possuíssem igual quantidade de recursos de armazenamento e rede. Outro problema é
que o algoritmo baseado em DHT exige que seja usada a função de hash H(A) para
localização dos recursos, o que inviabiliza outra pesquisa que não seja por busca exata.
3. O Algorimo de Lv, Ratnasamy e Shenker
O algoritmo proposto por Lv et al. [Lv et al 2002] utiliza controle de tráfego distribuído e
construção de topologia com as seguintes características:
-
Restringe o tráfego de consultas em um determinado peer de modo que ele
não se torne sobrecarregado;
Faz com que a topologia da rede evolua dinamicamente, de modo a direcionar
as mensagens aos nós que possuem capacidade suficiente para tratá-las.
Sobre essa topologia, utiliza-se um caminhamento aleatório com pesos, de modo
que os nós com maior capacidade tenham mais probabilidade de receber mensagens. A
combinação dessas funcionalidades resulta em um sistema cujas mensagens são
rapidamente direcionadas a nós com maior capacidade, além de, através da replicação de
objetos na rede, aumentar a probabilidade de encontrar as respostas desejadas. O
resultado é uma organização semi-hierárquica em que os nós com maior capacidade
ficam nos níveis mais altos da hierarquia. Essa hierarquia, porém, não é explícita; ela é
adquirida através de um algoritmo distribuído, adaptativo e auto-organizável.
3.1. Controle de tráfego e adaptação da topologia
A capacidade de um nó i é dada por Ci (número máximo de mensagens que um nó i pode
processar em um intervalo de tempo T). Um nó i é conectado a um conjunto de nós
vizinhos viz (i ) . Para cada nó j ∈ viz (i ) , i mantém as seguintes informações:
-
in[ j , i ] : número de mensagens que chegaram de j para i no último intervalo T.
A taxa total de mensagens recebidas por i é in[∗, i ] = ∑ in[ j , i ] ;
j∈viz ( i )
-
out[i, j ] : número de mensagens que i enviou a j no último intervalo T;
-
outMax[i, j ] : número máximo de mensagens que i pode enviar a j por
intervalo T.
Quando um novo nó i entra na rede, ele é conectado a um conjunto aleatório de
nós. Para cada novo vizinho j, i inicializa:
outMax[i, j ] = C i
in[ j , i ] = 0
out[i, j ] = 0
Cada nó i conta o número de mensagens que recebe e transmite a cada vizinho j.
Periodicamente, o nó i verifica se está sobrecarregado (a taxa de recebimento de
mensagens excede sua capacidade). Se sobrecarregado, o nó i tenta adaptar a topologia de
forma a reduzir sua taxa de recebimento - o nó i seleciona um nó p com alta taxa de envio
(alto in[ p , i ] ) e redireciona a outro vizinho q com sobra na taxa de recebimento. A sobra
na taxa de recebimento do nó q é calculada por C q − in[∗, q] . Intuitivamente, a regra de
adaptação de topologia anterior cria uma conexão direta entre um nó com alta taxa de
envio de mensagens (p) e um nó com alta capacidade (q) e tira do caminho o nó
sobrecarregado. Se o nó sobrecarregado i não puder encontrar um nó q apropriado (isto é,
todos os seus vizinhos estão perto de sua capacidade máxima), o nó i envia um pedido ao
nó p para que reduza o número de mensagens enviadas ao nó i.
Nota-se que todas as decisões sobre controle de tráfego e ajuste de topologia são
baseadas em informações locais (referente ao nó e a seus vizinhos somente). Além disso,
se a capacidade do nó sofrer uma rápida modificação, ou se o nó sair do sistema, a
topologia se adaptará automaticamente a fim de acomodar as mudanças.
3.2. Algoritmo de Busca
O algoritmo de busca da solução usa TTL a fim de terminar o caminhamento, e guarda o
estado da busca pelos nós onde passou, a fim de acelerá-la. O nó passa as mensagens
adiante ao seu vizinho com maior valor em outMax. Isso faz com que as buscas
rapidamente cheguem aos nós com maior capacidade. Em resumo, um nó i que recebe
uma mensagem, repassa a seu vizinho j com maior valor em outMax[i, j ] entre todos os
j ∈ viz (i ) de forma que out[i, j ] < outMax[i, j ] e i não enviou a mesma mensagem ao nó
j.
A fim de aumentar o desempenho do algoritmo, utilizam-se estratégias de
replicação. Quando um nó quer oferecer um recurso a ser compartilhado, este recurso (ou
uma referência a ele) é replicado em diversos outros nós. As cópias serão distribuídas
entre os nós, porém a probabilidade de essa replicação ser feita em um dado nó será
proporcional à sua capacidade. Assim, um nó com alta capacidade de transferência acaba
por consumir mais recursos de armazenamento.
3.3. Aperfeiçoamentos
Uma das limitações do algoritmo acima é o fato de que a única regra de distribuição de
mensagens entre os vizinhos é que elas são enviadas sempre para o vizinho com o valor
máximo em outMax. As mensagens rapidamente se movem para os nós com alta
capacidade, fazendo com que um reduzido número de nós tenha uma alta carga de
mensagens. Em uma rede de grande porte, esse comportamento pode tornar um número
reduzido de nós sobrecarregado, enquanto que uma boa parte dos nós da rede estão com
pouca ou nenhuma carga. Propõe-se então que se faça uma distribuição da carga entre
todos os nós, de maneira adaptável e gerenciável, através do uso de funções de
distribuição que podem ser configuradas em tempo de execução nos nós da rede.
Essa distribuição é feita definindo-se uma ordem total (representada por ≤) entre
os peers vizinhos em função da capacidade outMax de cada vizinho. Seja uma função
∂(i), sendo i a colocação do peer na ordem ≤. A partir de ∂(i) será feita a distribuição das
mensagens. Faz-se assim uma distribuição de mensagens em que os vizinhos com maior
capacidade recebem mais mensagens que os vizinhos com menor capacidade. Essa
distribuição pode possuir vários formatos, dependendo da função ∂(i) escolhida.
Outras modificações ainda foram feitas tirando proveito dos conceitos
disponibilizados pela arquitetura JXTA. Por exemplo, na arquitetura JXTA não há
diferença entre o comportamento de uma mensagem de busca ou uma mensagem de
anúncio de recursos. Assim, o mesmo algoritmo usado para a busca de recursos é também
usado para o anúncio dos recursos disponibilizados pelo peer, sem a necessidade de
implementação de um protocolo diferenciado para as duas operações.
Este é o algoritmo a que este trabalho se propõe implementar e discutir seus
problemas e outras melhorias, utilizando a API de programação da plataforma JXTA.
4. Implementação do protocolo RVP
Dado que a plataforma JXTA está dividida em camadas independentes, torna-se simples
criar uma nova implementação de uma dessas camadas e substituir a camada original por
sua nova implementação. O fato de o projeto JXTA ter código fonte aberto também
possibilita que a programação seja feita tendo como base a implementação padrão
disponível. Por isso, a partir do conjunto de classes Java do protocolo RVP disponíveis,
procedeu-se à implementação da camada RVP da plataforma, a fim de não haver
nenhuma modificação nas outras camadas da arquitetura.
O protocolo RVP consiste em uma interface Java (RendezVousService), acessada
por outras camadas, e sua classe de implementação (RendezVousServiceImpl). Três
principais métodos se encarregam da publicação e da busca: o método propagateInGroup
se ocupa da propagação de mensagens aos outros rendezvous, enquanto propagate e
propagateToNeighbors fazem a propagação apenas no escopo da rede local.
A classe RendezVousServiceImpl possui a classe interna RendezVousManager,
que mantém as informações de todos os peers vizinhos. Na implementação do algoritmo
proposto, a classe RendezVousManager foi alterada através de inclusão de uma lista
ordenada de objetos da classe chamada AddressElement. Cada objeto de AddressElement
armazena informações sobre um peer vizinho j nas propriedades: in (quantidade de
mensagens recebidas de j), out (quantidade de mensagens enviadas para j) e outMax
(quantidade máxima de mensagens que podem ser enviadas a j). Para manter a lista
ordenada de objetos AddressElement, é definida uma ordem total (≤) entre os peers
vizinhos que é função da capacidade outMax de cada vizinho. Essa lista é recuperada
através do método getAddresses da classe RendezVousManager. O método
propagateInGroup da classe RendezVousService é chamado no momento da publicação
de um recurso. A partir desse método, é feito o envio das mensagens, e, por isso, ali será
feita a implementação da função de distribuição de mensagens ∂(i).
4.1. Distribuição de mensagens
A partir da função ∂(i) é possível controlar a distribuição de mensagens entre os peers
vizinhos. Quatro principais esquemas de distribuição são considerados. No primeiro
esquema, se ∂(i) = 2-i, tem-se que a quantidade de mensagens em cada peer será
proporcional a 2-i, com i = ordem do vizinho na fila de vizinhos. O gráfico de distribuição
de mensagens é exponencial decrescente, conforme apresentado na Figura 2.
Distribuição (%)
50%
40%
30%
20%
10%
0%
0
1
2
3
4
5
6
7
8
Ordem (i)
Figura 2. Distribuição exponencial de mensagens para cada vizinho
Uma segunda opção de distribuição de mensagens usa uma descida linear da quantidade
n − i +1
de mensagens. A função de distribuição é dada por ∂ (i ) =
, onde n é a quantidade
P
n + n2
, chegando-se à função
2
p
de vizinhos da lista e P é o somatório
∑ n . Se P =
n =1
2
i 
∂ (i ) = 1 −
 implementada. A Figura 3 apresenta o gráfico considerando n = 8.
n  n + 1
Distribuição (%)
25%
20%
15%
10%
5%
0%
0
1
2
3
4
5
6
7
8
Ordem (i)
Figura 3. Distribuição linear de mensagens para cada peer
Uma terceira opção é tentar fazer com que a quantidade de mensagens seja inversamente
proporcional ao quadrado da colocação do vizinho na lista. A distribuição das mensagens
1
1
é dada pela função ∂ (i ) = −
(Figura 4).
i i +1
Distribuição (%)
50%
40%
30%
20%
10%
0%
1
2
3
4
5
6
7
8
Ordem (i)
Figura 4. Distribuição de mensagens recebidas
proporcional ao inverso do quadrado da ordem i
A quarta e última opção é uma distribuição que obedeça uma curva logística decrescente,
L
onde ∂ (i ) = L −
, em que L, k e a são parâmetros dos quais depende a
1 + e − ki + a
configuração da curva.
Distribuição (%)
50%
40%
30%
20%
10%
0%
1
2
3
4
5
6
7
8
Ordem (i)
Figura 5. Distribuição logística
A função descrita pelo gráfico da Figura 5 é desse tipo, e seria uma boa alternativa para
distribuição de mensagens pois concentra grande parte dos anúncios em um número
definido de peers de alta capacidade, o que pode vir a melhorar bastante o desempenho.
4.2. Implementação da distribuição das mensagens
A construção do algoritmo para distribuição das mensagens entre os peers é feita da
seguinte forma: a fim de que a distribuição seja estatística, é gerada uma função escolha
f (r ) que escolhe o peer destino da mensagem. A partir do número aleatório r, f (r )
retorna um valor que será o ordenamento i do peer escolhido. Essa função f (r ) deve ser
tal que, para uma distribuição randômica de r, a distribuição de i obedeça à função ∂ (i )
escolhida. Por exemplo, se a função de distribuição for ∂ (i ) = 2 − i , deve-se usar a função
escolha i = − log 2 (1 − r ) .
O resumo do algoritmo de distribuição de mensagens para busca e publicação é
descrito a seguir:
// n = número de peers vizinhos;
// f: função de escolha;
// mensagem = mensagem a ser enviada;
r = Número aleatório entre 0 e 1;
peers = Lista de endereços dos vizinhos;
i = f(r);
if (i > n) i = n;
EnviaMensagem(mensagem, peers[i]);
4.3. Testes da plataforma implementada
Durante sua execução, a plataforma emite um relatório que resume as operações
efetuadas. A análise abaixo foi feita sobre a execução de uma aplicação em uma rede
JXTA com oito peers utilizando o protocolo RVP implementado, usando para
distribuição de mensagens a função de distribuição exponencial. A quantidade de
mensagens recebidas e enviadas por cada peer da rede em relação ao total de mensagens
é apresentada na Tabela 1.
Tabela 1. Estatísticas de informações de um conjunto
de peers utilizando o novo algoritmo de busca
Nome do peer
RDV1HC
RDV2HC
RDV1MC
RDV2MC
RDV3MC
RDV1LC
RDV2LC
OUTMAX
6000
600
102
102
51
11
11
IN
49%
24%
10%
5%
4%
4%
3%
OUT
49%
25%
13%
6%
3%
1%
1%
Utilizando essa função, os peers vizinhos com maior capacidade recebem mais
mensagens que os outros. Essa distribuição pode ser interessante se é desejado que os
primeiros peers da lista recebam muito mais mensagens do que os últimos. É apropriada,
portanto, se for considerado que os peers obedecem a uma distribuição de Power Laws,
como sugere o trabalho de Jovanovic [Jovanovic et al. 2001].
Um anúncio publicado será sempre enviado a um número reduzido de peers, e a
busca será feita exatamente nesses peers, que constituem o conjunto com maior
capacidade. A rede é automaticamente estruturada como uma hierarquia, em que os peers
com maior capacidade estão em seu topo.
Na segunda função implementada, que usa uma descida linear da quantidade de
mensagens, o gráfico de distribuição de mensagens foi similar ao apresentado na Figura
3. O principal problema encontrado nesse caso é que, apesar de parecer uma função
simples, sua implementação é bastante complexa, pois envolve laços que também tornam
sua execução mais lenta.
Na função em que a quantidade de mensagens é inversamente proporcional ao
quadrado da posição do vizinho na lista, há a vantagem de que a implementação é
simples. Porém, como a quantidade de vizinhos não é infinita, o último vizinho acaba
recebendo as mensagens restantes, resultando em um gráfico com muitas mensagens
alocadas ao último elemento da lista, o que não é desejável. Uma maneira de contornar
esse problema é através do envio das mensagens restantes ao primeiro vizinho da lista.
Na quarta e última função implementada, a distribuição logística, foram
encontradas várias vantagens, devido ao uso dos parâmetros L, k e a. Esses parâmetros
podem ser facilmente configurados e até mesmo alterados em tempo de execução através
de troca de mensagens entre os peers. Quando o comportamento da rede não for
satisfatório, um gerente pode usar a própria infra-estrutura da rede para modificar esses
parâmetros. Uma vez que todos os peers da rede recebam as mensagens de
reconfiguração e alterem seus parâmetros, imediatamente o comportamento da rede é
alterado, seguindo as regras estabelecidas pelo gerente.
5. Conclusões
Este artigo apresentou a implementação de um algoritmo de busca em redes P2P através
de modificações na plataforma JXTA. Estratégias diferentes de distribuição de
mensagens foram também consideradas. Torna-se uma vantagem poder adaptar a
topologia da rede de forma a distribuir o tráfego de uma forma planejada e gerenciável.
Com esse planejamento, escolher a melhor distribuição para o tipo de rede escolhido e
mesmo modificar seu comportamento em tempo real, se assim for desejável. Pode-se usar
distribuições diferentes, como distribuição linear, distribuição exponencial ou de curva
logística. O algoritmo permite também que sejam feitas pesquisas aproximadas, que são
custosas em redes altamente estruturadas como as que utilizam algoritmos DHT.
Um dos problemas a serem resolvidos no algoritmo implementado é a descoberta
automática da largura de banda disponível em cada peer (no protocolo implementado, a
capacidade de cada peer foi configurada manualmente). Soluções para esse problema
foram estudadas e há propostas que podem ser usadas nessa implementação [Roesler et
al. 2003]. Uma funcionalidade a ser implementada é o redirecionamento de conexões,
descrito no algoritmo de Lv, Ratnasamy e Shenker. Quando um peer da rede começa a se
tornar sobrecarregado, este peer deve passar a redirecionar as suas conexões a outros
peers da rede menos carregados. Por fim, o algoritmo descrito oferece um sistema de
busca por caminhamento aleatório que pode retornar uma resposta após um número
grande de passos. Para diminuir esse número de passos e fazer com que a busca retorne
mais rapidamente, é possível melhorar o algoritmo fazendo com que o peer que gera a
busca, ao invés de enviá-la a apenas um peer, envie a dois ou mais.
6. Referências
Gong, L. (2001) “JXTA: A Network Programming Environment”, In: IEEE Internet
Computing, Vol. 5, issue 3, p. 88-95.
Helder, D. A. et al (2002) “End-host Multicast Communication Using Switch-tree
Protocols”, In: Proceedings of the Workshop on Global and Peer-to-Peer Computing
on Large Scale Distributed Systems (GP2PC), Maio.
Jovanovic, M., Annexstein, F., Berman, K. (2001) “Modeling Peer-to-Peer Network
Topologies through ‘Small-World’ Models and Power Laws”, In: IX
Telecommunications Forum, Dezembro.
JXTA (2003), “JXTA v2.0 Protocols Specification”, Sun Microsystems Inc.
http://spec.jxta.org/nonav/v1.0/docbook/JXTAProtocols.html. Novembro.
Kazaa (2004), “Kazaa Media Desktop”, http://www.kazaa.com
Lv, Q., Ratnasamy, S., Shenker, S. (2002) “Can Heterogeneity Make Gnutella Scalable?”
In: International Workshop on Peer-To-Peer Systems (IPTPS), Março.
Napster (2004), “Napster”, http://www.napster.com
Ratnasamy, S. (2002) “A Scalable Content Addressable Network”, Ph.D. Thesis,
University of California at Berkeley, EUA. Outubro.
Roesler, V. et al. (2003) “Análise do mecanismo de pares de pacotes visando estimar a
banda da rede via UDP”. In: 21º Simpósio Brasileiro de Redes de Computadores
(SBRC 2003), Natal, Brasil. Maio.
Ripeanu, M. (2001) “Peer-to-Peer Architecture Case Study: Gnutella Network”, In:
Proceedings of International Conference on Peer-to-peer Computing. Agosto.
Rowstron, A.; Druschel, P. (2001) “Pastry: Scalable, distributed object location and
routing for large-scale peer-to-peer systems”, In: Proc. of the 18th IFIP/ACM
International Conference on Distributed Systems Platforms (Middleware 2001).
Heidelberg, Alemanha. Novembro.
Sen, S.; Wong, J. (2002) “Analyzing peer-to-peer traffic across large networks”, In:
Proceedings of ACM SIGCOMM Internet Measurement Workshop. Novembro.
Stoica, I. et al. (2001) “Chord: A scalable peer-to-peer lookup service for internet
applications”, In: Proceedings of SIGCOMM 2001. Agosto.
Traversat, B. et al (2003) “Project JXTA: A Loosely-Consistent DHT Rendezvous
Walker”, Sun Microsystems, Inc. http://www.jxta.org/project/www/docs/jxta-dht.pdf
Março.
Zhao, B. Y. et al (2001) “Tapestry: An Infrastructure for Fault-tolerant Wide-area
Location and Routing”, Technical Report UCB/CSD-011141, University of California
at Berkeley, Computer Science Department. Abril.