Optimized Link State Routing Protocol

Dans le domaine des MANET, il existe deux classes de protocoles : les réactifs et les pro-actifs[8].

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[8].

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[8].

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[8].

Les protocoles pro-actifs sont : OLSR, Topology dissemination based on reverse-path forwarding (en) (TBRPF)[8].

Enfin, il existe des protocoles combinant les avantages des protocoles réactifs et pro-actifs, ce sont des protocoles hybrides, tels que Zone Routing Protocol (en) (ZRP) et TORA[9].

Le protocole OLSR est une variation du LSR (en) (en anglais « Link State Routing » ) spécialement conçu pour les MANET[10]. Contrairement au LSR où tous les nœuds sont indifférenciés, l'optimisation d'OLSR est d'utiliser des relais multipoints (MPR)[10]. Les MPR sont des nœuds choisis qui expédient des messages de diffusion pendant le processus d'inondation[11]. 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[10]. 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[12] :

• 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 [2].

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 [2].

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 [2].

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 [13].

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 [2].

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.

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 [14].

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[15] :

• 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 [16]:

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 »)

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 [14].

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 [17]:

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.

Ces messages sont transmis par les nœuds exécutant le protocole OLSR sur plus d'une interface [14].

Les messages MID sont utilisés pour relier les adresses des interfaces OLSR et les adresses principaux pour des nœuds OLSR à interfaces multiples[18]^,[19].

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[20]. 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[19].

Les messages HELLO et TC peuvent être emballés dans le même paquet[21].

Cela permet l'émission de plusieurs messages en même temps sur le réseau[21].

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[21].

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 [2].

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 [22]. 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 [22].

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 [23]. 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 [23]. 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 [23].

Relais Multipoints

OLSR repose sur la sélection des relais multipoints, 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 [24]. 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[24].

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[23].

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

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ée radio pour les réseaux Wi-Fi[26]^,[27].

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[28]^,[29].

Un lien asymétrique (ou unidirectionnel, le lien est valide que dans un seul sens) est représenté par un trait rouge simple[28]^,[29]. Ils sont détectés grâce aux messages Hello, mais ne sont pas utilisés tant qu'ils ne sont pas symétriques[28]^,[29].

Un lien symétrique (ou bidirectionnel, le lien est valide dans les deux sens) est représenté par un trait rouge double[28]^,[29].

Les différents étapes de l'algorithme sont [28]^,[29]:

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 trois étapes, jusqu'à ce qu’il n'y ait plus de nœud non relié dans N2.

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 [1]. Le tableau montre comment le nœud B sélectionne un MPR, basé sur le réseau représenté dans la figure :

Tableau

Si on prend le nœud B, les nœuds C et F couvrent l'ensemble des nœuds voisins à deux sauts. Cependant, le nœud C est sélectionné en tant que MPR car il a 5 voisins alors que le nœud F en possède 4 (on dit alors que le degré de C est supérieur au degré de F) [1].

Exemple d'architecture MPR

On peut répertorier les attaques en deux catégories[21] :

• 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. Chaque nœud 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 nœuds 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 [21].

Une attaque permettant de fournir une connectivité illicite au réseau doit résulter d'un comportement anormal d'au moins un des nœuds qui le composent.

Une attitude anormale peut résulter de deux comportements[21] :

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

Il existe de nombreuses possibilités afin d'introduire des nœuds 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[10] :

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

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 nœuds de s'échanger des informations utiles entre eux, notamment leurs routes respectives, et empêche ainsi la construction d'un réseau[21].

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

Un nœud a normalement deux responsabilités[10] :

• 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ôle sont envoyés[30]. 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").

Dans les schémas suivants, les nœuds jaunes sont des nœuds classiques et les autres des MPR.

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[30].

Usurpation d'identité d'un nœud

Usurpation d'identité d'un nœud

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

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

Usurpation d'identité d'un nœud

Usurpation d'identité d'un nœud

La corruption des données dans les messages TC consiste à insérer des MPR inexistants ou à en supprimer. La suppression de MPR au sein des tables de routage risque de fragmenter le réseau et certains MPR ne seront plus accessibles. L'insertion de nœuds MPR 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[30].

