François Baccelli

RÉSEAUX DE COMMUNICATION

Je travaille actuellement sur trois classes de problèmes de recherche :

CONTRÔLE DE CONGESTION DANS LES RÉSEAUX IP

Le protocole TCP, qui est le principal mécanisme de contrôle employé dans l'Internet, est décentralisé, simple et efficace. Voici les principaux résultats obtenus à partir des modèles mathématiques que nous avons élaborés pour ce type de contrôle :

  • MODÈLES AU NIVEAU PAQUETS. Ces modèles sont en principe équivalents à ceux d'une simulation à événements discrets.
    • UNE CONNEXION POINT A POINT, PLUSIEURS LIENS. Comme montré avec D. Hong dans un article d'Acm-sigcomm 2000, TCP admet une représentation simple comme un système dynamique (max, plus) linéaire (RR-3986 ). Ceci conduit à de nouvelles manières pour calculer le débit ainsi qu'à de nouvelles méthodes de simulation. Cet article est la base des travaux sur le multipoint listés ci-dessous.
    • UNE CONNEXION MULTIPOINT, PLUSIEURS LIENS. Dans le cas d'un grand groupe multipoint, un mécanisme de contrôle de congestion de type TCP qui utilise des rétroactions envoyées par tous les récepteurs ne peut pas fonctionner correctement, même lorsque le problème classique d'implosion est résolu par l'agrégation partielle des signaux de retroaction. Avec Augustin Chaintreau et Christophe Diot (alors chez Sprint), nous avons montré que même si les délais de traversée des routeurs ont des distributions à queue légère, le débit est inversement proportionnel au logarithme du nombre des récepteurs. Notre premier article ( RR-3987 ) sur ce sujet a été présenté à INFOCOM 2001 . Une solution plus prometteuse pour le multipoint IP fiable est celle fondée sur les réseaux applicatifs. En commun avec Augustin Chaintreau et Zhen Liu, chercheur chez IBM , nous avons proposé une architecture pour le multipoint que nous avons appelée "l'overlay TCP d'un vers beaucoup" (RR-5241 ). Deux versions de cette architecture ont été étudiées : l'une sans retroaction, qui a été présentée à Infocom 2004 , et l’autre avec retroaction, présentée à Infocom 2005 . Dans les deux cas, nous avons prouvé que cette solution fonctionne même pour un nombre infini de récepteurs. Pour plus d'information sur ce sujet, voir la thèse d'Augustin Chaintreau.
    • PLUSIEURS CONNEXIONS, PLUSIEURS LIENS. Le modèle mathématique d'interaction entre des connexions TCP et UDP que nous avons introduit avec T. Bonald (France Telecom R&D) concerne l'analyse du débit obtenu par la connexion TCP (RR-3434 ). ce débit n'est ni monotone ni convexe dans le taux d'émission des connexions UDP avec lesquels il partage les liens : une diminution du taux d'émission des connexions UDP ou une "régularisation" de ces flots peut avoir comme conséquence une diminution du débit obtenu par la connexion TCP.

