Autour de l’informatique : Mathématiques des réseaux

Réseaux et big data. RBD, CC BY

Un nouvel « Entretien autour de l’informatique ». Serge Abiteboul et Claire Mathieu interviewent François Baccelli. François est Directeur de recherche Inria à Paris, et responsable du centre Simons pour les mathématiques des réseaux à l’Université du Texas à Austin. Ses travaux sont à l’interface de nombreux domaines scientifiques, notamment les probabilités et l’informatique. Ceux sur la modélisation et le contrôle des réseaux de communication ont des impacts considérables tant théoriques que pratiques, par exemple sur les réseaux de téléphonie mobile. Cet article est publié en collaboration avec le blog Binaire.


Binaire : sur quel problème de recherche travailles-tu en ce moment ?

François Baccelli. Simmons, CC BY

François Baccelli : je travaille actuellement sur des graphes infinis appelés « graphes aléatoires unimodulaires ». Par exemple, on prend un nuage infini de points dans le plan (sous certaines conditions géométriques) et on relie deux points par une arête s’ils sont suffisamment proches l’un de l’autre. Cela définit un graphe aléatoire infini unimodulaire où on sait définir un nœud typique, une arête typique, un triangle typique, etc.

Pour étudier les graphes de très grande taille par exemple les réseaux sociaux numériques ou réseaux radios, il est souvent utile de voir ces réseaux comme des graphes infinis de ce type. Cela permet d’établir des propriétés importantes et utiles en pratique.

On étudie en particulier divers types de dynamiques sur ces objets infinis. Comme exemple de dynamique, on peut citer ce qui se passe quand on transfère des données d’un point à un autre sur Internet. Un outil de calcul fondamental pour analyser la dynamique de ces objets infinis est l’« équation de transport de masse » donnée par l’unimodularité. Le transfert de données est un sujet essentiel, mais il y en a bien d’autres. On peut chercher à comprendre les interactions entre les paquets qui passent par le même routeur, la gestion de files d’attente, le routage des paquets. Tout ceci détermine la qualité de service dans un réseau télécom. L’étude de tels phénomènes demande de développer des outils mathématiques nouveaux intégrant géométrie, dynamique et probabilités, et c’est sur cela que portent mes recherches actuelles.

Connexion au plus proche sur un processus de Poisson. F. Baccelli, Author provided

Prenons le cas du wifi. Lorsque vous utilisez ce protocole de transmission, votre téléphone va transmettre quand il détecte qu’autour de lui il n’y a personne en train de transmettre. Le protocole à la base du wifi génère donc une géométrie et une dynamique complètement différentes de celles des réseaux cellulaires 3G, 4G ou 5G.

La technique classique pour estimer le débit dans un tel réseau consistait à réaliser des simulations. La théorie permet maintenant de mettre cela en équations. On sait en effet faire des calculs exacts pour certaines de ces dynamiques.

Par exemple, dans un grand réseau 5G, on peut aujourd’hui déterminer ou prédire la distribution de la vitesse de téléchargement d’un fichier. On représente les antennes comme un nuage de points dans le plan (un « processus de Poisson »). On utilise la théorie de l’information pour représenter le débit que peut obtenir un utilisateur typique. Pour ce faire, on calcule la distribution du signal de la station de base la plus proche de l’utilisateur typique et celle de l’interférence créée par les autres stations, et on obtient une formule pour la distribution du débit et donc la vitesse de téléchargement typique.

Cela permet aux industriels de prévoir, par exemple, le nombre d’antennes à placer par kilomètre carré pour garantir un certain débit. Les résultats peuvent être paradoxaux : on peut par exemple montrer que, dans certains contextes, densifier un réseau cause une augmentation des interférences qui fait s’écrouler le réseau au lieu de l’améliorer.

Les systèmes sont devenus si complexes que de tels outils mathématiques sont désormais indispensables. Ils sont utilisés notamment dans le cadre des procédures de standardisation des communications. Les perspectives sont importantes, car cela permet de faire des prédictions beaucoup plus précises pour concevoir les réseaux du futur.

Tu crois que tu peux nous donner une petite idée de théorie mise en jeu ?

