Die Artikel im Archiv-Namespace sind veraltet und werden nur noch aus historischen Gründen aufbewahrt.

Archiv:B.A.T.M.A.N.

Aus wiki.freifunk.net
Zur Navigation springenZur Suche springen

Dieser Artikel ist veraltet und deckt z.B. die neueste Variante batman-adv nicht ab. Eine aktuelle Kurzzusammenfassung gibt es im Glossar.

B.A.T.M.A.N. (BETTER APPROACH TO MOBILE ADHOC NETWORKING) ist ein Routingprotokoll, welches von der Freifunk-Szene entwickelt wird. Problemstellung:

Klassische Routingprotokolle eignen sich nur bedingt für mobile Ad-Hoc Netze, da diese unstrukturiert, spontan wachsend/schrumpfend und inhärent unzuverlässig sind. Zudem kann die Verbindungsqualität zwischen einzelnen Knoten über den Zeitverlauf deutlich schwanken, wodurch ein einmal gefundener optimaler Weg bereits nach kurzer Zeit nicht mehr zwangsläufig weiterhin der optimale Weg sein muss. Die Herausforderung besteht also darin, die sich ständig ändernde Netztopologie inklusive der jeweiligen Verbindungsqualität aktuell abbilden zu können, um den optimalen Weg für die zu versendenden Pakete finden zu können.

Lösungsansatz:

Bei B.A.T.M.A.N. wird an das Problem AdHoc-Routing von einer neuen Seite herangegangen: Alle bisherigen bekannten Routingalgorithmen für mobile Ad-Hoc Netze versuchen Routen zu berechnen. B.A.T.M.A.N berechnet hingegen keine Routen - es spürt bereits vorhandene Routen auf und benutzt sie bei Bedarf. Dabei interessiert sich dieses Protokoll nicht für den Verlauf einer Route, sondern prüft lediglich über welchen Nachbarn ein bestimmter Netzwerkknoten am besten erreichbar ist. Wissenschaftlich gesehen ist diese Herangehensweise ähnlich zu der Wegfindung von Ameisen mittels Pheromonen. Somit entsteht ein Netzwerk aus kollektiver Intelligenz.


Funktionsweise

Ein Knoten in einem B.A.T.M.A.N-MANET interessiert sich nur dafür, von der Existenz aller anderer Knoten zu wissen die er direkt oder über eine Multi-Hop-Verbindung erreichen kann. Um mit einem indirekten Nachbarn zu kommunizieren muss B.A.T.M.A.N einen Nachbarn in direkter Funkreichweite bestimmen dem ein Datenpaket überreicht werden kann, damit dieser es auf dem günstigsten Weg zu dem Nachbarn in der Ferne routet. Am besten wird der Vorteil dieser Herangehensweise vielleicht deutlich wenn wir ältere Ansätze für Routing in MANETs zum Vergleich heranziehen - das sogenannte Source Routing und das Link State Routing.

Wer wissen möchte wie B.A.T.M.A.N zu einem bestimmten Knoten routet, kann das mit

  • ping -R <Zieladresse>

herausfinden. Das geht allerdings leider nicht mit dem in Busybox (Das 'Schweizer Taschenmesser': Multicall Binary für Embedded Linux) integrierten Ping-Kommando weil diese Option nicht zur Verfügung steht. Hier muss dann

  • traceroute -n <Zieladresse>

herhalten.

Vergleich mit dem Source Routing

Beim Source Routing 'denkt' ein Knoten Y im Meshnetzwerk, dass der beste Weg Daten an Knoten D zu schicken über die Knoten Q, S, H, W, F, C führt (in dieser Reihenfolge). Y gibt also an Q den Auftrag die Daten an S zu schicken. S erhält von Y den Auftrag, die Daten an H zu schicken und so weiter. Y gibt also den Weg zu D vor.

Dynamic Source Routing

