Batman-Test

BATMAN fliegt durchs Weimarnetz

• BATMAN ist ein neues, revolutionaeres ("ja, das sagen 'se alle...") Routingprotokoll, welches OLSR vielleicht mal abloesen wird
• Am 10 Juli 2006 um 12 Uhr wurde BATMAN auf allen - ca. 100 - Routern im Weimarnetz aktiviert.
• Deaktiviert: Aufgrund von uebermaessigem CPU-Verbrauch, wurde BATMAN in den fruehen Morgenstunden wieder deaktiviert. Siehe Batman-Test-Analyse
• Es laeuft auf einem Aliasinterface: 103.63.knotennummer.1 / wifi
• Ihr koennt in der Routentabelle mit ip route|grep 103.63 sehen, wieviel Routen schon existieren
• Version: Batman2-v0.06 - danke an Elektra dafuer! fries43 10:51, 10. Jul 2006 (CEST)
• Aus der Dokumentation :

B.A.T.M.A.N-II

BETTER APPROACH TO MOBILE AD-HOC NETWORKING

B.A.T.M.A.N ist eine völlig neue Herangehensweise an Ad-Hoc-Routing, deren
Durchführbarkeit wir mit diesem Code testen wollen. Alle bisherigen uns
bekannten Routingalgorithmen für MANETs (Mobile Ad-Hoc Networks) versuchen
Routen zu berechnen. B.A.T.M.A.N tut etwas völlig anderes. Es berechnet keine
Routen - es spürt das Vorhandensein von Routen auf, und benutzt sie bei
Bedarf. 

B.A.T.M.A.N interessiert sich nicht dafür wie eine Route verläuft die es
benutzt um mit einem anderen Knoten im Mesh-Netzwerk zu kommunizieren.
B.A.T.M.A.N prüft lediglich über welchen direkten Nachbarn ein bestimmter
Netzwerkknoten am besten zu erreichen ist. 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.


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.

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.

Einer der älteren Entwürfe für MANET Routing ist DSR - 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.

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.

Der bekannteste Vertreter von LSR ist OLSR von olsr.org. Inzwischen ist OLSR
mit ETX-Erweiterung und Fisheye-Algorithmus sehr brauchbar geworden.
Abgesehen von einigen wenigen Bugs in der Implementierung und dem störenden
Effekt, dass es sehr oft den Internetgateway wechselt, was bei geNATteten
Internetgateways zu Verbindungsabbrüchen führt. Letztendlich fehlen für OLSR
nur noch ein IP-Tunnel-Plugin um sich den Gateway aussuchen zu können und
ein paar Bugfixes.

Schlussendlich stört aber der hohe Rechenaufwand von OLSRD in den CPUs der
kleinen Meshrouter im Berliner Freifunk-Netz. Das Freifunk-MANET hat die
Grenzen des Wachstums mit dem proaktiven OLSR erreicht. Zeit also für etwas
einfacheres und besseres: B.A.T.M.A.N

Von Antoine Saint Exupery (Autor des 'Kleinen Prinz') stammt dieser Satz:

Alles menschliche Tun geht den Weg vom Primitiven über das Komplizierte zum
Einfachen. 


B.A.T.M.A.N ist eine Gruppe von Regeln an die sich ein Router halten muss.

#####################################
# Einfachstes B.A.T.M.A.N-Verfahren #
#	     		      	    #
# 	   B.A.T.M.A.N-I	    #
#####################################


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.

1.) Broadcasts

B.A.T.M.A.N findet seine Nachbarn und entfernte Netzwerkknoten im Mesh (im
folgenden Nodes genannt) durch Broadcasts die weitergereicht werden. In
einem Broadcast steht die Adresse des Erzeugers drin (im folgenden Orginator
genannt). Weiterhin enthält der Broadcast einen TTL-Wert und eine
Sequenz-Nummer. TTL steht für Time-To-Live. Die TTL ist eine Zahl die
jedesmal um den Wert 1 reduziert wird, wenn ein Datenpaket weitergereicht
wird. Wird der TTL-Wert 0 ist das Paket zu lange (üblicherweise auf
Irrwegen) unterwegs und wird verworfen. Anhand der TTL kann man daher auch
sehen wie oft ein Paket schon weitergereicht wurde. 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.

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.


######################################
# Verbessertes B.A.T.M.A.N-Verfahren #
#				     #
#	   B.A.T.M.A.N-II	     #
######################################



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:

1.) 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.

2.) 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.


3.) Ausnahme

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.


Happy testing!

Elektra, Thomas, Axel, Felix 

was wollen wir?

• route vergleichen ->trace
  • laenge -> trace
  • bandbreite der links - werden auch schmalbandige links genutzt? -> infoseite
  • packetloss -> floodping
  • Wechseln der Routen
• wie schnell fuellt sich die routingtabelle
• cpu auslastung -> infoseite / monitoring
• speicher -> infoseite / monitoring
• Anzahl der Nodes
• Traffic des Protokoll -> codeschnipsel

wie

• alle schalten batman ein -> infoseite
• wenige testen
• ein script fuer alle -> matas
• schoen waere die funktionalitaet vom monitoring zu nutzen -> jens

• • Ideen: Storchi 16:23, 24. Okt 2006 (CEST) und matas
• wer macht mit?
  • matas
  • Storchi 16:23, 24. Okt 2006 (CEST)
  • Andi.braeu 08:37, 25. Okt 2006 (CEST)
  • MegaDave 15:31, 25. Okt 2006 (CEST)
  • fries43 00:49, 26. Okt 2006 (CEST)

Batman installieren

• der grundsaetzliche Vorgaeng um Batman zu installieren ist im SVN zu finden und schon in die weimarnetzfirmware integriert
  • batman_starten
• der grobe vorgang beschreibt sich wie folgt:
  • Aliasinterface am dem WLAN anlegen mit
    • gleiche IP wie WLAN bisher nur erstes Oktett veraendern, dann blickt man besser durch
    • Beispiel: normale IP = 104.1.1.1 und BATMAN-IP dann 103.1.1.1, mit:

WIFI=$(nvram get wifi_ifname)
IP=$(nvram get lan_ipaddr|awk '{gsub(/104./,"103.");print}')
ip addr add dev $WIFI $IP/8 brd 103.255.255.255 label $WIFI:2

• • BATMAN starten, wie folgt:

batman $WIFI:2 &

• nun kann man nach einer weile alle batman-knoten anpingen, oder mit traceroute die wege verfolgen