16 juin 2010

Etude: utilisation des technologies des P2

15:08 Réseau , 0 Comments

1. Introduction

On entend de plus en plus parler de P2P aujourd'hui, mais qu'en savons nous vraiment ? D'un côté, de grands groupes d'industriels qui décrient l'emploi fait de cette technologie, quand ce n'est pas la technologie elle-même, et présentent les utilisateurs du P2P comme des délinquants systématiques. De l'autre, des gens de tous âges, de tous milieux sociaux, qui assurent ne pas faire de mal et être (presque) dans la légalité.

Quoiqu'il en soit, ce ne sont pas ces points de vue qui nous intéressent ici. Le but de ce document est de présenter les différentes architectures du P2P aujourd'hui, ainsi que d'autres pistes qui sont actuellement en exploration.


2. Qu'est-ce qu'un P2P

L'acronyme P2P signifie Peer to Peer, soit en bon français : Pair à Pair. Il s'agit d'un moyen de partager des ressources, comme le propose par exemple le mode client/serveur.

Le P2P est une technique. Cette technique est utilisée par de multiples applications. Par exemple le P2P est utilisé pour le partage de ressources parfaitement légales, comme des logiciels open sources (Linux, EDI, outils, etc... ) ou des versions d'évaluation par exemple.

L'utilisation de la technologie P2P pour des téléchargements non autorisés est illégale. Par exemple pour les fichiers musicaux, il existe actuellement de nombreux sites vous permettant de les télécharger en toute légalité tout en payant les droits d'usage de ces fichiers, de sorte que les auteurs soient rémunérés pour leurs créations. L'utilisation du P2P pour télécharger des oeuvres non libres de droits, ou dont vous ne vous êtes pas acquittés des droits, est illégale.


2.1. Comment partager de l'information

Lorsque l'on souhaite partager de l'information entre plusieurs ordinateurs, il existe de nombreuses solutions. Celle qui est la plus mise en oeuvre aujourd'hui est le modèle client/serveur.


2.1.1. Mode Client/Serveur

Rien de complexe dans cette notion : si vous préférez une image plus concrète, remplacez le contexte informatique par le contexte d'un restaurant, c'est identique ;)

Les clients désignent les applications qui cherchent à exploiter des services proposés par un serveur. Les clients ne disposent pas d'informations, mais sont capables d'aller en chercher. Par exemple, on peut citer les navigateurs web (Firefox, Internet Explorer, Mozilla, Safari, ...), mais aussi les logiciels de courrier électronique (mutt, outlook, thunderbird, ...), les clients FTP, ...
Si vous avez un ordinateur branché sur un réseau (internet ou réseau local), alors vous vous êtes déjà servi d'un client.

De l'autre côté sont les serveurs. Souvent situés sur des machines puissantes afin de pouvoir servir plusieurs clients en même temps ; ils ont l'information à disposition.

Un des gros avantages de ce mode client/serveur est sa relative simplicité de fonctionnement. En effet, une fois que vous avez l'information que vous souhaitez partager, vous ouvrez un serveur (un peu comme on ouvre un restaurant), et vous n'avez plus qu'à attendre les clients. Bien sûr, ici, pas question d'attendre que quelqu'un rentre à l'improviste, il faut faire connaître votre serveur.

Ce mode permet surtout une grande simplicité des mises à jour : chaque possesseur d'information la met sur un serveur (on parle alors d'upload d'une information, contrairement au download qui consiste à rapatrier les informations du serveur vers le client), et elle est disponible immédiatement pour tout le monde.

Le problème de ce mode de fonctionnement est son coût. En effet, si un ordinateur un peu puissant suffit largement à traiter quelques requêtes simultanées, dès que le nombre de requêtes devient grand, les serveurs (ordinateurs utilisés uniquement pour fournir un type de service) doivent se multiplier, et la connexion réseau doit également être augmentée, faute de quoi les performances (temps de réponse du serveur) seront dégradées. Le pire des cas est un crash du serveur : celui-ci n'est plus en mesure de répondre.


2.1.2. Le P2P

Une autre manière de partager de l'information est de ne pas se servir de serveurs, mais de relier tous les possesseurs d'informations. Cela a pour avantage de supprimer les serveurs, qui sont des machines coûteuses car très puissantes. En revanche, cela complique énormément la notion de recherche d'informations.

Ce mode de partage de l'information est le P2P. On peut considérer que chaque utilisateur d'un P2P est à la fois un peu client et serveur (nous verrons par la suite que ce n'est pas toujours exact, en fonction de l'architecture utilisée). Une fois que le demandeur sait où est l'information qu'il désire, les deux ordinateurs sont alors en mesure de s'échanger directement des informations, sans plus devoir passer par une machine tiers, c'est-à-dire sans utiliser des ressources autres que les leurs.


2.1.3. Avantages de l'un par rapport à l'autre

