Soutenance mémoire
Contexte
Le stockage de données décentralisé est au cœur des problématiques de l’informatique contemporaine. Cette dernière doit être en mesure de faire face à un flot colossal d’information à archiver, de manière sûre et sécurisée. Nous sommes actuellement en pleine ère de l’informatique dans les nuages, que l’on nomme également Cloud Computing. Ce concept, qui consiste à déporter un maximum de traitements sur des grilles de serveurs, pour offrir aux clients un accès universel à leurs ressources de n’importe où, est le résultat d’une évolution qui a débuté il y a plus de 20 ans. Le modèle centralisé, qui était jusqu’à la fin des années 1990 le modèle de référence pour le stockage de données, est devenu obsolète face à la croissance très rapide d’internet. L’augmentation conjointe du nombre d’utilisateurs et du volume de données à stocker au-dessus des capacités des serveurs, ont poussé les différents acteurs du stockage de données à considérer d’autres approches. Le modèle pair-à-pair s’est très rapidement distingué –par le biais de plateformes célèbres telles que Napster ou eMule– comme une alternative fonctionnelle, robuste et à faible coût pour le stockage et l’échange décentralisé de données. La philosophie derrière les architectures pair-à-pair consiste à répartir le service sur les clients (que l’on appelle pairs). Chaque pair peut alors occuper la fonction de client ou de serveur en fonction des requêtes qu’il reçoit. Dans les premiers types de réseaux pair-à-pair, seul le transfert de l’information était décentralisé alors que l’indexation était, quant à elle, centralisée pour des questions d’efficacité des requêtes de recherche. Les architectures pair-à-pair totalement décentralisées n’ont vu le jour qu’à l’issue d’un processus d’évolution mené en grande partie par la recherche scientifique– avec l’arrivée des tables de hachage distribuées .
La disponibilité des données stockées dans les architectures décentralisées en pair-à-pair s’obtient par la mise en place de schémas de l’information efficaces. Ces systèmes distribués sont, en effet, constitués d’un très grand nombre de machines hétérogènes sur lesquelles il n’existe aucun contrôle et qui sont inévitablement victimes de fautes. Chaque système de stockage doit donc s’assurer que les données qu’il héberge sont suffisamment redondantes pour ne jamais être perdues. La redondance consiste à dupliquer de l’information identique sur différents pairs pour tolérer un certain nombre de fautes. Ce niveau de redondance est calculé en fonction de la disponibilité souhaitée dans le système ainsi que par le nombre de fautes observées.
Les réseaux pair-à-pair
Du modèle client-serveur au pair-à-pair
Le modèle pair-à-pair émerge à la fin des années 1990 en réponse aux problématiques engendrées par l’explosion du nombre d’usagers d’internet . Il vient compléter l’approche client-serveur lorsque le nombre d’utilisateurs d’un service devient très grand et que ce service nécessite une utilisation intensive de ressources (temps CPU, espace de stockage, accès disques, bande passante, etc.) pouvant le mener vers un déni de service (DoS) quand la charge dépasse sa capacité.
Dans l’architecture client-serveur , un serveur s fourni un service réseau à un ensemble de clients ci par le biais d’une liaison point à point (unicast). La disponibilité du service est entièrement dépendante de s et cette architecture présente un certain nombre de vulnérabilités inhérentes à son aspect centralisé dont les plus critiques sont :
– la perte de s suite à une faute (panne de l’hôte, déconnexion réseau, attaque, etc.) rend indisponible le service à l’ensemble des clients ;
– la surcharge de s suite à un trop grand nombre de connexions peut entraîner un déni de service. i.e., s n’est plus en mesure de traiter les requêtes et le service devient indisponible ;
– la corruption de s par un tiers malveillant a des répercussions sur l’intégralité des clients du service.
Le modèle pair-à-pair propose une décentralisation du service en mettant à contribution les clients qui deviennent à leur tour chacun des fournisseurs d’une partie du service. Dans cette architecture, les pairs pi sont à la fois clients et serveurs. Nous verrons dans la suite de ce chapitre qu’en fonction des approches qui sont proposées, les rôles des pairs sont plus ou moins homogènes et que la transition du modèle client-serveur pur au pair-à-pair totalement décentralisé s’est faite en plusieurs étapes. Le choix du type d’architecture est en réalité dépendant du type de service que l’on souhaite déployer. C’est dans ce contexte de mutualisation et de partage de ressources que se sont développées les applications pair-à-pair large échelle tels que le partage de contenu (Napster, BitTorrent, Gnutella, eMule, KaZaa, …), la diffusion de flux (PPTV, Joost, TVants, PPLive, SopCast, …), le multicast applicatif (Scribe, Bayeux, NICE, OMNI, SCAMP, OverCast,…), la voix sur p2p (Skype), le stockage persistant (Oceanstore, Wuala, BitVault, Glacier, TotalRecall, …) ou encore les tables de hachage distribuées (CAN, Chord, Tapestry, …). De part sa décentralisation, le pair-à-pair a également favorisé le développement d’applications résistantes à la censure et proposant des niveaux d’anonymat à leurs utilisateurs. Plusieurs définitions du pair-à-pair ont été proposées dans la littérature. [Buford et Yu, 2010] en identifient deux qui couvrent les concepts de partage de ressources, d’auto-organisation, de décentralisation, de topologies et de réseaux logiques :
1. selon [Androutsellis-Theotokis et Spinellis, 2004] : « Les systèmes pair-à-pair sont des systèmes distribués qui consistent en une interconnexion de nœuds capables de s’autoorganiser en topologies réseau dont le but est de partager des ressources tel que du contenu, des cycles CPU, de l’espace de stockage et de la bande passante. Ces réseaux sont capables de s’adapter aux fautes et de tolérer les groupes de nœuds ayant un comportement instable tout en conservant un niveau de connectivité et de performances acceptable sans recourir au support d’un serveur global centralisé ni d’une quelconque autorité. » ;
2. selon [Buford et al., 2008] : « Un réseau logique est une couche réseau applicative virtuelle dans laquelle les nœuds sont adressables, qui fournit la connectivité, le routage ainsi que l’acheminement des messages entre les nœuds. Les réseaux logiques sont fréquemment utilisés comme support au déploiement de nouveaux services réseaux ou pour fournir une structure de routage qui n’est pas accessible à partir du réseau physique sous-jacent. Beaucoup de systèmes pair-à pair sont des réseaux logiques qui fonctionnent au-dessus d’internet. ». un réseau logique recouvre le réseau physique définissant de ce fait une nouvelle topologie virtuelle. Nous ajoutons à cette définition qu’un réseau logique définit une structure de voisinage entre les pairs.
Pair-à-pair centralisé
La première génération de réseaux pair-à-pair voit le jour en 1999 avec l’arrivée de Napster [Napster, 1999] puis en 2000 avec BitTorrent [Cohen, 2008]. Elle est dite centralisée parce que le fonctionnement de ces protocoles est dépendant de serveurs. En réalité, les protocoles de première génération présentent un début de décentralisation puisque l’échange d’information est effectivement fait de pair à pair. Par contre des serveurs jouent le rôle d’index pour chercher les données et mettre en relation les pairs.
Napster
Napster [Napster, 1999] était une plateforme d’échange de fichiers musicaux de type mp3 crée par Shawn Fanning et Sean Parker dans laquelle chaque pair pouvait mettre à disposition le contenu de sa bibliothèque musicale. Dans cette architecture, chaque pair envoie la liste de ses fichiers à un serveur qui stocke l’association adresse du pair ↔ données + métadonnées. C’est en réalité un cluster d’environ 160 serveurs selon [Saroiu et al., 2003]. Lorsqu’un pair recherche un nom de fichier, il envoie une requête sous forme de mots clés au serveur d’index auquel il est connecté. Ce dernier lui retourne une liste de n-uplets (ip, fichier, metadonnées). Une fois que l’utilisateur a choisi la donnée f ichieri qui l’intéresse, l’échange se fait directement entre le pair demandeur et l’hébergeur ipi . Quand le fichier est téléchargé, le pair demandeur devient à son tour un hébergeur qui est indexé dans le serveur central pour cette donnée.
Cette architecture fournit un mécanisme de recherche efficace puisqu’il consiste en la simple interrogation d’un index. Elle est également tolérante au churn (les perturbations engendrées par les connexions/déconnexions de pairs) et allie expressivité des requêtes à l’exhaustivité des réponses. Cependant, l’aspect centralisé, bien que relativement résistant au déni de service grâce à l’utilisation de cluster reste vulnérable à la censure. A titre d’exemple, la version gratuite et publique de Napster a été fermée en 2001 suite à une décision de justice et a signé l’arrêt total du service puisque les serveurs le faisant fonctionner ont été déconnectés.
BitTorrent
BitTorrent [Cohen, 2008] est un protocole créé par Bram Cohen mais également un client pair-à-pair [BitTorrent, 2012]. Son objectif est de fournir la possibilité à n’importe qui de déployer une infrastructure pair-à-pair sur ses propres serveurs. Dans BitTorrent, un serveur (le tracker) répertorie un certain nombre de ressources à partager (les torrents). Les pairs connectés au tracker s’abonnent aux torrents qui encapsulent les ressources qu’ils souhaitent récupérer. Un torrent est en fait un fichier contenant les méta-données de la ressource ainsi que l’adresse du tracker qui l’héberge. Il est donc en général mis à la disposition des pairs par son propriétaire au moyen d’un hyperlien sur un site web connu. Dans le protocole BitTorrent les données sont découpées en blocs de tailles fixes choisies entre 64Ko et 4Mo. Le fichier torrent contient la liste des blocs ainsi que leur somme de contrôle de type SHA-1 [SHA, 1995]. Lorsqu’un pair p souhaite télécharger une donnée d, il récupère le torrent de d et se connecte au tracker correspondant. Ce tracker lui retourne un sous ensemble pi de pairs parmi tous ceux déjà abonnés au torrent de d (le swarm). p peut ensuite récupérer le document en se connectant aux pairs pi et en téléchargeant les blocs de la donnée qu’ils possèdent tout en s’assurant que les sommes de contrôle sont valides.
|
Table des matières
Introduction
I État de l’art
1 Les réseaux pair-à-pair
1.1 Du modèle client-serveur au pair-à-pair
1.2 Pair-à-pair centralisé
1.2.1 Napster
1.2.2 BitTorrent
1.3 Pair-à-pair semi-centralisé et hybride
1.3.1 eMule et eDonkey
1.3.2 FastTrack et KaZaA
1.4 Pair-à-pair décentralisé non-structuré
1.4.1 Gnutella v0.4
1.4.2 Freenet <v0.7
1.5 Pair-à-Pair décentralisé structuré
1.5.1 Chord
1.5.2 CAN
1.5.3 Tapestry
1.5.4 Kademlia
1.5.5 Freenet >v0.7
1.6 Les réseaux aléatoires
1.6.1 Théorie des graphes aléatoires : le modèle de Erdös-Rényi
1.6.2 Diffusion épidémique de l’information
1.6.3 Application à la diffusion fiable en multicast
1.6.4 SCAMP : Scalable Membership Protocol
1.6.5 HiScamp : Hiérarchisation de SCAMP
1.7 Conclusion
2 Disponibilité de l’information dans les réseaux pair-à-pair
2.1 Problématiques et enjeux
2.2 Redondance des données et tolérance aux fautes
2.2.1 Réplication
2.2.2 Codes d’effacement
2.2.3 Codes linéaires
2.2.4 Codes de Reed-Solomon
2.2.5 Codes linéaires aléatoires
2.2.6 Codes régénérant
2.2.7 Codes hiérarchiques
2.3 Durabilité du système
2.3.1 Politiques de réparation
2.3.2 Politiques de placement et de supervision
2.4 Plateformes de stockage persistant
2.4.1 Oceanstore/POND
2.4.2 PAST
2.4.3 CFS
2.4.4 Farsite
2.4.5 Total Recall
2.4.6 Glacier
2.4.7 BitVault
2.4.8 Wuala
2.5 Modèles de disponibilité et modèles de fautes
2.5.1 Indépendance des fautes
2.5.2 Fautes corrélées
2.6 Conclusion
3 Agents mobiles, systèmes multi-agents et applications
3.1 Intelligence artificielle, agent et systèmes multi-agents
3.1.1 Intelligence artificielle
3.1.2 Le concept d’agent
3.1.3 Les systèmes multi-agents
3.1.4 Systèmes complexes et simulation multi-agents
3.2 Agents mobiles
3.2.1 Vers une mobilité du code
3.2.2 Du code mobile aux agents mobiles
3.2.3 Discussion autour de la technologie des agents mobiles
3.2.4 Les plateformes agents mobiles et la plateforme JavAct
3.3 Agents mobiles et applications
3.3.1 Informatique ubiquitaire
3.3.2 Diagnostic et réparation
3.3.3 Recherche d’information
3.3.4 Détection d’intrusions
3.4 Conclusion
II Contributions
4 Mobilité et autonomie des données stockées : un modèle de flocking bioinspiré
4.1 Autonomie et mobilité des données
4.2 Un modèle de nuées d’agents mobiles
4.2.1 Schéma de l’information mobile et architecture de l’application
4.2.2 Contrôle de la mobilité : le déplacement en nuées
4.2.3 Modèle de Reynolds
4.2.4 Nuées d’agents mobiles
4.2.5 Dépôts de phéromones
4.3 Cadre expérimental
4.3.1 Environnement de simulation
4.3.2 Environnement d’expérimentation en milieu réel
4.4 Évaluation du déplacement en nuées
4.4.1 Mesure de la cohésion
4.4.2 Mesure de la couverture
4.4.3 Distribution des déplacements
4.5 Recherche d’une nuée
4.5.1 Recherche par marche aléatoire
4.5.2 Recherche guidée par des phéromones
4.5.3 Évaluations des algorithmes de recherche
4.6 Conclusion
Conclusion
