Contribution de l'analyse d'algorithmes à l'évaluation de protocoles de communication / par Philippe Jacquet ; sous la direction de Philippe Flajolet

Bibliogr. en fin de chapitres

Thèse de doctorat informatique 1989 Paris 11

Cette thèse est dédiée à l’étude de certains protocoles de résolution de collision que l'on rencontre dans le bestiaire de l'informatique distribuée et de la communication. L'exemple qui vient en priorité à l'esprit est le désormais célèbre système Ethernet. Nous abordons le sujet sous la problématique de l'analyse d'algorithme et des applications à la combinatoire. Pour ce faire nous avons résolument tourné le dos à la construction d'un modèle trop précis de la réalité qui serait à même de cacher voire même d'inhiber les éléments de conclusion que nous esquissons au cours de l’étude. Ainsi nous modélisons les réponses du support physique au travers d'une discrétisation du temps appelée slot et la notion de trafic et de génération de messages est appréhendée sous le jour simplificateur de la loi de Poisson. Enfin les protocoles d'ordre supérieur ne sont généralement pas pris en compte ou sont à peine évoqués dans la gestion de files d'attente internes aux stations. Ceci dit, nous évaluons les performances des algorithmes au travers exclusif de développement analytiques et nous ne faisons jamais appel à la simulation. En conséquence, nous ne nous écartons jamais de l’intimité des mécanismes qui sont mis en jeu dans les protocoles et nous donnons les moyens d’appréhender plus efficacement leurs différences. L'analyse fait appel à la richesse de l'univers des chaines de Markov, des fonctions de Lyapunov et de l'analyse complexe. Nos protocoles préférés sont de type Ethernet ou ALOHA et surtout le protocole en arbre et ses différentes nouvelles versions