Considérons une entreprise. Pour des raisons de sécurité évidentes, elle souhaite être en mesure de sauver les informations, afin d'en disposer même si un ordinateur (quel qu'il soit) tombe en panne. Il est donc logique qu'elle s'oriente vers un modèle client/serveur : chaque employé, une fois le soir venu, transfèrera ses données sur un serveur, et une copie des données du serveur sera effectuée (ces opérations sont automatiques et ne demandent plus d'intervention, rendant la tâche encore plus facile).

Par contre, il est certain que cela a un coût non négligeable pour l'entreprise : elle doit disposer de suffisamment de serveurs en fonction du nombre d'employés, doit effectuer une sauvegarde quotidienne des données, ...

De même, cette entreprise ne souhaite pas que toutes les données soient accessibles à tout le monde. Or il est plus facile de surveiller quelques serveurs plutôt que quelques milliers de machines... En outre, les logiciels P2P n'offrent que peu de protections et de confidentialité sur les fichiers échangés, comme nous le verrons par la suite.

En revanche, le P2P a pour lui sa simplicité de mise en place et d'utilisation, ce que recherche un particulier. D'où un certain engouement pour ce type de technologie.

Pour ceux qui n'auraient jamais utilisé un logiciel de P2P, voici ce que ça demande : télécharger un logiciel depuis le site qui a (généralement) le même nom que le logiciel. L'installer en cliquant toujours sur suivant". Double-cliquer dessus pour le lancer, et cliquer sur "se connecter". Ensuite, vous avez à votre disposition un mode de recherche, qui vous permettra de trouver ce que vous voulez. Il ne vous reste plus ensuite qu'à double-cliquer sur le fichier proposé en retour de votre recherche, et attendre qu'il l'ait téléchargé.

Certes, cela se passe bien ainsi. Mais alors pourquoi existe-t-il tant de logiciels différents ? Et quelles sont leurs différences ? C'est justement à ce type de question que le chapitre suivant répond. Ensuite, nous verrons le P2P sémantique, avant de parler d'autres axes de recherches menées sur le P2P.


3. Les architectures P2P


3.1. Les architectures centralisées

Figure 1 : Exemple d'architecture centralisée
Le représentant le plus connu de ce mode de P2P est sans doute Napster. (1) Cette architecture se compose d'un unique serveur, dont le but est de recenser les fichiers proposés par les différents clients. Contrairement au mode Client/Serveur, ce serveur centralisé ne dispose pas des fichiers. Il dispose principalement de deux types d'informations : celles sur le fichier (nom, taille, ...), et celles sur l'utilisateur (nom utilisé, IP, nombre de fichiers, type de connexion, ...) Du côté du client, rien de plus simple : une fois connecté grâce au logiciel spécifique, il peut faire des recherches comme avec un moteur classique. On obtient alors une liste d'utilisateurs disposant de la ressource désirée. Il suffit alors de cliquer sur le bon lien pour commencer le téléchargement. Cette étape est complètement indépendante du serveur, et représente la seule partie P2P du logiciel.

Avantages
  • Le confort d'utilisation est grand, puisqu'il n'y a pas de soucis de connexion au bon serveur.
  • La recherche de document est facilitée. En effet, le serveur est omniscient : si un fichier est disponible sur le réseau, on est en mesure de le savoir systématiquement.
Inconvénients
  • La sécurité est le talon d'Achille de ce type d'architectures : il suffit de supprimer le serveur pour que l'intégralité du réseau soit inactif.
  • Sensible au partitionnement du réseau (serveur inatteignable) et aux attaques.
  • Aucun anonymat n'est possible, puisque chaque utilisateur est identifié sur le serveur. Il est alors on ne peut plus facile d'élaborer des profils utilisateurs (diverses possibilités d'utilisation : de la publicité ciblée à l'identification des clients violant les protections intellectuelles par exemple).

3.1.1. Un exemple de réseau centralisé : Napster

Napster2 est le réseau centralisé par excellence.

Figure 2: Exemple de fonctionnement de Napster
  1. Enregistrement du noeud i. Ajout des fichiers de i dans l'index.
    Demande du fichier "a.txt".
  2. Réponse contenant les noeuds disposant de "a.txt".
  3. Demande directe de i à j pour télécharger "a.txt".
  4. Téléchargement de "a.txt", et ajout dans la base de ressources partagées.

3.2. Architecture centralisée à serveurs multiples

Figure 3: Exemple d'architecture centralisée à serveurs multiples
Afin de pallier aux déficiences introduites par un unique serveur, une amélioration consiste à remplacer le serveur central par un réseau de serveurs. L'exemple le plus connu est sans doute le réseau eDonkey.
Dans ce type de réseau, on diffère encore une fois très bien les serveurs des clients. Ce sont d'ailleurs deux programmes totalement distincts.
Le serveur est, encore une fois, une machine puissante, (généralement) dédiée à faire tourner le programme (non pas que le programme soit lourd, mais les requêtes des utilisateurs oui). Tout le problème d'un serveur est de se faire connaître du public.
Les serveurs sont ensuite en mesure de se connecter entre eux, en fonction de leur connaissance les uns des autres. On peut donc avoir plusieurs réseaux indépendants (CF figure 3).
Lorsqu'un client lance le logiciel, il est alors obligé de choisir un serveur auquel se connecter. Pour cela, il doit connaître au moins un serveur. Des listes de serveurs sont donc disponibles sur le net, tout le problème résidant alors dans le fait de choisir le bon...
Pour ce faire, le logiciel client permet de disposer d'une description de chaque serveur avec son nom, son IP, une description (faite par le propriétaire du serveur), le ping, le nombre d'utilisateurs, le nombre maximal d'utilisateurs et le nombre de fichiers partagés.


3.2.1. Un exemple d'architecture à serveurs multiples : le réseau eDonkey

Ce réseau, dont le but est de permettre le partage de gros fichiers multi-sources dispose de deux réseaux de pairs : les clients et les serveurs. Un serveur connaît la localisation des documents contenus chez les clients qui sont connectés à lui, alors que le client va stocker des morceaux de fichiers.

Les fichiers
les fichiers sont identifiés de manière unique grâce à l'algorithme MD4 (2) sur les serveurs de localisation.
Afin de permettre un meilleur partage des fichiers, ceux-ci sont divisés en segments de 9 Mo chacun. Dès qu'un segment est complet, celui-ci est partagé par le client.
Ce système permet d'obtenir un plus grand nombre de personnes disposant du fichier, le rendant ainsi plus facile à obtenir, puisqu'une autre fonctionnalité d'eDonkey est le téléchargement depuis plusieurs sources.
Un dernier point intéressant est la propagation des sources entre les clients.
Supposons que l'on ait 3 clients : 1, 2 et 3. 1 et 2 sont sur le même serveur, et 3 sur un autre. Enfin, 3 dispose d'un gros fichier (mettons 90 Mo) que voudront 2, puis 1.

  • 2 effectue une requête
  • Le serveur répond que 3 dispose de la ressource
  • 2 demande le fichier à 3, le téléchargement commence
  • Dès que 2 dispose d'un segment complet du fichier (9 Mo consécutifs), il prévient son serveur qu'il dispose de la ressource "fichier".
  • 1 demande à son tour le fichier.
  • Le serveur lui répond que 2 en dispose
  • 1 demande le fichier à 2
  • 2 envoie le fichier et prévient 1 que 3 dispose également de la ressource
  • 1 va donc également demander à 3 des segments du fichier, afin de télécharger plus vite. A ce moment là, on a donc 1 qui télécharge chez 2 et 3, et 2 qui télécharge chez 3. Mais rien ne dit que 3 va envoyer les mêmes données à 2 et à 1. Il se peut donc que 1 dispose de segments souhaités par 2.
  • Donc 2 va également demander à 1 le fichier.
Point de vue du serveur
Comme en mode client/serveur, les serveurs disposent ici de logiciels spécifiques permettant aux clients de se connecter explicitement.
Afin de faciliter le choix du client, le logiciel permet de voir plusieurs informations à propos du serveur, comme le nom ou le ping, mais aussi des informations plus spécifiques comme le nombre de clients maximum, les nombre de clients connectés, ou encore le nombre de fichiers partagés.
Les serveurs ne sont pas directement reliés entre-eux, comme c'est le cas d'autres types de réseaux (Kazaa par exemple). En revanche, les serveurs s'échangent, entre autres, la liste des serveurs connus.
En revanche, côté client, le fait d'être connecté à un unique serveur n'est pas aussi limitant qu'on pourrait le croire. En effet, chaque client demande des IP sources (c'est à dire les adresses IP des personnes ayant la ressource recherchée) à l'ensemble des serveurs qu'il répertorie. Cette possibilité d'interroger tous les serveurs peut aussi être utilisée lors d'une recherche. Dernière précision : un client ne publie la liste des fichiers qu'au serveur auquel il est connecté. (3)

