Il est désormais une évidence que l'on ne peut pas concevoir de bons algorithmes sans de bons modèles d'évaluation de ces algorithmes.
L'équipe a une très forte expérience dans le domaine de l'accès multiple et de la résolution de collision (deux thèses sur la contribution de l'algorithmique aux protocoles de communications et sur l'évaluation des protocoles d'accès aux réseaux hauts débits, de nombreuses publications internationales). Le domaine est très actif depuis une quinzaine d'années, autour de l'avènement d'Ethernet.
Le problème consiste à définir le meilleur protocole d'accès à un médium de communication unique en sachant que des accès multiples simultanés résultent en collisions. Lorsqu'une collision intervient, il convient de la résoudre pour assurer la transmission correcte de tous les paquets impliqués dans la collision initiale. Si l'algorithme de résolution est efficace le protocole présente des propriétés de stabilité remarquables. Par exemple nous pouvons avoir la stabilité en population infinie ou en trafic asymétrique avec finitude des délais d'accès.
Il importe aussi de regarder le comportement d'un algorithme d'accès en condition de surcharge persistante, ou lors d'une collision soudaine de très forte multiplicité. Les algorithmes peuvent être analysés avec des paramètres supplémentaires comme des délais de propagation significatifs (satellite, câble TV, hauts débits) les files d'attente en station, les taux d'erreurs, des priorités, etc.
L'analyse combinatoire de certains algorithmes de résolution fait intervenir des équations fonctionnelles proches de celles que l'on rencontre dans l'analyse de certains algorithmes de compression, ou certaines structures de données arborescentes. Ceci permet de bénéficier des outils et des résultats d'analyses connus depuis Knuth (1973) et abondamment exploiteés depuis, notamment dans le projet Algorithmes.
Il n'existe, à notre connaissance, pas encore d'exemples de modélisation vraiment satisfaisants pour les algorithmes d'accès sans fil. En général il s'agit d'extrapolation très directe de ce qu'on sait déjà faire sur les réseaux câblés. Néanmoins il existe des différences fondamentales avec le câble, notamment les phénomènes de captures, les nuds cachés, les niveaux physiques versatiles. Les évaluations des algorithmes d'accès sans fil doivent tenir compte de ces points.
Le domaine est devenu très actif depuis cinq ans environ, lors de l'avènement de la communication mobile et le GSM.
Les qualités de service s'exprime souvent par des échéances et des priorités qui peuvent être attribuées dynamiquement. Il s'ensuit donc un processus d'ordonnancement des tâches. Dans un réseau, on rencontre deux types d'ordonnancement des messages: un ordonnancement local en station et un ordonnancement global entre les stations. Le premier ordonnancement ne présente pas de difficultés théoriques particulières, les files d'attente avec priorités étant connues et disséquées depuis fort longtemps. L'ordonnancement global est moins couvert et n'est vraiment exploré que depuis les débuts d'ATM et d'Internet nouvelle génération. En général l'ordonnancement global est réalisé au moyen de réservations et de priorités, donc à partir de connaissances partielles de l'état instantané du réseau.
Dans ce cas, l'état ordonné s'établit essentiellement autour d'une sorte d'équilibre thermodynamique et d'une interaction entre l'algorithme d'accès et le processus de priorités qu'il convient d'analyser. En général on demande au système de fournir des niveaux de priorités hiérarchiquement indépendants. L'indépendance hiérarchique signifie qu'un trafic possédant une priorité donnée ait certaines garanties de performances indépendantes des charges des trafics de priorités inférieures.