3. Algoritmos

Algoritmo de seleção de pares

Após a descoberta das sementes e dos pares simples (sanguessugas), faz-se necessário escolher de quais usuários baixar e para quais usuários enviar. O protocolo BitTorrent prevê um algoritmo que favorece a troca recíproca (tit-for-tat), numa tentativa de melhorar tanto o desempenho local quanto o global [1].

Dado que o objetivo é maximizar a taxa de download, o cliente tenta baixar de todos os pares que assim permitirem. Como a banda de upload normalmente é mais limitada, o algoritmo concentra os esforços de otimização de recursos neste aspecto, utilizando técnicas de engasgamento (choking) para decidir para quais pares enviar.

A escolha de para quais pares liberar o envio (unchoke) e para quais pares pausar (choke) observa os seguintes critérios, com os valores indicados servindo como escolha padrão (default) mas não-obrigatória:

- A cada dez segundos os pares liberados são recalculados.

- Os quatro pares com melhor média de download (calculada nos últimos 20 segundos) tem seu envio permitido.

- Um par escolhido aleatoriamente também tem seu envio liberado (optimistic unchoking), para permitir a descoberta de novas duplas de troca eficientes.

- Caso um par para quem ele esteja enviando não tenha enviado nada para ele no último minuto, deve-se considerar que ele foi engasgado e parar de enviar para esse par.

Para sementes, que não recebem arquivos de ninguém, o único critério utilizado é a sua taxa de envio para o par: envia-se para aquele capaz de receber mais dados (maior banda de download), pois assume-se que isto representará um uso máximo da própria banda.

Algoritmo de seleção de pedaços

Cada arquivo sendo baixado é dividido em pedaços, que podem ser obtidos simultaneamente de vários peers. A seleção de qual pedaço baixar tem forte influência na performance do download de um arquivo. Uma escolha incorreta pode fazer com que todos os pedaços mais comuns sejam obtidos primeiro, e o fim do download seja muito mais demorado.

Durante a maior parte de uma transferência BitTorrent, a seleção de pedaços segue o algoritmo Rarest First (o mais raro primeiro), que consiste na escolha do pedaço que está menos presente nos pares aos quais o usuário em questão está conectado. Este algoritmo apresenta duas grandes vantagens:

- Otimiza a performance global, principalmente quando a taxa de envio das sementesé baixa.

- Evita que algum pedaço desapareça da swarm (por exemplo, caso o seed se desconecte), pois os pedaços mais raros são replicados em pouco tempo.

Após ser totalmente baixado, um pedaço recebido tem seu hash calculado, e este é verificado contra o valor do hash para este pedaço armazenado no arquivo de metadados .torrent. Caso o valor seja diferente, o pedaço é considerado como danificado e é descartado, tendo de ser baixado novamente; esta verificação a cada pedaço garante que, caso o download seja corrompido, o desperdício de banda e tempo gasto com retransmissões para corrigir o problema seja mínimo.

Um pedaço é dividido em subpedaços para agilizar ainda mais o download e permitir uma paralelização maior; o algoritmo dita que subpedaços de um pedaço já sendo baixado tenham prioridade absoluta na seleção, a fim de que partes de um arquivo tenham seu recebimento concluído o mais rápido possível.

A escolha de qual dos pedaços enviar é mais simples, pois, dada a escolha do par para o qual se fará upload, o pedaço enviado será aquele escolhido pelo par.

Algoritmos alternativos

Durante os primeiros instantes de download de um torrent, o algoritmo de seleção de pedaços é modificado para requisitar um pedaço qualquer do arquivo. Este algoritmo recebe o nome de Random First Piece (primeiro pedaço aleatório).

Isto ocorre porque é importante obter um pedaço completo o mais rápido possível, para poder começar a fazer upload para outros pares. O algoritmo comum selecionaria o pedaço mais raro, porém este está presente em menos pares e, por isso, seria baixado mais lentamente, pois há menos pares de quem requisitar subpedaços.

O modo Random First Piece é encerrado quando ao menos um pedaço completo é obtido, e o usuário volta ao algoritmo usual Rarest First de seleção de pedaços.

Um cliente BitTorrent entra em modo Endgame – nome tirado do estágio composto pelos momentos finais do jogo de xadrez – quando todos os pedaços que faltam já foram requisitados. Para evitar que a demora de algum dos pares em responder ou sua lentidão de envio atrase o término do download, o cliente envia requisições de todos os pedaços restantes para todos os pares. A chance de receber todos os pedaços e concluir o download rapidamente, então, aumenta.

Quando um pedaço passa a ser recebido com velocidade satisfatória, tentativas de envio subseqüentes são canceladas para evitar desperdício de banda. Este modo é diferente do normal, no qual cada pedaço só é requisitado uma vez (exceto em caso de falha).