Chapitre 1 — Introduction

Ce mémoire présente une partie majeure des travaux de recherche que j’ai menés depuis ma thèse de doctorat, soutenue en décembre 2004. Il est centré autour du pair-à-pair (P2P), avec une attention toute spéciale dédiée au thème des réseaux à préférences. Mes travaux situés hors du champ P2P, principalement des travaux autour du PageRank de Google, ne sont pas développés (les références sont disponibles dans le Curriculum Vitae joint à ce mémoire). Les deux principales raisons de ce choix éditorial sont la volonté de présenter un ensemble articulé autour d’une problématique commune (le P2P), ainsi que l’intéressante contrainte posée par la rédaction d’un mémoire de taille limitée.

Dans ce chapitre d’introduction, je propose de partager avec le lecteur ma conception du pair-à-pair, non pas comme le sens commun l’entend, mais en tant que domaine de recherche. S’en suivra au chapitre suivant mon positionnement en tant que chercheur à l’intérieur de ce domaine et la structuration du reste du mémoire.

1.1 Histoire subjective du pair-à-pair

Il existe pléthore de travaux essayant de répondre à la question de savoir ce qu’est le pair-à-pair et comment l’aborder. Les taille, technicité et support sont extrêmement variables : livres [70, 72], études en ligne et wikilivres [69, 77], introduction pédagogique [76]…

Face à tout cela, il est difficile de donner une vision des choses qui n’ait pas déjà été proposée ailleurs. C’est pourquoi j’ai choisi de présenter le pair-à-pair en partant de son apparition en tant que phénomène social, vue sous l’angle de mon expérience personnelle. Je ne prétends pas que mon approche soit recommandée pour quelqu’un qui désirerait s’initier au pair-à-pair : il vaut mieux dans ce cas partir d’une des références ci-dessus. Néanmoins, je crois qu’aborder les choses « par le petit bout de la lorgnette », comme je m’apprête à le faire, permet de mieux comprendre le cheminement que j’ai suivi dans mes travaux de recherche, et de faire ainsi émerger ce qui les rassemble.

Ma propre analyse de l’histoire du pair-à-pair est donc la suivante : j’ai tendance à penser que le pair-à-pair est né au moment où c’était la seule solution technique capable de répondre à un besoin social. Plus précisément, remontons à il y a à peu près une dizaine d’années. La démocratisation de l’accès à Internet, couplée à des avancés significatives en traitement du signal (connues du grand public au travers des sigles MP3 et DiVX) commence à rendre possible de récupérer dans des délais raisonnables du « contenu » audio et vidéo.

Problème, d’où récupérer le contenu ? À l’époque (fin des années ), l’économie numérique n’en est qu’à ses balbutiements. Les médias classiques hésitent encore à franchir le pas numérique, et il n’existe bit¹ de portail permettant l’accès au contenu.

Dans un premier temps, des méthodes relativement anciennes sont employées au sein de cercles restreints d’utilisateurs underground : utilisation de FTPz (piratage d’un serveur FTP anonyme afin d’utiliser les ressources en stockage et bande passante du-dit serveur), pièces jointes des forums de discussions (les alt.binaries de Usenet), …

Puis, avec la bulle Internet apparaissent des sites de stockage en ligne. Cette solution est très vite préférée aux FTPz : plus besoin de scanner des adresses IP, et risque plus faible de perte des données. L’exemple le plus célèbre de cette époque doit être le site http://MySpace.com, qui n’est pas du tout le site de réseau social actuel, mais offre Mo de stockage par compte, sans limite de nombre de comptes et de bande passante².

Hélas, un jour, la bulle éclate. Les sites comme http://MySpace.com ferment, ou sont complètement bridés dans le meilleur des cas. L’absence de business model autour d’une offre de stockage illimitée et gratuite, et les coûts faramineux engendrés par l’utilisation abusive de la bande passante ne sont certainement pas étrangers à cela. Mais une partie des internautes a pris goût à la facilité d’accès au contenu, et ne veut pas revenir en arrière. Le besoin est là. C’est alors que, au gré des forums, une idée commence à émerger : Et si on mettait en commun nos ressources de stockage et de bande passante ? Avec suffisamment de participants, on aurait plus de ressources qu’avec n’importe quel serveur, non ?.

