b. Algorithme à Etat de lien :
Le principal défaut du routage vecteur distance
provient du fait que les routeurs n'ont la connaissance d'un changement
d'état du réseau que lorsque leur voisin le leur communique, ce
qui peut être long. Pour palier ce défaut, le routage à
état de lien procède différemment :
- chaque n°ud détermine le coût du lien qui
lui est raccordé ;
- en cas de modification de cet état, le n°ud
diffuse cette information dans le réseau, sous la forme (A,
B, c), c'est-à-dire le lien entre les n°uds A et
B a un coût de c ;
- Chaque n°ud entretient une table où figure pour
chaque lien son coût (matrice de coût). À l'aide de ces
informations, chaque n°ud peut reconstituer la cartographie
complète du réseau en utilisant un Algorithme de recherche plus
cour chemin dans un arbre, celui de Dijkstra est le plus utilisé.
Nous présentons par la suite deux protocoles, l'un
basé sur l'état de lien, le OLSR, et l'autre, une
amélioration du vecteur de distance, le DSDV.
II.2.1.1 Le protocole de routage DSDV
L'algorithme de routage appelé "Vecteur de Distance
à Destination Dynamique Séquencée" ou DSDV (Dynamic
Destination-Sequenced Distance-Vector) [Per01, BMJ98] a été
conçu spécialement pour les réseaux mobiles. Il est
basé sur l'idée classique de l'algorithme distribué de
Bellman-Ford, DBF, en y apportant des solutions à ses éventuels
problèmes. Ce protocole fonctionne de façon suivante :
Chaque n°ud maintient une table de routage qui contient
:
· Toutes les destinations possibles.
· Le nombre de saut nécessaire pour atteindre la
destination.
· Le numéro de séquences (SN : sequence
number) qui correspond à un n°ud destination. Afin de
maintenir la consistance des tables de routage dans une topologie qui varie
rapidement, chaque noeud du réseau transmet périodiquement sa
table de routage à ses voisins directs. Le noeud peut aussi transmettre
sa table de routage si le contenu de cette dernière subit des
changements significatifs par rapport au dernier contenu envoyé.
La mise à jour doit permettre à un n°ud de
pouvoir localiser, dans la plupart des cas, une autre unité du
réseau.
La mise à jour de la table de routage peut se faire de
deux façons:
· Une mise à jour complète.
· Une mise à jour incrémentale.
Dans la mise à jour complète, le n°ud transmet
la totalité de la table de routage aux voisins ce qui nécessite
l'envoi de plusieurs paquets de données ; alors que dans une mise
à jour incrémentale, juste les entrées qui ont subit un
changement par rapport à la dernière mise à jour, sont
envoyées ce qui réduit le nombre de paquets transmis.
Un paquet de mise à jour contient :
1- Le nouveau numéro de séquence
incrémenté, du noeud émetteur.
Et pour chaque nouvelle route :
2- L'adresse de la destination.
3- Le nombre de noeuds (ou de sauts) séparant le noeud de
la destination.
4- Le numéro de séquence (des données
reçues de la destination) tel qu'il a été
estampillé par la destination.
Les données de routage reçues par un n°ud,
sont comparées avec les données déjà disponibles.
La route étiquetée par la plus grande valeur du numéro de
séquence (i.e. la route la plus récente), est la route
utilisée. Si deux routes ont le même numéro de
séquence, alors la route qui possède la meilleure métrique
(nombre de sauts), est celle qui sera utilisée. Les
modifications faites sur les données de routage
locales, sont immédiatement diffusées à l'ensemble courant
des voisins. Les routes reçues par une diffusion, seront aussi
envoyées quand le récepteur procédera à l'envoi de
ses paquets de routage. Le récepteur doit incrémenter les
métriques des routes reçues avant l'envoi, car le
récepteur représente un noeud en plus, qui participe dans
l'acheminement des messages vers la destination. Un lien rompu est
matérialisé par une valeur infinie de sa métrique, i.e.
une valeur plus grande que la valeur maximale permise par la métrique
[PBh94].
Parmi les améliorations apportées au DBF
classique, Le concept de numéro de séquence, qui Permet à
tout moment de se renseigner sur la validité des routes, a permis au
DSDV de résoudre le Problème de boucle de routage et du comptage
à l'infini. Comme tout protocole de routage proactif, le DSDV
connaît la route, ponctuellement, au moment même où un
n°ud doit procéder à une transmission, ce qui permet
d'être efficace en délais de transmission. Cependant, ce protocole
ne résout pas la lenteur de la convergence des tables, qui est lui aussi
hérite du DBF ; l'échange périodique des table de routage,
pour maintenir les routes même si elle seront pas utilisés,
génère un nombre de paquet de contrôle énorme . Pour
finir, les auteurs de ce protocole l'ont renoncé aux profits du AODV
[Per01].
| 
