Babel est un protocole de routage de la famille des protocoles à vecteurs de distance. Il est adapté pour les réseaux IPv4 et aussi IPv6. Autres points forts de Babel, ses propriétés de convergence rapide et sa capacité à éviter les boucles. Il est basé sur des idées des protocoles DSDV, AODV et Cisco EIGRP, mais il a été conçu à la fois pour les réseaux filaires et les réseaux wifi maillés.

C'est un protocole de routage défini dans la RFC 6126.

Réseau maillé

Un réseau mesh, aussi appelé réseau maillé, est un réseau qui n'a pas de structure. Tous les hôtes sont connectés entre eux de proche en proche sans hiérarchie centrale. De plus, ce réseau peut être composé de nœuds filaires ou sans fils. C'est un réseau instable par nature car un nœud peut être déconnecté du réseau. A l'opposé d'un réseau de routeurs classiques par exemple où un routeur devient indisponible après une panne. Enfin, il faut savoir que dans un réseau maillé, le chemin le plus court n'est pas forcément le mieux à utiliser. Par exemple, un saut avec un taux de perte de paquet conséquent n'est pas à favoriser. Si un hôte est hors service, ses voisins passeront par une autre route.

Il existe plusieurs réseaux maillés qui sont déployés dans différents pays :

• Mesh potato qui est déployé à Johannesburg (Afrique du sud)
•  Freifunk (réseau de taille modeste)

Les protocoles de routages "classiques" dans les réseaux maillés

Les protocoles de routage classiques ne marchent pas dans les réseaux maillés car :

• ce sont des réseaux dont la topologie change tout le temps
• on peut rentrer par la même interface sur laquelle on est sortie.

Deux approches différentes ont été choisies. Soit créer un nouveau protocole en partant de zéro (OLSR et BATMAN ont fait ce choix) ou on reprend les techniques classiques et on corrige ce qui ne va pas en adaptant les protocoles aux conditions hostiles des réseaux maillés (choix fait par Babel).

Caractéristiques du protocole Babel

Bellman Ford

L'algorithme Bellman-Ford permet de trouver les plus courts chemins entre deux nœuds dans un réseau. Il converge en un temps qui est proportionnel au diamètre du réseau. Ce temps de convergence est relativement rapide lors de l'ajout d'un nouveau lien mais il est très lent lorsqu'un lien est cassé.

Ainsi, périodiquement chaque routeur annonce à tous ses voisins qui il sait joindre sur le réseau avec le nombre de sauts pour l'atteindre. Les routeurs exécutent un algorithme de routage dont le but est de déterminer à qui envoyer les paquets.

RIP utilise cet algorithme. Cependant, l'un des principaux inconvénients du protocole RIP est sa capacité à former des boucles lorsque le réseau change de topologie. Pour éviter cela, le nombre de sauts est limité à 15. Au-delà, les paquets sont supprimés.

Exemple:
Si l'on reprend le schéma précédent mais que le lien entre les nœuds S et A est coupé. Une boucle se forme.

On peut donc dire que RIP n'évite pas les boucles mais il les détecte.

Babel

Babel est un protocole de routage conçu pour les réseaux maillés. Il utilise l'algorithme Bellman-Ford (vu précédemment) mais apporte quelques améliorations.

En particulier, il améliore le temps de convergence en envoyant des messages déclenchés lors d'un changement majeur de topologie, en plus des messages périodiques.

Autre amélioration, un nœud Babel garde en mémoire des routes alternatives qui sont envoyées par d'autres voisins, en plus de celle utilisée comme route principale pour joindre un nœud. Ainsi, en cas de défaillance de cette route, le nœud peut utiliser l'une de ces routes pour continuer d'émettre.

De plus, il se sert d'une variante de l'algèbre ETX pour décider du meilleur lien. En effet, il va choisir les liens en prenant en compte la qualité de la propagation radio entre 2 nœuds. Suite à une instabilité, il se comporte de façon raisonnable. C'est à dire qu'il est conçu pour réagir rapidement aux instabilités. En particulier, il évite les boucles (contrairement à RIP qui fait de la détection de boucles). S'il soupçonne qu'il y a une possibilité de boucle, alors il préfère ne pas prendre la route.

C'est un protocole ouvert : RFC 6126.

Enfin, Babel a été conçu pour supporter des milliers de routeurs, mais dans la pratique il n'a jamais été testé à grande échelle.

Protocoles réactifs et proactifs

Autre caractéristique de Babel, c'est un protocole dit proactif. C'est à dire qu'il construit les tables de routage avant que la demande en soit effectuée. L'avantage est que les routes sont immédiatement disponibles. L'inconvénient est que le trafic de contrôle et de mise à jour peut être important et partiellement inutile.

OLSR et DSDV sont aussi des protocoles proactifs pour réseaux maillés.