Une première tentative, avec le logiciel Napster, a déjà tourné court à cause de problèmes légaux. Malgré tout, poussés par le besoin d’accès à du contenu, des logiciels comme KaZaA ou eDonkey [2, 3] commencent à voir le jour, tandis que quelque part sur la toile, un informaticien inconnu du nom de Bram Cohen travaille sur un protocole de partage de fichier et utilise des fichiers interdits aux moins de ans pour tester ce qui allait devenir BitTorrent [23]³. Nous sommes en et le pair-à-pair (P2P) naît des cendres des FTPz, de MySpace, et de Napster.

Je dois avouer que lorsque j’ai entendu parler pour la première fois de cette idée d’utiliser les utilisateurs, ma réaction fut de penser ça ne marchera jamais. Je ne croyais pas les utilisateurs prêts à offrir leur bande passante, avec toutes les contraintes que cela impliquait. De plus, j’avais à la va-vite estimé les performances d’un tel système à l’aide de la conservation de la bande passante, et j’en avais conclu qu’elles seraient extrêmement mauvaises. Depuis, j’ai eu le temps de réaliser mon erreur et de faire amende honorable, comme j’en parlerai plus en détails au Chapitre 3.

Aujourd’hui, le succès des applications de partage de fichiers P2P, qui n’utilisent que les ressources fournies par les utilisateurs, n’est plus à démontrer. L’heure est au développement de nouvelles fonctionnalités, comme par exemple la lecture en continu, ou streaming. Des applications de diffusion en direct (ou plutôt en léger différé) comme CoolStreaming [78], PPLive [41], SopCast [7], TVants [8], ou UUSee [9] deviennent de plus en plus populaires, tandis que la diffusion de vidéos-à-la-demande commence à apparaître [1, 4, 5].

1.2 Définir le pair-à-pair

Maintenant que le contexte est posé, on peut commencer à réfléchir à la question de la définition du pair-à-pair. Pour illustrer le problème, je me permets de raconter l’anecdote suivante : on a beaucoup parlé récemment de la loi dite DADVSI relative aux droits d’auteur et aux droits voisins dans la société de l’information. L’un des buts de cette loi était de contrer les usages illégaux du P2P, voire les logiciels P2P potentiellement illégaux. Mais pour légiférer, il faut bien définir, et c’est ce qu’essaie de faire l’article 21 qui rend passible de trois ans d’emprisonnement et 300 000 euros d’amende le fait d’éditer, de mettre à la disposition du public ou de communiquer au public, sciemment et sous quelque forme que ce soit, un logiciel manifestement destiné à la mise à disposition du public non autorisée d’œuvres ou d’objets protégés.

Cet article a fait couler beaucoup d’encre, notamment parce qu’ainsi rédigé, il incluait la plupart des logiciels de serveurs Web, dont le très connu logiciel Apache. Il a ainsi fallu exclure de manière ad-hoc ces logiciels en rajoutant une clause spéciale. Malgré tout, je trouve intéressante la définition du P2P qui ressort de ce texte de loi : un logiciel P2P est destiné à mettre à disposition du contenu, le sens de contenu étant a priori le plus large possible.

Cette première définition, que j’appellerai définition de motivation, est bien sûr insuffisante pour définir le P2P, comme la loi DADVSI l’a bien mis en évidence. Il faut donc chercher plus loin. C’est généralement là qu’intervient la définition par opposition : contrairement au paradigme classique client/serveur, où chaque constituant du système est soit serveur (distributeur de contenu), soit client (consommateur de contenu), le paradigme P2P considère un système où chacun peut être à la fois client et serveur.

Beaucoup plus ciblée que la définition par motivation, la définition par opposition au modèle client/serveur recèle néanmoins une faille lorsque l’on cherche à préciser ce que signifie pouvoir être à la fois client et serveur. Observons par exemple le protocole ssh, protocole réseau permettant à un client de se connecter à un serveur. Si j’ouvre une session ssh à partir de mon ordinateur vers l’ordinateur d’un ami, il est clair que je ne fais pas de pair-à-pair. Si cet ami ouvre en retour une session ssh sur mon propre ordinateur, chacun aura potentiellement accès aux ressources de l’autre (chaque ordinateur étant à la fois client et serveur), pourtant cela ne ressemble toujours à du pair-à-pair selon le sens commun. Mais si tout un réseau social se met à utiliser des sessions ssh afin de s’échanger du contenu⁴, cela finit par former un réseau pair-à-pair, ou plus précisément d’ami-à-ami dans ce cas précis. La question est : où est donc la limite ?

Réciproquement, il est très facile d’imaginer des usages client/serveur pour un logiciel P2P. Ainsi, chaque semaine, j’utilise le client BitTorrent pour récupérer des MP3s d’un ami⁵. Lui possède les fichiers, je les récupère, BitTorrent ne servant qu’à faciliter le transfert : les informations permettant la récupération des fichiers sont concentrées dans un petit fichier .torrent qu’il est très facile de produire et de s’échanger par mail. Là encore, la frontière entre paradigme client/serveur et P2P est extrêmement floue.