Les messages TC nécessitent d'être transmis à travers les MPR à l'ensemble du réseau, afin de transporter des informations critiques sur les tables de routage. Les nœuds relais peuvent trafiquer ces messages pendant leur transfert, en ajoutant ou supprimant des MPR. Les problèmes peuvent être plus sérieux que lors du trafique des messages HELLO, car les messages TC sont utilisés par tous les nœuds. Il est donc très facile de lancer une attaque de type "trou noir", qui met en œuvre des nœuds qui font discrètement disparaître le trafic[31].

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

• 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.

Deux approches reconnues assez efficaces pour bloquer les utilisateurs ou les nœuds non autorisés[6] :

• 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[6].

La redondance entre les messages HELLO et les messages TC est une opportunité pour vérifier des informations conflictuelles entre les nœuds afin de protéger le protocole OLSR[31]. Dans toutes les propriétés suivantes, TCp correspond à l'ensemble des sélecteurs de P, MPRp à l'ensemble des MPR liés à P et HELLOp à l'ensemble des voisins directs de p.

Propriété 1 Un message HELLO contient tous les voisins situés à un saut du nœud qui l'envoie, tandis qu'un message TC contient les sélecteurs de MPR du nœud (autrement dit, le message TC, envoyé par un MPR, dispose de tous les nœuds qui ont choisi celui-ci comme relai)[31]. Le message TC contient donc un sous ensemble du message HELLO, TCp ← HELLOp. Si cette propriété est violée, cela signifie que le nœud à l'origine du message TC a inséré des sélecteurs de MPR et qu'il prétend être un nœud MPR (link spoofing)[31].

Relations entre TCp et HELLOp

Propriété 2 Si un nœud MANET reçoit un message TC le listant comme un sélecteur de MPR, alors celui à l'origine de ce message doit être dans le voisinage de ce nœud[31]. Si C Є TCp, alors P Є HELLOc doit d'abord être vrai[31]. Si ce n'est pas le cas, cela peut indiquer plusieurs attaques. Le nœud à l'origine du message TC prétend être un MPR (link spoofing sur un message TC)[31].

Relations entre TCp, HELLOc et HELLOd

Propriété 3

Si une nœud MANET reçoit un message TC de ses voisins ayant pour information qu'il est un sélecteur de MPR, ce nœud doit d'abord avoir énuméré l'envoyeur du message comme un MPR dans son message HELLO[32]. Si Q Є TCp, alors P Є MPRq doit d'abord être vrai[32]. Si cette propriété est violée, le nœud à l'origine du message TC prétend être un nœud MPR pour le receveur et tout son voisinage, afin de détourner le trafic (link spoofing)[32].

Relations entre TCp et MPR

Propriété 4

Tous les messages TC transférés ont un contenu identique[32]. Afin de le vérifier, un composant peut être déployé dans tous les nœuds du réseau afin de détecter toutes les mises à jour illégitimes sur le message de contrôle. Les nœuds recevant les messages TC vont appliquer "une validation", qui sera aussi appliquée par les nœuds les transférant. La vérification de conflit permet alors d'augmenter le niveau de sécurité du protocole ainsi que la robustesse des opérations de routage[32].

Pour faire face aux inconvénients du protocole OLSR, différents protocoles sont en cours de développement ou ont été développés afin de répondre aux carences du protocole.

OLSR souffre d'un sérieux problème de synchronisation des messages TC et des informations relatives aux routes contenues dans chacun des nœuds[33].

En effet les routes connues par les nœuds et l'état réel de la topologie peuvent différer durant un certain laps de temps, et il est nécessaire d'attendre que la mise à jour de la topologie soit effectuée afin de disposer de routes à nouveau correctes, ce qui peut créer des boucles au sein du réseau[33].

C'est une des raisons pour lesquelles le développement du protocole BATMAN fut lancé[33].

OLSRv2 est également en cours de développement par l'IETF depuis 2005[34], corrigeant les défauts d'OLSR et actuellement encore à phase de standardisation, une version finale (RFC) devrait bientôt voir le jour[35].

CE-OLSR est une version basée sur OLSR mais intégrant la localisation des nœuds[36].

