Routage compact de plus court chemin dans les graphes de Halin cubiques complets

Abstract

Savoir comment transmettre une information est fondamental dans un réseau. Il est essentiel que chaque entité du réseau dispose d’une fonction de routage lui permettant de décider localement, avec sa vue du réseau, du chemin par lequel l’information doit passer. Dans le routage compact, on cherche à mettre en place de tels algorithmes tout en optimisant la table de routage, le chemin parcouru par le message et la latence du routeur. Dans leur travaux, sur le routage compact, Dieng et al., ont posé la question de savoir s’il est possible de router par de plus court chemin dans un graphe de Halin avec des tables de routage et des entêtes de message de taille O(logn) bits. Les seuls graphes possédant un tel schéma de routage sont les arbres, les graphes planaire extérieurs et les (k,r)-constellations. En ce qui est des graphes de Halin, les résultats apportés sont de Bassène et al. avec la proposition d’un schéma de routage compact avec un facteur d’étirement de 2. Dans ce mémoire, nous proposons un schéma de routage de plus cours chemin, dans les graphes de Halin cubiques complets; une sous famille des graphe de Halin.