Soutenance mémoire
Concepts fondamentaux des protocoles de routage ad hoc
Le routage est une opération essentielle dans les réseaux ad hoc puisqu’il constitue la base pour l’échange de données entre les nœuds mobiles. Selon Murthy et al. [MRM04], un protocole de routage ad hoc doit assurer :
– L’échange d’informations de routage garantissant l’établissement de chemin entre une source et une destination en se basant sur un certain nombre de critères (plus court, plus rapide, moins congestionné, absence de boucle de routage, etc.) ;
– La maintenance des chemins.
Cette description met en évidence deux processus essentiels à chaque protocole de routage ad hoc : i) la découverte de route et ii) la maintenance des routes. Parallèlement, Murthy et al. [MRM04] insistent sur le fait de prendre en considération les facteurs suivants lors de la conception d’un protocole de routage ad hoc :
– La mobilité compte parmi les caractéristiques des nœuds dans un réseau ad hoc. Mais, cette liberté de mouvement n’est pas sans inconvénients : elle cause la rupture plus au moins fréquente des liens entre les nœuds ;
– Les nœuds ont des ressources limitées en terme d’autonomie de la batterie, de taille de la mémoire et de puissance de calcul ;
– Le canal de transmission sans fil a un taux d’erreur élevé (entre 10⁻⁵ et 10⁻³ ) comparé au médium filaire (entre 10⁻¹² et 10⁻⁹ ) impliquant la perte de paquets. De plus, le canal est partagé par l’ensemble des nœuds présents dans cet espace ce qui implique que la bande passante des liaisons est limitée.
En fonction du mode de fonctionnement de la phase de découverte du chemin et de la mise à jour d’informations de routage, les protocoles de routage ad hoc sont classés en 3 catégories : pro-actif, réactif et hybride. Dans les trois sous-sections qui suivent, nous présentons chacune de ces catégories et fournissons des exemples représentatifs de protocoles.
Protocoles de routage ad hoc pro-actifs
Les protocoles de routage pro-actifs se basent sur l’établissement de routes à l’avance. Les nœuds mettent à jour périodiquement les données de routage de façon à obtenir en permanence le plus court chemin (calculé en terme du nombre de nœuds intermédiaires, aussi appelé nombre de sauts) vers tous les nœuds du réseau. Ainsi, si un nœud désire transmettre un paquet vers une destination, il consulte sa table de routage qui lui indique immédiatement le chemin à suivre. Il existe deux approches pour ce type de protocoles :
– L’approche vecteur de distance où chaque nœud diffuse les distances qui le séparent de tous les autres nœuds du réseau ;
– L’approche à état des liens où il s’agit de diffuser des descriptions des liens avec les nœuds voisins.
Destination Sequence Distance Vector (DSDV)
DSDV [PB94] (Destination-Sequenced Distance-Vector) est l’un des premiers protocoles de routage ad hoc pro-actifs à vecteur de distance. Il se base sur l’algorithme distribué Bellman-Ford DBF (Distributed Bellman-Ford [BGN87]) qui a été modifié pour s’adapter aux réseaux ad hoc. Comme il s’agit d’un protocole pro actif, chaque nœud a, à chaque instant une vision complète du réseau. Pour ce faire, chaque nœud récupère les distances le séparant de chaque autre nœud du réseau et ne garde que le plus court chemin. Ceci est fait grâce à des échanges périodiques d’informations sur leurs tables de routage respectives. Ces échanges sont classés en deux types :
– Les mises à jour incrémentales (incremental updates) pour lesquelles seules les données qui ont subit des modifications depuis la dernière mise à jour sont envoyées. Un exemple est présenté dans la figure 1.1 où, suite au déplacement du nœud 3 qui n’est plus à portée radio, le nœud 4 initie une procédure de mise à jour (update) qui ne concerne que l’entrée correspondant au nœud 3 dans sa table de routage (voir figure 1.1b). Chaque nœud recevant ce message le transfère en incluant les entrées qui viennent d’être modifiées. C’est le cas du nœud 1 qui initialise une mise à jour suite à la réception de celle du nœud 4 ;
– Les mises à jour complètes (full dump) pour lesquelles la totalité de la table de routage est envoyée. La figure 1.2 montre un exemple de cette procédure où le nœud 4 envoie la totalité de sa table de routage à tous les nœuds du réseau ce qui induit des changements au niveau de leurs tables de routage.
Pour gérer la mobilité des nœuds, DSDV associe à chaque nœud un minuteur (timer) qui est mis à jour à la valeur maximale à chaque fois qu’un message est reçu du voisin : c’est un indicateur de validité du lien. Ainsi, lorsque ce minuteur expire, le nœud considère que le voisin en question n’est plus à porté radio et que le lien est rompu. Il peut aussi utiliser les messages de la couche 2 pour détecter les ruptures de liens. La détection d’un lien rompu se traduit au niveau de l’entrée correspondante dans la table de routage par l’assignement de la valeur ∞ au nombre de sauts (en pratique, il s’agit de n’importe quelle valeur supérieure au maximum autorisé) et l’incrémentation du numéro de séquence au prochain numéro impair . Toutes les routes utilisant ce nœud qui n’est plus joignable sont aussi mises à jour comme étant des routes invalides. Ces changements sont envoyés en priorité à tous les voisins en utilisant un paquet de mise à jour. Il est à noter que c’est le seul cas où un nœud autre que la destination pourra changer le numéro de séquence de la destination qui n’est plus joignable .
À la réception d’un paquet de mise à jour, les routes avec les plus grands numéros de séquences sont privilégiées pour le choix des routes puisque cela signifie une route plus fraîche. Dans le cas de numéros de séquences égaux, le plus court chemin est retenu en se basant sur le nombre de saut. Le nœud intermédiaire procède ensuite à la rediffusion des informations qu’il vient de modifier dans sa table de routage tout en incrémentant son numéro de séquence. Malgré les améliorations qu’il propose par rapport à DBF en éliminant le problème des boucles de routage (routing loops) et le problème du comptage à l’infini (counting to infinity) grâce notamment à l’utilisation des numéros de séquence, DSDV reste long et coûteux. Il nécessite des mises à jour régulières de ses tables de routage même lorsque le réseau est inactif. À chaque mise à jour, un nouveau numéro de séquence est nécessaire ce qui augmente le temps avant que le réseau converge. Ceci rend DSDV peu adapté aux réseaux très dynamiques.
Optimized Link State Routing (OLSR)
OLSR [CJ03] (Optimized Link State Routing) est un protocole pro-actif à état de lien (link state). OLSR apporte certaines améliorations sur le principe de base de l’état de lien en vue d’atteindre de meilleures performances dans un contexte ad hoc : il permet de minimiser l’inondation du réseau en diminuant les retransmissions redondantes dans la même région du réseau et réduit la taille des paquets échangés. Pour cela, OLSR se base essentiellement sur la notion de relais multi point (MPR, Multi Point Relay), un sous ensemble des voisins à un saut qui permet d’atteindre la totalité des voisins à deux sauts. Ainsi, lors d’une diffusion, tous les voisins reçoivent et traitent le message mais seulement les nœuds choisis comme MPR le retransmettent ce qui diminue considérablement le nombre de messages émis dans le réseau .
Principe de fonctionnement du protocole. OLSR étant pro-actif, chaque nœud construit en permanence une vision de la topologie du réseau sous forme d’un graphe où les arcs constituent les liens entre les nœuds. La cohérence de cette vision est assurée grâce à des diffusions périodiques des liens sortants. Ainsi, un nœud recevant ces informations met à jour sa vision de la topologie et applique l’algorithme du plus court chemin pour choisir le prochain saut en direction de chaque destination. Nous présentons maintenant les étapes permettant la construction de la topologie :
– Écoute des voisins (neighbor sensing) : Il s’agit du processus de découverte du voisinage direct et symétrique qui est effectué grâce à la diffusion périodique de messages de type HELLO contenant des informations sur le voisinage ainsi que l’état des liens (link state) le reliant à cet ensemble de nœuds. Ce message de contrôle est destiné exclusivement aux voisins à un saut et n’est donc pas retransmis. De cette manière, un nœud construit la liste des voisins à un saut (Neighbor Set) tout en marquant les liens symétriques et puisqu’il voit aussi la liste des voisins de ceux-ci, il construit la liste des voisins à deux sauts 2HNS (2-Hops Neighbor Set).
– Sélection des relais multi-point : Cette sélection est faite de façon indépendante par chaque nœud. Elle passe par le choix du sous ensemble des nœuds à un saut qui permettent d’atteindre l’intégralité de voisins à deux sauts.
– Déclaration des relais multi-point : Les nœuds MPR diffusent des paquets de contrôle spécifiques appelés TC (Topology Control) pour construire une base d’informations sur la topologie du réseau. Les messages TC sont transmis à intervalles réguliers et déclarent l’ensemble MPRSS (Multi Point Relay Selector Set), c’est-à-dire l’ensemble contenant les voisins ayant choisit le nœud origine de ce message comme MPR. Les informations sur la topologie du réseau reçues dans les messages TC sont enregistrées dans la table de topologie (topology table).
– Calcul de la table de routage : La table des voisins (neighbor table) ainsi que la table de topologie (topology table) sont utilisées pour le calcul de la table de routage qui se base sur l’algorithme du plus court chemin [Dij59]. Toute modification de l’une de ces tables entraine la modification de la table de routage.
Cette amélioration à base de relais multi-point fournit des routes optimales en nombre de sauts tout en diminuant le nombre de messages de contrôles qui circulent lors d’une diffusion. Il convient ainsi aux grands réseaux ad hoc mais semble être moins efficace pour des petits réseaux [PJ03].
|
Table des matières
Introduction
1 État de l’art
1.1 Concepts fondamentaux des protocoles de routage ad hoc
1.1.1 Protocoles de routage ad hoc pro-actifs
1.1.1.1 Destination Sequence Distance Vector (DSDV)
1.1.1.2 Optimized Link State Routing (OLSR)
1.1.2 Protocoles de routage ad hoc réactifs
1.1.2.1 Dynamic Source Routing (DSR)
1.1.2.2 Ad hoc On-demand Distance Vector (AODV)
1.1.3 Protocoles de routage ad hoc hybrides
1.2 Sécurité du routage dans les réseaux ad hoc
1.3 Solutions et mécanismes de sécurité
1.3.1 Solutions basées sur la cryptographie
1.3.2 Systèmes de gestion de la réputation
1.3.3 Systèmes de gestion de la confiance
1.4 Positionnement
2 Analyse de la confiance
2.1 Vulnérabilités du protocole de routage ad hoc AODV
2.1.1 Attaques élémentaires portant sur les demandes de route
2.1.1.1 Suppression d’une demande de route
2.1.1.2 Modification d’une demande de route
2.1.1.3 Fabrication d’une demande de route
2.1.1.4 Rushing d’une demande de route
2.1.2 Attaques élémentaires portant sur les réponses de route
2.1.2.1 Suppression d’une réponse de route
2.1.2.2 Modification d’une réponse de route
2.1.2.3 Fabrication d’une réponse de route
2.1.3 Attaques élémentaires portant sur les erreurs de route
2.1.3.1 Suppression d’une erreur de route
2.1.3.2 Modification d’une erreur de route
2.1.3.3 Fabrication d’une erreur de route
2.1.4 Attaques composées
2.1.4.1 Répétition régulière d’attaques élémentaires
2.1.4.2 Insertion dans une route déjà établie
2.1.4.3 Insertion dans une route non encore établie
2.1.4.4 Création d’une boucle de routage
2.1.4.5 Création d’un tunnel
2.2 Analyse de la confiance implicite dans AODV
2.2.1 Présentation du langage de formalisation
2.2.2 Notations
2.2.3 Processus de découverte de route
2.2.3.1 Initialisation de la demande de route
2.2.3.2 Propagation de la demande de route
2.2.3.3 Propagation de la réponse de route
2.2.4 Maintient des routes
2.3 Détection des nœuds malhonnêtes
2.3.1 Présentation de la table d’historique étendue THE
2.3.2 Critères d’incohérences
2.3.2.1 Rejeu de messages
2.3.2.2 Fabrication de messages
2.3.2.3 Modification de messages
2.4 Résumé
3 Expérimentations
3.1 Environnement de simulation
3.2 Choix de l’implémentation d’AODV
3.3 Implémentation des critères d’incohérences
3.4 Implémentation du comportement malhonnête
3.5 Mise en place des simulations dans NS-2
3.6 Résultats des simulations
3.6.1 Performance du système de détection
3.6.1.1 Résultats concernant les attaques élémentaires
3.6.1.2 Résultats concernant les attaques complexes
3.6.1.3 Discussion concernant les faux-positifs
3.6.2 Performance du protocole
3.6.2.1 Taux de paquets reçus avec succès
3.6.2.2 Délai de bout-en-bout
3.6.2.3 Charge de routage
3.6.3 Mise à l’épreuve du système de détection
3.7 Résumé
Conclusion
Télécharger le rapport complet