A l'inverse des protocoles dit réactifs comme DSR (Dynamic Source Routing) ou AODV (Ad hoc On-Demand Vector Routing). Une route est établie uniquement sur demande. L'avantage est qu'il ne charge pas le trafic. L'inconvénient est qu'il met plus de temps pour "ouvrir" une route.

Avantages de Babel

• Il réutilise 50 ans de recherche dans les protocoles de routage filaire.
• C'est un protocole familier des gens du routage sauf qu'il est adapté aux réseaux maillés. Il a donc une plus grande chance de marcher dans les réseaux hybrides (filaires et sans fil).
• Il permet de garder la plus grande passante entre plusieurs nœuds, et est très rapide dans la "reconstruction" de routes.
  

Limites connues

Babel envoie périodiquement des messages de mise à jour sur la topologie du réseau, ce qui génère plus de trafic qu'avec d'autres protocoles, par exemple, OSPF (qui n'envoie de mise à jour que lors de changements).

Messages et tables de routage utilisés dans Babel

Messages utilisés dans Babel

Babel défini plusieurs types de messages dans sa RFC. Parmi les plus importants, on peut citer les messages Hello, IHU et Update :

Message Hello

Un nœud Babel envoie périodiquement en broadcast des messages HELLO à ses voisins sur chacune de ses interfaces réseaux. Le rôle de ce message est de

De plus, lorsqu'un nouveau voisin est découvert ou que la qualité d'un lien a brusquement changée,  le nœud Babel émet un message HELLO sans attendre la prochaine période d’envoi. Ainsi, le calcul du coût sur un lien est accéléré. Autre chose importante à savoir pour ces messages. L'intervalle d'émission peut être réduit à n'importe quel moment.

Message IHU (« I Heard yoU »)

Ce message est envoyé périodiquement par un nœud Babel aux voisins dont il a reçu un message HELLO depuis peut de temps. Grâce à ce message un nœud peut calculer le coût de la liaison avec son voisin.

De même qu'avec un message HELLO, un message IHU peut être envoyé sans attendre le prochain envoi programmé. Deux données transportées par le message IHU sont importantes :

1. le "coût" en réception qui sera utilisé par le voisin pour calculer la qualité de la liaison
   
2. l'intervalle de temps entre deux messages IHU

Ainsi lorsqu'un nœud reçoit un message IHU, il met à jour le coût de transmission sur le lien.

Message Update

Un message "Update" est envoyé à un nœud pour informer ses voisins d'une mise à jour de topologie.

Tables

Comme tous les protocoles de routage, un nœud Babel tient à jour plusieurs tables :

1. une table des interfaces
2. une table des voisins
3. une table des sources
4. une table de routage

Remarque : les éléments dans une table sont indexés afin d'en faciliter la recherche quand on en a besoin.

Installation et utilisation de Babel

Installation

Babel peut être installé sur différents environnements :

• Sous Debian avec la commande :
  

  $ apt-get install babeld

  Babel est accompagné du logiciel AHCP permettant d’auto-configurer le réseau ad-hoc (préfixe IPv6, adresse des serveurs DNS et NTP...).

• Sous OpenWRT (firmware libre).

• Sous Quagga (logiciel libre qui fourni différentes implémentations de protocoles de routage pour les plates-formes Unix).
  

Utilisation

Voici un exemple permettant d'utiliser Babel sur votre interface wifi avec les paramètres par défaut (port : 6697, hello interval : 4s,...) :

$ babeld wlan0

Vous pouvez aussi vous aider de la page de manuel qui décrit les différentes options de configuration du protocole ("man babeld" ou ici).

Enfin, si vous voulez vous connecter au réseau maillé de l'université de Jussieu, vous aurez besoin de ce script : wifi-autoconf.sh.

Bilan

Babel est encore un protocole de recherche mais il possède de nombreux atouts : rapidité de convergence, évite les boucles... De plus, il a été montré dans des publications indépendantes comme étant efficace, même sur des routeurs peu puissants. Enfin, il est entièrement documenté dans la RFC 6126.

Quelques références et liens utiles

Pour en savoir plus sur Babel, voici quelques liens utiles :

• la RFC de Babel :  http://www.rfc-editor.org/rfc/rfc6126.txt
• la page web du projet Babel :  http://www.pps.jussieu.fr/~jch/software/babel/
• une vidéo sur la commutation, routage et réseaux maillés : http://lacantine.ubicast.eu/videos/pses-commutation-routage-et-reseau-maille/
• page "man" de Babel :  http://www.pps.jussieu.fr/~jch/software/babel/babeld.html
• paquet Debian :  http://packages.debian.org/fr/squeeze/babeld
• réseau maillé déployé à l'université de Jussieu :  http://wifi.pps.jussieu.fr/