Il apparaît donc que même si c’est une bonne approximation, la définition par opposition est imparfaite. Tout comme l’on ne peut donc pas définir l’essence du pair-à-pair comme étant liée à une technologie, il n’y a pas de catégorisation architecturale (paradigme) simple où faire rentrer le pair-à-pair.

Tout cela explique pourquoi je me suis forgé au fil du temps ma propre définition du pair-à-pair, qui essaie de capturer au mieux le fait que selon mon expérience, le P2P est avant tout et d’abord une manière décentralisée d’aborder un problème de distribution dans un scénario matériel donné. Autrement dit, si l’on regarde l’évolution du P2P de ses débuts à nos jours, on voit un principe de base rester le même par delà les évolutions technologiques : si l’on veut offrir un service quelconque à un grand nombre d’utilisateurs en n’ayant pas ou peu de serveurs à disposition, la seule solution est de prendre les ressources au seul endroit où elles existent, à savoir chez les utilisateurs (les pairs) eux-mêmes.

Cette constatation amène à une troisième et dernière définition du P2P, que je décrirais comme une définition par complexité : un système, un usage, un scénario est de type pair-à-pair dès l’instant où la manière de répondre à la question
Qui récupère quoi de la part de qui ?
est non-triviale.

Cette définition peut sembler étrange et contre-intuitive, mais ses avantages sont certains : elle s’affranchit des questions technologiques et transforme une question sémantique (qu’est-ce que le pair-à-pair ?) en une problématique plus algorithmique. Ainsi, pour savoir si un assemblage de connections ssh forme un système P2P, la définition que je propose réponds oui, à condition que le système soit plus complexe qu’une succession de distribution bilatérales indépendantes⁶. En d’autres termes, on pourra parler de pair-à-pair dès que la recherche d’un fichier donné, ou son transfert, utilise plus d’une connection client/serveur.

On obtient aussi, et c’est cela qui m’intéresse en tant que chercheur, une manière de définir ce qu’est la recherche en pair-à-pair : essayer de comprendre la question qui récupère quoi de la part de qui quand celle-ci devient compliquée, la décomposer en sous-questions plus spécifiques d’un problème donné (recherche et distribution, disponibilité et volatilité, équité et hétérogénéité,…) et essayer d’y répondre de la meilleure manière possible.

1.3 Thématiques de recherche

Maintenant que le sujet de la recherche en pair-à-pair est ouvert, je propose de survoler les différentes thématiques et approches sur lesquels un chercheur en pair-à-pair peut être amener à travailler. Je propose d’employer une classification dichotomique basée sur quatre axes : localisation/distribution, structuré/non-structuré, push/pull, théorique/empirique. Cette classification est loin d’être unique et elle n’est pas parfaite, mais je la trouve relativement simple et pratique.

1.3.1 Localisation et distribution

La première manière de décomposer la question Qui récupère quoi de la part de qui ? est de séparer cette question en deux sous-problèmes : localisation et distribution. La phase de localisation consiste à répondre à la question Qui possède quoi ? : c’est la phase de localisation. Une solution est par exemple qu’un serveur central surveille tout le contenu présent dans un système, permettant ainsi de répondre à toute recherche. C’est par exemple le principe de fonctionnement des trackers BitTorrent [23] ou des serveurs eDonkey [3]. Bien sûr, ces solutions sont centralisées, et donc non pair-à-pair (la question qui possède quoi est alors triviale). Un premier pas vers la complexité est l’utilisation de plusieurs serveurs au lieu d’un seul (les super-nœuds). On réduit ainsi la concentration d’information, qui peut être dangereuse d’un point de vue de sécurité, mais il faut commencer à réfléchir à la communication entre super-nœuds : on a une solution semi-centralisée, semi-complexe, bref semi-pair-à-pair. Enfin, on peut laisser les pairs se débrouiller totalement entre eux pour savoir qui possède quoi. Parmi ces approches pair-à-pair de la localisation, il y par exemple l’inondation (flooding), qui consiste à émettre une demande de contenu et à la faire passer de proche en proche, mais l’approche la plus employée est sans doute celle des tables de hachage distribuées [34, 61, 64, 68, 73, 79], qui associent à chaque contenu un pair (voire plusieurs) chargé de savoir qui possède ce contenu.

