Protocoles de routage ad hoc pro-actifs

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.

Dans ce qui suit, nous détaillons ces approches par l’intermédiaires de deux exemples de protocoles pro-actifs de routage ad hoc : DSDV [PB94] et OLSR [CJ03].

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. 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 . Chaque nœud recevant ce message le transfère en incluant les entrées qui viennent d’être modifiées.

– Les mises à jour complètes (full dump) pour lesquelles la totalité de la table de routage est envoyée.

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 .

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. le nœud 1 choisit 2 comme MPR parce que c’est le seul nœud qui lui permet d’atteindre 5. Ensuite, il choisit le nœud 3 lui permettant d’atteindre 6, 7 et 8. De cette manière il couvre la totalité des voisins à deux sauts. Le sous ensemble obtenu est annoncé à tous les voisins dans des messages HELLO ultérieurs.
– 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.

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é
4 Étude des faux-positifs
4.1 Approche 1
4.1.1 Modifications apportées au critère d’incohérence
4.1.2 Implémentation
4.1.3 Résultats expérimentaux
4.2 Approche 2 : complément de détection
4.2.1 Principe
4.2.2 Mise en place
4.2.2.1 Cas 1 : décider puis traiter
4.2.2.2 Cas 2 : traiter puis décider
4.2.3 Résultats expérimentaux
4.3 Mesures prises à l’encontre des nœuds malhonnêtes
4.3.1 Types de mesures
4.3.1.1 Exclusion temporaire
4.3.1.2 Exclusion définitive
4.3.2 Comparaison de l’impact de chaque mesure
4.4 Résumé
Conclusion

Lire le rapport complet