Iliyan.Pavlov

COPIE DE LA PAGE WIKIPEDIA OLSR PENDANT SA REDACTION

OLSR (Optimized Link State Routing Protocol) est un protocole de routage destiné aux réseaux maillés, sans fil ou mobiles. Le protocole est une optimisation de l'algorithme d'état de liaison pure. Le concept clé utilisés dans le protocole est l’utilisation des relais multipoints (MPR). L'ensemble MPR est choisi de sorte qu'il couvre tous les nœuds qui sont à deux sauts de suite. Il fonctionne comme un protocole proactif, des informations de topologie avec d'autres nœuds du réseau sont échangées régulièrement .

Dans OLSR deux types de messages sont introduits : « Hello » et « TC » (Topology Control). Chaque nœud diffuse un message Hello contenant des informations sur son voisinage et l’état des liens. L’échange de ces messages permet de prendre connaissance de son voisinage . Pour construire les tables nécessaires au routage des paquets, chaque nœud envoie périodiquement un paquet TC contenant la liste de ses voisins l’ayant choisi comme MPR. Le message TC est diffusé sur tout le réseau. Seuls les voisins MPR rediffusent un paquet TC pour éviter l’inondation .

Ce protocole est défini dans la RFC 3626 de l'IETF, qui le reconnait comme l'un des quatre protocoles de base dans l'utilisation des réseaux MANETs.

Une nouvelle version est en cours de développement.

Historique

L’équipe projet HIPERCOM-INRIA a proposé OLSR en 2001 pour les réseaux ad hoc (ou MANET). Elle a aussi implémenté la première version d’OLSR.

Caractéristiques techniques

Le protocole OLSR est une variation du LSR (en anglais « Link State Routing » ) spéciallement désigné pour les MANETs. Contrairement au LSR ou tous les nœuds sont indifférenciés, l'optimisation d'OLSR est d'utiliser des relais multipoints (MPRs). Les MPRs sont des nœuds choisis qui expédient des messages de diffusion pendant le processus d'inondation. Ils sont les seuls à déclarer leurs liens et sont sélectionnés par les autres noeuds de manière à ce que ceux-ci puissent atteindre n'importe qui en deux sauts. Cette technique réduit sensiblement la surcharge due aux messages par rapport à un mécanisme classique d'inondation, où chaque nœud retransmet chaque message quand il reçoit la première copie du message. Dans OLSR, l'information d'état de lien est produite seulement par des nœuds élus comme MPRs, ainsi, une deuxième optimisation est réalisée en réduisant au minimum le nombre des messages de contrôle inondés dans le réseau. Comme troisième optimisation, un nœud de MPR doit rapporter seulement des liens entre lui-même et ses sélecteurs.

Les deux principales fonctionnalités d'OLSR sont :

• la découverte des voisins
• la diffusion de la topologie

OLSR est une optimisation d'un protocole d'état de liaison pur pour les réseaux mobiles ad hoc .

Premièrement, elle réduit la taille du paquet de contrôle: au lieu de tous les liens, il déclare qu'une partie des liens avec ses voisins, qui sont ses sélecteurs de relais multipoint. Deuxièmement, il minimise les inondations de ce contrôle de la circulation en utilisant uniquement les nœuds sélectionnés, appelés relais multipoint, pour diffuser son message dans le réseau. Seuls les relais multipoints d'un noeud peuvent retransmettre ses messages diffusés. Cette technique réduit considérablement le nombre de retransmissions dans une procédure d'inondation ou de diffusion .

Le protocole est conçu pour fonctionner de manière complètement distribuée et n'a donc pas dépendre de toute entité centrale. Le protocole ne nécessite pas une transmission fiable pour ses messages de contrôle: chaque nœud envoie ses messages de contrôle périodiquement, et peuvent donc subir une perte de certains des paquets de temps en temps, ce qui arrive très souvent dans les réseaux radio en raison de collisions ou d'autres problèmes de transmission .

Détection des voisins