Chaque message HELLO se voit ainsi ajouter un champ dans lequel sa propre position (coordonnées GPS) ainsi que celles de ses voisins sont ajoutées[37].

Chaque message TC quant à lui se voit également ajouter par les MPR un champ dédié aux coordonnées des autres sélecteurs MPR[37].

CE-OLSR apporte ainsi les améliorations suivantes [38]:

• Meilleure robustesse des messages de contrôle (topologie) par rapport à la perte de paquets.
• Les changements de topologie sont détectés plus rapidement, ce qui apporte un suivi précis du voisinage.
• Capacité à discerner les informations cartographiques récentes des obsolètes.
• Il en résulte de meilleures performances, sur le plan à la fois du débit et du temps de réponse et également une validité accrue des routes connues.

M-OLSR est une variante d'OLSR modifiant le protocole afin de fournir de meilleures performances au sein de WMN (réseaux maillés sans-fil), à savoir[39] :

• Amélioration du débit.
• Meilleur pourcentage de paquets délivrés.
• Réduction de la surcharge réseau liée au protocole.

Les WMN diffèrent des MANET de par leur architecture quelque peu différente. En effet, alors qu'un MANET ne possède aucun point fixe parmi tous ses nœuds, un WMN possède un nœud connu de tous les autres, jouant le rôle de colonne dorsale (backbone) au sein du réseau[39]. La répercussion d'une modification du protocole OLSR n'est donc pas forcément la même selon que le réseau concerné est de type WMN ou MANET[39].

La QoS n'est pas géré nativement dans OLSR, mais un projet intégrant cette fonctionnalité est en cours de développement[40].

La gestion du QoS n'est pas triviale dans le cas d'un protocole de routage à état de lien de par sa structure constamment changeante et la puissance limitée disponible au sein des nœuds composant des MANET[41].

Un protocole de routage pro-actif a l'avantage de pouvoir maintenir des routes pré-calculées sur lesquelles la QoS pourra s'appuyer afin de prendre rapidement des décisions, ce qui n'est pas le cas des protocoles de routage réactifs calculant les routes seulement à la demande[41].

Ceci est un avantage considérable dans le cadre de réseaux de nature imprévisible, comme les MANET. La couche de contrôle peut aisément vérifier si une route pré-calculée peut satisfaire la demande, et si ce n'est pas le cas ainsi éviter la génération d'un trafic inutile relatif au routage et à la topologie[41].

Une première manière de procéder consiste à modifier l'algorithme de sélection des MPR. Le comportement défini par la RFC d'OLSR indique que cette sélection s'effectue sur base du nombre de voisins, le nœud élu en tant que MPR étant celui possédant le plus de voisins à 2 sauts[5].

Cette méthode de sélection ne prend cependant pas en compte la qualité des liens interconnectant les nœuds, ce qui dans une optique de qualité de service est pourtant un des points les plus critiques[42].

Un autre algorithme pourrait consister à se baser sur la bande passante disponible en tant que premier critère de sélection des MPR. Le but est alors d'obtenir une route possédant un débit le plus élevé possible, facteur jouant un rôle prépondérant dans les applications temps-réel de plus en plus utilisées aujourd'hui[43].

À l'origine OLSR sélectionne le chemin le plus court lors de la sélection des MPR, ce qui n'est pas forcément synonyme de performance, encore faut-il définir le terme "performance" (latence, bande-passante, redondance, etc).

Dans le cas où l'on souhaite orienter les performances vers un aspect ou un autre en particulier, il faut modifier l'algorithme afin de sélectionner les MPR selon d'autres facteurs que la connectivité des nœuds, comme la vitesse, dans le cas où la bande passante est la contrainte première du QoS[43].

Une tentative de modification du protocole OLSR est illustrée ci-dessous, visant à maximiser la bande passante de bout en bout tout en assurant que chaque nœud à 2 sauts soit toujours connecté. Les valeurs indiquées représentant la bande passante : plus elle est élevée, plus la bande passante est importante.

Sélection d'un MPR selon les spécifications originales d'OLSR

Dans sa version originale, OLSR ne prend pas en compte la bande passante disponible pour chaque lien.

Le nœud B sélectionnera donc C comme étant son MPR dans ce cas de figure-ci, car c'est celui qui possède le plus de connexions avec les autres nœuds[43].

