Routage efficace pour les réseaux Pair-à-Pair utilisant des tables de hachage distribuées

Émergence des réseaux pair-à-pair

Le phénomène de Peer-to-Peer (P2P) est né en 1999 avec le lancement de Napster [Nap99]. Il s’agissait d’un service qui permettait aux utilisateurs « de partager » des fichiers de musique au format MP3. Napster avait un index central pour localiser les fichiers. L’idée à l’origine de ce service était le stockage décentralisé des fichiers au niveau des points terminaux (plutôt qu’au niveau des serveurs). Cette idée, pourtant simple et à la base du concept de l’Internet, a rencontré un succès énorme. Suite à la croissance spectaculaire de Napster, des systèmes similaires ont rapidement émergé, les uns après les autres. Mais cette nouvelle génération de systèmes de partage de fichiers a été complètement décentralisée en termes à la fois de stockage et de récupération des ressources. Cette montée du P2P décentralisé tire sa force des limites du modèle clientserveur. Ce modèle, qui fait tourner Internet, avait pourtant rapidement gagné en popularité depuis le début des années 80. Mais la nature centralisée d’un serveur est victime de la diversification en effervescence continue du réseau mondial. Le modèle client-serveur est devenu sujet à des goulots d’étranglement, facilement attaquable, et difficilement exploitable pour la mise en œuvre de systèmes distribués ou d’applications de partage de fichiers. De plus, toute modification du modèle est excessivement difficile et coûteuse. Cependant, avec la démocratisation du matériel informatique, de plus en plus puissant, et des connexions à haut débit, l’Internet continue son effervescence. Et les réseaux IP ne cessent de prendre de l’essor. Le nombre de machines connectées sur les lieux de travail, mais aussi – et parfois en quasipermanence – à domicile, continue de croître. Les nouvelles technologies sans fil et l’essor de la mobilité ont aussi un impact croissant. Tous ces facteurs rendent possible et favorisent alors l’utilisation des applications décentralisées de partage de fichiers. De manière générale, ce sont toutes les technologies connues sous le nom de P2P, qui se trouvent ainsi favorisées. Du coup, le P2P n’est point une révolution en lui-même, mais bel et bien une conséquence d’une vraie révolution. Il tire ses racines des infrastructures IP, recouvre le réseau Internet, et a donc toujours existé d’une certaine manière.

Quelques statistiques du pair-à-pair

Concrètement, le flux P2P consiste en un échange de données grâce à une application, dite aussi «logiciel client ». Il existe une panoplie de logiciels P2P aux particularités et performances différentes. Certains logiciels sont des variantes permettant d’accéder à un même réseau P2P ; d’autres permettent d’accéder à plusieurs réseaux. Depuis quelques années, les réseaux les plus populaires [SM07] sont BitTorrent [Bit, CC03, Cha05] et eMule [eMu, KB05].

Quant au type de fichiers les plus échangés au sein des différentes communautés P2P, la vidéo arrive en tête [SM07]. En 2004 déjà, 61,44% du volume global du trafic P2P était constitué de fichiers vidéo [Par04].

Depuis cinq ans, la popularité des réseaux P2P n’est plus à prouver (cf. fig. 2) : entre 43,5% et 83% du trafic mondial est constitué de flux P2P. Ces chiffres résument des résultats de deux études qui ont été menées par ipoque (pour l’Allemagne, le reste de l’Europe, le Moyen-Orient et l’Australie) [SM07] et par Sandvine (pour l’Amérique du Nord) [San08a]. Les figures 3 et 4 illustrent ces chiffres qui quantifient l’agrégation des flux P2P montants (upstream) et descendants (downstream). En effet, les deux types de flux ne représentent pas le même taux d’occupation de la bande passante. Ceci est notamment dû aux débits asymétriques des réseaux ADSL. Cependant les deux études (celle de ipoque et celle de Sandvine) montrent une nette dominance sur la voie montante du trafic P2P par rapport aux autres types de flux IP. Récemment, Sandvine a évalué à plus de 61% le taux journalier moyen d’occupation de la bande passante mondiale par le flux P2P sur la voie montante [San08b].

Bien qu’actuellement le trafic P2P domine nettement tous les autres flux Internet, les volumes échangés sur les réseaux P2P croîtraient de près de 400% sur les cinq ans à venir, avec les échanges légaux croissant dix fois plus vite que les illégaux [Dic08]. Cependant, la croissance du P2P est jusque là essentiellement due aux applications de partage de fichiers qui sont majoritairement de type vidéo. Par ailleurs, la vidéo sur Internet, un service de l’Internet indépendant du P2P, est aussi en train de gagner du terrain et devrait voir son flux approcher la moitié de la totalité des flux internet dans cinq ans (cf. fig. 5) [Cis08].

