BitTorrent

O BitTorrent é um protocolo P2P popular para distribuição de arquivos [BitTorrent, 2009]. No jargão do BitTorrent, a coleção de todos os pares que participam da distribuição de um determinado arquivo é chamada de torrent. Os pares em um torrent fazem o download de blocos de tamanho igual do arquivo entre si, com um tamanho típico de bloco de 256 KBytes. Quando um par entra em um torrent, ele não tem nenhum bloco. Com o tempo, ele acumula mais blocos. Enquanto ele faz o download de blocos, faz também uploads de blocos para outros pares. Uma vez que um par adquire todo o arquivo, ele pode (de forma egoísta) sair do torrent ou (de forma altruísta) permanecer no torrent e continuar fazendo o upload de blocos a outros pares. Além disso, qualquer par pode sair do torrent a qualquer momento com apenas um subconjunto de blocos, e depois voltar.

Observemos agora, mais atentamente, como opera o BitTorrent. Como o BitTorrent é um protocolo e sistema complicado, descreveremos apenas seus mecanismos mais importantes, ignorando alguns detalhes; isso nos permitirá ver a floresta através das árvores. Cada torrent tem um nó de infraestrutura chamado rastreador. Quando um par chega em um torrent, ele se registra com o rastreador e periodicamente informa ao rastreador que ainda está no torrent. Dessa forma, o rastreador mantém um registro dos pares que participam do torrent. Um determinado torrent pode ter menos de dez ou mais de mil pares participando a qualquer momento.

Como demonstrado na Figura 2.26, quando um novo par, Alice, chega no torrent, o rastreador seleciona aleatoriamente um subconjunto de pares (para dados concretos, digamos que sejam 50) do conjunto de pares participantes, e envia os endereços IP desses 50 pares para Alice. Com a lista de pares, Alice tenta estabelecer conexões TCP simultâneas com todos os pares da lista. Chamaremos todos os pares com quem Alice consiga estabelecer uma conexão TCP de “pares vizinhos” (na Figura 2.26, Alice é representada com apenas três pares vizinhos. Normalmente, ela teria muito mais). Com o tempo, alguns desses pares podem sair e outros pares (fora dos 50 iniciais) podem tentar estabelecer conexões TCP com Alice. Portanto, os pares vizinhos de um par podem flutuar com o tempo.

A qualquer momento, cada par terá um subconjunto de blocos do arquivo, com pares diferentes com subconjuntos diferentes. Periodicamente, Alice pedirá a cada um de seus pares vizinhos (nas conexões TCP) a lista de quais blocos eles têm. Caso Alice tenha L vizinhos diferentes, ela obterá L listas de blocos. Com essa informação, Alice emitirá solicitações (novamente, nas conexões TCP) de blocos que ela não tem.

Portanto, a qualquer momento, Alice terá um subconjunto de blocos e saberá quais blocos seus vizinhos têm. Com essa informação, Alice terá duas decisões importantes a fazer. Primeiro, quais blocos ela deve solicitar primeiro de seus vizinhos, e segundo, a quais vizinhos ela deve enviar os blocos solicitados. Ao decidir quais blocos solicitar, Alice usa uma técnica chamada rarest first (o mais raro primeiro). A ideia é determinar, dentre os blocos que ela não tem, quais são os mais raros dentre seus vizinhos (ou seja, os blocos que têm o menor número de cópias repetidas em seus vizinhos) e então solicitar esses blocos mais raros primeiro. Dessa forma, os blocos mais raros são redistribuídos mais rapidamente, procurando (grosso modo) equalizar os números de cópias de cada bloco no torrent.

Para determinar a quais pedidos atender, o BitTorrent usa um algoritmo de troca inteligente. A ideia básica é Alice dar prioridade aos vizinhos que atualmente fornecem seus dados com a maior taxa. Especificamente, para cada um de seus vizinhos, Alice mede continuamente a taxa em que recebe bits e determina os quatro pares que lhe fornecem na melhor taxa. Então, ela reciprocamente envia blocos a esses mesmos quatro pares. A cada 10 segundos, ela recalcula as taxas e possivelmente modifica o conjunto de quatro pares. No jargão do BitTorrent, esses quatro pares são chamados de unchoked (não sufocado). É importante informar que, a cada 30 segundos, ela também escolhe um vizinho adicional aleatoriamente e envia blocos para ele. Chamaremos o vizinho escolhido aleatoriamente de Bob. No jargão de BitTorrent, Bob é chamado de optimistically unchoked. Como Alice envia dados a Bob, ela pode se tornar um dos quatro melhores transmissores para Bob, caso em que Bob começaria a enviar dados para Alice. Caso a taxa em que Bob envie dados a Alice seja alta o suficiente, Bob pode, em troca, tornar-se um dos quatro melhores transmissores para Alice. Em outras palavras, Alice aleatoriamente escolherá um novo parceiro de troca e a começará com ele. Caso os dois pares estejam satisfeitos com a troca, eles colocarão um ao outro nas suas listas de quatro melhores pares e continuarão a troca até que um dos pares encontre um parceiro melhor. O efeito é que pares capazes de fazer uploads em taxas compatíveis tendem a se encontrar. A seleção aleatória de vizinho também permite que novos pares obtenham blocos, de forma que possam ter algo para trocar. Todos os pares vizinhos, além desses cinco pares (quatro pares “top” e um em experiência) estão “sufocados”, ou seja, não recebem nenhum bloco de Alice. O BitTorrent tem diversos mecanismos interessantes não discutidos aqui, incluindo pedaços (miniblocos), pipelining (tubulação), primeira seleção aleatória, modo endgame (fim de jogo) e anti-snubbing (antirrejeição) [Cohen 2003]. 

O mecanismo de incentivo para troca descrito acima é normalmente chamado de tit-for-tat (olho por olho) [Chen 2003]. Demonstrou-se que esse esquema de incentivo pode ser burlado [Liogkas, 2006; Locher, 2006; Piatek, 2007]. Não obstante, o ecossistema do BitTorrent é muito bem-sucedido, com milhões de pares simultâneos compartilhando arquivos ativamente em centenas de milhares de torrents. Caso o BitTorrent tivesse sido projetado sem o tit-for-tat (ou uma variante), mas com o restante da mesma maneira, ele provavelmente nem existisse mais, visto que a maioria dos usuários são pessoas que apenas querem obter as coisas gratuitamente [Saroiu, 2002]. 

Variantes interessantes do protocolo BitTorrent são propostas [Guo, 2005; Piatek, 2007]. Além disso, muitas das aplicações de transmissão em tempo real P2P, como PPLive e ppstream, foram inspirados pelo BitTorrent [Hei 2007].  

ATIVIDADE DE FIXAÇÃO