Table des matières

Principe de fonctionnement du protocole BitTorrent

Tout ce qui suit est avant tout basé sur «Incentives Build Robustness in BitTorrent», par Bram Cohen,

BitTorrent, qu'est-ce que c'est ?

BitTorrent (BT pour les intimes) est un protocole développé par Bram Cohen dans le but de permettre de distribuer du contenu (Musique, textes, programmes) sans surcharger la bande passante montante de l'éditeur originel. L'idée est de séparer le fichier en nombreux éléments de taille identique, que le distributeur (seeder) enverra petit à petit aux différents receveurs (leechers), ceux-ci se les redistribuant ensuite entre eux, ce qui permet à la fois au seeder de distribuer plus d'un exemplaire d'un programme en n'utilisant de sa bande passante que le temps d'uploader un exemplaire et au fichier de pouvoir continuer à se distribuer même si personne n'en a un exemplaire complet (il suffit que l'ensemble des morceaux soit disponible, sans nécessairement qu'une copie complète le soit, avantage énorme par rapport à d'autres réseaux de p2p type Gnutella).

Pour ce faire, BT utilise un petit fichier, le torrent, qui informe le client d'où récupèrer les fichiers et comment les remettre en ordre, et un petit serveur, le tracker, qui centralise les informations sur tous les seeders et leechers (ensemble, on les appelle les pairs) et permet à ceux-ci d'entrer en contact les uns avec les autres. Chaque client essaye alors d'optimiser l'échange.

Beaucoup de théorie

Ce qui fait la force de BT c'est qu'avant d'être un programme, c'est surtout un protocole qui s'appuie sur une mise en oeuvre extrêmement intelligente de la théorie des échanges et de la théorie des jeux. Le but de ce texte est d'essayer de comprendre comment ça marche et pourquoi ça marche si bien.

Technique

Une fois mis en rapport, les pairs échangent la liste des données qu'ils détiennent. Celles-ci consistent en fragments de fichiers, généralement de 256 ko. Lorsqu'un pair dispose d'un fragment qui intéresse un autre pair, il va lui transmettre, en le refragmentant en blocs de 16 ko afin d'optimiser la transmission (technique du pipeline, quatre fragments sont préparés pour l'envoi pendant qu'un est transmis, la taille des fragments permettant de ne pas perdre trop de temps en cas de transmission corrompue).

Critères de choix

Ce qui fait la véritable efficacité du protocole BT, c'est la façon dont un client va choisir quelle pièce envoyer à qui. Le choix de la pièce se fait selon 4 critères successifs :

La priorité stricte

Premier principe, lorsqu'un pair a commencé à transmettre des sous-fragments d'un fragment à un autre pair, il lui transmettra les autres sous-fragments de ce fragments avant d'envisager de lui transmettre d'autres sous fragments. C'est simple et cela permet d'assurer, autant que possible, que seuls des fragments complets circulent sur le réseau.

La pièce la plus rare d'abord

Là, on commence à rentrer dans ce qui fait l'efficacité de BT. Pour qu'un torrent reste actif, il faut que l'ensemble des pairs ait au moins, à eux tous, une copie complète du fichier. Mais si le système d'échange est aléatoire, le risque existe que, lorsqu'un pair se retire, il ait été le seul à disposer d'un fragment, bloquant dès lors la distribution du fichier. Donc, le client qui, rappelons-le, est tenu informé par les autres pairs des données dont ils disposent, va choisir en priorité le fragment le moins représenté sur le réseau, permettant ainsi de limiter les risques de disparition de fragments. Au contraire, les fragments les plus courants seront, eux, téléchargés en dernier

Les deux exceptions

Première pièce aléatoire

La pièce la plus rare, par définition, n'est que peu présente sur le réseau et est très demandée. Si tous les pairs la téléchargent, la bande passante des seeders va être saturée, ralentissant le téléchargement de tout le monde. Pour limiter cet effet néfaste, la règle utilisée pour les nouveaux leechers, qui n'ont rien à uploader, est différente, ils choisissent une première pièce au hasard, évitant ainsi d'encombrer les tuyaux pour les pièces les plus recherchées.

Fin de téléchargement

Lorsque l'on arrive en fin de téléchargement, pour éviter d'être bloqué par un pair ayant une faible vitesse d'upload, le client demande tous les sous-fragments qui lui manquent à tous les pairs qui en disposent, annulant ses demandes à mesure qu'il reçoit des sous-fragments. Ainsi, la fin du téléchargement peut se faire très rapidement sans surcharger la bande d'un seul pair et en mettant à disposition un nouveau seeder.

L'optimisation

Chaque client est responsable de l'optimisation de sa vitesse de téléchargement. Cette optimisation repose sur un système de donnant-donnant adapté du dilemme du prisonnier. Le principe est simple : je te donnes si tu me donnes et si tu ne me donnes pas, je cherche ailleurs pour voir s'il n'y a pas quelqu'un qui me donnerait plus, auquel cas je te lâche pour me tourner vers lui. Pour être sûr de ne pas rater une connection intéressante, une des connections du client change régulièrement et aléatoirement de pair pour voir si elle ne pourrait pas être intéressante. Le résultat est que, le plus souvent, on atteint à un optimum de Pareto (chaque pair est dans une situation telle qu'il ne peut l'améliorer sans détériorer celle d'un autre) qui n'est pas un équilibre de Nash mais qui apparaît bien comme une situation optimale au sens propre, puisque l'on a à la fois une optimisation de la vitesse de téléchargement de chacun des clients et de la vitesse de distribution du fichier.

Le cas des seeders

Pour améliorer l'optimisation, une fois que le fichier est entièrement téléchargé, le pair, qui accède au statut de seeder, va adopter une autre stratégie de choix, envoyant les données d'abord aux clients qui ont la plus grosse vitesse d'upload, permettant ainsi une redistribution rapide de ses données.

Conséquences pour chacun d'entre nous

Si vous avez compris ce qui précède, vous comprenez les deux caractéristiques principales de BT : à essaim constant (l'essaim est l'ensemble des pairs), votre vitesse de téléchargement va aller en croissant parce que vous deviendrez de plus en plus intéressant pour les autres leechers et qu'il y aura de plus en plus de seeders ; la vitesse de téléchargement ne dépend pas seulement du nombre de seeders mais du ratio seeders/leechers et, surtout, de la bande passante totale de l'essaim (la vitesse totale de téléchargement de l'essaim sera égale à la somme des bandes passantes de chacun des membres de celui-ci).

L'optimum impossible

Il est un point à noter : pour le ratio, l'optimum de Pareto se situe à 1:1 pour chacun des membres de l'essaim (sauf pour le seeder originel). Cela nécessite cependant deux conditions : que le seeder originel envoie exactement une copie de son fichier, pas plus, et que, à la fin du torrent, l'antépénultième pair distribue les deux moitiés du fichier aux deux derniers pairs et que ceux-ci terminent en s'échangeant leurs moitiés. La présence de leechers (au sens négatif du terme) et l'inégalité des bandes passantes rendent impossible d'atteindre cet optimum de Pareto. Il est fréquent, lorsqu'on dispose d'une importante bande passante en up, d'avoir un ratio supérieur à un dès la fin du téléchargement, ce qui est de toute façon souhaitable en raison de la présence de leechers. Il est en fait très important de porter son ratio nettement au-dessus de 1:1.

Article à l'origine écrit par Suger

Voir aussi