Etat de l’art sur le Routage Compact.

Abstract

Savoir comment transmettre une information est fondamental dans un r´eseau. Il est essentiel que chaque entit´e du r´eseau soit capable de d´ecider lo calement, avec sa vue du r´eseau, du chemin par lequel l’information doit passer. Ainsi, il est souvent utile d’´etudier la topologie du r´eseau, mod´elis´ee par un graphe, pour r´epondre `a ces exigences. Nous nous int´eressons dans un premier temps, `a une pr´esentation des g´en´eralit´es sur les graphes. En effet, comme dans beaucoup de probl`emes de graphes, pour ´etudier la topologie des r´eseaux afin d’exploiter les propri´et´es structurelles qui en d´ecoulent il est souvent pr´ef´erable de connaitre la notion de graphe et l’ensemble de ses propri´et´es. Ensuite, nous avons fait un ´etat de l’art sur le routage compact. En ef fet, la croissance de taille des r´eseaux est sup´erieure `a celle des capacit´es des routeurs actuels. La probl´ematique du routage compact consiste `a stocker des tables ayant moins d’entr´ees que les routeurs du r´eseau mais garantissant l’acheminement de messages par des routes proches des plus courts chemins. Dans cette partie, nous pr´esentons les principes d’impl´ementation de trois types de routage compact et un ´etat de l’art de chacun d’eux; le routage par inter valle, le routage de plus courts chemins et le routage de plus courts chemins avec facteur d’´etirement. Dans la derni`ere partie, nous abordons le probl`eme du routage compact dans les graphes de halin non valu´es. Nous nous sommes int´eress´es aux sch´emas de routage de plus courts chemins utilisant des adresses, des tables de routage de tailles optimales de O(log n) bits, o`u n est le nombre de sommets du graphe. Nous n’avons pas pu trouver un tel sch´ema de routage pour les graphes de halin mais, nous proposons un sch´ema de routage compact avec facteur d’´etirement d’au plus 2.