OLSR
Un article de Toulouse Sans Fil, un réseau wifi libre sur Toulouse.
Accueil | Technique | Théorie Réseau | OLSR
| Sommaire |
Définition
OLSR (Optimized Link State Routing Protocol) est un protocole proactif de routage pour objet mobile (MANET en anglais). Il permet d'échanger des informations sur la topologie et la régularité du réseau avec les autres noeuds. On y retrouve donc une approche des problèmes liées à l'usage d'un réseau hertzien, notamment la gestion de liens non fiables.
Fonctionnement
OLSR est utilisé dans ce que l'on appelle les réseaux maillés (mesh network en anglais) ad-hoc multi hops (de proche en proche, par sauts de puce). On peut résumer en disant que c'est un programme qui permet aux machines d'un réseau ad-hoc de communiquer entre elles pour qu'elles s'echangent des informations sur leur dispositions. Et ainsi cela permet de créer dynamiquement la topologie du réseau en fonction des machines qui y sont disponibles.
OLSR fait parti des protocoles de routage dits "proactifs". Ce systeme va en temps réel maintenir l'état de toutes les routes qui lui sont disponibles ; ceci selon les regles propres à ce protocole. (Note : à l'opposé les protocoles de routage réactif vont chercher la route à utiliser à chaque demande d'émission.)
Exemple
Avec 3 machines
Grâce au protocole OLSR, B va dire à C qu'elle peut communiquer avec A, et dire à A qu'elle peut communiquer avec C. Donc quand A et C veulent communiquer ensemble, B fera le relais !
Cas général
Maintenant, la seconde approche... ca se corse... En fait, OLSR est un protocole permetant une gestion distribuée du réseau : chaque machine participant au réseau gère sa zone de visibilité hertzienne d'un point de vue très égocentrique. La puissance de calcul nécéssaire pour controler le réseau est donc répartie sur l'ensemble de tous les participants.
Nous allons donc commencer par décrire ce qui se passe au niveau d'une seule machine (le point de vue égocentrique). Il faut d'abord savoir que chaque machine emet une balise à intervalle régulier. Cette balise contient la liste de toutes les machines vues par la machine émetrice. Donc la machine qui nous concerne va faire exactement la meme chose dans un premier temps : écouter et faire la liste des machines recues (que l'on qualifiera de HOP+1), et établir la liste des machines vues par les machines recues (que l'on qualifiera de HOP+2).
Tout message pour une machine HOP+1 ira directement vers la machine cible. Tout message pour une machine a HOP+2 sera acheminé indirectement via une machine l'ayant préalablement déclarée en vue. Toute machine en effet doit pouvoir faire office de relais pour les machines en vue hertzienne, à quelque règles protocolaires près.
Jusqu'ici tout va bien. la situation reste simple. Et toutes les machines se gèrent les unes les autres de la même façon, en employant des règles de sélections, de routage, etc, fonction de la qualité du signal, de la capacité annoncée de chaque machine à faire le relais, et ainsi de suite. On a donc bien un réseau avec une capacité de calcul repartie sur toutes les machines établissant une carte locale des routes à chaque noeud ou relais.
Logique du protocole et calcul distribué
Maintenant, il reste le probleme de sortir de chaque zone locale sans avoir un effet boule de neige ou d'innondation de message tout azimuths dès qu'il faut relayer un message vers une machine au delà de HOP+3. Si un relais devait arroser ses messages a retransmettre à toutes les machines voisines jusqu'à ce qu'un autre relais reconnaisse une de ses voisines, le réseau s'effondrerait dans l'instant.
La logique du protocole OLSR impose à chaque relais de ne choisir que le nombre minimal, nécessaire et suffisant de relais pour atteindre chaque machine visible à HOP+2. Le relayage de messages sera donc "contenu/limité" sur ces machines désignées comme relais. Le phénomèene d'inondation devient maitrisable et reste limité : nos mathématiciens seront à même de caractériser un tel réseau sans faire face à une explosion mathématique des communications. Ce process de sélection de relais préferentiels se fait en temps réel et varie en fonction de la structure meme du réseau, et ce de façon entièrement distribuée, requérant peu de puissance de calcul par machine.
Le mot magique ici est "calcul distribué" qui est une grande nouveauté dans le monde centraliste dans lequel nous vivons et pour lequel sont fait par exemple toutes les normes de communication pour internet. Ce protocole impose par ce biais une autre façon de penser les architectures.
C'est pour cela qu'actuellement des groupes de travail fonctionnent au sein de l'IETF pour mettre au point differents protocoles capable de gérer ce type de réseau. OLSR et la RFC 3626 (http://www.faqs.org/rfcs/rfc3626.html) qui y est associée en est l'exemple typique. On peut noter aussi que different protocoles de gestion fonctionnelle de réseau devrait arriver d'ici quelque temps de façon à pouvoir travailler sur un réseau réellement distribué (ex. localisation de services, serveurs de nom (DNS) distribués, etc).
En conclusion, OLSR permettra à quelqu'un du Nord de Toulouse de parler avec un pote du Sud, en faisant des "sauts" sur les machines qui sont sur le chemin...
Pour aller plus loin
Pour plus de détails, vous pouvez lire tout ou partie de la RFC 3626 (http://www.faqs.org/rfcs/rfc3626.html) qui est très instructive.
Mise en oeuvre
Pour utiliser OLSR, il faut que tous les éléments du réseaux soient capables de parler entre eux comme s'ils étaient à portée d'onde (le plus simple c'est de tous les déclarer dans le même réseau) par exemple : tout le monde dans le réseau 10.0.0.0/255.0.0.0 donc avec une adresse en 10.x.x.x et un masque de sous réseau en 255.0.0.0. (voir notre page Adressage IP)
Il suffit ensuite de lancer olsrd sur toutes les machines.
Choix de l'implémentation
Quelques sources :
- OLSR (http://www.olsr.org) : fonctionne en mode utilisateur (hors noyau), facile à compiler, maintenance très active. supporte Linux, NetBSD, FreeBSD, MacOS X, Windows32 ; différents plugins, une extention tenant compte de la qualité des liens par mesure statistique des messages HELLO reçus et perdus.
- pyOLSR (http://hipercom.inria.fr/pyOLSR/) OLSR en Python pour linux par l'INRIA : maison mere du protocole. Le package est moins facile a compiler-installer.
- RFC3626 (http://hipercom.inria.fr/olsr/rfc3626.txt) qui décrit le fonctionnement d'olsr
- olsr à la Navy (http://downloads.pf.itd.nrl.navy.mil/olsr/) OLSR pour linux et quelques autres OS par un laboratoire de recherche de la marine américaine. Dispose d'un panel de paramètres réglables impressionants.
Heu, désolé! Ce dernier lien n'a pas l'air atteignable. (Phil'sFree le 29 octobre 2005)
Merci. Corrigé. Rémi le 29/10/05