Le client
A l'instar de la plupart des autres p2p cités ici, il n'existe pas un unique logiciel pour se connecter au réseau eDonkey. On peut par exemple citer eDonkey(http://www.edonkey2000.com) ou eMule (http://www.emule-projet.net), qui est un peu son pendant français (avec d'autres fonctionnalités également), mais aussi des projets moins attendus comme MLDonkey (http://www.nongnu.org/mldonkey/), développé par l'INRIA (4) pour développer les langages fonctionnels (5) .


3.3. Architectures décentralisées

Figure 4: Exemple d'architecture décentralisée
Une autre architecture de P2P est l'architecture décentralisée. Gnutella est un des représentants de cette architecture P2P.
Ici, plus de serveurs au sens commun : tout le monde est à la fois client et serveur. Cela pose principalement un problème qui n'apparaît pas avec une architecture centralisée : comment connaître la topologie du réseau ?
Lorsqu'un client souhaite se connecter, il va donc être nécessaire d'envoyer un message broadcast (6) afin de savoir quels autres personnes du réseau sont actives. Seules ces personnes répondront au message broadcast. On est alors connecté au réseau.
Afin de garder des informations cohérentes, un utilisateur n'est pas connecté directement à plus de 3 ou 4 noeuds, et la hauteur d'arbre (7) est généralement de 7.
Lors des recherches, chaque noeud propage la requête à ses voisins (généralement 4), qui font de même. Le nombre de propagation est toutefois limité (généralement 7), et il est possible de détecter les cycles grâce à l'identificateur des paquets.


3.3.1. Principes Sous-jacents ...

Ces réseaux reposent sur les principes sous-jacents suivants :

  1. Principe d'égalité entre les noeuds
    o Même capacité (puissance, bande passante, ...)
    o Même comportement (à la fois client et serveur)
    o Bon comportement (pas de "mensonge")
  2. Principe de requêtes "populaires"
    o Les ressources demandées sont beaucoup répliquées
    o La plupart des requêtes ne concernent que peu de ressources
  3. Principe de topologie du réseau
    o Graphe minimisant le nombre de chemins entre deux noeuds o La longueur du chemin minimum entre deux noeuds est faible (5 à 8) (8) .

3.3.2. ... et réalités

  1. Principe d'égalité entre les noeuds
    1. L'article de S. Saroiu et al. [ (9) ] publié en 2002 montre que l'écart dans la bande passante disponible peut varier de 1 à 5 ! Il est d'ailleurs probable qu'avec les connexions internet disponibles actuellement, cet écart aura plus tendance à se creuser qu'à diminuer.
      • Risque de perturbation du réseau et de partitionnement (trop forte charge demandée à des noeuds connectés par modem RNIS par exemple).
    2. Ce même article tend à montrer des comportements de client ou de serveur, mais en tout cas pas ou peu de comportement à la fois client et serveur.
    3. De même, Adar et Hubermann [ (10) ] montrent que 70% des utilisateurs ne partagent aucun fichier (ou des fichiers inintéressants), et que 50% des résultats sont produits par 1% des noeuds.
      • Aucun intérêt pour ceux qui partagent (pas de réciprocité).
      • le réseau devient sensible aux fautes et aux attaques.
    4. Certains noeuds font exprès de sous-évaluer leur bande passante, afin de ne pas être choisis.
  2. Principe des requêtes populaires
    1. Les 100 requêtes les plus fréquentes sont distribuées uniformément.
    2. Les autres suivent une distribution de type Zipf (11)
    3. Les techniques de cache des résultats s'appliquent bien, et sont en mesure d'apporter une amélioration notable.
  3. Principe de topologie du réseau
    1. Plusieurs études montrent que le graphe sous-jacent de Gnutella est de type Small World, et que le degré des noeuds suit une distribution Power Law.
    2. Le principe de diffusion de Gnutella ne s'adapte pas à SW (beaucoup de messages redondants).
Avantages
  • La taille d'un tel réseau est théoriquement infinie, contrairement aux autres architectures dont le nombre de clients dépend du nombre et de la puissance des serveurs.
  • L'utilisation d'un tel réseau est anonyme, c'est à dire qu'il est impossible d'y repérer quelqu'un volontairement.
  • Réseau très tolérant aux fautes
  • S'adapte bien à la dynamique du réseau (allées et venus des pairs)
Inconvénients
  • Gros consommateur de Bande passante
  • Pas de garantie de succès, ni d'estimation de la durée des requêtes
  • Pas de sécurité, ni de réputation (pas de notion de qualité des pairs, ni des données fournies).
  • Problème du free-riding (personnes ne partageant pas de fichiers)

3.3.3. Un exemple de réseau décentralisé : Gnutella

Types Description Information
Ping Annonce la disponibilité, et lance une recherche de pair Vide
Pong Réponse à un ping IP et N° de port.Nombre et taille des fichiers partagés
Query Requête Bande passante minimum demandée Critères de recherche
QueryHit Réponse à query si on possède la ressource IP + N° de port + Bande Passante.Nombre de réponses + descripteur
Push Demande de téléchargement pour les pairs derrière un firewall IP du pair ; index du fichier demandé. Adresse IP + N° de port où envoyer le fichier
Ajout d'un noeud
Nous supposons ici que le pair A souhaite se connecter au réseau Gnutella. Afin de rendre les schémas plus lisibles, nous limitons le nombre de pairs à 5 (et donc aussi le nombre de propagations). Pour se faire, il va tout d'abord émettre un message ping (en traits pleins rouges sur la figure ). Ici, celui-ci est d'abord reçu par B, qui va alors faire deux choses :

  1. Répondre à A un message pong (en tirets noirs pour B, en "tirets point" orange pour D, "tirets point point" pour C et pointillés pour E).
  2. transférer le message de A vers les deux clients qu'il connaît, C et D.
Ceux-ci répètent alors la même chose (sauf si le nombre de propagations a déjà été atteint).

Figure 5: Ajout d'un noeud dans Gnutella
A va donc connaître les noeuds B, C, D et E. On peut d'ailleurs remarquer que E connaît l'existence de A grâce à C et à D, mais qu'il ne répond qu'une fois (via le chemin le plus court, ou le premier qui l'a contacté).

Recherche
Dans cet exemple, A cherche à obtenir le fichier a.txt, disponible chez C et E (ce que A ne sait pas bien évidemment).

Figure 6: Exemple de recherche dans Gnutella
A va donc envoyer un message Query (traits pleins rouges) au(x) premier(s) noeud(s) qu'il connaît (ici B), qui se charge

  1. de répondre s'il dispose de la ressource (ce qui n'est pas le cas)
  2. de propager la question
Les autres noeuds font pareil, ce qui conduit C à répondre et à propager la requête. A peut alors envoyer à C le message get a.txt, et le transfert peut alors commencer.

Observation de la Bande passante
  • Sur une période d'un mois :
    • o La taille d'une requête typique est de 560 bits (y compris headers TCP/IP)
    • o Les requêtes occupent 25% du trafic, les ping 50%
    • o En moyenne, un pair est connecté activement à 3 autres (Sur le schema 5, B est un pair typique).
  • Du point de vue de la bande passante, Gnutella ne passe pas à l'échelle.

3.3.4. Un autre exemple : Freenet

Freenet est un logiciel de P2P décentralisé, dont le but est la diffusion de fichiers de façon totalement anonyme. Ainsi, les données ne sont pas téléchargées directement d'un pair à un autre, mais peuvent transiter par un ou plusieurs pairs. Il est ainsi quasiment impossible de déterminer l'origine exacte d'un message. Afin de protéger les hébergeurs, tous les fichiers sont cryptés. Le possesseur d'un noeud ne peut donc pas connaître le contenu des fichiers stockés sur son noeud. Attention, il est illégal de posséder des fichiers ayant un contenu contraire à la loi. Dans la mesure où le but de freenet est de garantir un anonymat maximal, les mécanismes de routage sont assez complexes, et ne seront donc pas traités ici. On trouve de très bons documents à ce sujet sur l'internet ([ (12) ] par exemple). Il suffit juste de savoir que si le noeud 1 cherche une information, il demandera à son voisin (appelons-le 2) qui, s'il ne dispose pas de la ressource, transmettra la requête à 3, et ainsi de suite.

Faiblesses de ce réseau
Freenet dispose de nombreuses faiblesses, comme par exemple :

  • Temps de récupération d'un fichier Le temps nécessaire pour trouver un fichier dans Freenet reste très honorable. En revanche, le temps de récupération est beaucoup plus long, à cause des problèmes d'anonymat : afin de ne pas connaître la source du fichier, celui-ci sera copié sur tous les noeuds intermédiaires de la requête.
  • Diffusion des clefs Freenet utilise des clefs, notamment pour permettre d'identifier les fichiers. Une recherche de fichier sans cette clef étant quasiment impossible, il faut que la personne disposant d'un fichier dispose d'un moyen de diffuser la clef. Or si on envisage un site web, cela implique un serveur centralisant les données, ce qui va à l'encontre de l'esprit de freenet, à savoir la décentralisation totale. Il est actuellement possible d'héberger un site web sur freenet (donc sans offrir de serveur fixe), mais dans ce cas là, on revient au premier problème (temps de récupération) pour chaque page...
  • Attaques possibles Comme nous l'avons vu, chaque fichier est identifié par une clef. Ainsi, en générant aléatoirement un grand nombre de clefs, l'attaquant aura de fortes chances d'obtenir une clef proche de celle du fichier cible. En insérant d'énormes fichiers avec ces clefs, les noeuds ayant des chances de disposer du ficher cible vont être saturés. Ensuite, en réalisant de très nombreuses requêtes sur les clefs insérées, l'attaquant pourrait corrompre de nouveaux noeuds. Pour pallier ces défaillances, différentes solutions :
    • Identifier les nouveaux noeuds avec des clefs proches de celles de noeuds chargés, afin de répartir la charge.
    • Changer la politique de gestion des fichiers en local (prendre en compte la présence ou non d'une copie sur le réseau).
    • Disperser sur le réseau des fragments de fichiers, dans le but de pouvoir reconstruire le fichier original plus facilement. Des logiciels comme IBP (13) peuvent apporter beaucoup.
Conclusions sur Freenet
Freenet n'est pas le logiciel P2P le plus simple d'accès : la mise à disposition de fichiers reste complexe, et les recherches de fichiers fastidieuses (proximité sémantique de la clef) ; en outre, les temps de téléchargement sont très très supérieurs à ses concurrents. En revanche, les fichiers sont cryptés, et la source de téléchargement est inconnue du destinataire (et quasiment introuvable), assurant ainsi une grande sécurité et de l'anonymat. Le choix d'utiliser Freenet ou non va donc dépendre des attentes de chacun.


3.4. Une architecture hybride : les super-peer


3.4.1. Généralités

Il s'agit ici d'un modèle que l'on pourrait qualifier d'hybride entre le mode client/serveur et le P2P. En effet, tous les noeuds ne sont plus égaux :

  • Les noeuds disposant d'une bonne bande passante sont organisés en P2P. Ce sont les super-peers
  • Les noeuds avec une faible bande passante sont reliés en mode client/serveur à un super-peer
  • Les super-peers disposent d'un index des ressources de leur cluster
Le logiciel de P2P le plus connu utilisant cette technologie est sans doute Kazaa.

Figure 7: Exemple de réseau super-peer

3.4.2. Les super-peer redondants

Le choix d'un super-peer introduit de la sensibilité aux défaillances : si le super-peer n'est plus joignable, tous ses clients sont coupés du réseau. Une des améliorations possibles est donc de choisir parmi K super-peers au lieu d'un seul. Une restriction est que les super-peers soient partenaires. Dans ce cas, chaque partenaire est relié à chaque client, et possède un index de toutes leurs ressources. Les clients envoient leurs requêtes selon le principe du Round Robin (14) , ce qui permet de faire baisser la charge d'un facteur k. En revanche, la charge du coût d'entrée d'un nouveau client est multipliée par K, et le nombre de connexions ouvertes de K², comme le montre le graphique .

Figure 8: Exemple de réseau super-peer redondant

3.4.3. Règles de conception d'un super-peer

Pour plus d'informations, il est vivement conseillé de lire [ (15) ], qui décrit bien plus précisément ces règles de conception :

  1. Augmenter la taille d'un cluster diminue la charge agrégée, mais augmente la charge individuelle.
  2. La redondance de super-peer est favorable.
  3. Il faut maximiser le nombre de connexions des super-peers (permet de diminuer le nombre de sauts pour atteindre un résultat).
  4. Il est nécessaire de minimiser le TTL (16) .

3.4.4. Un exemple de réseau super nodal : Kazaa

Bien que les détails de fonctionnement de Kazaa ne soient pas entièrement divulgués, on sait que ce logiciel utilise une technique de super-peer. En outre, il s'intéresse aussi au problème de la qualité des noeuds (fiabilité des informations, mais aussi taux et vitesse d'upload, ...)

Principes de Kazaa
Un nouvel utilisateur doit ouvrir un compte, déclarer ses répertoires de fichiers partagés. En fonction de sa bande passante, le logiciel décidera si le client est ou non un super-peer (possibilité de l'activer ou de le désactiver manuellement). Une incertitude règne quant à la façon de connecter deux super-peer ensembles. Il se peut que ce soit grâce à un protocole décentralisé de type broadcast. Lors d'une recherche, un noeud envoie sa requête à son super-peer (il lui transmet en même temps un index de ses fichiers partagés). Le super-noeud dispose d'un index des ses propres ressources, ainsi que celle des noeuds de son cluster, ce qui lui permet de répondre à la requête. Les files d'attentes sont paramétrées en fonction de plusieurs critères, dont le ratio upload/download et la qualité des ressources.


3.5. Seti@home

Dans la plupart des articles sur le P2P, on retrouve quelque part un paragraphe concernant le projet Seti@home. Je tiens à préciser qu'il n'y a aucune raison de rapprocher ce projet du P2P. En effet, il y a un serveur centralisé, qui communique indépendamment avec chacun des utilisateurs ; ceux-ci sont incapables de communiquer entre eux. On a donc bien affaire ici à un programme fonctionnant typiquement sur le mode client/serveur. Merci de votre attention.


4. Le P2P sémantique

Bien qu'étant encore au stade de la recherche, le P2P sémantique nous semblait intéressant à présenter ici. Il ne s'agit plus ici de s'intéresser à une architecture ou à un programme précis, puisque la notion de P2P sémantique peut s'appliquer à toutes les architectures et tous les programmes précités (selon des changements plus ou moins importants). Le principe est d'ajouter de l'information dynamique aux tables de routage. Cette information peut être généraliste, ou bien au contraire très spécifique, en fonction des besoins. Un des problèmes est de chercher à trouver un équilibre entre taille et précision.


4.1. Quelle information ajouter

On peut ajouter de l'information sur 3 points particuliers : le contenu des noeuds, les requêtes ou encore les utilisateurs.

  1. Sur le contenu des noeuds
    • Suppose que le contenu des différents noeuds est homogène (même information partagée par tous)
    • Le routage se fera par comparaison entre la requête et les index
    • Exemple : Routing Indices [ (17) ] ou bien SON [ (18) ].
  2. Sur les requêtes
    • Suppose peu de requêtes différentes
    • Le routage se fait alors en comparant deux requêtes.
  3. Sur les utilisateurs
    • Suppose que les utilisateurs ont toujours les mêmes besoins
    • Routage en comparant les utilisateurs entre eux.
  4. On peut enfin avoir un mélange de ces trois solutions.

4.2. Routing Indices

Le but des indices de routage, comme expliqué dans [ (19) ] est d'introduire de l'information sur le contenu des noeuds (index). Dans ce sens, c'est un système analogue aux systèmes d'indices répartis et hiérarchisés pour les moteurs de recherche sur l'internet.

Figure 9: Exemple de Routing Indices
Chemin Nombre de documents BDD Langages Réseaux Théorie
B 100 20 30 0 10
C 1000 0 50 300 0
D 200 100 150 0 100
Table 1: Exemple de Routing Indices pour le noeud A

Le tableau 1 se lit de la façon suivante :
B peut accéder à 100 documents, dont 20 traitent de BDD, 30 de langages et 10 de théorie.
D accède à 200 documents : 100 concernent les BDD, 150 les langages, et 100 la théorie.

Dans la mesure où ce tableau représente les informations pour le noeud A, on peut en conclure que ce noeud est en mesure d'accéder à 1 300 documents (attention, ils ne sont pas forcément différents, puisque B, C D ainsi que leurs fils n'ont pas de liaisons directes), dont 120 traitent de BDD, 230 de langages, 300 de réseaux et 110 de théorie.
Cet exemple nous montre bien Que tous les documents n'apparaissent pas forcément dans une catégorie : B permet d'accéder à 100 documents, dont seulement 60 sont répertoriés dans les domaines cités. Qu'un document peut couvrir deux domaines, et donc être répertorié deux fois. C'est ici le cas pour le noeud D. Plus concrètement, un document traitant de la théorie du langage SQL sera répertorié en "théorie", en "langages", et en "BDD".

Algorithme de recherche
  • Résoudre localement la requête Q. S'il n'y a pas suffisamment de résultats :
    • Evaluer la proximité des successeurs
    • Tant qu'il n'y a pas assez de résultats
      • Prendre le successeur S le plus proche
      • Recherche (Q, S)
    • Retourner les réponses
Performances de la recherche
  • Le nombre de messages est diminué par rapport à l'algorithme de recherche de Gnutella
  • L'exploration est restreinte aux noeuds ayant la plus grande probabilité de succès
  • Pas de garantie d'avoir tous les résultats
  • Pas d'informations sur le nombre de sauts nécessaires (améliorations possibles grâce à d'autres RI)
  • Plutôt orienté recherche des K meilleurs résultats.
