OLSR

Optimized link state routing protocol

OLSR (Optimized Link State Routing Protocol) est un protocole de routage destiné aux réseaux mobiles. Le protocole est défini dans la RFC 3626 [1] de l'IETF.

Origine

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.

Fonctionnement général

Le concept principal utilisé dans le protocole est celui des relais multipoint, (MPRs). Les MPRs sont des nœuds choisis qui expédient des messages de diffusion pendant le processus d'inondation. 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 et comme troisième optimisation, un nœud de MPR doit rapporter seulement des liens entre lui-même et ses sélecteurs.

Type de paquets

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 :

• « 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, il doivent donc ne jamais être routé 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 :

• « 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-ensembles 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

Algorithme de sélection des MPR

Définition

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.

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.

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

Un lien symétrique est représenté par un trait rouge double.

D(u) est le nombre de lien symétriques d'un nœud u de N| |}

Algorithme

• 1 étape : On force tous les éléments de N à rerouter les messages.

• 2 étape : On calcule D pour chaque nœud de N

• 3 étape : 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).

• 4 étape : On réitère ces 3 étapes, jusqu'à ce qu’il n'y ait plus de nœud non relié dans N2

Implémentations

• http://hipercom.inria.fr/oolsr/ une implementation de OLSR (pour Linux, Windows, et pour le simulateur NS-2)
• http://www.olsr.org/ code source d'OLSR pour GNU/Linux, Windows, OS X, FreeBSD et NetBSD, avec une documentation riche et des études du protocole.

Voir aussi

• Topologie mesh

Liens

• RFC3626 la spécification d'OLSR
• http://hipercom.inria.fr/olsr/ études, simulations et extensions multicast et Qos pour olsr
• http://olsr.funkfeuer.at études sur les limites de scalabilité d'olsr.org
• http://hipercom.inria.fr/olsr/mpr-flooding.html démo flash
• http://freifunk.net/wiki/FreifunkFirmwareEnglish Firmware Freifunk (Anglais) - 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
• http://pyramid.metrix.net/ Linux Pyramid, une distribution embarquée pour carte x86 avec OLSR, interface WEB, etc.

Ce document provient de « Optimized link state routing protocol ».