B.A.T.M.A.N.

B.A.T.M.A.N. (Better Approach To Mobile Adhoc Networking) est un protocole de routage développé actuellement par la communauté Freifunk. Il tend à remplacer OLSR.

Définition du problème et approche de la solution

Les protocoles de routage classiques sont en général très peu adaptés aux réseaux mobiles Ad-Hoc (MANET), car ceux-ci sont déstructurés, connaissent des extensions/réductions spontanées et sont par nature non fiables. OLSR qui était jusqu'à maintenant la solution la plus prometteuse, devait clairement modifier sa conception initiale, avant de pouvoir évoluer vers le défi de réseaux maillés à l'échelle d'une ville. Certaines de ses briques de base se sont avérées inaptes dans la pratique (comme par exemple l'hystéresis ou le MPR (MultiPoint distribution Relays)), ou limitent le réseau maillé à une taille maximale, par exemple via l'envoi d'une trop grande quantité de données, et la nécessité permanente de calculer la topologie complète du réseau. Malgré des réajustements^[1] les limites d'OLSR se manifestent rapidement, particulièrement à travers la croissance des réseaux Freifunk. Les développeurs de B.A.T.M.A.N. ont décidé d'apprendre des expériences du protocole OLSR et d'autres idées existantes, pour construire leur propre protocole.

L'idée centrale de B.A.T.M.A.N réside dans le fait de partager les informations sur les meilleures connexions entre tous les nœuds B.A.T.M.A.N. dans le réseau complet. Grâce à cela, la nécessité d'informer l'ensemble des nœuds B.A.T.M.A.N. à chaque modification du réseau maillé disparaît. Chacun des nœuds regarde uniquement, d'où viennent les données reçues par leur partenaire de communication, et renvoient les données correspondantes via le même chemin. Sur le chemin vers la destination, les données seront transmises de cette manière de proche en proche. Scientifiquement parlant, cette approche est semblable à l'orientation des fourmis par les phéromones. Par conséquent il en résulte un réseau d'intelligence collective.

Fonctionnement

La tâche principale de B.A.T.M.A.N. est la même que pour les protocoles de routage classiques : il s'agit de découvrir les autres nœuds B.A.T.M.A.N. et de calculer la meilleure route vers ces nœuds. En plus de cela, il informe ses voisins sur les nouveaux nœuds et les routes vers ceux-ci. Dans les réseaux statiques, les administrateurs réseau ou les techniciens décident par quel câble ou quel moyen (par ex: les ondes) un ordinateur est joignable. Dans les réseaux sans-fil cela est défini par la puissance des signaux, mais ceux-ci peuvent subir de fortes variations, ce qui est un premier obstacle pour atteindre les conditions préalables les plus importantes pour les réseaux Freifunk. Ces tâches doivent donc être très largement automatisée :

Chaque nœud informe régulièrement ses voisins à travers un message de broadcast de son existence. Chaque voisin répond par son message d'existence, ce qui permet aux voisins des voisins d'apprendre également l'existence de ce nœud. C'est comme ça que l'information sur chacun des nœuds est distribué dans le réseau complet. Pour trouver le meilleur chemin vers tous les voisins, B.A.T.M.A.N. compte les messages reçu d'une même origine, et mémorise quel voisin lui a transmis. En opposition aux solutions existantes, le protocole n'essaye pas de définir le chemin complet vers un autre nœud, mais utilise les origines des messages collectés pour évaluer le premier saut dans la bonne direction. Ces données seront alors transmises uniquement au meilleur voisin pour cette direction, lequel appliquera le même principe. Ce processus se répète jusqu'à ce que les données arrivent au destinataire.

B.A.T.M.A.N. est conçu de cette manière générique, afin qu'il ne soit pas applicable uniquement dans les réseaux radio, mais qu'il puisse également être utilisé dans les connexions câblées classiques (par ex: Ethernet ou Token Ring)

Histoire de B.A.T.M.A.N.

Il fallait développer un protocole, qui soit aussi simple, petit et rapide que possible. Il a donc semblé logique de réaliser un développement en plusieurs étapes, afin d'implémenter les fonctions complexes les unes après les autres.

B.A.T.M.A.N. Version 1

Pour commencer, seulement l'algorithme de routage fut implémenté, et sa résistance à la pratique fut testée. Pour la réception et l'envoi de messages d'origine (les informations d'existence), le port 1966 du protocole UDP fut choisi.

B.A.T.M.A.N. Version 2

L'algorithme existant fait une hypothèse : dès qu'une information d'existence d'un nœud est reçue par un autre nœud, ce dernier considère qu'il peut lui renvoyer des données. Dans les réseaux radio, il faut cependant garder en tête que la communication peut aussi fonctionner de manière unidirectionnelle. Pour pouvoir prendre en compte ces cas, le protocole a été étendu pour la reconnaissance des voisins bi-directionnels. Avec la version 2, seuls les voisins avec lesquels la communication est bi-directionnelle sont conservés.

B.A.T.M.A.N. Version 3

La grande nouveauté est un support de plusieurs interfaces réseau. Maintenant, B.A.T.M.A.N. peut également travailler depuis des points centraux (clocher, toit haut, etc..) où plusieurs antennes ou câbles sont connectés. Un cas particulier pour la découverte de routes à travers le réseau a également été pris en compte pour éviter les boucles de routage. Chaque nœud peut désormais annoncer au réseau, qu'il offre un accès à Internet. Les utilisateurs sont alors capables de savoir qu'une connexion Internet est disponible à proximité et quelle bande passante est disponible. Ils peuvent alors choisir une passerelle spécifique ou alors laisser cette décision à B.A.T.M.A.N. (se basant sur des critères comme par exemple la connexion Internet la plus rapide).

De plus, il est désormais possible d'annoncer un périphérique dans un réseau B.A.T.M.A.N., même lorsque celui-ci n'est pas configuré avec B.A.T.M.A.N. C'est habituellement par ce biais que les réseaux domestiques peuvent se connecter au réseau maillé. Par exemple, l'installation sur le toit d'une antenne permet via B.A.T.M.A.N. de communiquer avec le reste du réseau maillé, le reste de la maison ayant accès au réseau maillé via cette installation.

Linux

Le protocole B.A.T.M.A.N. est supporté en natif dans le noyau Linux depuis la version 2.6.38^[2].

Voir aussi

• OLSR
• MANET
• Babel
• Réseaux sans fil communautaires

Notes et références

Liens

• Site officiel du projet B.A.T.M.A.N. Implementation pour Linux, FreeBSD et Mac OS
• Page sur B.A.T.M.A.N dans la documentation officielle de la communauté ubuntu française
• Comparaison avec d'autres protocoles de routage Ad-Hoc
  • Ad hoc routing protocol list(en)
  • Performance Comparison of Ad-Hoc-Networks (Présentation PDF) – protégé par mot de passe (10/2007), mais disponible sur l'Internet-Archive [1]
  • AODV
• Simulation de protocoles de routage (Applet Java, de)
• Applications pratiques dans des réseaux radio :
  • Berlin: www.olsrexperiment.de (de)

• Portail de l’Internet