|
3. AlgoritmosAlgoritmo de seleção de paresApó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çosCada 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 alternativosDurante 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). |