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é 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 a été proposé par l’équipe projet HIPERCOM-INRIA. Il 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 MANET.
Pour son aspect dynamique, le protocole OLSR est vulnérable à un certain nombre d'attaques, notamment du brouillage, envoi de mises à jour des messages invalides, ainsi que des attaques destinées au message de contrôle durant sa génération ou sa transmission. Des recherches sur des techniques d'authentification et de détection des intrusions ont été réalisées pour sécuriser le protocole. Des évolutions ont été réalisées au cours des études de performance du protocole sur le plan de la qualité de service et de consommation énergétique, suivant les différentes implémentations matérielles et logicielles.
Une nouvelle version est en cours de développement (2010) Spécifications du nouveau standard OLSRv2, dernière version rédigée le 20 avril 2010..
Protocole
Classe
Dans le domaine des , il existe deux classes de protocoles : les réactifs et les pro-actifs.
Les protocoles réactifs doivent systématiquement demander leurs routes en inondant le réseau de leur requête et en recevant la réponse associée.
L'utilisation d'un protocole de cette catégorie au sein d'un MANET implique la construction d'une topologie dans la zone concernée uniquement lorsque le besoin se présente.
Les protocoles réactifs sont : AODV & DSR.
Les protocoles pro-actifs quant à eux s'assurent que chaque nœud possède à tout moment les informations nécessaires relatives à la topologie pour construire une route vers n'importe quel autre point du réseau. Cela est rendu possible à travers des mises à jour régulières sur la topologie.
Les protocoles pro-actifs sont : OLSR, (TBRPF).
Enfin, il existe des protocoles combinant les avantages des protocoles réactifs et pro-actifs, ce sont des protocoles hybrides, tels que (ZRP) et .
Caractéristiques techniques Le protocole OLSR est une variation du LSR (en anglais « Link State Routing » ) spécialement conçu pour les MANET. Contrairement au LSR où tous les nœuds sont indifférenciés, l'optimisation d'OLSR est d'utiliser des relais multipoints (MPR). Les MPR 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 nœuds de manière 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 MPR, 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 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 multipoints. Deuxièmement, il minimise les inondations de la circulation par ce contrôle en utilisant uniquement les nœuds sélectionnés, appelés relais multipoints, pour diffuser son message dans le réseau. Seuls les relais multipoints d'un nœud 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, messages qui peuvent subir une perte de certains des paquets, 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és comme valides.
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çu), mais le lien n'est pas encore validé comme bidirectionnel : si un nœud trouve sa propre adresse dans un message BONJOUR, il considère le lien du nœud expéditeur comme bidirectionnel.
Type de messages Message Hello
Les messages HELLO sont utilisés pour la détection de voisin et calculs MPR. Ils sont transmis périodiquement à tous les voisins à 1 saut. Les messages HELLO incluent le type de lien, la volonté du nœud de devenir MPR, des informations sur les voisins etc. Le type de lien dans ces messages indique si le lien est symétrique, asymétrique ou tout simplement perdu.
Ces messages ne sont destinés qu'aux nœuds voisins (à un saut) de l'expéditeur afin de détecter les liens les inter-connectant, ils ne doivent donc jamais être routés par un MPR.
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.
Il contient également trois listes : Voisins qui ont été "entendus" mais pour lesquels une communication bi-directionnelle n'a pu être établie. Voisins avec qui le nœud a pu établir une liaison bi-directionnelle. Les nœuds désignés comme MPR par le nœud originaire du message HELLO.
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 »)
Message TC (topology control)
Ces messages sont utilisés pour construire la table de routage. Ce sont des messages d'état de liaison, diffusés périodiquement dans des réseaux entiers.
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:
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)
Ces messages sont transmis par les nœuds exécutant le protocole OLSR sur plus d'une interface.
Les messages MID sont utilisés pour relier les adresses des interfaces OLSR et les adresses principaux pour des nœuds OLSR à interfaces multiples.
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 principales et ainsi établir des chemins multiples entre deux nœuds voisins. Pour le routage, un nœud à interfaces multiples apparaî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.
600px|center|thumb|alt=Datagramme d'un paquet OLSR
Relais multipoints
L'idée des relais multipoints est de minimiser l'inondation de paquets de diffusion dans le réseau en réduisant les retransmissions en double vers un même nœud. 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çu à 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 nœuds dans leurs messages.
Chaque nœud sélectionne ses relais multipoints parmi ses voisins situés à un saut. Un saut correspond à un nœud dont la distance est la plus proche du nœud principal. Les relais multipoints sont choisis de manière à couvrir (quant à la portée radio) tous les nœuds qui sont situés à deux nœuds de distance. L'ensemble de relais multipoints d'un nœud N, noté MPR (N), est un sous-ensemble arbitraire du nœud de N qui satisfait la condition suivante : chaque nœud dont la distance est à deux sauts de N doit avoir un lien bidirectionnel vers les relais multipoints du nœud N. La figure montre la sélection de relais multipoints autour du nœud N.
300px|center|thumb|Relais Multipoints