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

B.A.T.M.A.N. (Better Approach To Mobile Adhoc Networking) ist ein Routingprotokoll, welches aktuell von der Freifunk-Community entwickelt wird. Es soll OLSR ablösen.

Problemstellung und Lösungsansatz

Klassische Routingprotokolle eignen sich nur bedingt für mobile Ad-hoc-Netze, da diese unstrukturiert, spontan wachsend bzw. schrumpfend und inhärent unzuverlässig sind. Der bisher vielversprechendste Ansatz, OLSR, musste deutlich von seinem ursprünglichen Design abgeändert werden, bevor das Protokoll den Herausforderungen stadtweiter Meshnetze gewachsen war. Einige seiner Kernkomponenten erwiesen sich als nicht praxistauglich, wie z. B. Hysterese oder MPR, oder sie limitieren das Meshnetz auf eine Maximalgröße, z. B. durch das Versenden zu großer Datenmengen und das ständige Durchrechnen der gesamten Netztopologie. Trotz dieser Anpassungen^[1] offenbarten sich schnell die Grenzen von OLSR, bedingt durch das fortwährende Wachstum der Freifunknetze. Die Entwickler entschieden sich, aus den bisherigen Ideen und den Erfahrungen mit OLSR zu lernen und diese Erkenntnisse in einem eigenen Protokoll umzusetzen.

Die zentrale Idee bei B.A.T.M.A.N. besteht darin, das Wissen der besten Verbindungen zwischen allen B.A.T.M.A.N.-Knoten auf das gesamte Netz zu verteilen. Dadurch entfällt die Notwendigkeit alle B.A.T.M.A.N.-Knoten über jede Änderung im Meshnetz zu informieren. Die einzelnen Knoten merken sich lediglich, aus welcher Richtung sie von ihren Kommunikationspartnern Daten erhalten haben und schicken ihre Daten entsprechend zurück. Auf dem Weg zum Ziel werden die Daten auf diese Weise von Nachbar zu Nachbar weitergegeben. Wissenschaftlich gesehen, ist diese Herangehensweise ähnlich der Wegefindung von Ameisen mittels Pheromonen. Somit entsteht ein Netzwerk aus kollektiver Intelligenz.

Funktionsweise

B.A.T.M.A.N.s Hauptaufgabe ist die eines klassischen Routingprotokolls: Es spürt andere B.A.T.M.A.N.-Knoten auf und ermittelt den besten Weg (Route) zu diesem Knoten. Außerdem informiert es seine Nachbarn über diesen neuen Knoten und den Weg dorthin. In statischen Netzen legen Netzwerkadministratoren oder Techniker fest, welcher Computer über welches Kabel bzw. welchen Weg (z. B. Funk) erreichbar ist. Da die Signalstärken bei Funknetzen aber starken Schwankungen unterliegen und niedrige Einstiegshürden eine der wichtigsten Voraussetzungen für Freifunknetze sind, muss diese Aufgabe weitestgehend automatisiert werden:

Jeder Knoten informiert regelmäßig alle seine Nachbarn, mittels eines sogenannten Broadcasts (allgemeine Nachricht an alle), über seine Existenz. Diese wiederum wiederholen seine Existenznachricht, wodurch die Nachbarn der Nachbarn auch von diesem Knoten erfahren. So wird die Information über jeden Knoten im ganzen Netzwerk verteilt. Um den besten Weg zu allen anderen Nachbarn zu finden, zählt B.A.T.M.A.N. jede erhaltene Orginatornachricht und merkt sich dabei, welcher Nachbar ihm diese zugestellt hat. Im Gegensatz zu bisherigen Ansätzen, versucht das Protokoll nicht den gesamten Weg zu jedem anderen Knoten zu ermitteln, sondern nutzt die gesammelten Orginatornachrichten, um den ersten Schritt in die richtige Richtung zu bestimmen. Die Daten werden nun dem besten Nachbarn für diese Richtung übergeben, welcher dann das gleiche Prinzip anwendet. Dieser Vorgang wiederholt sich, bis die Daten beim Empfänger angekommen sind.