Einer der älteren Entwürfe für MANET Routing ist Dynamic Source Routing. DSR enthält einen Algorithmus der Sourcerouten ermitteln und bei Bedarf erneuern soll, wenn diese nicht mehr existieren. Der Haken bei der Sache ist, dass MANETs hochgradig dynamischen Veränderungen unterworfen sind. In einem MANET gehen nicht nur Datenpakete der Nutzlast verloren, sondern auch Datenpakete die über die Struktur des Netzes Auskunft geben. Je weiter das Ziel von Y entfernt ist desto unwahrscheinlicher ist es, dass die Informationen die Y über die entfernte Netztopologie hat, stimmig sind. So kann W keinen Link mehr zu F und H haben - die Kette die sich Y ausgedacht hat ist schon lange zusammengebrochen, und Y erhält die Meldung "Ziel nicht erreichbar" und fängt immer wieder an einen neuen Pfad zu suchen.

Vergleich mit dem Link-State-Routing

Auch das Link-State-Routing (LSR) versucht Routen zu berechnen die für das gesamte Netz gültig sind. Glücklicherweise bedeutet das aber kein Source-Routing. Stattdessen berechnet ein Knoten mit einem Link-State-Routing-Algorithmus welchen Pfad seine Pakete nehmen müssten und gibt sie vertrauensvoll dem nächsten Nachbarn, der auf der gedachten Route an nächster Stelle steht. Dieser Nachbarknoten hat selbständig einen Pfad berechnet und gibt das Paket wiederum dem nächsten Nachbarn auf dem besten errechneten Weg zum Ziel. Jeder Netzwerkknoten trifft selbständig die Entscheidung wie das Paket weitergereicht wird. Das ist ganz gut so, denn je näher die Knoten dem Ziel sind, desto besser wissen sie über den Zustand der Route Bescheid. Letztendlich kann aber ein Knoten nur die Entscheidung des nächsten Sprunges treffen. Um die Entscheidung des nächsten Sprungs zum Ziel zu treffen betreibt LSR jedoch einen enormen Aufwand - es erfasst die Topologieinformationen des gesamten Netzes. Zu allen Knoten im Netz erfasst LSR die Informationen über die vorhandenen Nachbarn und berechnet sämtliche Routen. Auch hier ist aber die Sicht notwendigerweise unscharf. Die Unmöglichkeit die Informationen über die gesamte Netztopologie synchron zu halten kann zu Routing Loops führen, gerade weil LSR sich ein so umfassendes Bild des Netzes zu machen versucht. Es kann vorkommen das benachbarte Knoten sich über den Pfad derartig uneins sind, dass zwei oder mehrere Knoten sich ein Paket gegenseitig hin- und herschicken bis das Paket ungültig wird. Das geschieht so lange bis sich ihre Routingtabellen schliesslich synchronisieren. Macht man einen Ping zum Ziel erhält man in der Zwischenzeit die Rückmeldung, dass die TTL abgelaufen ist.

OLSR als Beispiel für LSR

Ein in Mesh-Netzwerken bekannter Vertreter von LSR ist OLSR von olsr.org. Inzwischen existieren für OLSR spezielle Erweiterungen. Mit der ETX-Erweiterung wird dem Umstand Rechnung getragen, dass Links asymmetrisch sein können. Mit dem Fisheye-Algorithmus ist OLSR auch für größere Netzwerke brauchbar geworden, da Routen zu weiter entfernten Knoten weniger häufig neu berechnet werden.

Regeln bei B.A.T.M.A.N.

B.A.T.M.A.N ist eine Gruppe von Regeln an die sich ein Router halten muss. Dabei wurden mehrere Varianten erstellt:


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

B.A.T.M.A.N verwendet Port 1966 UDP. Dieser Port muss für eingehende und ausgehende Nachrichten offen sein, also darf eine Firewall B.A.T.M.A.N nicht blockieren.

Broadcasts

