Optimized link state routing protocol
| Image manquante Symbole-ordinateur.png | Cet article est une ébauche concernant l'informatique, vous pouvez partager vos connaissances en le modifiant. |
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 |
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.
Datagramme :
Image manquante
Olsr-hello-packet.png
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 manquante
Olsr-tc-packet.png
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 manquante
SelectionMPR1.png
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étrique.
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