Cela signifie donc que lorsque D construira sa table de routage, il sélectionnera d'office la route D-C-B pour joindre le nœud B. Cette route est la pire de toutes avec un goulot d'étranglement souffrant de la vitesse la plus restrictive de tout le MANET (valeur de 3) entre D et C[43].

Par cet exemple flagrant, on réalise qu'OLSR ne sélectionnera pas le chemin le plus rapide.

Sélection d'un MPR selon la version #1 modifiée de l'algorithme OLSR

L'algorithme reste presque identique à la version originale.
Lorsqu'il existe plus d'un nœud à un saut, mais qu'ils couvrent tous le même nombre de nœuds à deux sauts, c'est celui qui possède la plus grande bande passante qui est élu MPR[43].
F est donc élu MPR à la place de C, car la liaison reliant B à F (100) possède une vitesse plus grande que la liaison entre B et C (50)[43].

Sélection d'un MPR selon la version #2 modifiée de l'algorithme OLSR

L'idée de cette deuxième version consiste à choisir les nœuds ayant la meilleure bande passante avant tout, tant que tous les nœuds à deux sauts sont couverts[43].

Dans ce cas-ci, les nœuds A et F seront sélectionnés avec respectivement une bande passante de 110 et 100 en partant de B[43].

À est d'abord sélectionné grâce à sa bande passante la plus élevée, mais n'élire que le nœud A en MPR ne permettrait pas d'établir une connexion avec tous les nœuds à deux sauts (E resterait injoignable par B)[43].
C'est pourquoi le nœud F est choisi en tant que deuxième MPR (et non C, car 100 > 50)[43].

Sélection d'un MPR selon la version #3 modifiée de l'algorithme OLSR

La troisième modification de l'algorithme compare chaque chemin partant de B vers chaque autre nœud se situant à 2 sauts du MANET. Il sélectionne alors le seul chemin ayant la bande passante la plus élevée vers chacun de ces nœuds[43].

Ci-dessous le tableau montre la comparaison des bandes-passante et la raison pour laquelle le nœud F est sélectionné pour connecter les nœuds B et D[43].

Même raisonnement pour joindre les nœuds B et E : C sera le MPR choisi.

Ces différentes modifications ont le potentiel d'améliorer les performances en apportant une meilleure bande-passante à chaque nœud[44].
En revanche, elles peuvent également engendrer une surcharge du trafic de contrôle (véhiculant les informations sur la topologie), surtout dans le troisième exemple où il est potentiellement possible d'élire un MPR différent par nœud à 2 sauts[44].

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. La vie de la batterie peut aussi affecter la performance de communication du réseau. Quand un nœud épuise l'énergie disponible, il cesse de fonctionner et il peut y avoir pénurie d'hôtes mobiles dans le partitionnement du réseau. Pour cette raison la réduction de la consommation énergétique est un sujet important dans les réseaux sans fil ad hoc[45]. 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 tire aucun avantage à partir de l’information des liaisons unicast du réseau[46]^,[47]. Les évolutions envisagées pour prendre en compte ces aspects sont entre autres les protocoles EE-OLSR[48], EOLSR[49] et DE-OLSR[50] :

Pour prendre en compte la consommation énergétique des nœuds certains métriques ont été introduites dans la couche réseau pour EE-OLSR [51]:

• MTPR (Minimum Total Transmission Power Routing) : simple métrique énergétique qui représente l'énergie totale consommée pour transférer l'information sur le chemin[51]^,[52].
• MBCR (Minimum Battery Cost Routing) : minimise la fonction mesurant la réticence des nœuds par rapport à l'énergie[51]^,[53].
• MMBCR (Min-Max Battery Cost Routing) : choisit la route avec les meilleures conditions parmi les chemins touchés par un nœud crucial en se servant de la fonction introduite pour le MBCR[51]^,[53].
• CMMBCR (Conditional MMBCR) : tente d'effectuer une approche hybride entre MTPR et MMBCR, en utilisant le premier tant que les nœuds d'une route possible ont suffisamment d'énergie restante suivant un seuil défini et le second quand parmi toutes les routes possibles il y au moins un nœud étant sous le seuil d'énergie restante[51]^,[54].
• MDR (Minimum Drain Rate) : introduit une fonction de coût prenant en compte l'indice de taux de décharge et la puissance résiduelle de la batterie pour mesurer le taux de dissipation de l'énergie d'un nœud[51]^,[55].

