View
218
Download
0
Category
Preview:
Citation preview
ESCALABILIDADE DE SISTEMAS P2P
Diego Ximenes Mendes
Projeto de Graduação apresentado ao Curso
de Engenharia de Computação e Informação
da Escola Politécnica da Universidade Federal
do Rio de Janeiro como parte dos requisitos
necessários à obtenção do título de Engenheiro.
Orientador: Edmundo Albuquerque de Souza
e Silva
Rio de Janeiro
Março de 2015
ESCALABILIDADE DE SISTEMAS P2P
Diego Ximenes Mendes
PROJETO SUBMETIDO AO CORPO DOCENTE DO CURSO DE
ENGENHARIA DE COMPUTAÇÃO E INFORMAÇÃO DA UNIVERSIDADE
FEDERAL DO RIO DE JANEIRO COMO PARTE DOS REQUISITOS
NECESSÁRIOS PARA A OBTENÇÃO DO GRAU DE ENGENHEIRO DE
COMPUTAÇÃO E INFORMAÇÃO .
Examinado por:
Prof. Edmundo Albuquerque de Souza e Silva, Ph.D.
Profa. Rosa Maria Meri Leão, D.Sc.
Prof. Daniel Sadoc Menasche, Ph.D.
RIO DE JANEIRO, RJ BRASIL
MARÇO DE 2015
Ximenes Mendes, Diego
Escalabilidade de Sistemas P2P/Diego Ximenes
Mendes. Rio de Janeiro: UFRJ/POLI, 2015.
XI, 44 p.: il.; 29, 7cm.
Orientador: Edmundo Albuquerque de Souza e Silva
Projeto (graduação) UFRJ/ Escola Politécnica/ Curso
de Engenharia de Computação e Informação, 2015.
Referências Bibliográcas: p. 43 44.
1. P2P. 2. Escalabilidade. 3. BitTorrent. 4.
Cadeias de Markov. I. Albuquerque de Souza e Silva,
Edmundo. II. Universidade Federal do Rio de Janeiro,
Escola Politécnica, Curso de Engenharia de Computação
e Informação. III. Título.
iii
Agradecimentos
Gostaria de agradecer os professores com quem pude ter contato durante a gradu-
ação, principalmente o Prof. Edmundo pelos valiosos ensinamentos durante a ori-
entação. Também agradeço Gabriel Mendonça pelas dicas com os experimentos.
iv
Resumo do Projeto de Graduação apresentado à Escola Politécnica/UFRJ como
parte dos requisitos necessários para a obtenção do grau de Engenheiro de
Computação e Informação
ESCALABILIDADE DE SISTEMAS P2P
Diego Ximenes Mendes
Março/2015
Orientador: Edmundo Albuquerque de Souza e Silva
Curso: Engenharia de Computação e Informação
Um sistema Peer-to-Peer (P2P) consiste de uma arquitetura descentralizada de
rede na qual os nós, chamados de peers, atuam tanto como consumidores quanto
fornecedores de conteúdo. Desse modo um sistema P2P permite a distribuição de
conteúdo na Internet de maneira simples, eciente e com escalabilidade, sendo at-
ualmente responsável por uma parte considerável do tráfego na Internet.
Entretanto, estudos recentes mostram que nem sempre sistemas P2P são es-
caláveis, o que é comprovado por um fenômeno chamado de síndrome do pedaço
faltante. Tal síndrome é congurada por uma situação onde a grande maioria dos
peers possuem todos os pedaços com exceção de um pedaço comum a todos esses
peers, cenário que contribui para um baixo desempenho do sistema.
Nesse contexto o presente trabalho visa realizar um estudo da escalabilidade
de sistemas P2P. Para isso são apresentados resultados obtidos através de modelos
Markovianos que permitem realizar a comparação da performance de diferentes algo-
ritmos e parâmetros. Também é exibida uma perspectiva experimental do assunto,
além de uma proposta de um novo algoritmo de seleção de taxas de upload.
v
Abstract of Undergraduate Project presented to POLI/UFRJ as a partial fulllment
of the requirements for the degree of Engineer
SCALABILITY OF P2P SYSTEMS
Diego Ximenes Mendes
March/2015
Advisor: Edmundo Albuquerque de Souza e Silva
Course: Computer and Information Engineering
A Peer-to-Peer (P2P) system consists of a decentralized network architecture in
which nodes, called peers, act as content consumers and providers. Therefore, a
P2P system enables an ecient, simple and scalable way of distributing les on the
Internet, being responsible for a signicant share of Internet trac nowadays.
However, recent studies show that P2P systems are not always scalable, which
is veried by a phenomenon called missing piece syndrome. This syndrome is char-
acterized by a situation where the vast majority of peers have all pieces except for
a single one common to all those peers, causing a poor system performance.
This work aims at studying P2P systems scalability. For this purpose we show
results obtained by Markovian models that allow comparison of the performance
of dierent strategies and parameters. In addition, an experimental approach is
presented and a new upload rate selection algorithm is proposed.
vi
Sumário
Lista de Figuras ix
Lista de Abreviaturas xi
1 Introdução 1
1.1 Contribuição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Organização do Texto . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Sistemas P2P e BitTorrent 3
2.1 Sistemas P2P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 BitTorrent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2.1 Algoritmos de Seleção de Peers . . . . . . . . . . . . . . . . . 7
2.2.2 Algoritmos de Seleção de Pedaços . . . . . . . . . . . . . . . . 8
3 Escalabilidade de Sistemas P2P 10
3.1 Comparação da Escalabilidade da Arquitetura Cliente-Servidor com
a P2P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Regiões de Estabilidade . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2.1 Limites Superiores Para a Vazão . . . . . . . . . . . . . . . . . 14
3.2.2 Altruistic Lingering . . . . . . . . . . . . . . . . . . . . . . . . 16
4 Seleção de Taxas 17
4.1 Serviço Modicado dos Peers com K − 1 Pedaços . . . . . . . . . . . 17
4.2 Algoritmo de Seleção de Taxas de Upload Baseado na Raridade dos
Pedaços . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5 Modelos Markovianos 22
5.1 Modelo de um Sistema Fechado . . . . . . . . . . . . . . . . . . . . . 22
5.2 Modelo de um Sistema Aberto . . . . . . . . . . . . . . . . . . . . . . 25
5.3 Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
6 Experimentos 28
6.1 GENI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
vii
6.2 Software de Experimentação Desenvolvido . . . . . . . . . . . . . . . 29
7 Resultados 31
7.1 Modelos Markovianos . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
7.1.1 Desempenho da Estratégia de Serviço Modicado dos Peers
com K − 1 Pedaços . . . . . . . . . . . . . . . . . . . . . . . . 31
7.1.2 Desempenho do Algoritmo de Seleção de Taxas de Upload
Baseado na Raridade dos Pedaços . . . . . . . . . . . . . . . . 34
7.1.3 Desempenho de um Sistema Aberto . . . . . . . . . . . . . . . 35
7.2 Experimentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
7.2.1 Evidência da Existência da Síndrome do Pedaço Faltante . . . 36
8 Conclusões e Trabalho Futuro 42
Referências Bibliográcas 43
viii
Lista de Figuras
2.1 Arquitetura Cliente-Servidor. Adaptado de [13]. . . . . . . . . . . . . 3
2.2 Arquitetura P2P. Adaptado de [13]. . . . . . . . . . . . . . . . . . . . 4
3.1 Swarm em que muitos peers possuem os mesmos pedaços baixados e
poucos possuem o pedaço mais raro. Células em azul indicam pedaços
que já foram baixados por aquele usuário. . . . . . . . . . . . . . . . 11
3.2 Dinâmica da troca de pedaços para λ > U quado o publisher
adota Most Deprived Peer/Rarest First Piece e os peers Random
Peer/Random Useful Piece em um sistema saturado com um grande
número de peers no one club. Retirado de [2]. . . . . . . . . . . . . . 15
5.1 Exemplo de uma Cadeia de Markov que Representa um Sistema
P2P do Tipo BitTorrent. O estado consiste do vetor denido como
(número de peers com assinatura 00, número de peers com assinatura
01, número de peers com assinatura 10) . . . . . . . . . . . . . . . . . 27
7.1 Número de Peers x Vazão utilizando a estratégia de serviço modi-
cado dos peers com K − 1 pedaços . . . . . . . . . . . . . . . . . . . 32
7.2 Número de Peers x Vazão utilizando diferentes valores de µ′ com a
estratégia de serviço modicado dos peers com K − 1 pedaços . . . . 33
7.3 µ′ x Vazão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
7.4 Número de Peers x Vazão utilizando o algoritmo de seleção de taxas
de upload baseado na raridade dos pedaços . . . . . . . . . . . . . . . 35
7.5 Número de Peers x Vazão em um sistema aberto . . . . . . . . . . . 36
7.6 Tempo x Fração de Peers referente à assinatura 000 em um experi-
mento com N = 400 . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
7.7 Tempo x Fração de Peers referente à assinatura 001 em um experi-
mento com N = 400 . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
7.8 Tempo x Fração de Peers referente à assinatura 010 em um experi-
mento com N = 400 . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
7.9 Tempo x Fração de Peers referente à assinatura 011 em um experi-
mento com N = 400 . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
ix
7.10 Tempo x Fração de Peers referente à assinatura 100 em um experi-
mento com N = 400 . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
7.11 Tempo x Fração de Peers referente à assinatura 101 em um experi-
mento com N = 400 . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
7.12 Tempo x Fração de Peers referente à assinatura 110 em um experi-
mento com N = 400 . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
7.13 Tempo x Fração de Peers referente a assinatura 000 em um experi-
mento com N = 150 . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
7.14 Tempo x Fração de Peers referente a assinatura 110 em um experi-
mento com N = 150 . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
x
Lista de Abreviaturas
API Application Programming Interface, p. 28
DHT Distributed Hash Table, p. 6
GENI Global Environment for Network Innovations, p. 2
GENI AM API GENI Aggregate Manager API, p. 28
HTTP Hypertext Transfer Protocol, p. 5
HTTPS Hyper Text Transfer Protocol Secure, p. 5
IP Internet Protocol, p. 5
NSF National Science Foundation, p. 27
P2P Peer-to-Peer, p. 1
PC Personal Computer, p. 28
SSH Secure Shell, p. 28
VLAN Virtual Local Area Network, p. 29
VM Virtual Machine, p. 28
XML eXtensible Markup Language, p. 28
xi
Capítulo 1
Introdução
Um sistema Peer-to-Peer (P2P) consiste de uma arquitetura descentralizada de rede
na qual os nós, chamados de peers, atuam tanto como consumidores quanto fornece-
dores de conteúdo. Desse modo um sistema P2P permite a distribuição de conteúdo
na Internet de maneira simples, eciente e com escalabilidade, sendo atualmente
responsável por uma parte considerável do tráfego na Internet.
Em uma aplicação de distribuição de arquivos, ao se incorporar a um swarm
(conjunto de peers interessados em um mesmo conteúdo), um peer trás consigo
recursos como banda e memória ao sistema. Portanto, a capacidade física do sistema
aumenta com o crescimento do número de peers uma vez que os peers adquirem dados
úteis a serem compartilhados com outros, além de aumentar a disponibilidade do
conteúdo sendo distribuído.
Apesar das vantagens descritas, estudos recentes [2] [3] [4] [5] [6] [9] mostram que
nem sempre sistemas P2P são escaláveis. Um sistema é dito escalável se a sua vazão
(taxa na qual os usuários completam os seus downloads) aumenta linearmente com
o crescimento da população de peers. Já um sistema é instável quando a sua vazão
é menor do que a taxa de chegada de peers ao swarm, que por consequência gera
o crescimento ilimitado da população de peers ao longo do tempo. A instabilidade
em sistemas P2P pode ser causada pelo fenômeno chamado de síndrome do pedaço
faltante que foi detectado através de modelos matemáticos [2] [3]. Tal fenômeno é
congurado por uma situação onde a grande maioria dos peers possuem todos os
pedaços com exceção de um pedaço comum a todos esses peers, cenário que contribui
para um baixo desempenho do sistema.
Nesse contexto o presente trabalho visa realizar um estudo da escalabilidade de
sistemas P2P baseado nos trabalhos de [2] [5] [6] [9]. Para isso são apresentados resul-
tados obtidos através de modelos estocásticos que permitem realizar a comparação
da performance de diferentes estratégias e parâmetros. Também é apresentada uma
perspectiva experimental do assunto além de uma proposta de um novo algoritmo
de seleção de taxas de upload.
1
1.1 Contribuição
O presente trabalho possui três contribuições principais:
• Desenvolvimento de uma ferramenta de experimentação do protocolo BitTor-
rent utilizando a plataforma de testes em redes GENI. A partir dessa ferra-
menta foram realizados experimentos que apresentam evidências da existência
da síndrome do pedaço faltante.
• Proposta de um novo algoritmo de seleção de taxas de upload baseado na
raridade dos pedaços.
• Elaboração de modelos Markovianos com o objetivo de analisar e comparar a
performance de diferentes estratégias e parâmetros em um sistema P2P do tipo
BitTorrent. Os modelos aqui criados diferem dos descritos em [2] [5] [6] [9] em
alguns aspectos, como por exemplo, o presente trabalho leva em consideração
sistemas abertos, e também o algoritmo de seleção de taxas proposto.
1.2 Organização do Texto
No capítulo 2 é apresentado o protocolo BitTorrent juntamente com os principais
algoritmos de seleção de peers e pedaços utilizados. O capítulo 3 discorre sobre
resultados recentes a respeito da escalabilidade de sistemas P2P do tipo BitTorrent,
comentando algumas regiões de estabilidade. No capítulo 4 são apresentadas duas
estratégias de seleção de taxas de upload. O capítulo 5 apresenta a descrição dos
modelos Markovianos elaborados. Já o capítulo 6 exibe a ferramenta de experi-
mentação desenvolvida e também a plataforma de testes em redes GENI utilizada
nos experimentos. O capítulo 7 apresenta os resultados obtidos através do mode-
los estocásticos e dos experimentos realizados. Por m, no capítulo 8 é feita uma
conclusão do trabalho com uma perspectiva de um trabalho futuro.
2
Capítulo 2
Sistemas P2P e BitTorrent
2.1 Sistemas P2P
Em uma arquitetura mais tradicional chamada cliente-servidor (ver Figura 2.1) ex-
iste um servidor central responsável por atender todas as demandas dos clientes.
Um clássico exemplo da utilização desse modelo consiste em um serviço web onde
um servidor é responsável por responder às requisições de navegadores web que estão
sendo executados nas máquinas dos usuários. Apesar da sua grande popularidade,
em muitas situações esse tipo de arquitetura se torna inviável já que o servidor deve
ser capaz de se adaptar às variações da curva de demanda, muitas vezes tendo que
manter alocado recursos sucientes para os picos de requisições mesmo que isso oca-
sione em ociosidade desses recursos em determinados momentos. Além disso, para
que o sistema seja escalável, ou seja, consiga atender de maneira ecaz um crescente
número de usuários, devem haver intervenções para a ampliação da infraestrutura
física que suporta o sistema. Dessa maneira, aplicações que seguem esse modelo
podem gerar soluções economicamente elevadas e com ineciente uso dos recursos
físicos.
Figura 2.1: Arquitetura Cliente-Servidor. Adaptado de [13].
3
Já em uma arquitetura P2P (ver Figura 2.2) existe uma necessidade mínima, em
algumas ocasiões até nula, da presença de um servidor dedicado à aplicação. Nesse
modelo, os clientes chamados de peers, podem se conectar entre si e atuar tanto como
consumidores quanto fornecedores de conteúdo. Dessa forma a escalabilidade é am-
parada pelos próprios recursos físicos que os clientes trazem ao sistema, reduzindo
assim os custos destinados a se manter e atualizar o servidor. Nos dias atuais exis-
tem diversas aplicações intensivas em termos de tráfego na Internet que utilizam a
arquitetura P2P, como por exemplo, compartilhamento de arquivos, vídeoconferên-
cia e streaming de vídeo [13]. Apesar de congurarem duas arquiteturas distintas,
algumas aplicações são baseadas em uma plataforma híbrida com uma combinação
da arquitetura cliente-servidor com a P2P.
Figura 2.2: Arquitetura P2P. Adaptado de [13].
2.2 BitTorrent
O BitTorrent [1] consiste de um protocolo P2P capaz de distribuir de maneira e-
ciente grandes arquivos pela Internet. Nesse protocolo o arquivo sendo distribuído é
dividido em pedaços e cada peer pode retransmitir os pedaços que já tenha recebido.
Caso fosse empregada uma arquitetura cliente-servidor nesse tipo de aplicação, have-
ria a necessidade da existência de um servidor responsável por transmitir uma cópia
do arquivo para cada cliente, e considerando uma situação comum atualmente em
que os arquivos são grandes e transmitidos para uma grande quantidade de usuários,
o modelo cliente-servidor se tornaria oneroso ou até mesmo impraticável.
No BitTorrent o arquivo é particionado em pedaços de tamanhos iguais que
podem ser recebidos e transmitidos de maneira independente pelos peers. Os pedaços
também são divididos em blocos, que são as unidades de transmissão na rede, porém
o protocolo contabiliza apenas as transmissões dos pedaços, ou seja, um peer só
pode transmitir um pedaço se todos os blocos referentes a ele já foram obtidos. Um
conjunto de peers interessados em um mesmo arquivo congura um swarm, que por
4
sua vez na versão mais tradicional do protocolo admite a existência de quatro tipos
de atores:
• Seed : Peer que possui todos os pedaços do arquivo e apenas faz upload para
outros usuários.
• Leecher : Peer que até o momento não possui a cópia inteira do arquivo e
pode atuar fazendo o download de pedaços que ainda não possui e upload de
pedaços que já possui de maneira simultânea.
• Tracker : Serviço HTTP/HTTPS que responde à requisições HTTP GET.
Responsável por gerenciar o swarm, armazenando a lista de peers pertencentes
ao swarm, fornecendo aos peers uma lista de outros peers com quem eles podem
tentar se conectar, e mantendo estatísticas úteis para os diferentes algoritmos
adotados durante o processo de compartilhamento. Também é permitido a
presença de mais de um tracker por swarm com o objetivo de evitar sobrecarga
e ponto único de falha.
• Publisher : Servidor que possui todo o arquivo e apenas faz o upload dos
pedaços. Na prática pode ser encarado como um seed, porém comumente
pode utilizar algoritmos no processo de distribuição diferentes dos adotados
por outros peers.
O processo de criação e evolução de um swarm é iniciado com um seed (ou
um publisher) interessado em compartilhar determinado arquivo. Para isso o seed
cria um arquivo metainfo, que possui extensão .torrent, e que segue uma estrutura
bem denida pelo próprio protocolo. Tal arquivo contém informações a respeito do
conteúdo sendo transmitido, como por exemplo, número de pedaços em que o arquivo
foi dividido, nome do arquivo e endereço do serviço HTTP/HTTPS associado ao
tracker. A partir desse momento o arquivo metainfo pode ser disponibilizado a
possíveis usuários interessados na obtenção do conteúdo compartilhado, sendo que
ao se interessar, um usuário informa o arquivo metainfo a um cliente BitTorrent para
que assim seja enviada uma mensagem de announce ao tracker informando o desejo
de se juntar ao swarm. Uma vez que o tracker recebe essa mensagem a lista de peers
do swarm mantida no próprio tracker é atualizada, e o tracker responde ao usuário
com uma lista de endereços IPs dos peers com quem ele pode tentar se conectar e
realizar as transmissões. Tal lista de peers informada ao cliente BitTorrent congura
os vizinhos desse cliente e normalmente possui 50 peers e é limitada, por padrão, a
no máximo 80 peers.
Durante todo o processo de troca de pedaços, periodicamente os peers enviam
mensagens ao tracker com informações a respeito de quais pedaços estes conseguiram
5
fazer o download, e o tracker também periodicamente reenvia uma lista de peers at-
ualizada indicando com quem pode haver uma tentativa de conexão. Dessa maneira
o tracker consegue manter estatísticas atualizadas sobre o swarm e o sistema man-
tém uma evolução robusta sem uma degeneração devido a saída de peers do sistema.
Além disso, toda a comunicação entre os peers e o tracker acontece utilizando um
protocolo especíco.
Além da utilização do tracker, versões recentes do protocolo BitTorrent admitem
outros tipos de métodos que não usam trackers para o controle do swarm [17]. Um
deles é o Local Peer Discovery onde cada peer irá descobrir a presença de outros peers
existentes na mesma rede local através de mensagens multicast e sem a intervenção
de outras entidades. Outra técnica consiste do uso de Distributed Hash Table (DHT)
[1], o que na prática faz com que cada peer se torne um tracker já que cada cliente
manterá uma lista de outros nós/peers que poderão ser utilizados para localizar
novos peers. Pelo fato da utilização do tracker ser a mais tradicional e difundida
atualmente o presente trabalho irá focar nesse tipo de abordagem.
A comunicação entre dois peers acontece através do Peer Wire Protocol. Nesse
protocolo, para que dois peers possam trocar pedaços entre si cada cliente deve
manter o estado de cada conexão feita com um peer remoto. Esse estado mantém
dois atributos:
• choked : se o peer remoto enviou uma mensagem de choke à esse cliente.
Quando um peer chokes um cliente signica que nenhuma requisição de
pedaços feita por este cliente choked será atendida até que o peer unchokes
o cliente.
• interessado: armazena se um peer remoto está interessado ou não em algum
pedaço que o cliente pode fornecer.
Portanto, um cliente deve manter para cada peer com quem ele está conectado
as seguintes informações:
• Se o peer remoto choked ou não o cliente.
• Se o peer remoto está interessado ou não no cliente.
• Se o cliente choked ou não o peer remoto.
• Se o cliente está interessado ou não no peer remoto.
Por padrão toda conexão começa choked e com estado de interesse "não interes-
sado". Um pedaço só será baixado por um cliente quando o cliente estiver interessado
em um peer remoto que possui esse pedaço e esse peer não choked o cliente. De
maneira simétrica, um pedaço só será transmitido por um cliente quando o cliente
6
não choked um peer remoto que não possui esse pedaço e esse peer está interessado
no cliente. Dessa modo é importante que cada cliente mantenha as informações de
interesse e choke atualizadas para um funcionamento uido do mecanismo de trocas
de pedaços. Além disso é necessário que cada cliente armazene quais blocos cada um
dos seus vizinhos possui. O Peer Wire Protocol dene, portanto, as mensagens que
devem ser implementadas para a correta manutenção das informações das conexões
entre os peers e também para as requisições e troca de pedaços. Os algoritmos
que decidem quais conexões são de interesse e quais devem ser choked ou não são
executados periodicamente, garantindo a consistência das conexões.
Uma vez que o cliente acabe o download do pedaço é feita uma vericação da sua
integridade utilizando técnicas de hash, especicamente o método SHA-1 [16]. Os
hashes dos pedaços são inicialmente incluídos no arquivo metainfo quando o mesmo
é criado, e dessa maneira é possível comparar o hash do pedaço obtido com o hash
presente no arquivo metainfo. Caso esses hashes coincidam então as estruturas
internas do cliente são atualizadas com a presença do novo pedaço e oportunamente
mensagens aos seus vizinhos e ao tracker são enviadas informando a atualização
ocorrida.
Uma vez que um cliente possui uma lista de vizinhos além da descrição do es-
tado de cada conexão e informações a respeito de quais blocos cada vizinho possui,
o cliente deve então escolher para qual peer ele deve fazer um upload e após essa
primeira escolha ele também deve decidir qual pedaço transmitir. Essas duas escol-
has encadeadas são fundamentais para que um sistema atinja uma boa performance,
e portanto, existem diversas estratégias para se realizar tais escolhas, sendo que cada
uma traz diferentes vantagens e condições de desempenho ao sistema. A seguir se
encontram alguns do principais algoritmos utilizados nessas decisões [2] [7] [16] [17],
sendo que nos próximos capítulos serão apresentadas análises do impacto de difer-
entes políticas de maneira matematicamente mais fundamentada.
2.2.1 Algoritmos de Seleção de Peers
Abaixo se encontram diferentes políticas que um cliente pode utilizar para selecionar
um peer a quem vai transmitir algum pedaço.
• Random Peer : Seleciona aleatoriamente de maneira uniforme um dos seus
vizinhos para transmitir. Uma das desvantagens está relacionada com o fato
de que esse algoritmo pode selecionar um peer que possui todos os blocos
que o cliente que está fazendo o upload possui, dessa maneira a tentativa de
transmissão será desperdiçada.
• Random Useful Peer : Dentre os vizinhos que podem se beneciar com um
pedaço que o cliente transmissor possui escolhe aleatoriamente de maneira
7
uniforme para qual deles fazer o upload. Essa política é uma adaptação da
anterior a m de eliminar a desvantagem descrita.
• Most Deprived Peer : Dentre os vizinhos o cliente transmissor escolhe o que
tem o menor número de pedaços baixados até o momento, ou seja, o menos
privilegiado. Caso exista mais de um vizinho menos privilegiado é feita uma
escolha aleatória dentre esses vizinhos empatados. Essa estratégia tenta fazer
uma espécie de balanceamento do swarm, buscando que os peers mantenham
uma quantidade parecida de pedaços, para que assim todos os peers consigam
realizar transmissões, e portanto, otimizando a utilização da capacidade de
serviço do sistema.
2.2.2 Algoritmos de Seleção de Pedaços
Após a escolha do peer para qual um cliente fará a transmissão o cliente deve decidir
o pedaço que será transmitido. Abaixo se encontram algumas dessas escolhas.
• Random Useful Piece: Dentre os pedaços úteis que o transmissor possui e o
peer que irá receber não possui é feita uma escolha aleatória e uniforme.
• Rarest First Piece: Dentre os pedaços que o cliente transmissor possui e o peer
receptor não possui escolhe o mais raro (menor quantidade de réplicas) do
swarm. Essa estratégia possui um overhead de informação consideravelmente
maior em relação à estratégia anterior já que é necessário que cada cliente
tenha acesso às estatísticas dos pedaços de todo o swarm, o que pode ser algo
custoso de manter atualizado com uma alta frequência pois existe a possibili-
dade de geração de sobrecarga por parte do tracker e pela grande quantidade
de tráfego associado às estatísticas. Em algumas implementações cada cliente
aproxima as estatísticas globais do swarm pelas estatísticas locais com relação
aos vizinhos desse cliente. A ideia por trás dessa estratégia está na tentativa
de fazer com que a disponibilidade (quantidade de réplicas) dos pedaços se
torne distribuída de maneira balanceada.
Por questões de justiça e para manter um bom desempenho do swarm como
um todo, todos os peers devem utilizar as mesmas estratégias de seleção de peers
e pedaços. O publisher, entretanto, pode adotar estratégias diferentes dos demais
peers o que pode ser justicado pelo fato de usualmente o publisher possuir uma
capacidade de banda maior do que os peers, e também pela maior facilidade de se
manter as estatísticas atualizadas de maneira mais frequente apenas no publisher.
Dessa maneira o publisher pode contribuir para a performance do swarm ao utilizar
estratégias que exijam informações atualizadas com mais frequência, como o Rarest
First Piece por exemplo.
8
As estratégias aleatórias adotadas em ambas escolhas tentam manter um bom
balanceamento do swarm de maneira eciente assumindo um comportamento es-
tatístico de longo prazo, além de serem de fácil implementação e com pouco over-
head já que a decisão pode ser feita de maneira local sem utilização de estatísticas
globais. A combinação do algoritmo de seleção de peers com o de pedaços tam-
bém pode ser decisivo para o desempenho do sistema, sendo que algumas dessas
combinações serão analisadas nos próximos capítulos.
9
Capítulo 3
Escalabilidade de Sistemas P2P
Um sistema é considerado escalável quando a vazão, ou seja, a taxa na qual os
usuários completam os seus downloads, aumenta linearmente com o crescimento da
população. Já um sistema é dito instável quando a taxa de chegada de usuários é
superior à taxa que o sistema consegue processar esses usuários.
Ao se juntar a um swarm um peer trás consigo recursos físicos como banda e
memória. Dessa maneira a capacidade física do sistema cresce com o aumento da
taxa de chegada dos peers, entretanto esse crescimento pode não ser correspondido
com o aumento da vazão devido a limitação da própria dinâmica das estratégias
empregadas em um protocolo P2P, fazendo com que em determinadas situações o
sistema não seja escalável.
Uma situação onde existem muitos peers com os mesmos pedaços baixados e
poucos peers com o pedaço mais raro, representa um exemplo claro de que nessa
situação o swarm não consegue utilizar integralmente sua capacidade de upload, já
que a maioria dos peers que possuem os mesmos pedaços não terão muitas opções
para a realização de transmissões, fazendo com que suas bandas de upload quem
ociosas. Abaixo segue uma gura que ilustra tal situação.
10
Figura 3.1: Swarm em que muitos peers possuem os mesmos pedaços baixados e
poucos possuem o pedaço mais raro. Células em azul indicam pedaços que já foram
baixados por aquele usuário.
Através do exemplo é possível perceber que os peers de 1 a 4 possuem os mesmos
pedaços e portanto uma tentativa de transmissão entre eles não teria sucesso. Já o
peer 5 é o único que possui o pedaço 4 fazendo com que apenas ele seja o respon-
sável imediato na disseminação desse pedaço. Extrapolando o cenário considerando
muitos peers na situação dos peers de 1 a 4 e poucos peers com a conguração do
peer 5 é obtido um exemplo onde a capacidade física do swarm é subutilizada.
3.1 Comparação da Escalabilidade da Arquitetura
Cliente-Servidor com a P2P
A m de comparar a escalabilidade da arquitetura cliente-servidor com a P2P, aqui é
apresentado um modelo simplicado baseado em [1] de uma aplicação de distribuição
de arquivos em ambas arquiteturas analisadas. Esse modelo visa encontrar um limite
inferior para o tempo de distribuição dos dois métodos.
Nesse modelo a taxa de upload do servidor é denida por U e as taxas de upload
e download do i-ésimo cliente/peer são denidas respectivamente por µi e di. Todas
as taxas aqui apresentadas são denidas em pedaços por segundo. O arquivo sendo
transmitido é divido em K pedaços de tamanhos iguais e o número de usuários no
sistema é N . O tempo de distribuição do arquivo é dado como o tempo para que
todos os usuários consigam completar o download do arquivo. Na análise simpli-
cada a seguir se supõe que as entidades participantes não fazem parte de outras
aplicações de rede, ou seja, a capacidade de download e upload são integralmente
direcionadas à distribuição do arquivo.
Em uma arquitetura cliente-servidor, o servidor deve transmitir uma cópia do
arquivo para cada um dos N clientes. Dessa maneira o servidor transmite NK
11
pedaços, fazendo com que o tempo mínimo de upload do arquivo por parte do servi-
dor seja NK/U . Já o tempo mínimo de download por parte dos clientes será o
tempo de download associado ao cliente com a menor taxa de download, ou seja,
considerando dmin = minidi, esse tempo mínimo de download será K/dmin. Colo-
cando o tempo mínimo de upload do servidor e download dos usuários de maneira
conjunta, o tempo distribuição mínimo (lower bound) do arquivo na arquitetura
cliente-servidor chamado de TCS é dado por:
TCS = max
NK
U,K
dmin
(3.1)
Considerando um caso homogêneo onde a taxa de upload e download dos peers
podem ser consideradas iguais (di = µi = µ ∀i):
TCS = max
NK
U,K
µ
(3.2)
Considerando a equação acima é vericado que o tempo mínimo de distribuição
aumenta linearmente com o crescimento de N , a partir do momento que NK/U >
K/µ.
Já a obtenção do tempo mínimo necessário para a distribuição do arquivo em um
sistema P2P pode ser bem mais complicada do que a análise feita para o caso cliente-
servidor pois esse tempo será diretamente afetado pela estratégia que o servidor e
os peers adotam. Entretanto algumas simplicações podem ser feitas permitindo
assim uma aproximação.
A dinâmica do protocolo começa em um cenário onde apenas o servidor possui
o arquivo sendo distribuído e a partir de então tal arquivo passa a ser disseminado
para toda a população de peers. Como os peers também atuam como fornecedores de
conteúdo o servidor deve transmitir cada bloco pelo menos uma vez, dessa maneira
o tempo mínimo de upload por parte do servidor é no mínimo K/U . Assim como na
arquitetura cliente-servidor o peer com menor taxa de download é um limitante para
o tempo de distribuição, portanto o tempo mínimo de download por parte dos peers
seráK/dmin. A capacidade física de upload total do swarm também caracteriza uma
restrição para o tempo de distribuição, sendo que essa capacidade agregada é dada
por µtotal = U +N∑i=1
µi. Com essa consideração, a distribuição do arquivo não pode
acontecer mais rápido do que NK/µtotal. Levando em conta todas essas limitações,
o tempo de distribuição mínimo TP2P do arquivo na arquitetura P2P é dado por:
TP2P = max
K
U,K
dmin,
NK
U +N∑i=1
µi
(3.3)
12
Considerando o caso homogêneo:
TP2P = max
K
U,K
µ,
NK
U +Nµ
(3.4)
Comparando o tempo mínimo de distribuição das duas arquiteturas é vericado
que esse tempo cresce de maneira mais lenta no modelo P2P em relação ao cliente-
servidor, ou esse crescimento também pode ser igual nas duas arquiteturas. Dessa
maneira pode-se dizer que a arquitetura P2P é mais eciente em termos de escala-
bilidade.
3.2 Regiões de Estabilidade
Em essência a instabilidade ocorre em situações em que o publisher é o gargalo, isto
é, a performance do sistema se torna altamente dependente do servidor. Nesse tipo
de cenário quando dois peers se conectam com alta probabilidade eles não possuem
pedaços úteis a serem trocados, ou seja, ambos possuem os mesmos pedaços e o
publisher se torna responsável por boa parte das transmissões a serem realizadas.
Nesse contexto, uma região de estabilidade é denida por um conjunto de valores
de parâmetros em que o sistema é conhecido como estável.
Nesta seção são apresentados alguns resultados recentes na literatura referente
a algumas regiões de estabilidade de sistemas P2P do tipo BitTorrent. Para isso
é assumido que o arquivo sendo transmitido é divido em K pedaços de tamanhos
iguais, o único servidor possui capacidade de upload U , e os peers taxa de upload
e download homogêneas de µ pedaços por segundo. Também é considerado que
os peers chegam ao sistema a uma taxa λ peers por segundo pertencente a uma
distribuição Poisson.
Em [2], [3], [4], [5], [6] foram mostradas diversas conclusões a respeito da escala-
bilidade de sistemas P2P, como por exemplo, que as políticas de seleção de pedaços
Rarest First Piece e Random Useful Piece possuem a mesma região de estabilidade.
Também foi mostrado que quando os peers e o servidor adotam as políticas Ran-
dom Peer/Random Useful Piece o sistema se torna instável quando λ > U . Além
disso, algumas pequenas modicações podem melhorar o desempenho e até mesmo
evitar uma situação de instabilidade, como por exemplo, se os peers permanecerem
no swarm após baixarem todo o arquivo na média pelo mesmo tempo que levaram
para realizar o download então o sistema é sempre estável [2]. Porém, como os peers
não possuem muitos incentivos a permanecerem no swarm é importante investigar
outras propostas que possam contribuir para a melhora do desempenho.
13
3.2.1 Limites Superiores Para a Vazão
Nesta subseção é apresentada uma análise feita em [2] sobre a escalabilidade quando
o publisher adota as estratégias Most Deprived Peer/Rarest First Piece e os peers
adotam Random Peer/Random Useful Piece, sendo que o peer deixa o swarm assim
que completa o download do arquivo. Como é conhecido que o sistema é estável
para λ < U o estudo é feito para uma situação em que λ > U .
Nesse cenário uma fração U/λ dos peers recebem conteúdo do servidor imediata-
mente após entrarem no swarm. Isso acontece pois a política empregada pelo servi-
dor sempre privilegia os peers mais desfavorecidos (menor quantidade de pedaços
baixados), e como λ > U e os recém chegados podem ser considerados mais desfa-
vorecidos o servidor somente servirá peers recém chegados. Tais peers que recebem
esse pedaço inicial do publisher são chamados de gifted peers, e dessa maneira a taxa
na qual os gifted peers entram no sistema é dada por U e a taxa na qual non-gifted
peers entram no sistema é denida por λ − U , assumindo que em toda tentativa
de transmissão do servidor ele irá encontrar algum peer recém chegado com alta
probabilidade.
Caso os gifted peers e os non-gifted peers pudessem completar os seus downloads
a taxas U e λ− U respectivamente o sistema seria estável, porém isso nem sempre
acontece. Um cenário em que a estabilidade não ocorre é descrita pela síndrome do
pedaço faltante. Nessa síndrome existe um grande número de peers com todos os
pedaços com exceção de um mesmo pedaço c, chamado então de pedaço faltante.
Todos os peers que possuem todos os pedaços com exceção do c caracterizam um
grupo especial chamado de one club. A partir do momento que a síndrome é cong-
urada o sistema tende a uma situação em que one club cresce indenidamente com
o tempo e o servidor se torna um gargalo, causando assim a instabilidade. Dessa
forma uma análise mais detalhada de uma conguração com um grande número de
peers no one club se torna um modo interessante de analisar os limites do sistema,
sendo que tal análise é apresentada a seguir [2].
Se o one club é grande o suciente os gifted peers irão transmitir pedaços apenas
para o one club com alta probabilidade devido a política de Random Peer. Todos
os uploads do publisher são para os recém chegados (assim como explicado anteri-
ormente) sendo que uma fração U/λ dos peers que entram no sistema recebem um
pedaço do publisher. Após receber o pedaço do servidor, um gifted peer ca em média
mais (K−1)/µ segundos no sistema, servindo assim em média µ(K−1)/µ = K−1
peers do one club, sendo que tal tempo é obtido pela própria limitação da taxa de
download do peer já que como o one club é abundante sempre haverá uma oportu-
nidade de transmissão de um peer do one club para o gifted peer. Fazendo a mesma
análise anterior, um non-gifted peer levará em média (K − 1)/µ segundos até se
14
tornar pertencente ao one club. Assim, a taxa de entrada de peers no one club é
dada pela taxa de entrada dos non-gifted peers, ou seja, λ − U , e a taxa de saída
dos peers do one club será limitada pela taxa de serviço do servidor, U , mais a taxa
de serviço dos gifted peers para o one club, U(K − 1). A taxa U(K − 1) é obtida
a partir da taxa de entrada dos gifted peers ponderada pela quantidade de peers do
one club que em média um gifted peer serve. Portanto, a vazão do sistema será a
taxa de saída dos peers do one club mais a taxa de saída dos gifted peers do swarm,
ou seja, a vazão será limitada superiormente por U(K − 1) + U = KU . O sistema
será estável quando a taxa de chegada de peers for menor que a vazão [2]:
λ < KU (3.5)
Abaixo, na Figura 3.2, se encontra um diagrama que ilustra a dinâmica descrita
acima.
Figura 3.2: Dinâmica da troca de pedaços para λ > U quado o publisher adota Most
Deprived Peer/Rarest First Piece e os peers Random Peer/Random Useful Piece em
um sistema saturado com um grande número de peers no one club. Retirado de [2].
Caso o mesmo estudo anterior fosse aplicado para um publisher que adote a
política de Random Useful Piece: o servidor da mesma maneira sempre servirá U/λ
dos peers recém chegados porém, apenas U/(λK) desses peers receberão o pedaço
faltante, ou seja, a taxa na qual o publisher contribui para a inserção do pedaço
faltante no swarm será de U/K. Portanto a taxa de serviço dos gifted peers ao
one club será U(K − 1)µ/(Kµ) = U(K − 1)/K. Dessa forma a vazão do sistema
será limitada superiormente por U(K − 1)/K + U/K = U e o sistema será estável
quando:
λ < U (3.6)
Apesar das descrições acima, a existência da síndrome do pedaço faltante foi
identicada através da utilização de modelos matemáticos recentemente na literatura
15
[2] [3], sendo assim criticado pela inexistência de evidências experimentais. Nesse
contexto no capítulo 7 são apresentados resultados experimentais que apoiam a
existência dessa síndrome.
3.2.2 Altruistic Lingering
Considerando que o servidor e os peers adotam Random Peer]Random Piece, se
uma fração F dos peers permanecerem no sistema na média por 1/γ segundos e se
µF/γ > 1 então o sistema é estável. Tal situação é conhecida por altruistic lingering
e foi apresentado em [2].
Cada seed contribui com uma taxa µ para servir os peers do one club. Con-
siderando como λ′ a taxa na qual os peers saem do one club, pelo resultado de Little
o número médio de seeds no sistema é dado por λ′F/γ. A taxa de saída do one club
necessária para manter o sistema estável deve ser maior do que a taxa de entrada
de peers no one club, ou seja, λ. Desse modo:
µλ′F
γ> λ
µF
γ>λ
λ′
Como λ ≥ λ′:
µF
γ> 1 (3.7)
16
Capítulo 4
Seleção de Taxas
Neste capítulo é apresentada uma perspectiva em relação à seleção de taxas na
dinâmica do protocolo BitTorrent. Para isso, na seção 4.1 é descrita uma estratégia
proposta em [5], já na seção 4.2 é proposto um novo algoritmo de seleção de taxas.
4.1 Serviço Modicado dos Peers com K − 1
Pedaços
Nessa estratégia proposta em [5], quando um peer possui K − 1 pedaços a taxa de
upload desse peer é modicada para µ′, sendo que µ′ < µ. Essa política se baseia na
ideia de diminuir a taxa de upload dos peers pertencentes ao one club, fazendo assim
com que os gifted peers se mantenham mais tempo no sistema e possam fornecer o
pedaço mais raro ao one club por mais tempo. Nesse contexto seria mais eciente
diminuir apenas as taxas dos peers pertencentes ao one club e não a de todos os peers
com K− 1 pedaços, porém a identicação se um peer está no one club pode não ser
uma implementação trivial, já a estratégia descrita acima possui fácil implementação
e apresenta bons resultados assim como mostrado em [5] e no capítulo 7.
O aumento da vazão com essa pequena variação é signicativo e possui um bom
apelo na questão de economia de banda por parte dos peers. Através dos resultados
obtidos em [5] é vericado que na medida que µ′ diminui a vazão aumenta, entretanto
esse aumento não é ilimitado, a vazão aumenta enquanto µ′ diminui até atingir uma
vazão máxima, e a partir de então a diminuição de µ′ gera a diminuição da vazão.
Tal decrescimento é explicado pelo fato do sistema se degenerar a um caso cliente-
servidor onde o servidor se torna responsável pela grande maioria das transmissões
no swarm.
17
4.2 Algoritmo de Seleção de Taxas de Upload
Baseado na Raridade dos Pedaços
Com a síndrome do pedaço faltante em consideração, a seguir é proposto um novo
algoritmo de seleção de taxas de upload baseado na raridade dos pedaços.
A ideia do algoritmo é a de evitar que o sistema se torne instável prevenindo a
ocorrência da síndrome do pedaço faltante. Além disso, caso a síndrome ocorra o
algoritmo tenta impedir que ela se agrave e procura recuperar a estabilidade. Adap-
tando a taxa de upload considerando a disponibilidade do pedaço sendo transmitido
em relação à disponibilidade dos outros pedaços permite a tentativa de manter a
quantidade de réplicas dos pedaços bem distribuída, ou seja, tenta fazer com que
a quantidade de réplicas de um pedaço seja parecida com as demais. Isso é feito
determinando que pedaços menos raros sejam distribuídos com uma taxa menor
do que pedaços mais raros, e indo além, as taxas são denidas de maneira propor-
cional à distribuição da quantidade de réplicas no swarm. Fazendo com que a taxa
nunca que menor que um determinado valor se evita que o sistema se degenere a
um caso cliente-servidor onde o publisher será responsável pela grande maioria das
transmissões.
Em um cenário onde todos os pedaços ocorrem de maneira aproximadamente uni-
forme em termos de contagem de réplicas, o swarm consegue utilizar sua capacidade
de upload de maneira eciente evitando ociosidade, já que com alta probabilidade
quando dois peers tentarem realizar uma transmissão encontrarão um pedaço útil
para a troca. Nesse contexto, a estratégia apresentada diminui consideravelmente
as taxas de upload para pedaços muito frequentes (em termos relativos), fazendo
com que a quantidade de réplicas desses pedaços cresça de maneira mais devagar
do que o número de cópias dos pedaços menos frequentes, assim o sistema sempre
tende para um situação de homogeneidade da quantidade de réplicas.
A seguir é apresentado o pseudocódigo da ideia descrita.
18
Algorithm 1 Calcula Raridades1: function CalculaRaridades(K, quantidadeReplicas,minRaridade)
2: for i← 1 to K do
3: v[i].cnt← quantidadeReplicas[i]
4: v[i].id← i
5: end for
6: Ordenar v de maneira crescente em relação à cnt
7: raridade[v[1].id]← 1
8: for i← 2 to K do
9: raridadeRelativa← raridade[v[i− 1].id]×(
1− v[i].cnt−v[i−1].cntmax(v[i].cnt,1)
)10: raridade[v[i].id]← max(minRaridade, raridadeRelativa)
11: end for
12: return raridade
13: end function
Os parâmetros desse algoritmo são: número de pedaços K em que o arquivo foi
particionado; vetor quantidadeReplicas onde quantidadeReplicas[i] indica a quan-
tidade de réplicas do pedaço i no swarm; e a menor raridade possível de ser atribuída
a um pedaço, chamada então de minRaridade. O argumento minRaridade deve
pertencer ao intervalo 0 ≤ minRaridade < 1, e a escolha de qual valor utilizar pode
ser fundamental para o desempenho da estratégia. A m de manter uma coerência
com a política de serviço modicado dos peers com K − 1 pedaços foi adotado que:
minRaridade =µ′
µ(4.1)
Já o retorno do algoritmo é um vetor raridade, onde raridade[i] indica a rari-
dade do pedaço i no swarm, sendo que a relação a seguir é sempre obedecida:
minRaridade ≤ raridade[i] ≤ 1. Portanto, a taxa na qual um pedaço i será trans-
mitido por um peer é dada por:
taxaUploadPeer[i] = µ× raridade[i], i = 1, 2, . . . , K (4.2)
Dessa forma, a nova taxa de upload para um pedaço i qualquer estará sem-
pre no intervalo minRaridade × µ ≤ taxaUploadPeer[i] ≤ µ, garantindo assim a
consistência da taxa.
De maneira análoga, um publisher irá transmitir o pedaço i com a seguinte taxa:
taxaUploadPublisher[i] = U × raridade[i], i = 1, 2, . . . , K (4.3)
Assim como descrito no pseudocódigo, o pedaço mais raro no sistema possui
raridade igual à 1, ou seja, a maior raridade possível. A raridade do segundo
19
pedaço mais raro do swarm será igual à raridade do pedaço mais raro menos uma
diferença percentual da quantidade de réplicas entre os dois pedaços, considerando
o pedaço cuja raridade está sendo calculada como referência. A raridade do terceiro
pedaço mais raro será feito da mesma maneira como foi feito com o segundo mais
raro em relação ao primeiro mais raro, entretanto a raridade do terceiro mais raro é
calculada em relação ao segundo mais raro. Dessa maneira é denida uma indução
onde basta ordenar os pedaços pelas suas quantidades de réplicas de maneira
crescente e aplicar a relação de raridade, sendo que o valor da raridade é limitada
inferiormente por minRaridade. É importante notar que as seguintes relações são
satisfeitas:
Se cntReplicas[i] == cntReplicas[j] então raridade[i] == raridade[j]
Se cntReplicas[i] < cntReplicas[j] então raridade[i] ≥ raridade[j]
Considerando a ocorrência da síndrome do pedaço faltante, o algoritmo fará
com que a taxa referente ao pedaço faltante seja a maior possível, ou seja, µ, e as
taxas dos outros pedaços sejam a menor possível, ou seja, µ ×minRaridade = µ′.
Dessa maneira quando o sistema estiver saturado, ou seja, quando o one club for
muito grande, o algoritmo irá atuar da mesma forma como a estratégia do serviço
modicado para os peers com K − 1 pedaços.
Em um primeiro momento a ideia de diminuir a taxa de upload e assim aumentar
a vazão pode parecer contraintuitiva. Entretanto, ao se entender que a ocorrência
da síndrome do pedaço faltante implica em uma grande perda de performance, e
uma vez que tal síndrome se conrma ela tende sempre a se agravar, métodos que
evitam a ocorrência dessa síndrome e a rápida remoção dela após a sua instalação
possuem a propensão de obter bons resultados em termos de vazão global, mesmo
que a princípio, localmente pareça uma estratégia ruim diminuir a taxa de upload.
Apesar do algoritmo ter sido denido para adaptar a taxa de upload, a adaptação
poderia ter sido feita na taxa de download utilizando os mesmos princípios, bastando
perceber que ambos os métodos lidam com os mesmos fatores e objetivos.
Apesar da simplicidade do algoritmo, a capacidade de um peer ter acesso a
informação da quantidade de réplicas de cada pedaço do swarm de maneira frequente
é fundamental para se atingir um bom desempenho. Tais estatísticas, assim como
descrito no capítulo 2, podem ser estimadas pelos clientes localmente a partir de
informações dos vizinhos.
Com a ideia de que a redução da taxa de upload pode gerar um aumento da
vazão, é possível dizer que existe um conjunto de taxas ótimo considerando as taxas
possíveis em todas as congurações de quantidades de réplicas. Entretanto, até
o presente trabalho não foram estudadas maneiras de realizar essa otimização de
20
maneira eciente em termos computacionais.
Modelos estocásticos presentes no capítulo 7 apontam uma melhora signicativa
no desempenho do sistema ao se utilizar essa estratégia, entretanto uma abordagem
experimental não foi feita até o presente trabalho. Além disso tal política ainda
carece de uma análise matemática mais formal, mesmo que simplicada, com o
objetivo de se obter regiões de estabilidade e limites superiores para a vazão nessa
estratégia.
21
Capítulo 5
Modelos Markovianos
Para a avaliação da performance do protocolo BitTorrent foram modeladas cadeias
de Markov de tempo contínuo com espaço de estados Ω e matriz de taxas de tran-
sições entre estados Q. Tais cadeias de Markov foram baseadas no modelo descrito
em [6], porém com alguns ajustes na notação, denições para um maior número de
políticas, e extensão para um sistema aberto (ver seção 5.2).
Dessa maneira foi possível comparar diversos algoritmos e parâmetros de maneira
objetiva e matematicamente embasada. Para a construção dos modelos foi consid-
erado que o arquivo sendo transmitido é divido em K pedaços de tamanhos iguais.
Aqui são feitas duas abordagens, a primeira consiste de um sistema fechado em
que o tamanho do swarm, ou seja, o número de peers no sistema, é constante ao
longo do tempo e igual à N . Já um sistema aberto considera que os peers chegam
ao swarm de acordo com uma taxa λ distribuída exponencialmente, e portanto o
tamanho do swarm varia ao longo do tempo. Apesar do sistema aberto ser mais el
a um swarm real o sistema fechado permite modelar um cenário de saturação do
swarm.
5.1 Modelo de um Sistema Fechado
Em um sistema fechado o tamanho do swarm é constante ao longo do tempo e igual
à N . Para atingir esse número constante os peers deixam o sistema assim que com-
pletam seus downloads e cada saída gera a entrada de um novo peer que não possui
pedaços. Assim como foi feito em análises anteriores se considera um caso homogê-
neo onde o servidor possui capacidade de upload U e os peers capacidade de upload
e download µ pedaços por segundo constantes no tempo e seguindo distribuições
exponenciais.
Seja o conjunto de pedaços F = 1, ..., K e C o conjunto de subconjuntos de
F . Cada elemento do conjunto S = C \ F representa uma possível conguração
de pedaços que um peer pode possuir. Tal conguração é chamada de assinatura,
22
sendo que a cardinalidade do conjunto S é n = |S| = 2K − 1. O conjunto F não
consta em S pelo fato dos peers deixarem o swarm imediatamente após concluírem
o download de todos os pedaços, não existindo assim a necessidade de se representar
essa assinatura no modelo.
Uma estratégia ingênua para a escolha do espaço de estados seria manter a
assinatura de cada peer no sistema, porém, devido a simetria do cenário tratado é
possível uma escolha do espaço de estados mais eciente. Seja ωs o número de peers
com a assinatura s ∈ S. Um estado ω ∈ Ω é caracterizado pelo número de peers
com cada assinatura possível, ou seja, ω = (ws1 , ..., wsn), sendo quen⋃i=1
si = S e
si 6= sj ∀i 6= j.
Um peer de assinatura s passa a ter uma nova assinatura ao receber um pedaço
que ainda não possui. A função T (s, i) denida a seguir mapeia qual a nova assi-
natura de um peer quando o mesmo possui assinatura s e recebe o pedaço i quando
i /∈ s.
T (s, i) =
s ∪ i, se |s| < K − 1
∅, caso contrário(5.1)
Sejam RS(s, i) e RP (s, i) funções que representam a taxa agregada de transição
dos peers com assinatura s para T (s, i) fornecida respectivamente pelo servidor e
pelo conjunto de peers no swarm. A taxa de transição total será dada então por
R(s, i) = RS(s, i) + RP (s, i). As funções RS e RP são denidas de acordo com a
estratégia de seleção de pedaço e peers adotadas. Para facilitar a notação algumas
denições são feitas: Bs consiste do conjunto de pedaços úteis a um peer com
assinatura s e que são menos replicados no swarm. Já Bs′s é o conjunto de pedaços
que um peer com assinatura s′ possui e que um peer com assinatura s não possui
e são menos replicados no sistema. M representa o conjunto de assinaturas dos
peers mais desfavorecidos em termos de pedaços baixados no sistema, sendo que
apenas assinaturas presentes no swarm são consideradas. A seguir se encontram
alguns exemplos de denições dessas funções para diferentes políticas abordadas no
presente trabalho:
• Random Peer/Random Useful Piece
RS(s, i) =
ωsUN(K−|s|) , se i /∈ s
0, caso contrário(5.2)
RP (s, i) =
ωsµN−1
∑s′∈Si∈s′
ωs′|s−s′| , se i /∈ s
0, caso contrário
(5.3)
23
• Random Peer/Rarest Useful Piece
RS(s, i) =
ωsUN |Bs| , se i /∈ s; i ∈ Bs
0, caso contrário(5.4)
RP (s, i) =
ωsµN−1
∑s′∈Si∈s′
ωs′|Bs′s|
, se i /∈ s; i ∈ Bs
0, caso contrário
(5.5)
• Most Deprived Peer/Random Useful Piece
RS(s, i) =
ωsU
(K−|s|)∑
s′∈M
ωs′, se i /∈ s
0, caso contrário(5.6)
RP (s, i) =
ωsµ
∑s′∈Si∈s′
ωs′
|s−s′|( ∑
s′′∈M
ωs′′−1(s′∈M)
) , se i /∈ s
0, caso contrário
(5.7)
• Most Deprived Peer/Rarest Useful Piece
RS(s, i) =
ωsU
|Bs|∑
s′∈M
ωs′, se i /∈ s
0, caso contrário(5.8)
RP (s, i) =
ωsµ
∑s′∈Si∈s′
ωs′
|Bs′s|( ∑
s′′∈M
ωs′′−1(s′∈M)
) , se i /∈ s
0, caso contrário
(5.9)
Caso as políticas de seleção de taxas de upload sejam utilizadas basta trocar as
taxas µ e U pelas respectivas taxas adaptadas, assim como foi descrito no capítulo 4.
A partir das possíveis transições entre assinaturas e as taxas agregadas de tran-
sições dos peers com determinada assinatura é possível denir quais serão as taxas
da matriz de transição entre estados Q. A m de facilitar a notação se dene o vetor
es com a mesma dimensão de ω possuindo todas as coordenadas zero com exceção
da coordenada referente à assinatura s que possui valor 1. Se ωs > 0, a taxa de
transição entre os estados ω e ω − es + eT(s,i) será dada por:
q(ω,ω − es + eT(s,i)) = R(s, i) (5.10)
As taxas não descritas aqui são denidas como tendo valor zero.
24
A métrica escolhida para avaliar as estratégias é a vazão (taxa na qual os peers
completam o download do arquivo inteiro). A vazão é calculada a partir do modelo
vericando a taxa agregada das transições na cadeia de Markov que representam
saídas de peers do swarm. Considerando π o vetor de probabilidades do estado
estacionário e πω a probabilidade estacionária do estado ω, a vazão é denida por:
vazao =∑ω∈Ω
K∑i=1
ωF\i>0
πωq(ω,ω − eF\i + e∅) (5.11)
Mesmo fazendo uso das possíveis simetrias dos estados, a cardinalidade do espaço
de estados cresce exponencialmente com o aumento de N . Dessa maneira a solução
da cadeia de Markov ou mesmo uma simulação precisa só pode ser feita com um
número bastante limitado de peers e pedaços.
5.2 Modelo de um Sistema Aberto
Em um sistema aberto os peers chegam ao sistema de acordo com uma taxa λ
distribuída exponencialmente. Para a criação desse modelo é necessário limitar o
número máximo de usuários no sistema para assim ter uma cadeia de Markov com
espaço de estados nito e conseguir resolver a cadeia. Para isso é denido que o
número máximo de peers no swarm é N ′. Essa estratégia, mapeando em um swarm
real, signica que o sistema limita o número de usuários no sistema, não permitindo
que clientes entrem no swarm quando este atinge um tamanho máximo.
Em um sistema aberto as assinaturas e o estado são os mesmos do sistema
fechado. As funções RS e RP também são as mesmas. Já a função T (s, i) é ligeira-
mente diferente.
Quando i /∈ s e |s| < K − 1:
T (s, i) = s ∪ i (5.12)
Porém, quando |s| = K − 1 a transição da assinatura s acontece para nenhuma
outra assinatura, ou seja, a saída de um peer não gera a entrada automática de
outro peer. As taxas entre estados também são denidas de maneira diferente.
Se |s| < K − 1 e ωs > 0:
q(ω,ω − es + eT(s,i)) = R(s, i) (5.13)
Se |s| = K − 1 e ωs > 0:
q(ω,ω − es) = R(s, i) (5.14)
25
Se w∅ < N ′:
q(ω,ω + e∅) = λ (5.15)
As taxas não descritas aqui são denidas como tendo valor zero.
vazao =∑ω∈Ω
K∑i=1
ωF\i>0
πωq(ω,ω − eF\i) (5.16)
A cadeia de Markov modelada para um sistema fechado possui espaço de estados
nito. Entretanto, caso o modelo for de um sistema aberto existe a possibilidade
do one club crescer indenidamente fazendo, portanto, que o espaço de estados seja
innito, a não ser que o modelo limite o tamanho máximo do swarm.
Considerando um sistema que tende o surgimento da síndrome do pedaço fal-
tante, no sistema fechado a vazão máxima atingida pode ser maior do que em um
sistema aberto sem truncamento, utilizando os mesmo parâmetros é claro. Isso
ocorre devido ao fato de que no sistema fechado há a probabilidade não nula associ-
ada à estados em que uma fração de peers fora do one club seja signicativa, o que
ocorre devido ao número de peers nito e constante.
5.3 Exemplo
Por questões de ilustração, a seguir é apresentado gracamente um modelo de um
sistema fechado gerado para uma quantidade pequena de pedaços e peers. Assim
como descrito anteriormente, o estado consiste do vetor denido como (número de
peers com assinatura 00, número de peers com assinatura 01, número de peers com
assinatura 10). As políticas utilizadas foram Most Deprived Peer, Rarest Useful
Piece e Taxas de Upload Baseadas na Raridade dos Pedaços, já os parâmetros
utilizados são:
• N = 3
• K = 2
• µ = 0.5 pedaços/segundo
• µ′ = 0.05 pedaços/segundo
• U = 1.0 pedaços/segundo
26
3,0,0
2,0,1
2,1,0
1,1,1
1,0,2
1,2,0
0,1,2
0,2,1
0,0,3
0,3,0
0.5
0.5
0.05
1.0
1.0
0.05
1.0
1.0
1.0
0.1
1.0
0.1
1.17
0.42
1.17
0.42
1.0
1.0
Figura 5.1: Exemplo de uma Cadeia de Markov que Representa um Sistema P2P do
Tipo BitTorrent. O estado consiste do vetor denido como (número de peers com
assinatura 00, número de peers com assinatura 01, número de peers com assinatura
10)
27
Capítulo 6
Experimentos
Com o intuito de apresentar uma justicativa experimental para existência da sín-
drome do pedaço faltante foi criado um ambiente de software capaz de criar, geren-
ciar e analisar um experimento de um swarm através de uma implementação do
protocolo BitTorrent. Para isso foi utilizada uma implementação do BitTorrent
chamada libtorrent, e os experimentos foram realizados na plataforma de testes em
redes GENI [8]. Além da detecção dessa síndrome o experimento também permite
que sejam feitas comparações da vazão experimental utilizando diferentes políticas.
6.1 GENI
O Global Environment for Network Innovations (GENI) consiste de um projeto da
National Science Foundation (NSS) cujo objetivo é prover um laboratório virtual
para a exploração de soluções de engenharia em redes e sistemas distribuídos em
larga escala. A infraestrutura possibilita que experimentos utilize diversos recursos,
como por exemplo, PCs físicos e virtuais, links, roteadores, roteadores programáveis,
etc. O GENI é um testbed compartilhado onde múltiplos usuários podem executar
experimentos simultaneamente, fato que é possível devido à técnicas de virtualização
que permitem a partilha dos recursos de rede entre redes virtuais.
No GENI, um experimento deve fazer parte de um projeto que organiza um
estudo sendo realizado na plataforma, contendo as pessoas e os experimentos en-
volvidos. Um projeto é criado por um único responsável chamado de Project Lead
(apenas professores ou membros seniors de uma organização podem ser Project Lead,
estudantes por exemplo, não podem ser). Cada projeto pode ter vários membros, e
cada usuário pode estar associado à diversos projetos.
O GENI possui uma infraestrutura construída por um conjunto de aggregates,
que são responsáveis por oferecer diversos recursos como armazenamento, processa-
mento e recursos de rede. Cada aggregate contribui com recursos para a comunidade
usuária do GENI porém mantém sua própria autonomia para manter sua infraestru-
28
tura, além disso grande parte dos aggregates proveem canais de comunicação com
a Internet, permitindo assim a comunicação com redes fora do GENI. A maioria
dos recursos do GENI consiste de máquinas com o sistema operacional Linux, sendo
que diversas distribuições são disponibilizadas, além da possibilidade de se criar
uma própria imagem a ser utilizada em experimentos, dessa forma tais máquinas
usualmente podem ser acessadas utilizando SSH.
Para a realização de um experimento, supondo que o projeto já foi estabelecido,
deve ser criado um slice. O conceito de slice consiste em uma unidade de isolamento
para experimentos, sendo que um experimento é executado em um slice e apenas
membros daquele slice podem fazer alterações nele. Através desse isolamento se
torna possível que o GENI seja um testbed compartilhado sem que experimentos
simultâneos inuenciem um ao outro. O slice pode ser criado por qualquer usuário
associado ao projeto e os participantes desse slice são denidos pelo seu próprio
criador, com exceção do Project Lead que sempre tem acesso aos slices do projeto.
Um slice contém todos os recursos (VMs, PCs, links de rede, etc) alocados para o
experimento, sendo que tais recursos podem ser obtidos de mais de um aggregate.
Os usuários solicitam recursos de um aggregate utilizando uma API chamada
GENI Aggreagate Manager API ou GENI AM API. Essa API permite que os
usuários: listem os recursos disponíveis em um aggregate; solicite recursos especí-
cos para serem alocados em um slice; liste o status (operacional, alocando recurso,
solicitação falhou) dos recursos alocados; e remova os recursos reservados ao slice.
A solicitação através dessa API acontece com o envio de um XML por parte do
usuário indicando os recursos para serem reservados, e o aggregate então envia um
XML com os recursos que foram efetivamente alocados.
6.2 Software de Experimentação Desenvolvido
Devido as vantagens de se obter recursos isolados, ou seja, integralmente destinados
ao experimento, e pela disponibilidade de recursos que podem ser reservados, a
plataforma GENI foi adotada no presente trabalho.
A libtorrent foi a implementação do protocolo BitTorrent utilizada nos experi-
mentos. Sua escolha foi baseada no fato dessa ferramenta ser open-source, possibili-
tando assim que fosse adaptada, além de ter uma comunidade ativa de usuários. As
modicações feitas foram referentes as políticas de escolha de peers na transmissão,
sendo que foram implementadas as estratégias de Random Peer e Most Deprived
Peer que até então não constavam na implementação da libtorrent. Já para o papel
do tracker foi utilizado o software opentracker, que consiste de um projeto também
aberto que não necessitou de modicações.
Para os experimentos foi optado pela utilização de máquinas virtuais por ser
29
um recurso mais abundante na infraestrutura do GENI. Cada máquina virtual alo-
cada tem associada algumas entidades da dinâmica do protocolo, sendo que todas
essas máquinas pertencerão a mesma VLAN. Um cliente BitTorrent que faz o papel
do publisher e o tracker possuem cada um uma máquina virtual exclusiva. Já as
máquinas virtuais referentes aos peers podem estar associadas a mais de um peer
simultaneamente, sendo que a quantidade de peers por máquina virtual é um dos
parâmetros do experimento. A limitação das taxas de upload ocorrem através da
utilização da própria libtorrent.
No experimento é considerado um sistema fechado em uma situação com taxas
homogêneas, dessa maneira é possível planejar um experimento alocando um número
xo de máquinas virtuais. Para atingir um cenário de um sistema fechado, quando
um peer acaba o download do arquivo o cliente remove o arquivo anunciando sua
saída aos seus vizinhos e ao tracker, e após isso reinicia o processo de download
do mesmo arquivo. Nos experimentos elaborados o cliente BitTorrent que repre-
senta o publisher possui a mesma implementação de um peer comum, porém possui
estratégias e taxas diferentes das dos demais, sendo que tais características são con-
guráveis.
O ambiente de software construído neste trabalho é responsável por criar, geren-
ciar, analisar e destruir um experimento, sendo que nesse momento um projeto e um
slice já devem ter sido criados no GENI. O processo de criação é iniciado em uma
máquina fora da plataforma GENI que irá executar o software de controle do ex-
perimento. Primeiramente um arquivo de conguração deve ser elaborado contendo
informações referentes ao experimento, como por exemplo, número de pedaços que o
arquivo distribuído deve ser particionado, número de peers, políticas adotadas, taxas
de upload dos peers e servidor, tempo de duração do experimento, etc. Uma vez que
esse arquivo é criado a ferramenta automaticamente aloca os recursos necessários no
GENI, cria o arquivo a ser distribuído e o arquivo metainfo a ser utilizado, congura
o experimento movendo os clientes BitTorrent e arquivos associados ao experimento
para as respectivas máquinas virtuais, e sincroniza o início do experimento.
A ferramenta executada fora do GENI também é responsável por, após o término
do experimento, fazer o download dos logs gerados nas máquinas virtuas. A análise
desses logs procura por possíveis falhas que possam ter acontecido, além de gerar
grácos referentes ao experimento e realizar cálculos de métricas de vazão. Final-
mente, após todos os passos anteriores o software desaloca os recursos do GENI,
encerrando todo o processo.
30
Capítulo 7
Resultados
7.1 Modelos Markovianos
Nesta seção são apresentados alguns dos resultados obtidos utilizando os modelos
estocásticos apresentados no capítulo 5.
7.1.1 Desempenho da Estratégia de Serviço Modicado dos
Peers com K − 1 Pedaços
Com o objetivo de analisar a escalabilidade de um sistema P2P fechado é comum
apresentar grácos que relacionam o tamanho do swarm com a respectiva vazão,
permitindo assim vericar o comportamento do sistema quando N (número de peers
no swarm) cresce.
Na gura abaixo se encontra uma curva que mostra o desempenho para diferentes
valores de N de um sistema P2P fechado onde tanto os peers quanto o publisher
adotam as políticas Most Deprived Peer/Rarest Useful Piece/Serviço Modicado
dos Peers com K − 1 Pedaços. Os parâmetros utilizados foram: K = 2, U = 0.1,
µ = 0.5, µ′ = 0.05.
31
Figura 7.1: Número de Peers x Vazão utilizando a estratégia de serviço modicado
dos peers com K − 1 pedaços
O formato especíco da curva acima é recorrente em diversas estratégias ado-
tadas. Para valores pequenos do número de peers o swarm possui escalabilidade
próxima de linear, onde a capacidade de serviço de cada peer é usada de maneira
eciente. Entretanto, enquanto N cresce o sistema rapidamente atinge um ponto
de vazão máxima e a partir dai o aumento de N gera o decrescimento da vazão até
ocorrer uma situação de convergência. Dessa forma, considerando um número de
peers muito grande, a inserção ou remoção de peers não contribui para a alteração
da vazão do swarm, demonstrando que os recursos físicos disponíveis não são bem
aproveitados.
Abaixo se encontra outro gráco de um sistema com os mesmos parâmetros e
políticas do exemplo anterior, com exceção do parâmetro µ′. São mostradas três
curvas referentes à três valores distintos de µ′.
32
Figura 7.2: Número de Peers x Vazão utilizando diferentes valores de µ′ com a
estratégia de serviço modicado dos peers com K − 1 pedaços
No gráco acima é possível perceber que quanto menor for µ′ melhor é o de-
sempenho obtido, apesar do fato das três curvas convergirem para o mesmo ponto
de vazão quando N tende à innito. Entretanto, assim como descrito no capítulo
4, esse crescimento de vazão não é ilimitado com a diminuição de µ′. A seguir, na
Figura 7.3, é apresentado um gráco que relaciona µ′ com a respectiva vazão para
um sistema fechado onde os peers adotam as estratégias Random Peer/Random Use-
ful Piece e o publisher adota Most Deprived Peer/Rarest First Piece. Os seguintes
parâmetros foram utilizados K = 3, U = 0.2, µ = 1.0, N = 10.
33
Figura 7.3: µ′ x Vazão
Assim como descrito anteriormente, é vericado que com a diminuição de µ′ a
vazão aumenta até atingir um ponto máximo, a partir desse máximo a diminuição
de µ′ gera decrescimento da vazão, ou seja, o servidor se torna um gargalo.
7.1.2 Desempenho do Algoritmo de Seleção de Taxas de Up-
load Baseado na Raridade dos Pedaços
A seguir é apresentado um gráco que relaciona o tamanho do swarm com a re-
spectiva vazão em um sistema que os peers e o publisher utilizam as estratégias
Most Deprived Peer/Rarest Useful Piece/Algoritmo de Seleção de Taxas de Upload
Baseado na Raridade dos Pedaços. Os parâmetros utilizados são K = 2, U = 0.1,
µ = 0.5, µ′ = 0.05, ou seja, os mesmos parâmetros e estratégias do gráco
7.1, com exceção da adição da política de seleção de taxas de acordo com a raridade
do pedaço sendo distribuído.
34
Figura 7.4: Número de Peers x Vazão utilizando o algoritmo de seleção de taxas de
upload baseado na raridade dos pedaços
É possível perceber que o algoritmo proposto possui um desempenho signicati-
vamente melhor do que as opções de não utilizá-lo ou utilizar a política de serviço
modicado para peers com K − 1 pedaços. Também é importante notar que para a
situação descrita o algoritmo alcança uma escalabilidade linear. Apesar do resultado
promissor, devido ao fato de não se ter uma avaliação mais teórica sobre possíveis
regiões de estabilidade e limites superiores para a vazão, não se sabe se o algoritmo
torna o sistema estável ou não.
Caso o sistema continue instável, a curva N versus Vazão deve possuir o mesmo
formato das curvas em outras estratégias, ou seja, enquanto N cresce a vazão au-
menta, atinge um máximo e depois diminui até convergir. Desse modo o gráco
apresentado acima seria apenas o início dessa outra curva descrita que possui uma
característica linear no seu início.
7.1.3 Desempenho de um Sistema Aberto
De maneira distinta ao que vinha sendo feito com sistemas fechados, em um sistema
aberto (ver capítulo 5) a escalabilidade será aqui analisada a partir de grácos que
relacionam λ (taxa de chegada dos peers ao swarm) versus Vazão. Abaixo se en-
contram duas curvas comparando a performance da estratégia de serviço modicado
para peers com K − 1 pedaços em um sistema aberto em que os peers adotam as
estratégias Random Peer/Random Useful Piece e o publisher adota Most Deprived
Peer/Rarest First Piece. Os seguintes parâmetros foram utilizados: K = 3, U = 0.2,
35
µ = 1.0. O tamanho máximo do swarm foi limitado em N ′ = 17 peers.
Figura 7.5: Número de Peers x Vazão em um sistema aberto
O gráco acima mostra que em um sistema aberto a estratégia de serviço mod-
icado para os peers com K − 1 possui um melhor desempenho do que a opção de
não usar essa política. O formato da curva difere da de um sistema fechado já que
a vazão não decresce em nenhum momento, apesar de que a partir de determinado
ponto a vazão se mantém com pouca variação. A justicativa desse padrão pode
estar relacionada com a característica de limitação do tamanho do swarm.
7.2 Experimentos
Nesta seção são apresentados os resultados obtidos nos experimentos utilizando a
ferramenta desenvolvida que foi descrita no capítulo 6. Tais experimentos foram
realizados em cenários de sistemas fechados.
7.2.1 Evidência da Existência da Síndrome do Pedaço Fal-
tante
A seguir se encontram sete grácos, um para cada assinatura possível de um peer
assumir em um experimento de um sistema fechado com K = 3, sendo que as
possíveis assinaturas são 000, 001, 010, 011, 100, 101, 110. Os grácos mostram a
fração de peers com uma determinada assinatura ao longo do tempo de experimento.
Nesse experimento os peers adotam as estratégias Random Peer/Random Useful
36
Piece e o publisher adota Most Deprived Peer/Rarest First Piece. Já os parâmetros
utilizados foram K = 3, U = 0.2, µ = 1.0, N = 400.
Figura 7.6: Tempo x Fração de Peers referente à assinatura 000 em um experimento
com N = 400
Figura 7.7: Tempo x Fração de Peers referente à assinatura 001 em um experimento
com N = 400
37
Figura 7.8: Tempo x Fração de Peers referente à assinatura 010 em um experimento
com N = 400
Figura 7.9: Tempo x Fração de Peers referente à assinatura 011 em um experimento
com N = 400
38
Figura 7.10: Tempo x Fração de Peers referente à assinatura 100 em um experimento
com N = 400
Figura 7.11: Tempo x Fração de Peers referente à assinatura 101 em um experimento
com N = 400
39
Figura 7.12: Tempo x Fração de Peers referente à assinatura 110 em um experimento
com N = 400
É vericado a partir dos grácos acima que a assinatura 110 domina em relação
à sua ocorrência no experimento. Na grande maioria do tempo a maior parte dos
peers possuem a assinatura 110, sendo que a fração de peers com essa assinatura
se mantém muito próxima à 1 ao longo de todo experimento, fato que pode ser
considerado como uma ocorrência da síndrome do pedaço faltante, onde o pedaço
de índice 3 é o pedaço faltante e os peers com assinatura 110 caracterizam o one
club.
A segunda assinatura mais presente é a 000, porém possui uma fração de peers
próxima a zero ao longo do experimento. O fato de ser a segunda mais presente se
deve a saída dos peers do one club que automaticamente geram a entrada de peers
com zero pedaços. Já as outras assinaturas se mostram com presença praticamente
nula no swarm, sendo que apenas no início algumas outras assinaturas se mostram
presentes enquanto o one club está em processo de rápido crescimento.
A tendência é que, para valores ainda maiores do que o N utilizado, se encontre
grácos onde a assinatura 000 que com fração de peers mais próxima de zero
e a assinatura referente ao one club que ainda mais próxima de 1 ao longo do
experimento. A m de exemplicar tal fato, a seguir é apresentado dois grácos
de um experimento com N = 150 referentes a assinatura 000 e 101 (one club desse
novo experimento). É possível perceber que no experimento com N = 150 as curvas
são menos próximas à fração de peers 0 e 1 em relação ao experimento anterior com
N = 400. Nesse segundo experimento as outras assinaturas seguem o mesmo padrão
40
do experimento anterior e as estratégias e parâmetros, com exceção de N , são os
mesmos.
Figura 7.13: Tempo x Fração de Peers referente a assinatura 000 em um experimento
com N = 150
Figura 7.14: Tempo x Fração de Peers referente a assinatura 110 em um experimento
com N = 150
41
Capítulo 8
Conclusões e Trabalho Futuro
A partir dos resultados apresentados no capítulo 7 é possível vericar a existência
experimental da síndrome do pedaço faltante. Também é possível notar que peque-
nas e simples estratégias como a do serviço modicado para peers com K−1 pedaços
podem gerar um impacto positivo e signicativo na performance de um sistema P2P.
Além disso, o algoritmo proposto se mostra promissor através dos modelos estocás-
ticos desenvolvidos, porém ainda necessita de um maior aprofundamento na análise
de regiões de estabilidade e na perspectiva experimental.
A partir da análise feita também é possível notar que a síndrome do pedaço
faltante é um ponto crucial para um bom desempenho de um swarm, dessa maneira
métodos que previnam essa síndrome podem se tornar fundamentais para uma boa
performance. Através das publicações recentes e do estudo aqui feito se percebe um
certo direcionamento para a pesquisa em temas relacionados à seleção de taxas de
upload, que até pouco tempo atrás não havia sido explorado na literatura.
Como trabalho futuro constam: extensão da ferramenta de experimentação para
lidar com sistemas abertos; criação de soluções experimentais para a detecção local
pelos peers da ocorrência da síndrome do pedaço faltante; elaboração de modelos
estocásticos mais ecientes em termos de complexidade computacional a m de se
obter resultados para swarms de tamanhos maiores; obtenção teórica a respeito de
regiões de estabilidade na utilização do algoritmo de seleção de taxas de upload
baseado na raridade dos pedaços; e análise experimental do algoritmo proposto.
42
Referências Bibliográcas
[1] KUROSE, J., ROSS, K. Computer Networking A Top-Down Approach. 6 ed. ,
Pearson, 2013.
[2] MENASCHÉ, D. S., ROCHA, A. A., DE SOUZA E SILVA, E., LEÃO, R. M.,
TOWSLEY, D. Stability of peer-to-peer swarming systems. In: SBRC,
2012.
[3] HAJEK, B., ZHU, J. The Missing Piece Syndrome in Peer-to-Peer Com-
munication, CoRR, v. abs/1002.3493, 2010. Disponível em: <http:
//arxiv.org/abs/1002.3493>.
[4] ZHU, J., HAJEK, B. Stability of a Peer-to-Peer Communication System,
CoRR, v. abs/1110.2753, 2011. Disponível em: <http://arxiv.org/
abs/1110.2753>.
[5] DE SOUZA E SILVA, E., MENASCHÉ, D. S., LEÃO, R. M., TOWSLEY, D.
Sobre a Capacidade de Serviço de Sistemas P2P. In: SBRC, 2014.
[6] DE SOUZA E SILVA, E., LEÃO, R. M. M., MENASCHÉ, D. S., TOWSLEY,
D. Scalability Issues in P2P Systems, CoRR, v. abs/1405.6228, 2014.
Disponível em: <http://arxiv.org/abs/1405.6228>.
[7] LEGOUT, A., URVOY-KELLER, G., MICHIARDI, P. Rarest First and Choke
Algorithms Are Enough. In: Proceedings of the 6th ACM SIGCOMM
Conference on Internet Measurement, IMC '06, pp. 203216, New York,
NY, USA, 2006. ACM. ISBN: 1-59593-561-4. doi: 10.1145/1177080.
1177106. Disponível em: <http://doi.acm.org/10.1145/1177080.
1177106>.
[8] DUERIG, J., RICCI, R., STOLLER, L., et al. Getting Started with GENI: A
User Tutorial, SIGCOMM Comput. Commun. Rev., v. 42, n. 1, pp. 72
77, jan. 2012. ISSN: 0146-4833. doi: 10.1145/2096149.2096161. Disponível
em: <http://doi.acm.org/10.1145/2096149.2096161>.
43
[9] MENASCHÉ, D. S., DE A. ROCHA, A. A., DE SOUZA E SILVA, E. A.,
TOWSLEY, D., MERI LEÄO, R. M. Implications of Peer Selection
Strategies by Publishers on the Performance of P2P Swarming Sys-
tems, SIGMETRICS Perform. Eval. Rev., v. 39, n. 3, pp. 5557, dez.
2011. ISSN: 0163-5999. doi: 10.1145/2160803.2160859. Disponível em:
<http://doi.acm.org/10.1145/2160803.2160859>.
[10] MENASCHÉ, D. S., DE ARAGÃO ROCHA, A. A., DE SOUZA E SILVA,
E., LEÃO, R. M. M., TOWSLEY, D. F., VENKATARAMANI, A. Es-
timating Self-Sustainability in Peer-to-Peer Swarming Systems, CoRR,
v. abs/1004.0395, 2010. Disponível em: <http://arxiv.org/abs/1004.
0395>.
[11] DE SOUZA E SILVA, E., FIGUEIREDO, D. R., LEÃO, R. M. The TAN-
GRAMII Integrated Modeling Environment for Computer Systems and
Networks, SIGMETRICS Perform. Eval. Rev., v. 36, n. 4, pp. 6469,
mar. 2009. ISSN: 0163-5999. doi: 10.1145/1530873.1530886. Disponível
em: <http://doi.acm.org/10.1145/1530873.1530886>.
[12] STEWART, W. J. Probability, Markov Chains, Queues, and Simulation: The
Mathematical Basis of Performance Modeling. Princeton University Press,
2009.
[13] MURAI, F. Sobre dois fenômenos em redes P2P do tipo BitTorrent. Master
thesis, UFRJ, Rio de Janeiro, Rio de Janeiro, Brasil, 2011.
[14] LIBTORRENT. libtorrent. http://www.libtorrent.org/, 2015. Acessado
em Fevereiro de 2015.
[15] GENI. GENI Concepts. http://groups.geni.net/geni/wiki/
GENIConcepts, 2015. Acessado em Fevereiro de 2015.
[16] BITTORRENT.ORG. The BitTorrent Protocol Specication. http://www.
bittorrent.org/beps/bep_0003.html, 2015. Acessado em Fevereiro de
2015.
[17] . Bittorrent Protocol Specication. https://wiki.theory.org/
BitTorrentSpecification, 2015. Acessado em Fevereiro de 2015.
44
Recommended