overcrowded / C R C Mardi

Le Contrat de Recherche Collaboratif Mardi met en relation une équipe de France Télécom R&D et un projet de l'INRIA Rocquencourt. La collaboration a pour but d'étudier l'informatique théorique appliquée aux réseaux de pair à pair.

Pour plus de renseignements, contactez GwendalSimon.

Présentation générale

Les équipes

L’avant-projet Gyroweb de l’Inria Rocquencourt étudie l'algorithmique des graphes liée aux réseaux. Ses principaux domaines d’application sont le graphe du web, la structure d’Internet et les réseaux de pair à pair. Les membres de l’équipe participant initialement à cette collaboration seront deux chercheurs ( Laurent Viennot et Fabien de Montgolfier) et un thésard ( Anh-Tuan Gai).

Le Projet de Recheche Pluri-disciplinaire (PRP) Spontex s’intéresse aux réseaux dont la croissance, le comportement et la structure résultent des comportements individuels et coopératifs des éléments qui les constituent. Les lots 1 et 2 du projet s’intéressent notamment aux réseaux décentralisés sur Internet. Trois chercheurs (JoaquinKeller?, FabienMathieu? et GwendalSimon) et un thésard (FabioPianese?), impliqués dans ces deux lots, interviendront initialement dans cette collaboration.

Le thème

Les deux équipes de l'INRIA et de France Télécom R&D se sont rencontrées à plusieurs reprises dans le cadre de séminaires, notamment les séminaires PairAPair liés à l' ACI Masse de données.Les deux équipes partagent de nombreux intérêts communs. La collaboration viserait à mutualiser et enrichir les études, éviter la redondance des travaux, profiter d'une complémentarité prometteuse et rendre fructueux des échanges jusqu'alors informels.

La collaboration porte sur l'étude et la conception de réseaux décentralisés sur Internet. Ces réseaux admettent un fort intérêt théorique et un large champ applicatif.

Mesures dans Internet par et pour réseaux décentralisés

Les réseaux décentralisés étudiés dans le cadre de cette collaboration utilisent Internet comme infrastructure de transport.Nous chercherons ici à concevoir un réseau décentralisé permettant de réaliser une large collection de mesures de certaines caractéristiques d'Internet. L'analyse de ces mesures devrait offrir un vaste champ d'études pour l'amélioration des performances de réseaux décentralisés.

La compréhension fine des caractéristiques des réseaux sur lesquels les réseaux pair à pair reposent s'inscrit dans le courant des recherches actuelles sur les modèles pour ces réseaux logiciels. Dans ce domaine, les deux équipes partagent une vision qui tendrait à infirmer la modélisation d'Internet par une métrique. En effet, alors que beaucoup de travaux de recherches
existants font l'hypothèse que le réseau possède certaines propriétés topologiques fortes (''doubling dimension'', 'bounded growth''...), des mesures réelles récentes semblent remettre en
cause de manière significative jusqu'à l'existence d'une inégalité triangulaire dans les latences du réseau Internet. Mettre au point des outils de mesure décentralisés nous permettrait de pousser plus loin nos études sur le sujet.

Intérêt de l'opérateur

Effectuer des mesures fiables des caractéristiques (débit, congestion, délais, latence\ldots) du réseau Internet est primordial pour France Télécom. Les outils de dimensionnement du réseau nécessitent une bonne connaissance de l'état et de l'évolution des ''tuyaux''. L'évolution qualitative du trafic, notamment l'importance croissante du trafic lié aux réseaux décentralisés, rend de plus en plus nécessaire l'intégration d'une nouvelle famille d'outils de mesure qui sache prendre en compte la formation de réseaux virtuels (Réseaux overlay) en sur-couche du réseau physique.

Intérêt de l'Inria

L'étude et la modélisation d'Internet requiert l'acquisition de mesures à large échelle. Utiliser une application de pair à pair pour cela constitue une approche novatrice scientifiquement intéressante à double titre: pour les résultats qu'elle peut apporter et pour la manière de les apporter.

Modélisation de la dynamique des noeuds et des échanges

Les réseaux logiciels décentralisés se caractérisent par la forte volatilité des noeuds participants: les arrivées et les départs sont incessants. Une modélisation courante des réseaux décentralisés repose sur des graphes dynamiques à grande échelle. L'étude théorique des systèmes distribués, dans ce contexte particulier, recèle de nombreuses pistes d'étude.

