INRIA

GANG

Responsable

Thèmes de recherche

Équipe Inria commune avec l'IRIF (équipe Algorithmes distribués et graphes, UMR 8243, Université Paris Diderot et CNRS).

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.).

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 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.


Membres

NomTéléphoneBureauFonctionMail
Boufkhad Yacine 01 57 27 94 05 4011 Maître.sse de conférence Mail
Charbit Pierre 0157279224 4030 Maître.sse de conférence Mail
Collet Simon 4001 Doctorant.e Mail
Delporte Carole 01 57 27 92 25 4006 Professeur.e - directrice adjointe UFR informatique Mail
Feuilloley Laurent 4001 Doctorant.e Mail
Fraigniaud Pierre 01 57 27 92 60 4016 Directeur.rice de recherche - CNRS Mail
Habib Michel 01 57 27 94 42 3042a Professeur.e Mail
Kosowski Adrian 4011 Chargé.e de recherche Mail
Viennot Laurent 01 57 27 92 50 3016 Directeur.rice de recherche Mail
ZOU Mengchuan Doctorant.e Mail
de Montgolfier Fabien 01 57 27 92 32 4018 Maître.sse de conférence Mail