B.A.T.M.A.N. ist so generisch konzipiert, dass es nicht nur im Bereich der Funknetze Anwendung findet, sondern auch über herkömmliche Kabelverbindungen (z. B. Ethernet, Token Ring) eingesetzt werden kann.

Geschichte

Es sollte ein Protokoll entwickelt werden, welches so einfach, klein und schnell wie möglich ist. Es schien daher logisch, dass die Entwicklung in mehreren Stufen ablaufen sollte, wobei komplexere Funktionen nur schrittweise Einzug hielten:

Version 1

Zunächst wurde nur der Routingalgorithmus implementiert und auf Praxistauglichkeit geprüft. Für den Empfang und Versand der Originatornachrichten (Existenzinformationen) wurde der UDP Port 1966 gewählt.

Version 2

Der bisherige Algorithmus macht eine implizite Annahme: Sobald ein Knoten Existenzdaten von einem anderen Knoten empfängt, nimmt er an, dass er auch Daten zurückschicken kann. In Funknetzen kann aber häufig beobachtet werden, dass die Kommunikation lediglich in eine Richtung funktioniert. Um diesem Umstand Rechnung zu tragen, wurde das Protokoll um einen Mechanismus erweitert, welcher das Erkennen von bidirektionalen Nachbarn (die Kommunikation funktioniert in beide Richtungen) ermöglicht. Mit Version 2 werden nur noch Nachbarn berücksichtigt, mit denen eine bidirektionale Kommunikation erfolgreich ist.

Version 3

Größte Neuerung ist die Unterstützung von mehreren Netzwerkschnittstellen. Nun kann B.A.T.M.A.N. auf einem zentralen Punkt (Kirchturm, hohes Dach, etc.), welcher mit mehreren Antennen oder Kabeln verbunden ist, seine Arbeit verrichten. Auch wurden einige Sonderfälle beim Finden der Wege durch das Netz berücksichtigt, so dass keine Kreisrouten (dabei erreichen die Daten nie ihr Ziel) entstehen können. Jeder Knoten kann nun im Netzwerk bekanntmachen, dass er einen Internetzugang bereitstellt. Andere Nutzer sind damit in der Lage, zu erkennen, dass es einen Internetzugang in ihrer Nähe gibt und welche Bandbreite zur Verfügung steht. Sie können sich für ein spezielles Gateway entscheiden oder B.A.T.M.A.N. (anhand von Kriterien wie z. B. schneller Internetzugang) die Entscheidung überlassen. Außerdem besteht die Möglichkeit, Geräte in einem B.A.T.M.A.N.-Netz anzukündigen, selbst wenn diese kein B.A.T.M.A.N. einsetzen. Üblicherweise werden auf diese Weise Hausnetze in Meshnetzwerke eingebunden. Es gibt eine Antenneninstallation auf dem Dach, welche via B.A.T.M.A.N. mit dem Rest des Netzes kommuniziert, der Rest des Hauses wird lediglich angekündigt und ist dadurch erreichbar.

Siehe auch

• Babel (Protokoll)

Weblinks

• Chaosradio Express 045 mit Tim Pritlove und Elektra Wagenrad
• offizielle Homepage des B.A.T.M.A.N. Projekts Implementation für Linux, FreeBSD und Mac OS
• Vergleiche mit anderen AD HOC Routingprotokollen
  • Ad hoc routing protocol list
  • Performance Comparison of Ad-Hoc-Networks (Präsentation als PDF) – passwortgeschützt (10/2007), aber im Internet-Archiv verfügbar
  • AODV
• Online Simulation einiger Routing Protokolle (Java-Applet)
• Praktische Anwendung in freien Funknetzen:
  • Berlin: www.olsrexperiment.de
  • Berlin-Nordost: www.freifunk-bno.de
  • Bern: www.openwireless.ch
  • Halle (Saale): freifunk-halle.de
• olsr.freifunk.net Deutsche Plattform für OLSR-Funknetzwerke
• WLAN-Mesh im Eigenbau: Pimp your Wi-Fi
• Performance vermaschter Netze: WLAN-Mesh im Heimnetz
• Test Sonos Mesh-Performance im Tom's Networking Guide Deutschland

Quellen

1. ↑ http://www.open-mesh.org/wiki/open-mesh/The-olsr-story