Bilan des RI
  • La structure d'indexation est assez simple, mais sa mise à jour (non présentée ici, mais explicitée dans [ (20) ]) génère beaucoup de messages
  • Fonctionne bien pour obtenir les meilleurs résultats, mais qui ne sont pas forcément tous les résultats
  • Nécessite la détection (ou la prévention) des cycles (A a pour fils B qui a pour fils C qui a pour fils A)
  • Bien pour des langages de type mots-clef, mais pas généralisable à des langages plus complexes
  • RI ne donne pas d'indications sur le nombre de sauts (mais d'autres oui).

4.3. SON : Semantic Overlay Networks

Figure 10: Exemple de SON
L'exemple présenté sur la figure 10 nous montre 8 noeuds classés par genre de musique. Un noeud est relié à un autre par un lien logique de type ni, nj, lk (lire noeud i, noeud j, lien k). Par exemple, sur le schema, le lien entre A et B est : A, B, 'Rock'.
Les liens ayant le même l forment un SON.
Ici, nous avons les SON suivants : Rock, avec les noeuds A, B et C ; Rap, avec B, E, et F ; Jazz, avec E, F et G ; Techno, avec F, D et H ;

Un SON avec un seul label est un P2P classique. On peut également remarquer que lorsque le SON a été choisi, suite à une requête, alors on retombe une nouvelle fois sur un P2P classique.
Encore une fois, le plus gros problème vient de la définition sémantique : comment définir le SON ?
Pour ce faire, on peut imaginer un style (musique) avec des sous-styles (Rock, Jazz, ...) comprenant eux-mêmes d'autres sous-styles (Pop, Rock'n Roll, indépendants, ... pour Rock par exemple).
Une bonne hiérarchie de classification demande : Des classes dont les documents appartiennent à un petit nombre de noeuds. Que les noeuds se trouvent dans peu de classes. Des classificateurs faciles à construire et les plus fiables possibles.

