O tema escolhido para o trabalho foi "Anatomia do BitTorrent: a Ciência da Computação por trás do protocolo", onde será estudado a versão mais usada do protocolo de compartilhamento de arquivos BitTorrent e sua implementação pelo cliente de código aberto Transmission.
Desde o início da história da computação, o compartilhamento de dados é uma ação natural e necessária para o trabalho nesta área e que passou a ser mais comum com a criação dos dispositivos de armazenamento de dados sob a forma de arquivos e, anos depois, com o advento da Internet. Porém, foi a partir de 1999, com o surgimento do Napster, que as redes ponto-a-ponto (peer-to-peer, ou p2p) se tornaram populares e passaram a ser o método mais usado.
A partir daí, o p2p veio se desenvolvendo até que, em 2003, Bram Cohen divulgou um método mais eficiente de publicação e localização de arquivos do que o utilizado naquela época: o protocolo BitTorrent. Assim, muitos programas de compartilhamento BitTorrent passaram a ser desenvolvidos, e o protocolo foi sendo estudado pela área acadêmica, passando por algumas melhorias.
Atualmente, o BitTorrent contém conceitos das áreas de teoria dos jogos, estrutura de dados como tabelas de dispersão (mais conhecidas como tabelas hash) e de topologias de rede otimizadas, se tornando a forma mais eficiente e utilizada de compartilhamento de arquivos via Internet atualmente.
O objetivo do trabalho é estudar e analisar o protocolo BitTorrent em suas três componentes principais (teoria dos jogos, tabelas hash e teoria de redes) e identificar a sua implementação feita pelo cliente de código aberto Transmission, fazendo uma ponte entre teoria e prática.
A primeira atividade foi iniciar um estudo geral do protocolo como forma de aprendizagem inicial.
Depois, foram pesquisados programas cliente de BitTorrent que contém seu código aberto, para que se pudesse avaliar qual daqueles clientes seriam usados na avaliação de código.
Por fim, foram pesquisadas e adquiridas referências acadêmicas que estudaram a eficiência do protocolo existente na época ou que implementavam melhorias mais específicas.
Como cronograma, está sendo planejado, informalmente:
| Atividade / Mês | Fev-Mar | Abr-Mai | Jun-Jul | Ago-Set | Out | Nov | Dez |
|---|---|---|---|---|---|---|---|
| Estudo inicial do protocolo | X | X | |||||
| Pesquisa de referências | X | X | X | X | X | X | |
| Monografia | X | X | X | X | X | ||
| Estudo de código | X | X | X | X | X | ||
| Apresentação | X | X | X |
Contextualização e história do protocolo BitTorrent
Descrição rasa do protocolo BitTorrent, sem aprofundamento dos conceitos usados no mesmo.
Descrição detalhada de cada uma das partes específicas do protocolo, contextualizando a teoria empregada e a respectiva implementação no programa Transmission.
Aqui estão algumas das referências encontradas para o estudo do TCC. Estão resumidas apenas as que mostraram alguma relevância com o tema.
Analisa vários artigos que sugerem melhorias, como por exemplo subsemeação (subseeding), que é quando se tem um subsemeador (subseeder) entre o semeador (seeder) original e o resto dos nós (comumente chamados de peers), ou ainda a subdivisão de partes do arquivo distribuído entre subseeders a fim de reduzir a carga nos rastreadores (trackers); melhorias no algoritmo olho-por-olho (tit-for-tat) para se obter melhor justiça.
Resumido: melhorias em escalabilidade, disponibilidade, vazão do sistema e justiça.
Foca em uma nova métrica de justiça definida pela razão entre a quantidade de dados enviados e descarregados por cada peer e discute o algoritmo de estrangulamento (choking) original, mostrando que ele não é muito justo, propondo 3 modelos diferentes de choking e simulando-os, mostrando que um peer é tratado com maior justiça quanto maior for a sua taxa de envio (taxa de upload) que ele fornecer outras partes.
Mostrou uma série de experimentos que focaram na análise e compreensão do BitTorrent em diversos cenários, detalhando em 2 métricas principais: utilização da capacidade de upload dos peers, e a injustiça em termos do volume de dados servidos por peers. Assim, comprovaram que o algoritmo tit-for-tat não previne injustiça entre peers em relação à quantidade de dados servidos, e corrigido esse problema combinando peers pelas suas largura de banda de conexão. Além disso, constataram a importância do seed de servir pedaços raros no início e que a política de pedaços raros primeiro é importante para se evitar o "problema do último bloco".
Propõe uma alternativa simples e escalável que faz uso mais inteligente da banda de seeders diminuindo a eficiência dos free-riders, que são peers que não contribuem com recursos dos arquivos sendo compartilhados, e mantendo a eficiência ou melhorando-a dos nós contribuintes.
Altera o algoritmo de funcionamento do BitTorrent para aplicar e melhorar a performance de ambiente de computação em nuvem.
Propõe alterar o algoritmo de seleção de pedaços raros de vizinhos para uma em que esses pedaços sejam priorizados (por pesos) de acordo com a quantidade de pedaços baixados por eles, o que aumenta a cooperação entre peers e, por conseguinte, a eficiência do BitTorrent com relação ao tempo total de download (descarregamento).
A fim de coletar metadados eficientemente das tabelas hash distribuídas (DHT's) baseados no algoritmo Kademlia, o artigo mostra quais foram as otimizações utilizadas para a obtenção dos dados de forma sustentável e distribuída, sem que houvesse prejuízo de eficiência de nós na rede DHT.
Parece antigo. Mediu e estudou o funcionamento do protocolo.
Artigo da época inicial que explica como o algoritmo tit-for-tat busca a eficiência de Pareto e como isso faz com que os níveis de robustez e de utilização de recursos fossem maiores do que outras técnicas cooperativas.
Estudaram o efeito dos free-riders no BitTorrent e concluíram que a maior parte da performance do protocolo não vem do algoritmo tit-for-tat, mas sim da contribuição "altruísta" de uma minoria de peers que possuem alta capacidade de banda. Além disso, mostraram que peers egoístas podem ou não afetar a performance de um enxame (conjunto de nós conectados entre si). Para isso, implementaram um novo cliente (BitTyrant) para tentar responder algumas questões, sem sucesso.
Sugere o uso de codificação LT ("Luby transform codes") para permitir concorrência de download de peers diferentes e o compartilhamento de partes parcialmente baixadas e estuda por simulações que uma melhor performance pode ser atingida se considerar arquivos de tamanho pequeno ou uso sob condições adversas de rede.
A partir de dados coletados de DHTs, estudaram várias propriedades como alcance, latência, vivacidade de nós e de churns (ciclo de um peer que entra na rede, faz o download do arquivo de interesse e desconecta) e identifica uma variedade de problemas como tempos de lookup acima de 1 minuto. Mostram ainda que tabelas DHT de tipo Kademlia que utilizam de roteamento iterativo e a falta de consideração pela vizinhança local causam problemas de corretude e baixa performance. Por fim, identificaram bugs e problemas de design e de segurança, sugerindo correções.
Estudaram abordagens gulosas de exploração do altruísmo da versão original do protocolo que tentavam maximizar dos benefícios dessa ooperação. Para isso, estudaram o BitTyrant, um cliente estratégico implementado na época, concluindo que o desempenho dele se deve mais pelo fato do alto número de conexões que ele cria do que pela disseminação de conteúdo na fase inicial do processo de distribuição.
Propõe um método de melhorar a vazão de dados em enxames pequenos localizando-os nos trackers e rearrajando entre outros enxames.
Implementa um novo cliente chamado BitMate, que é focado para bandas estreitas de conexão com a Internet, e explica que este é melhor do que o protocolo original porque faz o peer compartilhar mais dados com peers de banda semelhantes, recebendo então maior performance de download desses clientes.
Após medir as velocidades de download de milhões de usuários, percebeu-se que o cliente uTorrent alcança maior velocidade que o Vuze. Por isso, os autores realizaram uma engenharia reversa em ambos e descobriram que eles diferem em pontos chave como, por exemplo, na forma em que gerenciam as vizinhanças e como distribuem as banda de upload entre os peers.
Analisa alguns casos de estratégias egoístas que podem ser implementados para burlar a estratégia de cooperação do protocolo.
Tese de doutorado sobre o estudo da performance dos algoritmos utilizados pelo protocolo.
Estudo geral bastante didático e em português do protocolo como um todo, explicando a história, o funcionamento e a teoria por trás dele.
Estuda a formação de topologias de grafos de conexão formados pelos peers e as características dessas redes, concluindo terem achado evidências de "small-worlds" nas redes de peers, na de peers interessados entre si e na de peers que baixaram dados recentemente um do outro. Também encontraram características de rede livre de escala na rede formada por peers que foram desestrangulados por outros.
Mediu a transmissão de pacote de dados TCP de conexões BitTorrent e as modelou segundo distribuições estatísticas.
Propõe mudanças no algoritmo de seleção de peers vizinhos para priorizar os peers que utilizam um mesmo provedor de internet (ISP) e, caso necessário, buscar por peers que estão na mesma região geográfica mas de ISP's diferentes.
Tese de mestrado onde o pesquisador desenvolveu uma aplicação para medir as características de conexão de internet dos usuários finais usando o protocolo BitTorrent. Juntamente usado com outra aplicação, o iPlane, pôde predizer sobre a performance das conexões de Internet.
Propôs 2 modelos analíticos a fim de prever a performance do sistema sob utilização usual em aspectos diferentes: um em estado estacionário, que simula os períodos em que o número de usuários se mantém fixo, e outro sob um olhar dinâmico, simulando usuários novos aparecendo e usuários que com o fim do download saem da rede.
Estudou as diferentes topologias de redes formadas por diferentes swarms, mostrando que o estado inicial não prevê a performance geral. Entre outros pontos abordados, tentam introduzir clusterização de grafos de redes, sugerindo a adição de 2 parâmetros aos trackers para que estes escolham peers pelos cliques.
Procurou uma forma de adicionar QoS (qualidade de serviço) ao protocolo BitTorrent, além de estudar um modelo híbrido que adiciona um superseeder para auxiliar na distribuição de conteúdo.
Estudaram o efeito do gerenciamento de downloads pelo protocolo usando "broadcatching", que é a criação de tarefas de downloads recebidos através de feeds RSS, procurando o intervalo de atualização de feed que melhor contribui com o desempenho.
Estuda o impacto da latência de rede e da perda de pacotes no tempo total de download de arquivos através do protocolo BitTorrent e se clusters de servidores dedicados podem ser usados para reproduzir experimentos realísticos.
Estudo recente que tentou categorizar os enxames pela rede pelo tipo de objeto baixado.
Apresentação que conta como utilizar os DHTs para criar índice de um site de buscas de torrents.
Avalia diversos clientes BitTorrent.
[1] Vishal Misra, Alix L. H. Chow, Leana Golubchik. Improving BitTorrent: A Simple Approach.
[2] Venkata N. Padmanabhan, Ashwin R. Bharambe, Cormac Herley. Analyzing and Improving BitTorrent Performance. Rel. téc. Microsoft Research, 2005.
[3] Walid Dabbous, Ashwin Rao, Arnaud Legout. Can Realistic BitTorrent Experiments Be Performed on Clusters?
[4] Bo Li, Cameron Dale, Jiangchuan Liu. On the Network Topologies Formed in BitTorrent Downloads.
[5] Joseph Peters, Bo Li, Cameron Dale, Jiangchuan Liu. Evolution and Enhancement of Bit-Torrent Network Topologies.
[6] Category:Technical Information — Vuze Wiki, [Online; acessado em maio de 2013]. 2013.
url: http://wiki.vuze.com/w/Category:Technical_Information.
[7] Hongbo Jiang, Wenyu Liu, Yi Wang, Chen Tian, Xue Liu. Improving BitTorrent Traffic Performance by Exploiting Geographic Locality.
[8] Jan-Ming Ho, Chi-Jen Wu, Cheng-Ying Li. Improving the Download Time of BitTorrent-like Systems.
[9] Bram Cohen. Incentives Build Robustness in BitTorrent.
[10] Member, IEEE, Pietro Michiardi, Francesco Albanese, Damiano Carra, Giovanni Neglia. On the Robustness of BitTorrent Swarms to Greedy Peers.
[11] Adrian Popescu, David Erman, Dragos Ilie. BitTorrent Session Characteristics and Models.
[12] Aaron Grunthal. Efficient Indexing of the BitTorrent Distributed Hash Table.
[13] Niklas Carlsson, György Dán. Dynamic Swarm Management for Improved BitTorrent Performance.
[14] Index of BitTorrent Enhancement Proposals. [Online; acessado em maio de 2013]. 2012.
url: http://www.bittorrent.org/beps/bep_0000.html.
[15] Tomas Isdal. Using BitTorrent for Measuring End-To-End Internet Path Characteristics.
[16] D. H. J. Epema, H. J. Sips, J. A. Pouwelse, P. Garbacki. The BitTorrent P2P File-Sharing System: Measurements and Analysis.
[17] K. Y. Lin. Survey on BitTorrent. 2006.
[18] Xiaoyuan Yang, Pablo Rodriguez, Marios Iliofotou, Georgos Siganos. Comparing BitTorrent Clients in the Wild: The Case of Download Speed.
[19] Marinho P. Barcellos, Flávio Roberto Santos, Matheus B. Lehmann, Rodrigo B. Mansilha. Swarming: como BitTorrent Revolucionou a Internet.
[20] Thomas Anderson, Arvind Krishnamurthy, Arun Venkataramani, Michael Piatek, Tomas Isdal. Do incentives build robustness in BitTorrent?
[21] Walfredo Cirne, Francisco Brasileiro, Nazareno Andrade, Jaindson Santana. On the Efficiency and Cost of Introducing QoS in BitTorrent.
[22] Stefano Cucchiella, Paolo Di Francesco. Selfish strategies affecting the BitTorrent protocol.
[23] Nicolae Tapus, Razvan Deaconescu, Razvan Rughinis. A BitTorrent Performance Evaluation Framework.
[24] William Chan, Jan Medval, George Suwala, Tony Bates, Amy Zhang, Ruchir Bindal, Pei Cao. Improving Traffic Locality in BitTorrent via Biased Neighbor Selection.
[25] Marco Grangetto, Matteo Sereno, Salvatore Spoto, Rossano Gaeta. BitTorrent and fountain codes: friends or foes?
[26] Dan S. Wallach, Scott A. Crosby. An Analysis of BitTorrent's Two Kademlia-Based DHTs.
[27] Alex Sherman. Guaranteeing Performance through Fairness in Peer-to-Peer File-Sharing and Streaming Systems.
[28] Anirban Basu, Soumya V. L. "Modified BitTorrent Protocol and its application in Cloud Computing Environment". Em: International Journal of Computer Science, Engineering and Applications (IJCSEA) 2.5 (2012), pp. 23-31.
[29] Richard Thommes, Mark Coates. BitTorrent Fairness: Analysis and Improvements.
[30] David Hock, Simon Oechsner, Zoran Despotovic, Wolfgang Kellerer, Maximilian Michel, Tobias Hoßfeld, Frank Lehrieder. Characterization of BitTorrent swarms and their distribution in the Internet.
[31] Umar Saif, Umair Waheed Khan. BitTorrent for the Less Privileged.
[32] Konstantinos Psounis, Wei-Cherng Liao, Fragkiskos Papadopoulos. Performance Analysis of BitTorrent-like Systems in Heterogeneous Networks.
[33] Konstantinos Psounis, Constantinos Psomas, Wei-Cherng Liao, Fragkiskos Papadopoulos. Modelling BitTorrent-like systems with many classes of users.
[34] Theory.org Wiki. Main Page — Theory.org Wiki, [Online; acessado em maio de 2013]. 2013.
url: https://wiki.theory.org/index.php?title=Main_Page&oldid=216.
[35] Wikipedia. File sharing — Wikipedia, The Free Encyclopedia. [Online; acessado em maio de 2013]. 2013.
url: http://en.wikipedia.org/wiki/File_sharing
[36] Wikipedia. Peer-to-peer — Wikipedia, The Free Encyclopedia. [Online; acessado em maio de 2013]. 2013.
url: http://en.wikipedia.org/wiki/Peer-to-peer
[37] Wikipedia. Peer-to-peer file sharing — Wikipedia, The Free Encyclopedia. [Online; acessado em maio de 2013]. 2013.
url: http://en.wikipedia.org/wiki/Peer-to-peer_file_sharing
[38] Scott Wolchok. Crawling BitTorrent DHTs for Fun and Profit.
[39] Yang Chen, Yongqiang Xiong, Jacky Shen, Hongqiang Liu, Beixing Deng, Xing Li , Zengbin Zhang, Yuan Lin. Experimental Study of Broadcatching in BitTorrent.