Une fois le contenu localisé se pose alors le problème de sa distribution effective : comment récupérer le contenu ? C’est un problème qui varie énormément suivant ce que l’on entend par distribution : téléchargement d’un petit ou d’un gros fichier, visualisation d’une chaîne en léger différé, d’une vidéo-à-la-demande… Les subtilités liés aux différents types de distribution seront approfondies dans le Chapitre 3. Pour l’instant, on retiendra simplement que le problème exact à résoudre étant variable, la palette des solutions est large : arbres de diffusions, utilisation de files d’attente, échanges réciproques…

La plupart du temps, ces deux problèmes, localisation et distribution, sont indépendants. Par exemple, si la localisation dans un système BitTorrent est historiquement assurée par un tracker centralisé, les versions récentes offrent aussi la possibilité de recourir à une DHT. De même, le choix du protocole de distribution peut s’adapter en fonction du résultat de la localisation : c’est l’approche multi-protocoles, employée par MLDonkey [30].

Bien sûr, il y a des exceptions, et la distinction entre localisation et distribution n’est pas toujours hermétique. Ainsi, pour des raisons de sécurité et de confidentialité, le logiciel Freenet [22] est conçu de telle sorte que la distribution emprunte le même chemin réseau que celui créé au moment de la localisation, rendant les deux problèmes indissociables.

1.3.2 Structuré, non-structuré

Une autre manière d’aborder la question qui-quoi-de-qui est de réfléchir à la manière dont on va résoudre le problème en pratique. De ce point de vue, deux courant majeurs existent : les approches structurées et auto-structurées.

Le principe des approches structurées est de faire en sorte que les pairs se conforment à une structure pré-déterminée. Cette structure va guider les pairs dans leur comportement et leur manière d’échanger des messages ou du contenu. La plupart des tables de hachage distribuées utilisent un algorithme structuré [34, 61, 64, 68, 73, 79]. Des solutions structurées ont également été proposées pour résoudre le problème de la diffusion en léger différé [19, 35].

Les dites structures sont généralement des graphes (arbres, arbres à nœuds intérieurs disjoints [19], graphes de de Brujin [34, 35], graphes réguliers, …), parfois construits à partir d’une topologie virtuelle (anneau [61, 73], -tore [64], hypercube [61, 68, 73, 79], …).

La force des approches structurées est que le comportement du système est déterminé par une structure connue à l’avance, et que celle-ci peut être conçue pour garantir des performances optimales, ou quasi-optimales. Leur faiblesse vient des difficultés à maintenir une structure face à la volatilité des pairs. De plus, beaucoup de structures supposent que les pairs ont des capacités similaires, et à de rares exceptions près [75], elles s’adaptent mal à une population souvent hétérogène dans les faits.

L’autre solution est de laisser (plus ou moins) les pairs se débrouiller, c’est-à-dire les laisser prendre des décisions en fonction de leur propre perception du système. Il n’y a alors plus de structure explicite, mais une pseudo-structure floue et implicite résultant de la somme de choix locaux. C’est pourquoi, d’ailleurs, je préfère le terme auto-structuré au terme non-structuré qui est généralement employé. Après tout, une structure n’est, par définition, que la manière dont un ensemble est agencé. Par exemple, avec toutes les propriétés qu’il possède (degré moyen, composantes connexes, diamètre, …), le graphe d’Erdős-Rényi, qui est construit à partir de décisions locales (cette arête est-elle dans le graphe ?), est pour moi l’exemple parfait d’auto-structure.

L’approche auto-structurée, dont l’un des exemples les plus représentatifs est certainement BitTorrent, est principalement employée dans la distribution du contenu, que ce soit en partage de fichier ou pour la lecture en continu. Elle est utilisée en localisation dans certains systèmes comme Freenet ou Gnutella, et peut apparaître sous une forme hybridée (comme dit précédemment, aucun cloisonnement n’est complètement rigide) dans certaines DHTs [34, 61].

Par construction, les approches auto-structurées sont adaptées à la volatilité et l’hétérogénéité des pairs. Mais comme leur structure n’est pas connue a priori, il est délicat de prédire leurs performances, et la validation doit souvent être faite de manière empirique. Cependant, des avancées ont été faites afin de donner aux systèmes auto-structurés une base théorique [14, 37, 62].

1.3.3 Push et Pull

On peut aussi caractériser, d’un point de vue recherche, la nature d’un système pair-à-pair, en regardant où les décisions sont prises : au niveau de la partie client (pull), de la partie serveur (push), ou un peu des deux.

