Stratégies de recherche de données dans les systèmes pair-à-pair décentralisés

Les systèmes pair-à-pair ont pour but la mise en relation d’utilisateurs (personnes ou machines) afin de mutualiser des ressources (processeurs, espace mémoire, fichiers). Ils sont apparus dans Internet à la fin des années 90, et ont été depuis en développement continuel. Ces systèmes sont parfois appelés réseaux pair-à-pair par référence au réseau d’interconnexion des utilisateurs du système. D’abord apparus à des fins de partage de fichiers, les systèmes pair-à-pair sont utilisés depuis quelques années pour des applications variées nécessitant une décentralisation (grilles, réseaux ad-hoc, etc.). Depuis les débuts d’Internet, le modèle client serveur était le modèle de référence pour la mise à disposition de ressources. Dans ce modèle un serveur stable donne accès à des ressources ; il peut s’agir :

– De services, comme le fait un DNS (Domaine Name System) qui traduit les noms de domaines en adresses IP ;
– De fichiers, comme le font les serveurs FTP (File Transfert Protocol) ;
– D’un contenu multimédia diffusé en continu comme les radios et télévisions en ligne;
– Ou encore de contenus plus complexes comme le font les sites qui donnent accès à des pages hypertextes ou des bases de données.

Lors de l’utilisation du modèle client-serveur, il est nécessaire de prévoir une augmentation potentiellement rapide de la charge. Ceci nécessite toutefois des ressources importantes, et impose des contraintes d’entretien, de bande passante, de sécurité, de charge et de rapidité d’accès à la ressource. Toutes ces exigences rendent de tels systèmes coûteux.

Vue d’ensemble des systèmes pair-à-pair

Généralités

Les systèmes pair-à-pair sont des systèmes visant à permettre à des utilisateurs la mise en commun d’objets et leur recherche en vue de leur récupération (pour les fichiers) ou de leur utilisation (pour les ressources de calcul). Dans la suite, le terme objet sera utilisé pour nommer indistinctement une ressource de calcul, un fichier, ou une autre information (entrée DNS par exemple), et le terme récupération sera utilisé qu’il s’agisse d’obtenir un accès à une ressource de calcul, de télécharger un fichier, ou d’obtenir une autre information.

Les systèmes pair-à-pair ont plusieurs caractéristiques les distinguant des autres systèmes de partage d’objets.
– Ils permettent de représenter des échanges sociaux au sens où ils lient des utilisateurs qui interagissent de manière humaine. Les objets sont échangés selon les intérêts des utilisateurs.
– Le nombre d’utilisateurs d’un système pair-à-pair peut être très important, de l’ordre du millier ou million selon les systèmes [22].
– Ils sont dynamiques, car ils doivent permettre à chaque instant l’arrivée et le départ d’utilisateurs.
– Ils sont décentralisés, au moins en partie : la récupération des objets, voire la recherche d’objets, ne nécessite pas l’utilisation de serveurs stables.

Dans ce mémoire, le terme de réseau pair-à-pair sera utilisé pour désigner un réseau d’utilisateurs créé par un système pair-à-pair. La dénomination de système pair-à-pair sera utilisée pour parler du fonctionnement des protocoles de recherche et de publication et non uniquement de l’interconnexion des utilisateurs. La récupération des objets sera à l’inverse peu abordée ici. Nous effectuerons l’étude des réseaux pair-à-pair es sentiellement au travers d’une modélisation par des graphes. Nous allons voir dans la suite comment utiliser le formalisme de la théorie des graphes dans le cadre des systèmes pair-à-pair.

Modèle utilisé 

Permettre la recherche d’objets dans les systèmes pair-à-pair demande de répondre à plusieurs questions. Comment les nœuds sont-ils connectés entre eux ? Comment sont envoyés les messages dans le réseau ainsi créé ? Afin d’utiliser une terminologie claire, les notations utilisées dans ce mémoire sont détaillées ci-dessous.

Terminologie
Un système pair-à-pair fait évoluer les machines connectées selon un protocole propre. Un réseau logique est l’interconnexion qui relie virtuellement les utilisateurs, au dessus du réseau physique permettant à toute machine de communiquer avec toute autre machine. Le réseau logique repose sur des connexions logicielles maintenues grâce à u n protocole de communication (par exemple TCP/IP).

Un nœud représente un processus client-serveur exécuté sur une machine et permettant à un utilisateur d’utiliser le système pair-à-pair. Chaque nœud peut être tour à tour demandeur ou fournisseur d’un objet du système. Il peut jouer pour chaque requête le rôle de :
o client, lorsqu’il cherche un objet dans le réseau ;
o Serveur, lorsqu’il fournit un objet cherché par un autre nœud ;
o Routeur, lorsqu’il reçoit une requête qui devra être dirigé vers d’autres nœuds.