B.A.T.M.A.N findet seine Nachbarn und entfernte Netzwerkknoten im Mesh (im folgenden Nodes genannt) durch Broadcasts die weitergereicht werden. Ein Broadcast beinhaltet die Adresse des Erzeugers (Orginator), einen TTL-Wert (Time-to-live) und eine Sequenz-Nummer. Anhand der TTL kann man erkennen, wie oft ein Paket weitergereicht wurde, da diese von jedem weiterreichenden Knoten um Eins verringert wird. Erreicht der TTL-Wert 0, wird das Paket verworfen, um lange Irrwege zu vermeiden. Besonders wichtig für B.A.T.M.A.N ist die Sequenznummer. Das sind die laufenden Nummern der Orginator-Nachrichten die ein Orginator aussendet. So kann ein (entfernter) Nachbar erkennen, ob zwischenzeitlich Pakete verloren gegangen sind.

Broadcasts werden in einem festgelegten Intervall von jedem Node als Orginator ausgesendet und von allen anderen Nodes als Relais weitergereicht (wenn bestimmte Bedingungen erfüllt sind), so dass sie immer weiter durch das Mesh reisen oder unterwegs irgendwann verloren gehen. Geht ein Broadcast verloren wird nicht nach dem Verbleib oder einer Neuübetragung gefragt - anders als bei TCP-Daten, wo bis zu 7 mal die Übertragung wiederholt wird, wenn eine Bestätigung des Empfängers ausbleibt.

Nehmen wir an wir haben eine Kette von Mesh-Knoten: 

Node A <--> Node B <--> Node C <--> Node D

Nehmen wir weiterhin an, jeder Node kann nur seine unmittelbaren Nachbarn sehen. Nun sendet Node A eine Orginator-Nachricht. Node B sieht diese und wiederholt sie.

Dadurch sieht Node C: Nachricht von Node A, weitergeleitet von Node B, Sequenz Nummer 0, TTL 49

Node C wiederholt die Nachricht. Also sieht Node D: Nachricht von Node A, weitergeleitet von Node C, Sequenz Nummer 0, TTL 48

Nun weiss Node D:

Es existiert Node A, den erreiche Ich über zwei Zwischenstationen. Um Node A zu erreichen müssen die Pakete an Node C gesendet werden. Mehr muss Node D gar nicht wissen.

Das erste Beispiel ist natürlich sehr einfach gehalten. Was geschieht nun wenn das Netz so aussieht: 

       * ---- Node B ---- Node C ---- *
       |                              |
Node A + ------------ Node D -------- + Node F 
       |                              |
       * ------------ Node E -------- *

Die Grafik soll verdeutlichen, dass Node A die Nodes B, D, E als Nachbarn hat. Ebenso hat Node F die Nodes C, D, E als Nachbarn. Was macht BATMAN nun?

Node A schickt eine Orginator-Meldung mit Sequenznummer 0. B, C, D und E wiederholen sie. Betrachten wir den Werdegang der Orginator Nachrichten von Node A.

Node F sieht die Orginator-Nachricht Sequenznummer 0 von Node A über Node D zuerst und merkt sich, dass er A über D gesehen hat. Node F ignoriert die Orginator-Nachricht mit Sequenznummer 0 von Node A, die von Node B wiederholt wird und über Node C eintrifft, da sie später ankommt. Die Nachricht von Node E geht unterwegs verloren oder kommt ebenfalls zu spät.

Auf dem besten Pfad zwischen Node A und F kommen die Pakete häufiger und meist auch schneller an. Node F merkt sich nun, von wem er die Orginatorpakete von Node A am häufigsten erhält. Schnelligkeit ist hier entscheidend weil Node F sich immer nur für das am schnellsten ankommende Paket mit übereinstimmender Orginatoradresse und Sequenznummer interessiert. Will Node F nun mit Node A kommunizieren benutzt er den Nachbarn mit der besten Statistik als Router.

