Equipe de recherche GANG

Réseaux, graphes et algorithmes

Présentation de l'équipe

L'objectif central de GANG est le développement d'algorithmes pour la conception et le contrôle des réseaux à grande échelle, en s'appuyant sur les propriétés structurelles de ces réseaux. Le domaine d'application de GANG va de la conception de protocoles optimisés pour la gestion de grands réseaux dynamiques tels que les réseaux radio mobiles ou les réseaux logiques de systèmes de pair à pair sur Internet, jusqu'à l'étude de la navigabilité dans les réseaux sociaux. Les outils de GANG sont issus des avancées les plus récentes en algorithmique de graphes aussi bien centralisée que distribuée, dont en particulier les décompositions de graphes et la prise en compte de paramètres géométriques (dimension doublante, plongements dans des métriques de faible dimension, etc.).

Axes de recherche

La gestion des grands réseaux de communication, et en particulier d'Internet, se fait actuellement de façon ad hoc ("best effort"). Or, les applications courantes doivent prendre en compte une demande toujours croissante de mobilité (réseaux radio, réseau ad hoc, etc.) et de dynamisme (volatilité des utilisateurs, pannes, etc.), et ce dans un contexte fortement décentralisé. Une gestion ad hoc même partiellement décentralisée de ces réseaux n'est plus à même de répondre aux problèmes soulevés par le passage à grande échelle, mobile et dynamique. Il devient ainsi nécessaire de concevoir une nouvelle génération d'algorithmes et de protocoles, optimisés et entièrement décentralisés.

Dans le même temps, de nouveaux outils théoriques sophistiqués se sont développés de façon importante et suggèrent des pistes novatrices pour l'étude des grands réseaux. Ainsi, les résultats obtenus par la communauté informatique fondamentale dans le développement d'algorithmes sophistiqués, centralisés ou distribués, pour résoudre les problèmes de graphes donnent un nouvel éclairage pour aborder les problèmes cruciaux des grands réseaux de communication, comme le routage, mais aussi la recherche d'information, la localisation, ou l'équilibrage de charge. En effet, un grand nombre de techniques algorithmiques nouvelles se basent sur la prise en compte de propriétés structurelles que l'on observe dans un grand nombre de réseaux réels : approximation de la topologie par des espaces métriques de faible dimension, largeur arborescente faible, dimension doublante faible, et/ou absence de mineur de graphe spécifique. D'autre part, les techniques générales de décomposition de graphes ont également beaucoup progressé, et par conséquent la communauté scientifique se trouve à présent armée pour aborder la gestion optimisée de grands réseaux. Elle a d'ailleurs accompli des progrès considérables ces dernières années, en particulier dans le cadre de la conception de réseaux logiques structurés pour les systèmes de pair à pair, et dans la compréhension de la structure et de la navigabilité des grands réseaux d'interactions.

L'objectif de GANG est de pousser encore plus avant ces recherches afin d'étendre les résultats théoriques récents dans les domaines listés ci-dessus et de les prolonger vers des algorithmes distribués dédiés à des applications réelles. Parmi ces applications, nous comptons en particulier nous consacrer à :

  • l'architecture d'Internet, via une modélisation des latences par des métriques spécifiques ;
  • des applications de pair à pair nouvelles, comme la diffusion coopérative de flux vidéo ou la sauvegarde croisée ;
  • la gestion de grands réseaux dynamiques, tels que par exemple les réseaux ad hoc ou les réseaux logiques sur Internet.

Logiciels

Relations industrielles et internationales

  • France Telecom : MARDI est un contrat de recherche en collaboration (CRC) entre l'INRIA et France Telecom. Il regroupe GANG et Spontex (FT) autour de l'étude des réseaux décentralisés sur Internet.
  • Action COST 295 DYNAMO sur l'étude de solutions algorithmique pour les réseaux dynamiques, incluant Internet, le Web, les réseaux ad hoc, les systèmes P2P, etc.

Mots-clés : Réseau Graphe Algorithme

Equipes de recherche du même thème :

Siège et centres de recherche Inria

Accès direct

Social