Résolution d'une requête
Il faut tout d'abord chercher les concepts correspondants à la requête, puis ensuite propager cette dernière dans le SON correspondant, ainsi qu'à ses ascendants et descendants.

Bilan des SON
Ces réseaux reposent avant tout sur la classification des documents. Celle-ci est relativement complexe à mettre en oeuvre, et est surtout liée à un domaine précis. Il est d'envisager des SON ayant traits à des domaines divers, mais d'autres problèmes surgissent alors.
Les SON favorisent la précision, mais pas la complétude.
Du point de vue technique, on peut tout à fait paralléliser les SON afin d'obtenir des temps de réponse meilleurs (les requêtes sont alors lancées dans chacun des SON sélectionnés par un classificateur).
Les résultats expérimentaux montrent une amélioration notable du nombre de messages comparativement à Gnutella.


5. Problèmes ouverts dans la recherche sur les P2P

Un problème ouvert est un problème auquel on n'a pas encore trouvé de solution, et auquel on est susceptible d'en trouver une (21) .

  • Sécurité
    • Disponibilité
    • Authentification des ressources (si plusieurs sources pour une ressource : plus vieille ressource (probabilités que ce soit l'originale, et donc une version plus "authentique")), réputation des pairs, vote
    • Anonymat de l'auteur du document (CF authentification), des serveurs (quels documents sont sur un serveur donné), du lecteur, et des documents (sur quel noeud est un document précis).
  • Réputation
  • Contrôle du Free-Riding
  • Tables de hachage dynamiques
  • P2P Sémantique : ce n'est que le début. On peut explorer par exemple le mélange de différentes technologies, ou bien encore chercher à introduire des connaissances dynamiques, comme l'apprentissage (modifications de différents paramètres en fonction des observations menées sur le réseau).

6. Utilisations du P2P


6.1. Calculer

Le P2P permet de mettre en commun de nombreux ordinateurs, disposant chacun de ressources limitées. Mais en "additionnant" les ressources de chacun, on obtient des performances théoriques gargantuesques.
Un exemple parlant aux mathématiciens est le calcul de matrices : l'une des méthodes permettant l'inversion des matrices nécessite n3 opérations (n étant la taille de la matrice (qui comporte donc n² cases)). Un des challenges actuels est de réaliser un tel calcul grâce au P2P, avec n = 10^6 (un million), soit un total de 10^18 (un milliard de milliard) opérations ... (22)
Le but est donc de diviser ce gros calcul qu'est l'inversion de la matrice en petits calculs plus ou moins indépendants que l'on pourra répartir entre les pairs. Cet algorithme demande cependant d'avoir déjà une partie des informations pour pouvoir continuer. Il faudra donc que les pairs échangent des données afin de pouvoir effectuer de nouveaux calculs.
Toutefois, outre le fait de trouver suffisamment de pairs pour réaliser ce test, d'autres problèmes surviennent :

  • Les noeuds sont volatiles, c'est-à-dire qu'ils arrivent et partent quand ça leur plaît. Donc il va falloir confier le même calcul à plusieurs noeuds (notion de clouage).
  • Du fait que l'algorithme a besoin des calculs précédents pour en effectuer de nouveaux, les temps de communication entre deux noeuds sont très supérieurs aux temps de calcul. Or sans vouloir faire intervenir la rentabilité ici, le projet ne présentera que peu d'intérêt si les 3/4 du temps sont passés à échanger des données et non à calculer.
  • ...
Des solutions sont donc actuellement étudiées afin de réaliser de grands calculs grâce au P2P. On peut citer, entre autres projets :


6.2. Diffuser des données

La diffusion de données en utilisant le P2P permettrait de toucher beaucoup plus de personnes avec des moyens bien inférieurs à ceux nécessaires aujourd'hui. Actuellement, si on veut émettre de la vidéo (par exemple), il faut non seulement une machine qui diffuse la vidéo (logique), mais également une très très bonne connexion : plus le nombre de gens est important, plus la connexion doit être grosse (23) .
En revanche, en utilisant le P2P, chaque personne devient à la fois réceptrice et émettrice. Ainsi, le diffuseur initial n'a plus que quelques clients connectés à lui, chacun de ces clients jouant également le rôle de diffuseurs pour d'autres clients.
Encore une fois, c'est plus complexe à mettre en oeuvre qu'à expliquer, les principaux problèmes étant la volatilité des clients (enfin des serveurs devrais-je dire), qui pose des problèmes de rattachement des clients, comme le montrent les figures 11, 12 et 13.

Figure 11: Modèle de diffusion avant le départ d'un pair
Figure 12: Situation au moment du départ
Figure 13: Une des manières de relier les 3 pairs orphelins

7. Conclusion

Dans cet article, j'ai souhaité mettre en avant le fait qu'il existe différents modèles de P2P, chacun disposant d'avantages et d'inconvénients. Il est donc logique que l'utilisation faite de ceux-ci ne soit pas la même.
Etonnamment, la recherche sur les P2P est en retard. En effet, contrairement aux cas plus traditionnels, cette technologie n'est pas issue de la recherche fondamentale, mais a été récupérée par cette dernière. C'est pour cette raison qu'on en n'est qu'au début du P2P sémantique, ou même du calcul P2P, de la diffusion de données, ...
Si vous souhaitez vous renseigner sur ces technologies, le plus simple est encore d'aller voir les sites des projets qui vous semblent intéressants, ou de rechercher des informations via un moteur de recherche.


8. Sources

Ce document est en partie inspiré d'un cours de Bruno Defude, que vous trouverez ici.
Les autres sources s'appliquant à des parties plus ciblées du document sont citées dans les notes de bas de page.


9. Notes


(1) Napster est un des premiers logiciels P2P grand public. C'est principalement lui qui a permis l'essor du P2P. Site officiel : http://www.napster.com
(2) Message Digest 4 : Fonction de hachage à sens unique de 128 bits conçue par Ron Rivest, utilisant un ensemble simple de manipulations de bits sur des opérandes de 32 bits.
(3) Je tiens à remercier les administrateurs de razorbak2 pour ces précisions. PLus d'informations sur http://www.razorback2.com/
(4) Institut National de Recherche en Informatique et en Automatique
(5) Plus d'informations : le site du projet COMETE et le site de mlDonkey
(6) Un message broadcast est un message qui va être envoyé à toutes les machines d'un (sous) réseau.
(7) La hauteur d'arbre est la distance maximale, en noeuds, d'un bout à l'autre de l'arbre. Ici, il s'agit donc du nombre d'ordinateurs entre soi-même et le client le plus lointain. Sur la figure 4, cette hauteur est de 3.
(8) Cela revient à dire que deux noeuds se "connaissant" (comme ceux du graphique page ) ne sont pas séparés par plus de 5 à 8 machines.
(9) S. Saroiu, P. Gummadi, S.Gribble, "A measurement study of peer-to-peer sharing systems", Multimedia Computing and Networking, 2002.
(10) E. Adar, B. Hubermann, "Free riding on gnutella" IEEE ICDE, 2002.
(11) Dans les années 30, un scientifique de l'université de Harvard, G.K. Zipf, a montré qu'en classant les mots d'un texte par fréquence décroissante, alors, on observe que la fréquence d'utilisation d'un mot est inversement proportionnelle à son rang. La loi de Zipf stipule que la fréquence du second mot le plus fréquent est la moitié de celle du premier, la fréquence du troisième mot le plus fréquent, son tiers, etc. Cette loi peut s'exprimer de la manière suivante :
Fréquence d'un mot de rang N = (Fréquence du mot de rang 1) / N
(12) M. Derbali, F. Embouazza, "Etude des réseaux peer-to-peer", TER encadré par O. Fourmaux, Université de Paris 13, 2003.
(13) IBP : Internet Backplane Protocol est un middleware (ou intergiciel) permettant le stockage et la gestion de données à distance. Plus d'informations : http://loci.cs.utk.edu/ibp/
(14) Algorithme d'ordonnancement permettant une répartition de charge équitable entre les serveurs.
(15) B. Yang, H. Garcia-Molina, "Designing a super-peer network" ICDE Conf., 2003. http://wwwdb.stanford.edu/~byang/pubs/superpeer.pdf
(16) TTL : Time To Live : temps de vie. Ici, cela représente le nombre maximal de noeuds auxquels sera propagé une requête.
(17) A. Crespo, H. Garcia-Molina, "Routing indices for peer-to-peer systems" ICDCS, 2002.
(18) A. Crespo, H. Garcia-Molina, "Semantic overlay networks for p2p systems" Technical Report, Computer Science Dpt, Stanford University, 2002. http://www-db.stanford.edu/~crespo/publications/op2p.pdf
(19) A. Crespo, H. Garcia-Molina, "Routing indices for peer-to-peer systems" ICDCS, 2002.
(20) A. Crespo, H. Garcia-Molina, "Routing indices for peer-to-peer systems" ICDCS, 2002.
(21) Par exemple 1 + 1 = 5 n'a pas encore de solution (on oublie les modulo et les changements de base, merci), mais on n'est pas capable de démontrer qu'il n'y en a pas.
(22) Pour donner une meilleure idée de la taille, nous présentons ici le calcul de la taille que prendra la matrice originale (et elle seule) en mémoire : Chaque nombre est codé sur 32 bits, et nous avons 10^12 nombres, soit un total de 32 * 10^12 bits, soit 32 000 Gb, ce qui revient donc à 4 Go.
(23) La bande passante ne doit pas être égale à la somme des BP nécessaire à chaque client, mais est proportionnelle au nombre de clients, selon une loi probabiliste. Ceci s'explique par le fait que l'envoi via internet ne se fait pas en continu, mais par paquets. Donc entre l'envoie de deux paquets au client 1, je peux glisser un pour plusieurs paquets pour d'autres clients
By Price:
Product Tags:

Aucun commentaire:

Enregistrer un commentaire

Inscription à : Publier les commentaires (Atom)