Optimized link state routing protocol

Un article de Freepedia.

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 1 Origine 2 Fonctionnement général 3 Type de paquets 3.1 Message Hello 3.2 Message TC(Toplogie Control) 3.3 Message MID 4 Algorithme de sélection des MPR 4.1 Définition 4.2 Algorithme

Origine

Fonctionnement général

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 à 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 choix fait par l'expéditeur de son MPR (Multi-Point Relays).

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

Message TC(Toplogie 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'on choisit comme MPR. Il sert à établir les tables de routages. Aussi pour qu'il soit diffusé sur tous le réseau, la valeur du TTL dans l'header du message (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 connaître l'information la plus récente.
• « Advertised Neighbor Main Address » : Adresse IP des nœuds à un saut (qui sont annoncés par les paquets Hello)

Message MID

Algorithme de sélection des MPR

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

L'ensemble N2 est constitué des voisins à 2 sauts du même nœud que précédemment. Tous les voisins à un saut du noeud rouge en utilisant les messages hello, vont déclarrer 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étéctés grâce aux messages Hello, mais ne sont pas utilisé 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étrique 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 tout 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 suppriment les nœuds de N2 reliés par ce MPR (on les considère comme relié).

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