Chaque nœud doit détecter les nœuds voisins avec lesquels il a un lien direct et bidirectionnel. Les incertitudes sur la propagation radio peuvent rendre certains liens unidirectionnels. Par conséquent, tous les liens doivent être contrôlés dans les deux directions, afin d’être considérée comme valide .

Pour accomplir cela, chaque nœud diffuse périodiquement ses messages BONJOUR, contenant les informations sur ses voisins et leur état de lien. Ces messages de contrôle sont transmis dans le mode de diffusion. Ils sont reçus par tous les voisins situés à un saut, mais ils ne sont pas relayées à des nœuds supplémentaires . Un des messages BONJOUR contient :

- La liste des adresses des voisins pour lesquels il existe un lien bidirectionnel valide.

- La liste des adresses des voisins qui sont entendues par ce nœud (un BONJOUR a été reçue), mais le lien n'est pas encore validé comme bidirectionnelle : si un nœud trouve sa propre adresse dans un message BONJOUR, il considère le lien du nœud expéditeur comme bidirectionnelle.

Type de messages

Message Hello

Expéditeur : Chaque nœud du réseau envoie des messages HELLO

Destinataire : Adresse de broadcast

Fonction : Le message HELLO transmet plusieurs informations et a plusieurs utilités. Il sert d'abord à découvrir l'ensemble du réseau. Il transmet ensuite l'état et le type de lien entre l'expéditeur et chaque nœud voisin. Enfin, il spécifie le MPR (Multi-Point Relays) choisi par l'expéditeur.

Datagramme :

Datagramme