Avec l'inclusion de ces métriques et encore deux autres améliorations de l'aspect énergétique du protocole OLSR le protocole EE-OLSR établit ces mécanismes :

• Mécanisme basé sur la volonté d’émettre. La volonté d’un nœud à émettre 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[48].
• Mécanisme de l’exclusion de l’écoute. Éteindre 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)[47].
• 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[51]. On découple ainsi la procédure d’élection MPR du mécanisme de routage des paquets[47]^,[50].

Le protocole EOLSR a été conçu comme EE-OLSR à minimiser la consommation d'énergie pour la transmission d'un paquet, à faire de l'équilibrage de charge entre les nœuds du réseau, d'éviter les nœuds avec peu d'énergie restante et de réduire la surcharge[49]. Pour ce faire, la conception a été élaborée dans ces quatre aspects [49]:

• Le calcul efficace des routes est établi suivant un modèle énergétique adapté au protocole MAC choisi[49].
• La sélection des nœuds MPR est pris en compte dans le modèle énergétique et une nouvelle information est incluse dans le message Hello calculé avant chaque réémission[49].
• La sélection des routes se fait en minimisant la consommation énergétique de point à point basé sur le coût du flux comme critère de chaque chemin à emprunter[56].
• Le message de broadcast est optimisé pour les ressources énergétiques du réseau. Un nœud transfert un message pour broadcast avec un TTL non nul si et seulement s'il reçoit ce message pour la première fois d'un nœud qui l'a sélectionné comme MPR[56].

Dans un cadre un peu différent des deux autres le protocole DE-OLSR a été conçu pour des réseaux ad-hoc VANET[57]. Ceux-ci sont conceptuellement similaires aux réseaux MANET et sont destinés à la communication sans fil des véhicules équipés d'ordinateurs de bord, des éléments électroniques de la signalisation de la circulation, capteurs et aussi des piétons avec des smartphones[57]. À la base, cet algorithme n'implémente pas de solution spécialement conçue pour être performant sur le plan du coût d'énergie. L'idée principale est de trouver un paramétrage efficace pour optimiser la qualité de service du protocole OLSR du point de vue du taux de livraison de paquets de la charge de routage normalisée et un délai moyen en point à point de paquets de données des réseaux VANET[50]. Ceci est mené par le couplage avec une méta-heuristique Differential Evolution (DE)[58]^,[59]. Le protocole arrive à économiser presque deux tiers d'énergie en moyenne par rapport à l'OLSR standard sur l'échange des messages de contrôle dans un réseau VANET tout en diminuant la consommation d'énergie en transmission de données et la charge[60].

D'autres protocoles de routage existent pour les réseaux mobiles. Voici une comparaison non exhaustive entre quelques-uns d'entre eux :

Plusieurs tests de performances ont été effectués dont notamment une comparaison pratique entre des implémentations d'OLSRv1 et BATMAN au sein de réseaux de taille et trafic variables[61].

Pour ce qui est du ratio des paquets délivrés, il s'est avéré que lorsque le trafic est faible, OLSR est plus performant que BATMAN . La tendance s'inverse lorsque le trafic devient important[62].

Pour ce qui est de la surcharge du trafic (informations relatives au routage et à la topologie), OLSR est plus performant que BATMAN tant que le nombre de nœuds reste modeste, quelle que soit l'intensité du trafic[63].

Dès lors que le nombre de nœuds devient plus important, BATMAN devient le protocole le plus performant des deux[63].

Une comparaison entre les protocoles DSR & AODV (réactifs) et OLSR (pro-actif) a également été réalisée, mettant en évidence l'attrait d'OLSR pour les sources CBR (tels que la voix sur IP), garantissant des délais plus courts que les protocoles réactifs précédemment mentionnés.

En revanche, OLSR consomme beaucoup plus de bande passante à cause des routes qu'il maintient continuellement engendrant un trafic soutenu continuel.