Dans une approche pull, le demandeur d’un contenu va lui-même initier la distribution auprès des possesseurs du contenu⁷, en décidant éventuellement quelle partie récupérer de qui. C’est le genre d’approche employée dans les principaux systèmes de partage de fichiers actuels (BitTorrent et eDonkey).

À l’inverse, la philosophie push veut que ça soit les possesseurs qui gèrent le bon fonctionnement du système, les demandeurs ayant un rôle plus passif. Les systèmes de distribution basés sur des arbres de diffusion, où le contenu est routé de la source aux destinataires, sont généralement considérés comme typiques du push [19, 35].

Comme on peut le voir dans les exemples précédents, cette classification est généralement associée à la problématique de la distribution. La raison est que les principales solution de localisation, les DHTs (mais aussi les solutions de localisation centralisées), font un peu des deux : les possesseurs transmettent de manière pro-active la description de leur contenu à un tiers, et les demandeurs vont par la suite chercher ces descriptions. Cette approche de type publish/suscribe peut malgré tout être interprétée, conceptuellement, comme un cas particulier d’hybridation push/pull.

Une autre idée reçue (que j’ai volontairement reproduite dans les exemples qui précèdent) consiste à associer la distribution push aux systèmes structurés et la distribution pull aux systèmes auto-structurés. Intuitivement, cette association est facile à justifier : en approche pull, chaque demandeur organise lui-même la manière dont il récupère le contenu, et on peut penser qu’une structure trop rigide risquerait d’amoindrir la marge de manœuvre. Réciproquement, laisser un ensemble de possesseurs gérer la distribution d’un contenu semble voué à l’échec sans un minimum de concertation, c’est-à-dire de structure. Et pourtant, les algorithmes de diffusion épidémiques [14], dont je parlerai plus en détails au cours du Chapitre 3 sont clairement orientés push (avec une légère rétroaction pull, précisons-le), auto-structurés, et malgré tout promis à un avenir je l’espère brillant.

1.3.4 Théorique, empirique

Au-delà des trois critères que je viens de décrire, qui sont liés aux problématiques propres du pair-à-pair, je crois qu’il est aussi nécessaire de considérer la distinction entre théorie et pratique. C’est une classification (voire un clivage parfois) qui a des origines épistémologiques très lointaines, mais dont les répercussions sur le pair-à-pair sont largement aussi importantes que les distinctions évoquées plus haut. Pour reprendre une définition empruntée à Matthieu Latapy, l’approche théorique (ou plus généralement de la recherche fondamentale) cherche en priorité à comprendre, tandis que le but de l’approche empirique est avant tout de faire (recherche appliquée).

En étant un peu caricatural, le partisan d’une approche purement empirique dénigrera toute recherche qui n’a pas été validée par une série d’expériences en conditions réelles. C’est par exemple la position défendue par Bram Cohen, le concepteur de BitTorrent⁸. À l’inverse, l’approche purement théorique va chercher à proposer des solutions dont on peut montrer qu’elles doivent marcher, ou des modèles dont on peut penser qu’ils capturent l’essence d’un phénomène. C’est ainsi que procèdent la plupart des solutions structurées citées plus haut, ou encore la modélisation fluide de BitTorrent proposée par Qiu et Srikant [63].

Dans l’absolu, chacune des deux approches prise à l’état pur est incomplète, et c’est seulement combinées qu’elles peuvent exprimer pleinement leur potentiel. Soit en proposant une théorie permettant de comprendre des observations (induction), soit en essayant de falsifier (au sens épistémologique) une théorie à travers une série d’expériences. Ce n’est hélas pas toujours aisé, le cloisonnement croissant des domaines n’aidant pas vraiment à réaliser ce grand écart, et un travail de recherche donné (y compris en pair-à-pair) sera toujours perçu avec une couleur plus empirique ou plus théorique, la nuance exacte dépendant bien sûr de l’oeil de l’observateur.

1.3.5 Synthèse

Comme les exemples donnés ci-dessus l’ont illustré, la classification que je propose est loin d’être un cloisonnement rigide, et il faut plutôt la voir comme une boussole permettant d’essayer de s’orienter à l’intérieur du domaine de recherche du pair-à-pair. Les systèmes deviennent de plus en hybrides et mélangent des genres supposés antagonistes. Il n’est plus possible, et ce n’est pas forcément une mauvaise chose, d’isoler complètement les thématiques comme ce fut le cas à une époque où les principaux thèmes abordés étaient les propositions de DHTs (localisation, structuré, publish/suscribe, théorique) et les études de traces réelles (localisation ou distribution suivant la trace, empirique).