Pour un aperçu sur les premiers modèles de niveau de paquet, voici les diapositives d'un cours de l' atelier de Madison sur les réseaux stochastiques en juin 2000 : Partie I , Partie II , Partie III , Partie IV

  • MODÈLES HYBRIDES. Ces modèles combinent des dynamiques fluides et des dynamiques à événements discrets.
    • PLUSIEURS CONNEXIONS, UN SEUL LIEN. Avec D. Hong , nous avons proposé un nouveau modèle pour le cas de plusieurs connexions qui se partagent un lien. Ce modèle a été présenté à INFOCOM 2002 ( papier AIMD ). Ce modèle réduit le partage du lien à des produits des matrices aléatoires dans l'algèbre conventionnelle. Cette classe de modèles est actuellement étudiée par Robert Shorten et Douglas Leith au Hamilton Institute.
    • GRAND NOMBRE DE CONNEXIONS, UN SEUL LIEN. En collaboration avec David McDonald (université d'Ottawa) et Julien Reynier (ENS), nous avons étudié un modèle de champ moyen pour RED qui mène à l'étude d'une classe d'EDP non locales: RR-4449 . Cette approche a été récemment prolongée au cas de connexions non-persistantes dans une série d'articles. Le premier RR-5205  (présenté à Sigmetrics 2004 ), étudie les conséquences de la "mise en phase" des connexions; les deux autres (RR-5301, qui a été présenté à Euro NGI 2005 et RR-5653 qui va paraître dans QUESTA) se concentrent sur l'analyse des EDP associées au cas non-persistant.
    • GRAND NOMBRE DE CONNEXIONS, PLUSIUERS LIENS. L'extension du modèle AIMD au cas de plusieurs liens est considérée dans l'article "Interaction of TCP Flows as Billiards", RR-4437 (ps.gz) , RR-4437 (.pdf). La version finale de cet article est parue en 2005 dans « IEEE Transactions on Networking ».

Cette modélisation hybride est utilisée par la start-up N2NSoft, créée en 2003 par D. Hong , avec laquelle je collabore. Le logiciel de simulation Netscale, qui est dédié à l'analyse de grands réseaux IP et qui est en partie fondé sur cette approche, a déjà été utilisé avec succès pour le design de DSLAMs.
Les propriétés statistiques du trafic TCP sont parmi les questions qui peuvent être étudiées en utilisant ces modèles hybrides. En particulier, la graduation fractale du trafic agrégé du TCP comme observé sur de vraies traces peut être expliquée par un modèle simple de l'Algorithme Multiplicatif de Diminution et d'Augmentation Additive, comme montré dans le journal de l’AIMD. Pour en savoir plus sur cette classe des modèles hybrides, voyez la page Web de l’AIMD .

Plusieurs ateliers ont été organisés sur le modèle du TCP à l’Ecole Normale Supérieure , les pages suivantes contiennent les programmes de ces ateliers ainsi que plusieurs articles sur le modèle mathématique du TCP :

RÉSEAUX SANS FIL

  • RÉSEAUX CELLULAIRES

Dans le cdma et le w-cdma, les antennes partagent le même canal et créent des interférences entre les signaux. La région où le signal d'une antenne donnée peut être reçu correctement est celle où le rapport de la puissance de ce signal à celle des interférences est suffisamment grand.

Voici les diapositives d'une présentation des premières étapes de cette approche qui a été faite lors de l'école d'été de recherche l'EPFL en juillet 2000. Les résultats obtenus nous ont permis de calculer des quantités d'intérêt pratique dans ce contexte : par exemple la probabilité qu'une certaine configuration est faisable, ou la loi du nombre d'antennes couvrant un point donné. Nous avons aussi défini une nouvelle classe de protocoles distribués de contrôle d'admission de grands réseaux cdma ; cette classe de protocoles a été présentée à Infocom 2003 (voir le RR-4702 ).

  • RÉSEAUX MOBILES AD HOC
    • CONNECTIVITÉ. Dans l'article sur la connectivité (présenté à INFOCOM 2003 (voir aussi le version plus complète parue dans « IEEE Transaction on Networking en 2005), co-écrit avec Olivier Dousse et Patrick Thiran de l'EPFL, nous avons étudié l'impact des limitations imposées par la théorie de l'information sur la faisabilité conjointe d'une collection de canaux sans fil dans un réseau ad-hoc mobile.
    • PROTOCOLES MAC. Conjointement avec Bartek Blaszczyszyn (INRIA et ENS) et Paul Muhlethaler (INRIA), nous avons proposé et étudié une version spatiale du protocole Aloha (RR-4955 ) pour l'accès au medium partagé dans un réseau mobile ad-hoc. Une version plus complète de cet article est parue dans « IEEE Transaction and Information Theory » en 2006.
    • CONTROLE DE PUISSANCE. L'utilisation du contrôle de puissance dans les réseaux mobiles ad-hoc a été récemment étudiée par Nicholas Bambos , Carri Chan de l'université de Stanford et moi-même dans un article présenté à INFOCOM 2006.
  • RÉSEAUX WIFI

Tout à fait récemment, j'ai commencé à étudier l'auto organisation de points d'accès WIFI (IEEE 802.11), en commun avec un groupe de chercheurs d'INTEL Cambridge . Nous avons proposé des algorithmes entièrement distribués pour l'association optimale des utilisateurs aux points d'accès et pour le choix optimal du canal des points d'accès (RR-5649). Ces algorithmes sont fondés sur l'échantillonneur de Gibbs.