| dc.description.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. | en_US |
