II.2.1.2 Le protocole de routage OLSR
Optimized Link State Routing est un protocole par
état de lien qui utilise une technique optimisée pour la
diffusion des messages topologiques. La solution consiste à ne permettre
qu'à un sous-ensemble de voisins de retransmettre les messages (voir
FIG. 2.4) [CJL02, CJL01]. Ces voisins sont appelés les relais
multipoint ou MPRs (multipoint
relays).Chaque n°ud effectue la sélection de ses MPRs en se
basant sur la connaissance de son voisinage à deux sauts. L'ensemble des
MPRs doit être le plus petit possible, tout en assurant que la diffusion
par leur intermédiaire permet d'atteindre le voisinage à deux
sauts dans sa totalité. Le problème qui consiste à trouver
le plus petit ensemble de MPRs est analogue au problème de la recherche
d'ensemble dominant minimal dans un graphe. Dans OLSR, les noeuds appliquent
une heuristique qui permet de se rapprocher de l'ensemble minimal dans la
majeure partie des cas.
Figure 2.4 : Diffusion par inondation (à gauche) et
diffusion optimisée (à droite)
Différents mécanismes sont utilisés dans le
fonctionnement de ce protocole ce protocole.
a. Découverte de voisinage
Chaque noeud émet périodiquement des messages
appelés HELLO qui contiennent essentiellement la liste des
liens connus vers les voisins directs. La fonction de ces messages est
multiple. Ils servent tout d'abord à détecter les voisins directs
et la qualité des liens vers ceux-ci, à savoir s'ils sont
symétriques ou asymétriques. Comme chaque noeud y publie la liste
de ses voisins, il est possible pour un n°ud d'acquérir des
informations sur son voisinage à deux sauts. Par ailleurs, une fois
qu'un noeud a effectué la sélection de ses MPRs, il indique dans
ses messages HELLO lesquels de ses voisins sont ses MPRs. Ceci permet
à un n°ud de savoir quels voisins l'ont choisi comme MPR, autrement
dit de constituer son ensemble de MPR-selectors.
b. Diffusion optimisée
Lorsque qu'un n°ud reçoit un message de
contrôle OLSR, il le traite et ne le transmet que si l'émetteur du
message (l'adresse source du message, qui peut être différente de
l'adresse de l'émetteur si le message a été
généré par un noeud distant) appartient à
l'ensemble des MPRselectors. Cette technique permet de diffuser des messages
dans tout le réseau en évitant la saturation.
c. Les messages topologiques
Les messages topologiques, appelés TC
(topology control) ne sont émis par un noeud
qu'à condition que son ensemble de MPR-selectors n'est pas vide,
c'est-à-dire qu'il est MPR d'un
de ses voisins. Les messages contiennent la liste des
MPR-selectors du n°ud. Les n°uds du réseau reconstituent donc
une topologie globale mais partielle, puisque tous les noeuds atteignables sont
connus, mais pas tous les liens. Cette topologie partielle est néanmoins
suffisante pour calculer des chemins minimaux en nombre de sauts vers tout
destination.
Le fait de ne permettre qu'aux MPRs de générer
des messages TC permet de limiter la quantité de messages
diffusés dans le réseau et le fait de ne diffuser que la liste
des MPRselectors permet de limiter la taille des messages.
d. Les changements topologiques
À chaque changement de topologie, le calcul des routes
vers toutes les destinations est déclenché pour mettre à
jour les tables de routage. Par ailleurs, lorsque son ensemble de voisins
directs ou à deux sauts change, un noeud doit effectuer la
sélection de ses MPRs à nouveau.
e. Calcul des routes
Une fois que les n°uds auraient envoyé les TC (les
liens qui leur lie aux MPRs), chaque Q°ud constitue sa matrice des
coût et utilise un Algorithme de recherche de plus cour chemin dans un
graphe pour tracez sa cartographie du réseau (méthode à
état des liens).
Dans ce protocole, seuls les n°uds, pour lesquels le
MPRs-selector est non vide, ont droit à diffuser les messages
topologique. Si bien que la quantité de message de contrôle
générer par le réseau est limité. La convergence
des tables de routage est rapide dans la mesure où chaque Q°ud
constitue sa cartographie du réseau au lieu d'attendre que leur voisin
le leur communique. Pour ce qui est le délai de transmission, il est
efficace vu la nature proactive du protocole. En fin, ce protocole montre tous
ces avantages mais il n'y a aucun algorithme de recherche de plus court chemin
qui résout complètement le problème de boucle de routage
temporaire, aussi, les fonctions de calcules qui permettent à un
n°ud de sélectionner ses MPRs sont très complexes.
| 