On nommera logiciel client-serveur un logiciel permettant d’accéder à un système pair-àpair via un protocole donné (et permettant d’être client et serveur). Dans un système pair-àpair, chaque nœud peut se servir d’un logiciel client-serveur différent, tant que ce logiciel est compatible avec le protocole avec le protocole utilisé. Afin de préciser le rôle d’un nœud à un instant donné, on pourra caractériser un nœud client, pour un nœud effectuant une recherche, et un nœud serveur, pour un nœud fournissant un objet, et un nœud routeur pour un nœud transmettant un message dans le réseau.

Un lien entre deux nœuds symbolise une connexion logicielle permettant la communication entre ces deux nœuds. Ces liens ont plusieurs caractéristiques.
– Un lien passe par plusieurs liens physiques.
– La traversée de chacun de ces liens peut prendre un temps arbitrairement long car les réseaux physiques (et donc les liens physiques) au dessus desquels sont créés les réseaux pair-à-pair sont souvent asynchrones.
– Enfin, si certains systèmes pair-à-pair utilisent des liens orientés pour le réseau logique, la plupart de ces systèmes sont basés sur le protocole réseau IP, qui permet de connaître l’origine d’un message. Il est alors possible et facile de connaître les liens entrants, même dans des systèmes pair-à-pair utilisant des liens non orientés.

Les systèmes pair-à-pair sont dynamiques, c’est-à-dire que chaque nœud peut arriver et repartir au cours du temps. Les utilisateurs doivent en effet pouvoir s’y connecter ou s’en déconnecter à volonté. La propriété précédente (forte connexité) doit bien sûr rester vérifiée au cours du fonctionnement du système, donc en cas de déconnexion de plusieurs nœuds. Un envoi d’informations d’un nœud à un autre au sein du réseau sera nommé message. Lorsque ce message correspond à une recherche d’objet, il sera nommé requête.
– Voisin d’un pair : Un pair P est voisin d’un pair Q si Q est connu dans la table de routage de P. Cette relation n’est pas symétrique.
– Topologie d’un P2P : C’est la vue globale sur le P2P. Elle est un graphe dont les sommets sont les pairs. Un sommet N est connecté au sommet M si et seulement si N est voisin de M. La topologie montre la connectivité du P2P. Elle est très liée au mécanisme de routage.
– Espace dataID : Chaque donnée du système a une clé dataID qui l’identifie. L’espace de ces clés est l’Espace dataID. Les clés peuvent être générées aléatoirement, par une fonction de hachage, ou obéir à une logique propre à l’application. Par exemple, dans une application de gestion de bibliothèque, il est primordial que les clés respectent une structure arborescente (exemple : sciences/sociales/sociologie/…). L’Espace dataID est donc un espace qui peut être équiréparti ou disparate, homogène ou hétérogène.
– Espace nodeID : Chaque pair a une identité logique dans le P2P. Cette identité est-à-priori indépendante de son adresse IP.
– Distributed Hash table (DHT) : C’est l’extension du c oncept de fonction de hachage en environnement distribué. Il s’agit d’une table distribuée indexée par des clés générées par une fonction de hachage distribuée. Cette notion peut être vue comme une boîte noire qui prend en entrée une dataID et fournit en sortie le nodeID en charge de la donnée .

Table des matières

Introduction
1. Vue d’ensemble des systèmes pair-à-pair
1.1 Généralités
1.2 Modèle utilisé
Terminologie
1.2 Quelques systèmes Pair-à-pair
1.3.1 Les systèmes pair-à-pair hybrides ou ‘super pair’
1.3.2 Systèmes pair-à-pair décentralisés non structurés
1.3.3 Systèmes pair-à-pair décentralisés structurés
1.4 Comparaison des systèmes pair-à-pair
Conclusion
2. Etude analytique des réseaux pair-à-pair décentralisés non structurés
2.1 Définitions de base
2.2 Graphe aléatoire généralisé et recherche probabiliste
Conclusion
3. Contribution : Systèmes décentralisés avec proximité d’intérêts
3.1 Représenter les intérêts des pairs comme un graphe
3.2 Utiliser la propriété de loi puissance
3.3 Utiliser les agrégats
3.3.1 Choisir efficacement ses voisins
3.3.2 Diminuer le trafic
3.4 Contribution : REBI (Recherche sur un Réseau logique Basé sur les Intérêts)
3.4.1 Proposition d’une méthode de recherche efficace
3.4.2 Principes utilisés dans REBI
Conclusion
4. Validation expérimentale de notre proposition
4.1. Présentation du simulateur OverSim
4.1.1 Design du simulateur OverSim
4.1.2 Protocoles Overlay supportés
4.2. Scénario de simulation et métriques de performance
4.3. Résultats
Conclusion et perspectives d’amélioration
5. Conclusion générale et perspectives
Bibliographie

Lire le rapport complet