Bien qu’actuellement le trafic P2P domine nettement tous les autres flux Internet, les volumes échangés sur les réseaux P2P croîtraient de près de 400% sur les cinq ans à venir, avec les échanges légaux croissant dix fois plus vite que les illégaux [Dic08]. Cependant, la croissance du P2P est jusque là essentiellement due aux applications de partage de fichiers qui sont majoritairement de type vidéo. Par ailleurs, la vidéo sur Internet, un service de l’Internet indépendant du P2P, est aussi en train de gagner du terrain et devrait voir son flux approcher la moitié de la totalité des flux internet dans cinq ans (cf. fig. 5) [Cis08].

Certes, la décentralisation des systèmes P2P à l’échelle du réseau mondial présente des faiblesses et des menaces. Outre la vaste question de la sécurité, les enjeux sont principalement éthiques et juridiques, tant au plan social qu’économique. Nous ne regarderons cependant pas le revers d’une médaille qui continue de séduire par ses atouts et ses potentiels.

Dans un réseau P2P, tous les pairs sont des sources potentielles de données, et les communications entre eux se développent de manière autonome et spontanée. L’avancement des techniques et du comportement des usagers aidant, un tel réseau – comme tout système auto-organisable – est donc indépendant du réseau sous jacent. Or, la rapidité dans les recherche et récupération de contenu (ou ressource), même dans un réseau overlay, va nécessairement dépendre du réseau sous-jacent. C’est pourquoi sensibiliser le réseau P2P au réseau sous-jacent se manifeste comme une problématique réelle. Cette sensibilisation doit consister à favoriser le dialogue entre pairs voisins dans le réseau sous-jacent (au sens de la proximité sous-jacente, en nombre de sauts IP). Par ailleurs, la croissance continue du volume du trafic P2P semble intimider les opérateurs de réseaux. D’une part, cette croissance augmente leur nombre d’abonnés aux meilleures offres de débit. D’autre part, cette croissance constitue une menace pour eux. En fait, mis à part le coût de gestion et de maintenance, ceux-ci paient un coût réel pour la bande passante utilisée par leurs abonnés. Par conséquent, une coopération effective entre les deux parties constitue un vrai défi. Elle amènerait chaque pair à trouver et récupérer la ressource qu’il souhaite, selon les critères et politiques de l’opérateur du réseau sous-jacent. Nous nous retrouvons donc là face à une problématique de sensibilisation particulière au réseau sous-jacent du réseau P2P. Enfin, la majorité des systèmes P2P émergeants, notamment les applications les plus populaires utilisent des tables de hachage distribuées (DHT). En bref, il s’agit d’algorithmes qui garantissent la localisation des ressources disponibles dans un système distribué. Sauf que les DHTs supposent les éléments du système (en l’occurrence, les pairs et les ressources) uniformément répartis ; ce qui est bien exceptionnellement le cas. Notre problématique se résume alors à la sensibilisation efficace d’un réseau P2P utilisant une DHT à l’infrastructure du réseau sous-jacent, avec une coopération possible entre les flux P2P et les opérateurs de réseaux. Nos travaux se sont d’ailleurs déroulés à Orange Labs (anciennement France Télécom R&D), les laboratoires de recherche d’Orange, opérateur de réseaux.

Réseaux de recouvrement

Ce paragraphe définit les réseaux de recouvrement et en donne quelques exemples..

Définition
Un réseau de recouvrement ou overlay est un réseau virtuel s’appuyant sur un ou plusieurs réseaux physiques existants. Parmi ces réseaux existants, dits sous-jacents ou underlay, l’Internet (ou des sous-réseaux de l’Internet) est un bon exemple. Dans la suite, ce sont les qualificatifs anglais : « overlay » pour un réseau de recouvrement et « underlay » pour un réseau sousjacent, qui seront privilégiés. Le réseau overlay est formé d’un sous-ensemble des nœuds du réseau underlay et d’un ensemble de liens logiques entre eux. Ces liens permettent une communication « directe » entre les nœuds concernés, en faisant abstraction de la topologie et des protocoles du réseau underlay. Nous désignons par nœud tout équipement du réseau, terminal ou intermédiaire, de quelque nature qu’il soit, jouant le rôle de routeur, client ou serveur.

Les réseaux overlays ont vu le jour dès lors qu’un nouveau service, inexistant dans le réseau, devait y être implanté. Ainsi tout problème informatique peut se résoudre par une couche d’indirection ou plutôt une redirection vers un nouveau réseau virtuel qui implémente la solution . Aussi peut-on concevoir une superposition de réseaux overlays. Dans ce cas, les réseaux overlays supérieurs s’appuient sur un ou plusieurs autres réseaux intermédiaires ayant l’Internet pour réseau underlay.

Quelques exemples
Voici quelques exemples de réseaux overlays : Resilient Overlay Network (RON) [ABK+ 01], Content Delivery Network (CDN) [Mor03] et Eternity [And96].

