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.
Relations internationales et industrielles
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.