J’ai déjà mentionné la théorie de l’information. Cette théorie est aux technologies du numérique ce que la thermodynamique est à la première révolution industrielle. En effet c’est cette théorie qui donne les limitations fondamentales pour la transmission de l’information, sa compression et son stockage. Je travaille aussi activement sur les connexions entre la théorie de l’information et la géométrie en grandes dimensions. Je vais donner un exemple en compression. Prenons un espace à deux dimensions. On choisit au hasard une infinité de droites. Pour un point donné et pour chaque droite, on peut regarder si le point est à gauche ou à droite de la droite : 0 ou 1, c’est un bit d’information. Ces droites définissent donc un encodage des points de plan que je considère ici comme les données. Plus on a de droites, plus on a de précision sur la position du point. Cela ne permet pas de distinguer un point d’un autre très proche, mais pour de bonnes plages de paramètres, cela définit une « petite » zone où il se situe. On obtient ce qu’on appelle un code de compression sur un bit qui est particulièrement important en grandes dimensions.

Claude Shannon. Wikipedia, CC BY

Dans la théorie de l’information de Shannon, on considère un canal où on transmet de l’information (une communication radio par exemple) et où du bruit déforme le message. Pour pouvoir restituer les informations à la réception, on encode l’information à transmettre avec des mots de code longs. Pour décoder le message bruité reçu, l’algorithme du maximum vraisemblance donne une solution simple. Avec le regard de la géométrie en grandes dimensions, dans le cas de bruit gaussien, cette solution revient à proposer comme message émis le mot de code le plus proche du message reçu.

Ce point de vue permet de revisiter des notions de base de la théorie de l’information à partir de la géométrie aléatoire en grandes dimensions, et de comprendre les limites fondamentales pour de nouveaux types de canaux et de nouveaux types de compressions.

Couverture au sens de Shannon sur un processus de Poisson. François Baccelli, Author provided

Quelle est la culture scientifique qui te sert dans ta recherche ?

Tout ce qui a trait aux mathématiques des grands réseaux : les probabilités, la théorie de l’information, la géométrie, les systèmes dynamiques. Si on cherche à avoir un véritable impact sur le monde industriel (réseaux radio, réseaux sociaux numériques), il faut aussi un ancrage dans l’ingénierie des réseaux pour comprendre dans le détail pourquoi et comment ces réseaux sont actuellement développés et utilisés. Pour les réseaux radio par exemple, il faut connaître la couche physique, les protocoles de contrôle, le trafic ; pour les réseaux sociaux, la dynamique des connexions, l’algorithmique sous-jacente, notamment algorithmes de détection de communautés.

Qu’est-ce qui te fait te lever le matin pour aller à ton travail ?

La vraie récompense, le vrai plaisir, c’est de comprendre. Par exemple, comprendre ce qui se passe en grande dimension, voir des objets nouveaux ou des structures nouvelles. Bien sûr, constater que des résultats qu’on a obtenus sont utilisés à grande échelle par d’autres, parfois longtemps après, c’est gratifiant aussi.

Que dirais-tu à un jeune doctorant ou une jeune doctorante qui voudrait te prendre comme modèle ? Lui conseillerais-tu le métier de chercheur ?

Comme disait Héraclite, on n’entre jamais deux fois dans le même fleuve. Le monde a changé… Il reste néanmoins toujours essentiel et exaltant d’essayer de comprendre et mieux maîtriser le monde numérique. Pour ce qui concerne le métier de chercheur, les conditions ont changé aussi. C’est beaucoup plus difficile aujourd’hui de faire de la recherche avec impact sur le long terme il me semble. La pression productiviste est devenue excessive dans beaucoup d’institutions, surtout en début de carrière. Il faut sélectionner les institutions où on fait de la vraie recherche. Il n’en manque pas dans le vaste monde.

Un dernier mot ?

Ma recherche au sens large est à la croisée de deux domaines : les mathématiques et EECS (Electrical Engineering and Computer Science) qu’on pourrait traduire par « Informatique et Communication ». L’informatique et les communications sont à la base des technologies et de l’économie du futur : aujourd’hui nos données, nos téléphones, demain notre Internet des objets, notre sécurité. Est-ce que nous avons vraiment pris conscience de l’importance de ces questions ? Il faut que la France et l’Europe restent dans la course.

Pour ce faire, il est essentiel de participer à la conception de ces systèmes : des composants aux systèmes d’exploitation, des algorithmes de traitement de données de masse aux nouvelles architectures de réseaux, etc. Nous avons en France de grands atouts : de très bons étudiants notamment grâce à notre système de classes préparatoires, des chercheurs et des industriels actifs dans ces domaines. Il est essentiel de développer dans ces disciplines des structures académiques qui soient au niveau de ce qu’on trouve dans les grandes universités d’Amérique du Nord ou de ce qui se crée actuellement en Asie. Il faut investir de manière plus volontaire et ambitieuse dans l’éducation supérieure de niveau international, avec une vraie vision planétaire.