Optimized link state routing protocol

Un article de Wikipédia, l'encyclopédie libre.
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

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.

Sommaire

[modifier] Origine

L’équipe projet HIPERCOM-INRIA a proposé OLSR en 2001. Elle a aussi implémenté la première version d’OLSR. L’équipe Hipercom n’est pas a sa première success-story, elle est aussi a l’origine du Hiperlan qui utilise le concept des MPRs qu’on retrouve dans OLSR.

[modifier] Fonctionnement général

Le concept principal utilisé dans le protocole est celui des relais multipoint, (MPRs). 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.

[modifier] Type de paquets

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

Image:olsr-hello-packet.png

  • « 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 (une exception : Pour choisir les MPR).

[modifier] Message TC (Topologie 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 : Image:Olsr-tc-packet.png

  • « 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 des nœuds à un saut (qui sont annoncés par les paquets Hello)

[modifier] Message MID

[modifier] Algorithme de sélection des MPR

[modifier] Définition

Image:SelectionMPR1.png

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| |}

[modifier] 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

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

[modifier] Liens