• « Reserved » : Ce champ doit contenir « 0000000000000000 »
• « Htime » : Intervalle d'émission des messages HELLO
• « Willigness » : permet de forcer le passage d'un nœud en MPR
• « Link Code » : Code identifiant le type de lien (pas d'information, symétrique, asymétrique, etc.) entre l'expéditeur et les interfaces listées (« Neighbor Interface Address »)

Les messages HELLO ne sont destinés qu'aux nœuds voisins (à un saut) de l'expéditeur, ils ne doivent donc jamais être routés par un MPR.

Message TC (Topology Control)

Expéditeur : Seuls les MPR envoient des messages TC

Destinataire : Adresse de broadcast

Fonction : Le message TC permet au MPR de transmettre la liste de ses voisins qui l'ont choisi comme MPR. Il sert à établir les tables de routage. Aussi, pour qu'il soit diffusé sur tout le réseau, la valeur du TTL dans l'header du message est 255, la valeur maximale (voir « paquet type envoyé par le protocole »).

Datagramme :

Datagramme

• « Reserved » : Ce champ doit contenir « 0000000000000000 »
• « ANSN (Advertised Neighbor Sequence Number) » : Entier incrémenté à chaque changement de topologie. Il permet de ne pas tenir compte des informations obsolètes, pour tenir les tables le plus à jour possible.
• « Advertised Neighbor Main Address » : Adresse IP de nœuds à un saut. L'ensemble des nœuds publiés dans les messages TC est un sous-ensemble des voisins à un saut. La version par défaut recommande de publier les "MPR-Selectors", c'est-à-dire les voisins pour lesquels le nœud courant est un relai MPR.

Message MID (Multiple Interface Declaration)

Les messages MID sont utilisés pour relier les adresses des interfaces OLSR et les adresses principaux pour des nœuds OLSR à interfaces multiples.

Datagramme d'un message MID

Le message MID contient la liste d’adresses des interfaces associées à son adresse principale. Il est envoyé par le nœud dans le réseau pour les déclarer à tous les autres nœuds. Pour obtenir une meilleure fiabilité et un meilleur débit les messages MID peuvent servir à sélectionner plusieurs interfaces comme principaux et ainsi établir des chemins multiples entre deux nœuds voisins. Pour le routage un nœud à interfaces multiples paraîtra comme deux nœuds séparés. Si un lien est en panne, un nœud avec de multiples interfaces pourrait encore fournir le chemin de routage pour les autres nœuds.

Agrégation des messages

Les messages HELLO et TC peuvent être emballés dans le même paquet.
Cela permet l'émission de plusieurs messages en même temps sur le réseau. Le traitement et la méthode de propagation des messages restent néanmoins propres à leur catégorie. Par exemple les messages de type HELLO ne sont pas relayés tandis que ceux de type TC le sont.

Datagramme d'un paquet OLSR

Les relais Multipoints

L'idée des relais multipoint est de minimiser l'inondation de paquets de diffusion dans le réseau en réduisant les retransmissions en double vers un même noeud. Chaque nœud dans le réseau sélectionne un ensemble de nœuds dans son voisinage, qui retransmet ses paquets. Cet ensemble de nœuds voisins sélectionné est appelé le relais multipoint de ce nœud ou MPR .

Les voisins du nœud N qui ne sont pas dans son ensemble MPR, peuvent lire et traiter le paquet, mais ne peuvent pas retransmettre le paquet de diffusion reçus à partir du nœud N . Pour cela, chaque nœud maintient une liste de ses voisins qui sont appelés les sélecteurs de MPR de ce nœud. Chaque message de diffusion provenant de ces sélecteurs MPR d'un nœud est supposé être retransmis par ce nœud. Cet ensemble peut changer au fil du temps, ce qui est indiqué par le sélecteur de noeuds dans leurs messages .

Chaque nœud sélectionne ses relais multipoint parmi ses voisins situés à un saut. Un saut correspond à un noeud dont la distance est la plus proche du noeud principal . Les relais multipoint sont choisis de manière à couvrir (en termes de portée radio) tous les nœuds qui sont situés à deux nœuds de distance . L'ensemble de relais multipoints d'un noeud N, noté MPR (N), est un sous-ensemble arbitraire du noeud de N qui satisfait la condition suivante : chaque noeud dont la distance est à deux sauts de N doit avoir un lien bidirectionnel vers les relais multipoints du noeud N. La figure montre la sélection de relais multipoint autour noeud N .

Relais Multipoints

OLSR repose sur la sélection des relais multipoint, et calcule ses routes vers toutes les destinations connues à travers les nœuds. Les nœuds MPR sont choisis comme des nœuds intermédiaires dans le chemin . Pour mettre en œuvre ce schéma, chaque nœud dans le réseau envoie périodiquement des informations à ses voisins qui ont été choisis comme relais multipoint. Dès réception de l'information sur les sélecteurs MPR, chaque nœud calcule et met à jour ses itinéraires pour chaque destination connue. Par conséquent, la route est une séquence de sauts à travers les relais multipoints de la source à la destination.

Les relais multipoints sont choisis parmi les voisins à un saut avec un lien bidirectionnel. Ainsi, l'itinéraire en passant par les relais multipoints évite automatiquement les problèmes associés au transfert de données par paquets sur les liens unidirectionnels.

Pour le calcul d'itinéraire, chaque nœuds calcule sa table de routage en utilisant un "algorithme de plus courts chemin hop" basé sur la topologie du réseau partielles qu'il a appris .

Exemple de sélection des MPR

La sélection des MPR est le point clé dans le protocole OLSR. La sélection du MPR se fait en choisissant le nœud voisin à un saut. S’il y a plusieurs nœuds, le nœud choisi est alors celui qui a le plus de voisins . Le tableau montre comment le noeud B sélectionne un MPR, basé sur le réseau représenté dans la figure :

Tableau

Si on prend le noeud B, les noeuds C et F couvrent l'ensemble des noeuds voisins à deux sauts. Cependant, le noeud C est sélectionné en tant que MPR car le noeud C a 5 voisins alors que le noeud F en possède 4 (on dit alors que le degré de C est supérieur que le degré de F) .

Exemple d'architecture MPR

Définition

Schéma d'algorithme de sélection des MPR

Sur le schéma d'algorithme de sélection des MPR, l'ensemble N est constitué des voisins à un saut du nœud (ici en rouge), dont on veut déterminer les MPR. Un saut correspond à tous les voisins qui ont répondu au message Hello, cela correspond à la porté radio pour les réseaux Wi-Fi. ^{[réf. nécessaire]}

L'ensemble N2 est constitué des voisins à 2 sauts du même nœud que précédemment. Tous les voisins à un saut du nœud rouge en utilisant les messages hello, vont déclarer leurs voisins à un saut. Ainsi le nœud rouge connaîtra les nœuds à un saut qu'il faudra solliciter pour transmettre un paquet à un voisin à 2 sauts. ^{[réf. nécessaire]}

Un lien asymétrique est représenté par un trait rouge simple. ^{[réf. nécessaire]} Ils sont détectés grâce aux messages Hello, mais ne sont pas utilisés tant qu'ils ne sont pas symétriques.^{[réf. nécessaire]}

Un lien symétrique est représenté par un trait rouge double. ^{[réf. nécessaire]}

Algorithme

Les différents étapes de l'algorithme suit : ^{[réf. nécessaire]}

1. On force tous les éléments de N à rerouter les messages.
2. On calcule D pour chaque nœud de N.
3. Pour tous les nœuds dans N2 qui n'ont qu'un et un seul lien symétrique avec un nœud de N, on définit ce nœud de N comme MPR, et on supprime les nœuds de N2 reliés par ce MPR (on les considère comme reliés). Si le nœud considéré dans N2 a des liens symétriques avec plusieurs nœuds de N (ensemble « E »), on prend comme MPR le nœud « X » de l'ensemble E qui a le plus haut degré D, et on efface les nœuds de N2 joignables par le nœud « X » (on les considère comme reliés).
4. On réitère ces 3 étapes, jusqu'à ce qu’il n'y ait plus de nœud non relié dans N2.

Sécurité

Le protocole OLSR est vulnérable à différents types d'attaques. Il n'est pas nécessaire de passer par un point d'accès pour se connecter au réseau, ce qui le rend très vulnérable. L'utilisation d'une topologie dynamique laisse place à de grandes failles de sécurité. L'utilisation des MPRs rend le protocole OLSR moins sécurisé que le LSR puisque seule la connectivité utile est exploitée, les noeuds ne dupliquent plus l'information.

Types d'attaques

On peut différencier les attaques en deux catégories :

• Attaques communes à tous les protocoles de routage pro-actifs.
• Attaques inhérentes au protocole OLSR.

Cette page portant uniquement sur le protocole OLSR, les vulnérabilités présentées concernent majoritairement les attaques propres à ce protocole.

Une attaque permettant de fournir une connectivité illicite au réseau doit résulter d'un comportement anormal d'au moins un des noeuds qui le composent.
Une attitude anormale peut résulter de deux comportements :

• Un noeud supposé connecté au réseau a été compromis et ne possède plus les mêmes caractéristiques conformes au protocole qu'auparavant.
• Un noeud fait partie du réseau alors qu'il ne le devrait pas.

Chaque noeud a pour rôle premier de générer du trafic propre au protocole de routage, et deuxièmement est responsable de relayer les informations de routage des autres noeuds du réseau.
Un comportement incorrect résulte donc de la génération d'informations erronées sur le routage, ou de l'absence de relais de ces informations.

Des recherches ont été réalisées afin de sécuriser le protocole sur plusieurs niveaux :

• des techniques d'authentification et de chiffrement pour sécuriser le réseau d'attaques externes;
• des détections d'intrusions et des méthodes de communication pour protéger le réseau d'attaques internes.

Brouillage

OLSR est vulnérable au brouillage, c'est d'ailleurs le cas pour tous les autres protocoles de routage utilisés sur réseaux ad-hoc. Le brouillage consiste à générer une grande quantité d'interférences radio. Le bruit généré entraîne alors l'impossibilité pour les noeuds de s'échanger des informations utiles entre eux, notamment leurs routes respectives, et empêche ainsi la construction d'un réseau.

Cette vulnérabilité ne peut pas être corrigée au niveau du protocole de routage.

Protection des attaques externes

Deux approches reconnues assez efficaces pour bloquer les utilisateurs ou les noeuds non autorisés :

• utiliser une Autorité_de_certification distribuée;
• authentifier les messages de contrôle en leur introduisant des signatures permettant de vérifier l'origine et l'intégrité des informations.

Ces solutions ne permettent pas de se protéger d'attaques externes. De plus, l'utilisation de clés dans un réseau MANET est compliquée et lourde à gérer.

Il existe de nombreuses possibilités afin introduire des noeuds dans le protocole OLSR (en partant d'un OLSR définit par la RFC, dépourvu de procédure de validation) pour lancer différentes attaques :

• une surchage des routeurs en inondant le réseau afin de le saturer ("déni de service" ou "Denial_of_service");
• l'envoi de message de mises à jour invalides.

Envoi de message de mises à jour invalides

Un nœud a normalement deux responsabilités :

• générer des messages de contrôles;
• les transférer.

Pour compromettre l'intégralité du protocole de routage, l'attaquant peut soit envoyer des paquets de contrôle incorrects lorsque le nœud génère les messages de contrôle, soit les modifier lorsque les messages de contrôles sont envoyés. Un message de contrôle peut être trafiqué en changeant son identité (en anglais "identity spoofing") ou en endommageant ses données (en anglais "link spoofing").

Attaque sur le message de contrôle durant sa génération

Dans les schémas suivant, les noeuds jaune sont des noeuds classiques et les autres des MPRs.

Usurpation d'identité avec un message HELLO

Un nœud malicieux prétend en être un autre en usurpant son adresse IP (Usurpation_d'adresse_IP), afin d'envoyer un message HELLO à son voisinnage.

Le nœud 5 usurpe l'identité du nœud 3.

---

Vue selon les noeuds 6 et 7, qui ne connaissent pas le nœud 3 et sont persuadés que les noeuds 1 et 2 sont voisins du 5.

---

Corruption des données du message HELLO

Les messages HELLO vont contenir des falsifications de la topologie du réseau avec l'insertion de noeuds inexistants, pour que des usurpateurs soient reconnus comme des MPRs, pouvant alors contrôler tous les flux qui passent par eux.
Il est aussi possible de supprimer des noeuds existants (par omission dans les messages HELLO) afin de les rendre inaccessibles dans la topologie ainsi construite.

Usurpation d'identité d'un nœud avec un message TC

Le nœud 5 est censé envoyer un message TC indiquant qu'il est le dernier saut jusqu'au noeuds 6 et 7.

Le nœud 5 usurpe l'identité du nœud 1.

---

Le trafic destiné aux noeuds 6 et 7 ira jusqu'au nœud 1. Le nœud 1 est devenu le dernier saut jusqu'aux noeuds 6 et 7.

---

Corruption des données avec un message TC

La corruption des données dans les messages TC consiste à insérer des MPRs inexistants ou à en supprimer. La supression de MPRs au sein des tables de routage risque de fragmenter le réseau et certains MPRs ne seront plus accessibles. L'insertion de noeuds MPRs non existants permet de créer de faux liens et de déformer la topologie du réseau, ce qui aura pour conséquence de créer des "boucles" lors du routage ou de générer des conflits lors du calcul des tables de routage.

Consommation énergétique

Les nœuds du réseau MANET ne sont pas connectés sur le réseau électrique et il en résulte que l'énergie de leur batterie est limitée. Le protocole OLSR ne tient pas compte de la consommation énergétique pendant l’élection des nœuds MPR, ni pendant le routage des paquets de données et ne prend aucun avantage de l’information unicast du réseau. Les évolutions envisagées pour prendre en compte ces aspects sont :

Mécanisme basé sur la volonté d’emmètre

La volonté d’un nœud à emmètre est exprimée par une variable fixée par défaut qui représente la disponibilité de ce nœud d’agir comme un MPR. Le choix de cette variable est basé sur la capacité de sa batterie et la durée de vie estimée.

Mécanisme de l’exclusion de l’écoute

Eteindre le nœud pendant l’échange d’un message unicast dans le voisinage. Ceci est réalisé en utilisant les mécanismes de signalisation des couches inférieures qui servent à éviter les collisions (échange RTS / CTS réalisée par l'IEEE 802.11).

Prise en compte de l’énergie pour les paquets à transmettre

Des métriques d’énergie sont introduites dans les nœuds MPR voisins pour sélectionner le prochain saut du routage à partir des mécanismes de routage MPTR, MMBCR et MDR. On découple ainsi la procédure d’élection MPR du mécanisme de routage des paquets.

Implémentations logicielles

• olsrd : une implémentation libre du protocole OLSR.
• nuOLSRv2 : première implémentation OLSRv2 réalisée par l'université de Niigata.

Voir aussi

RFC

• (en) « Optimized Link State Routing Protocol (OLSR) », octobre 2003

Articles scientifiques

• (en) M. Wang, L. Lamont, P. Mason et M. M. Gorlatova, « An effective intrusion detection approach for OLSR MANET protocol », 1st IEEE ICNP Workshop on Secure Network Protocols, 2005. (NPSec), IEEE,‎ 6 novembre 2005, p. 55 - 60 (ISBN 0-7803-9427-5, DOI 10.1109/NPSEC.2005.1532054)

• (en) T. Plesse, J. Lecomte, C. Adjih, M. Badel, P. Jacquet, A. Laouiti, P. Minet, P. Muhlethaler et A. Plakoo, « OLSR performance measurement in a military mobile ad-hoc network », 24th International Conference on Distributed Computing Systems Workshops, 2004. Proceedings, IEEE, vol. 24th International Conference on Distributed Computing Systems Workshops, 2004. Proceedings,‎ mars 2004, p. 704 - 709 (ISBN 0-7695-2087-1, DOI 10.1109/ICDCSW.2004.1284109)

• (en) Frank Y. Li, Lorenzo Vandoni, Giampietro Zicca et Stefano Zanoli, « OLSR Mesh Networks for Broadband Access: Enhancements, Implementation and Deployment », Circuits and Systems for Communications, 2008. ICCSC 2008. 4th IEEE International Conference, IEEE,‎ mai 2008, p. 802-806 (ISBN 978-1-4244-1707-0, DOI 10.1109/ICCSC.2008.175)

• (en) Nabil Ghanem, Selma Boumerdassi et Éric Renault, « New energy saving mechanisms for mobile ad-hoc networks using OLSR », PE-WASUN '05 Proceedings of the 2nd ACM international workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks, ACM Press,‎ 2005, p. 273 (ISBN 1-5959-3182-1, DOI 10.1145/1089803.1090006)

• (en) Jamal Toutouh et Enrique Alba, « An efficient routing protocol for green communications in vehicular ad-hoc networks », GECCO '11 Proceedings of the 13th annual conference companion on Genetic and evolutionary computation, ACM Press,‎ 2011, p. 719-725 (ISBN 9781450306904, DOI 10.1145/2001858.2002076)

• (en) Floriano De Rango, Marco Fotino et Salvatore Marano, « EE-OLSR: Energy Efficient OLSR routing protocol for Mobile ad-hoc Networks », Military Communications Conference, 2008. MILCOM 2008. IEEE, IEEE,‎ novembre 2008, p. 1-7 (ISBN 978-1-4244-2676-8, DOI 10.1109/MILCOM.2008.4753611)

• Amina Naimi Meraihi et Philippe Jacquet, « Le Contrôle du Délai dans le Protocole OLSR », ,‎ juillet 2003, p. 9

Articles connexes

• Topologie mesh
• Babel
• Freifunk, un firmware basé sur OpenWRT utilisant OLSR. Il est conçu pour établir des réseaux mesh extérieurs avec des AP WiFi, comme le LinksysWRT54G.

Liens externes

• (en) RFC3626 La spécification d'OLSR
• (en) Études, simulations et extensions multicast et Qos pour olsr
• (en) Linux Pyramid, une distribution embarquée carte x86 avec OLSR, interface WEB, etc.

Catégorie:Standard Internet Catégorie:Réseau sans fil Catégorie:Wi-Fi Catégorie:Protocole réseau