Les tests ont montré que les protocoles réactifs étaient plus adaptés qu'OLSR dans le domaine de copie de données (échange de fichiers par exemple), sans pour autant savoir clairement départager DSR et AODV du point de vue des performances.

Une autre comparaison entre les protocoles OLSR, AODV et TORA a pu faire ressortir les résultats suivants[64] :

L'étude ayant mené la comparaison de ces trois protocoles de familles différentes a pu conduire aux constatations suivantes[64] :

• Les performances des trois protocoles au sein d'un réseau à densité faible étaient relativement stables avec un trafic faible[65].
• OLSR est plus efficace dans les réseaux à forte densité avec un trafic hautement sporadique. Il nécessite de disposer d'une bande-passante continuelle afin de régulièrement échanger les messages propres à la topologie. Par ailleurs, AODV préserve des performances régulières en milieu dense[65].
• Enfin toujours selon cette même étude, TORA donne les meilleurs résultats pour la livraison de paquets en réseau dense grâce à son mécanisme de sélection des meilleures routes[65].

• OLSRd : une implémentation libre du protocole OLSR[66].
• nuOLSRv2[67] : première implémentation OLSRv2 réalisée par l'université de Niigata[68].
• OOLSR [69] : implémentation en C++ avec plusieurs outils supplémentaires, développée par l'équipe HIPERCOM elle-même.
• pyOLSR [70] : implémentation en Python avec plusieurs outils additionnels, développée par l'équipe HIPERCOM également (rendu obsolète par OOLSR).
• Qolyester [71] : implémentation de QOLSR en C++, version modifiée d'OLSR avec ajout de la fonctionnalité "Qualité de service".
• Une implémentation de CRC [72] (première version gérant l'IPv6)

Puisque OLSR est une couche réseau de niveau couche 3, il est hautement portable et exécutable sur tout système d'exploitation standard I386 et PPC via le plugin d'interface utilisateur de OLSRd[73].

• MSB-430 : un nœud de capteur conçu au CST-Freie Universitat-Berlin et utilisé pour tester les protocoles OLSR et B.A.T.M.A.N. dans un réseau WSN[74].
• WRT54G : un routeur sans fil avec un processeur basé MIPS de chez LinkSys(Cisco)[75].
• MeshCube : un petit routeur sans fil de chez 4G Systems avec processeur MIPS à 400Mhz et 64 Mo de mémoire vive[76].
• iPAQ : un assistant personnel de chez Compaq/HP avec une architecture processeur strong-ARM et NetBSD en système d'exploitation[77].
• Nokia N900 sous Linux Maemo[78].
• Google phone sous Android, G1[79].

• (en) « Optimized Link State Routing Protocol (OLSR) », sur ietf.org, octobre 2003

• (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,‎ 23 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) C.-K. Toh, « Maximum battery life routing to support ubiquitous mobile computing in wireless ad hoc networks », IEEE Communications Magazine, IEEE, vol. 39,‎ juin 2001, p. 138-147 (ISSN 0163-6804, DOI 10.1109/35.925682)
• (en) Dongkyun Kim, J.J. Garcia-Luna-Aceves et K. Obraczka, « Power-Aware Routing Based on The Energy Drain Rate for Mobile Ad Hoc Networks », Computer Communications and Networks, 2002, IEEE,‎ octobre 2002, p. 565-569 (ISBN 0-7803-7553-X, DOI 10.1109/ICCCN.2002.1043126)
• (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-274 (ISBN 1-5959-3182-1, DOI 10.1145/1089803.1090006)
• (en) Saoucene Mahfoudh et Pascale Minet, « Energy-aware routing in wireless ad hoc and sensor networks », Proceedings of the 6th International Wireless Communications and Mobile Computing Conference, ACM Press,‎ 2010, p. 1126-1130 (ISBN 978-1-4503-0062-9, DOI 10.1145/1815396.1815654)
• (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) Hassan Sinky et Bechir Hamdaoui, « Implementation and performance measurement and analysis of OLSR protocol », IWCMC '10 Proceedings of the 6th International Wireless Communications and Mobile Computing Conference, ACM Press,‎ 2010, p. 286-290 (ISBN 978-1-4503-0062-9, DOI 10.1145/1815396.1815463)
• (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)
• (en) Abd Al Basset Almamou, Raphaela Wrede, Pardeep Kumar, Houda Labiod et Jochen Schiller, « Performance evaluation of routing protocols in a Real-World WSN », Information Infrastructure Symposium, 2009. GIIS '09, IEEE,‎ juin 2009, p. 1-5 (ISBN 978-1-4244-4623-0, DOI 10.1109/GIIS.2009.5307052)
• (en) Kenneth V. Price, Rainer M. Storn et Jouni A. Lampinen, « Differential Evolution A Practical Approach to Global Optimization », Natural Computing Series, Springer Berlin Heidelberg,‎ 2005, p. 37-134 (ISBN 978-3-540-31306-9, DOI 10.1007/3-540-31306-0)
• (en) S. Sharma, « P-OLSR: Position-based optimized link state routing for mobile ad hoc networks », LCN 2009. IEEE 34th Conference, IEEE,‎ octobre 2009, p. 237-240 (ISBN 978-1-4244-4488-5, DOI 10.1109/LCN.2009.5355100)
• (en) Ying Ge, Thomas Kunz et Louise Lamont, « Quality of Service Routing in Ad-Hoc Networks Using OLSR », HICSS’03 Proceedings of the 36th Annual Hawaii International Conference,‎ 2003, p. 1-9 (ISBN 0-7695-1874-5, DOI 10.1109/HICSS.2003.1174847, lire en ligne)
• Amina Naimi Meraihi et Philippe Jacquet, « Le Contrôle du Délai dans le Protocole OLSR », HIPERCOM - INRIA Rocquencourt, Rapport de recherche,‎ juillet 2003, p. 1-9 (résumé, lire en ligne)
• Rabah Meraihi, « Gestion de la qualité de service et contrôle de topologie dans les réseaux ad hoc », Thèse ecole nationale supérieure des télécommunications,‎ 2004, p. 1-136 (lire en ligne)
• (en) Philippe Jacquet, Paul Muhlethaler, Thomas Clausen, Anis Laouiti et Laurent Viennot, « Optimized Link State Routing Protocol for Ad Hoc Networks », HIPERCOM - INRIA Rocquencourt, Rapport de recherche,‎ 2001, p. 1-53 (DOI 10.1109/INMIC.2001.995315, résumé, lire en ligne)
• (en) Thomas Clausen et Philippe Jacquet, « The Optimised Routing Protocol for Mobile Ad-hoc Networks: protocol specification », HIPERCOM - INRIA Rocquencourt, Rapport de recherche,‎ mars 2004, p. 1-53 (lire en ligne)
• (en) P. Kuppusamy, K. Thirunavukkarasu et B. Kalaavathi, A Study and Comparison of OLSR, AODV and TORA Routing Protocols in Ad Hoc Networks, 2011 (DOI 10.1109)
• (en) Leonard Barolli, Makoto Ikeda, Giuseppe De Marco, Arjan Durresi et Fatos Xhafa, « Performance Analysis of OLSR and BATMAN Protocols Considering Link Quality Parameter », AINA '09 Proceedings of the 2009 International Conference on Advanced Information Networking and Applications,‎ 2009, p. 307-314 (ISBN 978-0-7695-3638-5)
• (en) Paul Amrita Bose et Nandi Sukumar, Modified Optimized Link State Routing (M-OLSR) for Wireless Mesh Networks, 17-20 décembre 2008 (ISBN 978-0-7695-3513-5)
• (en) Thierry Plesse, Jérôme Lecomte, Cedric Adjih, Marc Badel et Philippe Jacquet, « OLSR Performance Measurement in a Military Mobile Ad-hoc Network », Ad Hoc Networks, vol. 3,‎ 2004, p. 575-588

• Topologie mesh
• Babel
• Freifunk (en), un firmware basé sur OpenWRT utilisant OLSR. Il est conçu pour établir des réseaux mesh extérieurs avec des AP Wi-Fi, comme le Linksys WRT54G.

• (en) RFC3626 Spécification d'OLSR
• (en) Études, simulations et extensions multicast et QoS pour OLSR

• Portail de l’informatique
• Portail des télécommunications