Herrscht Gleichstand an empfangenen Paketen von zwei oder mehreren Nachbarn entscheidet die größte TTL (geringster Hopcount). Herrscht Gleichstand auch bei der TTL entscheidet wer das letzte eingegangene Orginator-Paket zum Zielknoten gebroadcastet hat.

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

Das einfachste B.A.T.M.A.N-Verfahren hat einen Haken: Es berücksichtigt nicht, dass Verbindungen unsymmetrisch sein können. Die Annahme ist, dass auf dem Pfad auf dem die Pakete von Node A den Node F erreichen auch die beste Übertragung in die Gegenrichtung möglich ist. Das ist im Fall von unsymmetrischen Links ein Trugschluss. Unsymmetrische Links treten auf wenn ein Router zwar einen anderen hört, aber umgekehrt nicht. Es kann sein, dass eine perfekte Übertragung möglich ist - aber nur in eine Richtung. Das einfache B.A.T.M.A.N-Verfahren würde hier komplett scheitern. Es muss also geprüft werden ob Links symmetrisch sind und nur Informationen die von diesen kommen dürfen ausgewertet und verwendet werden.

Dafür gibt es ein einfaches Set von Regeln:

Symmetrieprüfung

Nachbarn, die unsere eigenen Orginatornachrichten mit TTLMAX - 1 wiederholen haben Uns gesehen und wir haben sie gesehen. Nur Nachbarn, die unsere eigenen Orginatorpakete (aus der Sicht des Nodes) mit TTLMAX-1 wiederholen, werden berücksichtigt. Bekommen wir in einem bestimmten Zeitraum unsere Orginatornachrichten nicht von unseren Nachbarn als Wiederholung zu sehen ist der Link unsymmetrisch.

Broadcasts

Broadcasts von Nodes zu denen wir keinen symmetrischen Link haben, werden ignoriert und nicht weitergeleitet. Wir ignorieren sie so lange bis die Symmetrieprüfung wieder erfolgreich ist.

Ausnahmen

Broadcasts von Orginatoren aus der direkten Nachbarschaft werden immer wiederholt (Broadcasts mit TTLMAX), auch dann wenn sie (noch) nicht symmetrische Nachbarn sind. In diesem Fall ist ein Unsymmetrieflag in dem wiederholten Broadcast enthalten - damit der Orginator weiss, dass wir Ihn gesehen haben. Andere Knoten wissen, dass sie den Broadcast den wir wiederholen ignorieren können. Die wiederholte Orginatornachricht die mit dem Unsymmetrieflag gesendet wird geht nur den Orginator was an, alle anderen Knoten ignorieren sie.

Diese Ausnahme ist notwendig um ein Henne-und-Ei Problem zu verhindern. Ansonsten würden wir die Orginatornachrichten unserer direkten Nachbarn stets ignorieren - weil sie unsymmetrisch sind und bleiben. Und sie würden uns ignorieren... Andere Nodes dürfen indirekt empfangene Orginatormeldungen mit TTLMAX -1 nicht wiederholen wenn der Unsymmetrieflag gesetzt wird - sonst fällt B.A.T.M.A.N doch noch auf Broadcasts rein, die von unsymmetrischen Links stammen.


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

B.A.T.M.A.N-III-0.1 hat trotz seiner niedrigen Versionsnummer bereits den benötigten Funktionsumfang und es ist davon auszugehen, dass die gesteckten Ziele für eine generische Implementierung des B.A.T.M.A.N-III Algorithmus bereits weitgehend erreicht sind. Die gewünschten Features sind bereits implementiert und wurden getestet. Die letzte Hürde auf dem Weg zu Programmversion 0.1 ist der reibungslose Support für beliebig viele Interfaces, die von einem B.A.T.M.A.N-III-Daemon verwaltet werden. Weitere Bugfixes für den Multiple-Interface-Support sind inzwischen in den Code eingeflossen.

Siehe Auch

Weblinks

Abgerufen von „https://wiki.freifunk.net/index.php?title=Archiv:B.A.T.M.A.N.&oldid=28673“