Optimized link state routing protocol

OLSR (en anglais « Optimized Link State Routing Protocol ») est un protocole de routage destiné aux réseaux maillés, sans fil ou mobiles. Le protocole est défini dans la RFC 3626^[1] de l'IETF.

Une nouvelle version est en cours de développement^[2].

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

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

Algorithme de sélection des 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.

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.

Algorithme

Les différents étapes de l'algorithme suit :

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.

Implémentations logicielles

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

Notes et références

Voir aussi

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.

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