II.2.2.1 Le protocole de routage DSR
Dynamic Source Routing (DSR) [JMH01] est un protocole
réactif basé sur l'utilisation de la technique source routing
(routage source). Le chemin à parcourir est contenu dans
l'entête du paquet de données. Ainsi lorsqu'un noeud reçoit
un paquet, il le route vers le noeud suivant dont l'adresse est indiquée
dans l'entête.
Les deux opérations de base du protocole DSR sont : la
découverte de routes et la maintenance de routes. L'opération de
découverte de routes permet à n'importe quel n°ud du
réseau de découvrir dynamiquement un chemin vers un n°ud
quelconque du réseau. Un noeud initiateur de l'opération de
découverte diffuse un paquet requête de route qui identifie
l'hôte cible. Si l'opération de découverte
est réussie, le noeud initiateur reçoit un paquet réponse
de route qui liste la séquence de n°uds par lesquels, la
destination peut être atteinte. En plus de l'adresse de l'initiateur, le
paquet requête de route contient un champ enregistrement de route, dans
lequel est stockée la séquence des n°uds visités
durant la propagation de la requête de route dans le réseau (voir
la figure 2-5 (a)).
Au passage du paquet, chaque noeud stocke en mémoire
chaque nouvelle route, pour une utilisation postérieure
éventuelle. Si le noeud ne trouve pas de route correspondant à
l'entête du paquet, alors il initialise une découverte de route.
Ainsi un noeud intermédiaire n'est pas obligé de connaître
et d'avoir une table de routage à jour pour l'ensemble du réseau,
mais seulement pour les noeuds qui lui sont adjacents.
Ce protocole est simple dans sa démarche et sa mise en
place. Il permet également au réseau d'être auto
structurable et configurable. Il n'y a donc aucun message de mise à jour
des tables de routage autres que ceux contenus dans les entêtes des
paquets transitant dans le réseau. Le paquet requête de route
contient ainsi un identificateur unique de la requête. Dans le but de
détecter les duplications des réceptions de la requête de
route, chaque n°ud du réseau ad hoc maintient une liste de couples
<adresse de l 'initiateur, identificateur de requête> des
requêtes récemment reçues.
[1, 2, 6]
Destination
2
6
[1]
Source
1
8
[1]
3
[1, 3]
[1]
[1. 3, 5]
[1, 3, 5, 7]
5
4
[1, 4]
7
[1, 2]
(a) Construction de l'enregistrement de route
[1, 2, 6]
[1, 2, 6]
2
6
[1, 2, 6]
Source Destination
1
8
3
5
4
7
(b) Utilisation de la route dans le DSR
Figure 2.5 : La découverte de chemins dans le DSR.
Lors de la réception d'un paquet requête de route
par un n€ud p du réseau, le traitement suivant est
effectué :
- Dans le cas où le couple <adresse de
l'initiateur, identificateur de requête du paquet reçu>
existe déjà dans la liste des requêtes
récemment reçues, le paquet est ignoré.
- Dans le cas contraire, si l'adresse de p existe
dans le champ enregistrement de route du paquet de la requête, le paquet
est ignoré.
- Sinon, si l'adresse de p est la même que
l'adresse de la destination, alors l'enregistrement de route (contenu dans le
paquet de la requête) contient le chemin à travers lequel le
paquet de la requête est passé avant d'atteindre le n€ud
p. Une copie de ce chemin est envoyée dans un paquet
réponse de route à l'initiateur (voir la figure 2-5(b)).
- Sinon, l'adresse de p est ajoutée dans
l'enregistrement de route du paquet reçu, et le paquet est
rediffusé (voir la figure 2-5(a)).
De cette manière, la requête de route est
propagée dans le réseau jusqu'à ce qu'elle atteigne
l'hôte destination qui va répondre à la source. Le fait
d'ignorer la requête dans le cas où l'adresse du récepteur
existe dans l'enregistrement de route garantit que la propagation d'une unique
copie de la requête ne peut pas se produire à travers des boucles
de n€uds.
Dans le but de retourner le paquet réponse de route
à l'initiateur de l'opération de découverte, le n€ud
destination doit connaître un chemin vers l'initiateur. Dans le cas
où la destination n'a pas déjà gardé une telle
route, le chemin spécifié dans l'enregistrement de route contenu
dans
le paquet requête de route peut être
inversé et utilisé (voir la figure 2-5(b)). Cependant, cela exige
que les liens entre les n°uds participant à la route doivent
être bidirectionnels, ce qui n'est pas vérifié dans
certains environnements.
Afin de réduire le coût et la fréquence de
la découverte de routes, chaque n°ud garde les chemins appris
à l'aide des paquets de réponses. Ces chemins sont
utilisés jusqu'à ce qu'ils soient invalides.
Afin d'assurer la validité des chemins utilisés,
le protocole DSR exécute une procédure de maintenance de routes.
Quand un n°ud détecte un problème fatal de transmission, un
message erreur de route (route error) est envoyé à
l'émetteur originel du paquet. Le message d'erreur contient l'adresse du
n°ud qui a détecté l'erreur et celle du n°ud qui le
suit dans le chemin. Lors de la réception du paquet erreur de route par
l'hôte source, le n°ud concerné par l'erreur est
supprimé du chemin sauvegardé, et tous les chemins qui
contiennent ce n°ud sont tronqués à ce point là. Par
la suite, une nouvelle opération de découverte de routes vers la
destination est initiée par l'émetteur.
Après la découverte de route vers la
destination, pour envoyer un paquet de donnée à un autre
Q°ud, l'émetteur construit une route source et l'inclut en
tête du paquet. La construction se fait en spécifiant l'adresse de
chaque n°ud à travers lequel le paquet va passer pour atteindre la
destination. Par la suite, l'émetteur transmet le paquet au premier
n°ud spécifié dans la route source. Un n°ud qui
reçoit le paquet et qui est différent de la destination supprime
son adresse de l'entête du paquet reçu, puis le transmet au
n°ud suivant identifié dans la route source. Ce processus se
répète jusqu'à ce que le paquet atteigne sa destination
finale.
Parmi les avantages du protocole DSR, on peut citer le fait
que les n°uds de transite n'aient pas besoin de maintenir les informations
de mise à jour pour envoyer les paquets de données, puisque ces
derniers contiennent toutes les décisions de routage. En outre, dans ce
protocole, il y a une absence totale de boucle de routage, car le chemin
source-destination fait partie des paquets de données envoyés.
| 