Resilient Overlay Network
Resilient Overlay Network (RON) [ABK+ 01] est une architecture overlay, basée sur l’Internet. Elle surveille la qualité des liens Internet pour permettre la détection rapide de routes alternatives lors des interruptions de service des applications unicast distribuées. Elle assure ainsi le rétablissement d’une communication entre un groupe de nœuds en quelques dizaines de secondes au lieu de plusieurs minutes, comme c’est le cas avec BGP-4 [RFC1771]. Il a été, en effet, observé qu’il est parfois plus rapide d’envoyer un message via un ou plusieurs intermédiaires, que de l’envoyer directement à sa destination.

Content Delivery Network
Content Delivery Network (CDN) [Mor03] est un réseau de serveurs cache offrant un dispositif de gestion optimisée des flux de données grand consommateurs de bande passante, permettant leur transit dans de bonnes conditions et empêchant les goulots d’étranglements. Les clients du CDN sont des fournisseurs d’accès au réseau ou des fournisseurs de contenu qui souhaitent fiabiliser leur disponibilité. Les principaux fournisseurs sont Akamai [Aka] et Cisco [Cis]. Il est à noter qu’un réseau de diffusion de contenu ne se limite pas au streaming (diffusion en temps réel de contenus audio/vidéo). Aussi est-il possible qu’un réseau pair-à-pair soit utilisé en tant que réseau de diffusion de contenu, moyennant les outils logiciels adéquats.

Eternity
Eternity [And96] a été développé dans le but de construire un moyen de stockage résistant aux attaques par déni de service. C’est un modèle pair-à-pair de stockage anonyme qui assure la réplication des données et la redondance des chemins. Il n’a jamais été implémenté.

Table des matières

INTRODUCTION
Émergence des réseaux pair-à-pair
Quelques statistiques du pair-à-pair
Problématique de recherche
Contributions et structure du mémoire
CHAPITRE 1 :ÉTUDE ET ANALYSE DES RÉSEAUX PAIR-À-PAIR
1.1 – Réseaux de recouvrement
1.1.1 – Définition
1.1.2 – Quelques exemples
1.2.4.1 – Resilient Overlay Network
1.2.4.2 – Content Delivery Network
1.2.4.3 – Eternity
1.2 – Caractéristiques et pratiques des réseaux pair-à-pair
1.2.1 – Définition
1.2.2 – Différentes approches
1.2.2.1 – Infrastructures pair-à-pair
1.2.2.2 – Applications pair-à-pair
1.2.2.3 – Communautés pair-à-pair
1.2.3 – Caractéristiques générales
1.3 – Architectures types des réseaux pair-à-pair
1.3.1 – Architecture centralisée
1.3.2 – Architecture décentralisée
1.3.2.1 – Caractéristiques
1.3.2.2 – Architecture décentralisée non structurée
1.3.2.3 – Architecture décentralisée structurée
1.3.3 – Architecture hybride
1.3.4 – JXTA
1.4 – Architectures et protocoles pair-à-pair décentralisés et structurés
1.4.1 – Les tables de hachage distribuées
1.4.2 – Architecture en anneau
1.4.3 – Architecture maillée de Plaxton
1.4.3.1 – Tapestry
1.4.3.2 – Pastry
1.4.4 – Architecture torique
1.4.5 – Architecture en papillon
1.4.6 – Architecture en arborescence
1.4.7 – Graphes de ‘de Bruijn’
1.4.8 – Analyse comparative des principales architectures avec DHT
1.4.8.1 – Limites des tables de hachage distribuées
1.4.9 – Graphes à enjambement
1.4.9.1 – Skip lists
1.4.9.2 – Skip graphs
1.4.9.3 – SkipNet
1.4.9.4 – Analyse des graphes à enjambement
CHAPITRE 2 : SPÉCIFICATION DES EXIGENCES POUR UN ROUTAGE PAIR-À-PAIR EFFICACE
2.1 – Le routage efficace
2.2 – Adéquation du routage pair-à-pair au réseau sous-jacent
2.2.1 – Corrélation entre le flux pair-à-pair et le réseau Internet
2.3 – Techniques de génération des informations de proximité
CHAPITRE 3 :ANALYSE DES SOLUTIONS EXISTANTES POUR UN ROUTAGE PAIRÀ-PAIR EFFICACE
3.1 – Techniques d’exploitation de la proximité
3.1.1 – Routage de proximité
3.1.2 – Agencement géographique
3.1.3 – Choix du voisin à proximité
3.2 – Solutions de prise en compte de la topologie du réseau sous-jacent
3.2.1 – Brocade
3.2.2 – Expressway
3.2.3 – Hieras
3.2.4 – Toplus
3.2.5 – Plethora
3.3 – Solutions de coopération entre flux pair-à-pair et opérateur de réseaux
3.3.1 – Solution de service intermédiaire
3.3.2 – Provider Portal for Peer-to-Peer
Marguerite Fayçal Janvier 2009
CHAPITRE 4 : CONCLUSION

Cours gratuitTélécharger le document complet

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *