Equipe 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.).
Thèmes 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 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.