Cette volatilité peut s'appréhender en analysant les périodes de connexion des Internautes, afin de modéliser le comportement dynamique des noeuds. Il pourrait alors devenir possible d'estimer la disponiblité espérée d'un noeud et d'étudier une utilisation de ses ressources qui dépende de cette estimation.

D'autre part, les liaisons entre les pairs se renouvellent également régulièrement. L'étude de la stabilité et de la dynamique de mécanismes de connexion distribués, inspirée de la théorie des mariages stables, pourrait permettre la prédiction de certaines performances des réseaux décentralisés, indépendamment de l'implémentation sous-jacente.

Intérêt de l'opérateur

Les bases théoriques sur l'algorithmique distribuée dans les graphes dynamiques à large-échelle peuvent s'appliquer à une partie des travaux menés dans Spontex. Alors que la troisième génération de réseaux décentralisés (BitTorrent?, Kademlia...) touche le grand public, cette vue globale permettrait à France Télécom d'acquérir une expertise primordiale sur les réseaux virtuels de demain.

Intérêt de l'Inria

Étudier les aspects dynamiques des réseaux est un thème scientifique complexe qui a déjà sa place à l'Inria. Développer ce thème autour des applications logicielles décentralisées
offrira sans doute de nombreuses pistes scientifiques à défricher.

Conception et structuration de réseaux décentralisés

La réalisation de grands réseaux logiciels soulève deux principaux problèmes pratiques : l'adaptation aux caractéristiques du réseau physique sous-jacent et la stabilité face à la volatilité des utilisateurs.

Une piste intéressante liée au premier défi considère les violations de l'inégalité triangulaire évoquées ci-dessus : il est parfois possible d'envoyer plus rapidement un message d'un point à un autre en passant par un tiers. Concevoir un réseau virtuel capable de surpasser parfois le réseau sous-jacent en usant à bon escient de raccourcis topologiques constitue un vaste domaine d'étude. En effet, la découverte de raccourcis topologiques ou de routes logiques efficaces ne doit pas passer par une exploration totale du réseau physique.

Le second défi consiste à structurer le réseau logiciel de manière stable vis-à-vis de la volatilité des noeuds. L'approche initiée dans ce domaine par Kademlia consiste à utiliser une forte redondance topologique pour résister aux départs sans qu'il soit nécessaire de réparer immédiatement la topologie. Ceci permet de traiter les défaillances comme de simples départs. L'équipe Gyroweb a notamment cultivé ce principe pour concevoir des topologies résistantes de tables de hachages distribuées ou de distribution de flux.

Nous nous intéressons aux opportunités applicatives de nos études et envisageons la conception et la réalisation de nouveaux réseaux logiciels décentralisés. Un but à plus long terme conciste à déterminer les familles d'applications pouvant être résolues par une mise en oeuvre totalement décentralisée, et ainsi, pouvant potentiellement passer à l'échelle. Dans ce cadre, des preuves d'impossibilité pourraient alimenter des travaux plus applicatifs.

Intérêt de l'opérateur

Les études estiment que le trafic lié aux réseaux décentralisés représente près des deux tiers du trafic total. Plutôt que de subir cette évolution, France Télécom a pris le parti de concevoir ses propres réseaux décentralisés à travers différents projets (maay ou solipsis).

L'objectif est ici d'encourager l'équipe Gyroweb à participer au développement des réseaux de pairs actuellement développés et d'élaborer conjointement de nouveaux réseaux de pairs. L'utilisation de mesures durant la phase de construction de tels réseaux constitue une voie prometteuse pour obtenir des réseaux optimisés vis à vis de l'infrastructure de transport. À la clé, peut-être une amélioration des performances par rapport à ce qu'offre le réseau physique brut (France Télécom : ''plus rapide qu'Internet !'').

Intérêt de l'Inria

Permettre le développement d'application de large échelle rentre dans l'un des sept défis scientifiques prioritaires de l'Inria : "concevoir et maîtriser les futures infrastructures des réseaux et des services de communication". D'une part, les problèmes algorithmiques offrent dans ce contexte distribué un domaine d'étude riche dont la portée devient critique lorsque la taille de l'application croît. D'autre part, de nombreux développement théoriques pertinents dans ce modèle sont à développer : quel est le meilleur réseau logiciel qu'on puisse avoir pour une infrastructure donnée ? à quel point, en fonction des mesures à effectuer, peut-on s'en approcher ? Le fait que l'infrastructure doit être découverte par des mesures dont le coût entre en compte produit certainement un paradigme nouveau de conception de protocole.

---

TAG: FractalAggregator | Branche1 | Branche12

---