Author: axel Date: 2010-06-19 14:06:34 +0200 (Sat, 19 Jun 2010) New Revision: 1707

Added: branches/bmx-0.3.x/ Removed: branches/bmx-0.3.x/INSTALL branches/bmx-0.3.x/LIESMICH branches/bmx-0.3.x/README Modified: branches/bmx-0.3.x/batman.h branches/bmx-0.3.x/control.c branches/bmx-0.3.x/posix/tunnel.c Log: branch bmx-0.3.x

Deleted: branches/bmx-0.3.x/INSTALL =================================================================== --- trunk/batman-experimental/INSTALL 2010-06-18 21:20:58 UTC (rev 1706) +++ branches/bmx-0.3.x/INSTALL 2010-06-19 12:06:34 UTC (rev 1707) @@ -1,180 +0,0 @@ - -################################### -B.A.T.M.A.N. Installation and Usage -################################### - - -� ( This documentation is actually for the stable batman-0.2.x branch. -� However, the main steps described here for compilation and usage should -� be almost the same for the currently unstable 0.3.x branch. - There is also a very nice HOWTO from Wesley available as a pdf at: - http://open-mesh.net/batman/documentation/batmand_howto.pdf ) - - -Compiling from source -===================== - -Pre-requirements ---------------- - -You need the usual compile environment and the libpthread-library -and the kernel module "tun". Both should already be installed on -your machine, if you use a PC using Linux. On embedded devices -both may not be installed in order to save space. - -Compiling ---------- - -You don't necessarily need to compile. Our download.store at -downloads.open-mesh.net is likely to offer precompiled packages -for your system. - -Download and compile the latest stable sources from the download -section http://www.open-mesh.net/wiki/Download by executing eg.: - -�$ wget http://downloads.open-mesh.net/batman/stable/sources/batmand_0.2-current_sou... -�$ tar xzvf batmand_0.2-current_sources.tgz -�$ cd batmand_0.x-rvxyz_sources -�$ make - -After the compilation process is finished you'll find a executable -file called 'batmand'. This executable is quite big because it is -not stripped. Don't strip it if you want to help us finding a bug -in the daemon. Strip it by executing: - -�$ strip batmand - -Note there is no installation script at the moment. If you want to -install it, copy the daemon (batmand) to a location somewhere in -your path, for example - -�$ cp batmand /usr/sbin/ - -Or start it right from the directory where you compiled it by -issuing: - -./batmand - - -Installation on a Freifunk Router -================================= - -Just to be sure, there has been some confusion with outdated -batman(d) packages. So its a good idea to check for any old -package by login into your router and executing: - -�$ ipkg status | grep batman - -Remove everything listed by doing for example: - -�$ ipkg remove batman batman-iii freifunk-batman-de ... - -Then continue with the installation of fresh and stable batman packages! - -If you use a wireless router based on Freifunk-Firmware or OpenWRT you can -use the ipkg-package management system. Add the line: - -� src lui http://freifunk.schmudde.com/ipkg - -to your package sources file ( /etc/ipkg.conf ) and update the list of -available packages by executing: - -�$ ipkg update -�$ ipkg install batmand -�$ ipkg install freifunk-batman - -If not already installed (or automatically resolved) you may also need to -explicitly install the libpthread and kmod-tun package. Do this by executing: - -�$ ipkg install libpthread -�$ ipkg install kmod-tun - -Afterwards, reboot your WRT and check the web interface. You need to enable -batman for one (or several) interfaces and specify the netmask and IP address -as well as other optionally parameters. - -Alternatively you can get the latest stable release (as well as development) -versions from �http://www.open-mesh.net/wiki/Download - -For example to install batmand-0.2 on a freifunk WRT do: - -�$ ipkg install http://downloads.open-mesh.net/batman/stable/wrt-freifunk/batmand_0.2-curren... - -� Be aware that, a recent batmand-...ipk from open-mesh.net -� should be equal to the batmand-...ipk from freifunk.schmudde.com/ipkg. -� Both packages install /usr/sbin/batmand and the last installed -� one will overwrite the previous one. - - - -Usage -===== - -Make sure you have no firewall running that is blocking UDP -port 1966 (originator messages), port 1967 (HNA messages). -Port 1968 has to be open for incoming UDP traffic if you run the -B.A.T.M.A.N. visualization server. - -First the network interfaces supposed to participate -in the batman mesh must be configured properly. Assuming you -are already running olsr on interface eth1 with the IP address -104.1.12.123/8 and now want to run batman in parallel to olsr -on the same physical interface but with a 105.1.12.123/8 IP/netmask. - -�$ ifconfig eth1:bat 105.1.12.123 netmask 255.0.0.0 broadcast 105.255.255.255 -�$ batmand -d 3 eth1:bat -� -This will configure an alias interface on top of eth1 named eth1:bat and start -the batman daemon with debug level 3 on that alias interface. As soon as -another running batmand (with the same netmask and broadcast address) is -connected to that link (or within the range of the wireless link) -both batman daemons should see each other and indicate this in the debug output. - -The daemon started with debug level 3 can be terminated with ctrl-c. -If no debuglevel is given at startup, using -� -$ batmand eth1:bat - -the daemon will immediateley fork to the background (as is the usual behavior -of a daemon). However you can always connect to the main daemon (running -in background) by launching a client-batmand process with the --c and -d <number> option, where the number represents the desired -debug-level. The following command will connect to a running batmand -process providing debug-level 1 informations. -� -$ batmand -c -d 1 # shows a list of other nodes in the mesh - -$ batmand -c -d 2 # shows a list of nodes offering internet GW access - -$ route -n # shows your current routing table as modified by batmand - -For a full list of supported debug-levels and other startup options see - -�$ batmand -h # providing a brief summary of options and - -�$ batmand -H # for a more detailed list of options - -Use ctrl-c to terminate a process running in foreground and -� -$ killall batmand - -to terminate the main batmand daemon running in background. - -If you want to use one of the batman-internet gateways showed with -debug-level 2 launch the main batmand using: - -�$ batmand -r 3 eth1:bat # to automatically select a reasonable GW -� -�$ batmand -r 3 -p <ip-of-batmand-gw-node> eth1:bat # to set a preferred GW - -In case of success this will setup a tunnel to a (preferred) batman-gw-node -and configure the routing table that all packets matching the default route -are forwarded (tunneled) respectively. -More information is available using the -h and -H options. - - - - -Happy routing! - -The B.A.T.M.A.N. contributors

Deleted: branches/bmx-0.3.x/LIESMICH =================================================================== --- trunk/batman-experimental/LIESMICH 2010-06-18 21:20:58 UTC (rev 1706) +++ branches/bmx-0.3.x/LIESMICH 2010-06-19 12:06:34 UTC (rev 1707) @@ -1,264 +0,0 @@ - - - ----------------------------------------------------------------------------- -HINWEIS HINWEIS HINWEIS HINWEIS HINWEIS HINWEIS HINWEIS HINWEIS HINWEIS - -Die deutschsprachige Doku (dieser Text) ist veraltet. Die englische Version -'Readme' ist dagegen up-to-date. - -HINWEIS HINWEIS HINWEIS HINWEIS HINWEIS HINWEIS HINWEIS HINWEIS HINWEIS ----------------------------------------------------------------------------- - -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 \ No newline at end of file

Deleted: branches/bmx-0.3.x/README =================================================================== --- trunk/batman-experimental/README 2010-06-18 21:20:58 UTC (rev 1706) +++ branches/bmx-0.3.x/README 2010-06-19 12:06:34 UTC (rev 1707) @@ -1,362 +0,0 @@ -B.A.T.M.A.N.-III - -BETTER APPROACH TO MOBILE AD-HOC NETWORKING - -#################### -# 1.) INTRODUCTION # -#################### - -B.A.T.M.A.N. is a new approach to Ad-Hoc-Routing, unlike other algorithms -that we are aware of. Reactive MANET protocols search for routes when a node -initiates communication to a remote node. Proactive protocols (all -link-state algorithms and some distance-vector algorithms) calculate routes -proactively from all nodes to all nodes in the mesh-cloud, whether they are -necessary or not - while reactive protocols search for routes on demand. -B.A.T.M.A.N. doesn't calculate or search for routes - it continuously detects -the existence of routes by forwarding and receiving broadcast packets, and -it proactively populates the routing-table with nodes in the mesh. The -algorithm does not try to find out which path packets follow to a remote -node. B.A.T.M.A.N. merely checks which single hop neighbor it has to send a -package to in order to push it on the best way to a node in the mesh. If you -want to find out how B.A.T.M.A.N. routes to a certain node, perform a - -ping -R <destination address> - -Note that this command does not work with busy box (a multi-call binary, -the 'swiss knife' for embedded Linux systems, used for example in -OpenWRT and Freifunk firmware), since 'ping' doesn't have the -R -option in busybox. You can do - -traceroute -n <destination address> - -instead. - -################# -# 2.) EVOLUTION # -################# - -B.A.T.M.A.N.-III is the third stage in the evolution of the -B.A.T.M.A.N. algorithm - hence the numbering scheme. B.A.T.M.A.N.-I -didn't check for bidirectional link conditions when forwarding -packets. This was an obvious design flaw. We didn't bother to add -bidirectional link checks in the first experimental implementation -that was meant to merely test the algorithm. The results of -B.A.T.M.A.N.-I were however promising, so B.A.T.M.A.N.-II was -implemented introducing a simple mechanism to check for bidirectional -links to perform further tests in real-live scenarios. - -B.A.T.M.A.N.-II implemented the bare algorithm with bi-directional link -checks for meshnodes with one interface only and was tested in the -Freifunk meshclouds of Berlin and Weimar. Thank you very much, you are -really brave guys! It was working quite nice on PCs, but the quick and -dirty implementation was causing high CPU-Loads on embedded systems -and even broadcast packet storms! - -We found out that the algorithm of B.A.T.M.A.N.-II still had its -flaws. We identified conditions where B.A.T.M.A.N.-II would choose -routes far from optimal and even could cause routing loops. Hence -B.A.T.M.A.N.-III implements changes in the algorithm to cope with these -scenarios. - -Some new features, namely Internet gateway detection and -auto-negotiation of IP-Tunnels, have been added. Support for multiple -interfaces per node has been implemented. And last but not least we -have a mechanism to collect link state information in a centralized -server so people can download data from this server to display those -fancy three-dimensional meshclouds with s3d or two-dimensional with -dot-draw. - -Now B.A.T.M.A.N.-III has - in theory - everything to replace other MANET -routing daemons. As this is a young and experimental development it needs -further testing to improve maturity, of course. - -On December 13th 2006 we had a party at c-base in Berlin, to celebrate -the release of this milestone as B.A.T.M.A.N.-III-0.1! - -B.A.T.M.A.N. will have a hard time to gain the same popularity like olsrd -from olsr.org. OLSR is now the same for community mesh networks in Europe -and elsewhere what 'Tempo' is for handkerchiefs in Germany. Tempo is a -German brand that produces handkerchiefs. Germans with a cold rather ask for -a 'Tempo' than for a 'Taschentuch' (= handkerchief). - -The formula: - -OLSR = Community Mesh Network - -is now established in the minds of community networkers today. - -It is overwhelming to see what olsr.org has been growing into. Let's wait and see -the way that B.A.T.M.A.N. goes :) - - -##################################### -# 3.) MANET THEORY AND B.A.T.M.A.N. # -##################################### - -A node in a B.A.T.M.A.N.-MANET is only interested to learn about the -existence of all nodes that it can communicate with, either in single or -multi-hop range, and which single hop neighbor it has to choose as a router -to a certain destination. To communicate with a node in multi-hop range a -B.A.T.M.A.N. node only needs to know which single hop neighbor is the best -to send its packets to, so that the packets takes the best way to the node -in the distance. To explain the advantage of this approach it may be best to -compare it with other ideas about mesh routing - namely source routing and -link state routing. - -Reactive (Source Routing) Algorithms - -Source routing means a node Y in the mesh 'thinks', that the best way to -send data to node D is a path where the packet travels from node Q to node -S, from node S to node H, from H to W - and so on - until the data -terminates at the destination node. Y gives Q the directive to send the data -to S. S receives the directive from Y to send the data to H - the whole -chain is planned by the originator of the traffic. So Y computes the path to -D and tells intermediate nodes what to do. - -One known design for MANET Routing is DSR - Dynamic Source Routing. DSR -contains an algorithm that aims to find source routes and to maintain them, -in case they break down. The fly in the ointment is, that MANETs are subject -to highly dynamic changes. A MANET does not only lose payload data, but -loses topology information also. If the originator is several hops away from -the destination it is very likely that the information about the topology on -the other end is very hazy, incomplete and outdated. The originator is the -node most incompetent to decide the path of the data on the other end of the -path. The chain could be already broken down before Y sends its first -packet. Y then receives a message that the destination host is unreachable -and starts looking for a new path again. - -Proactive (Link State Routing) Algorithms - -In a mesh with proactive link state routing (LSR) every node tries to -calculate routes valid for the whole mesh from every single node to every -other. Fortunately this does not mean source routing, because the view about -the topology in the distance is hazy, too. In fact every node maintains a -individual huge database and computes paths that packets should follow and -hands payload packets confidingly to the next neighbor on the path that it -has calculated. While one node may believe that it knows the path that the -packages are actually going to travel, each node maintains its own database -and calculates its own paths. So every node autonomously computes its own -decisions when initiating or forwarding traffic. - -There are two flies in the ointment that come with this approach. First -tradeoff is the calculation of huge databases, while all a node can decide -is select the next single hop neighbor that it hands a packet to. Second -the databases in nodes in a mesh with a considerable number of nodes are -never really consistent - so routing loops can occur if the route -calculations of two nodes involved in forwarding traffic are not in sync and -collide with each other. Link state routing therefore bears a lot of -overhead and problems. The advantage compared to source routing is that a -node closer to the destination has better information about the status of -the topology and can compute better decisions about the path. - -If routing loops occur you get the message 'Time to live exceeded' when -performing a 'ping'. - -The link state routing protocol (LSR) that is most popular today in the open -source world is OLSR from olsr.org. OLSR with LinkQualityExtension and -Fisheye-Algorithm works quite well, apart from a few bugs and the annoying -effect, that it too often switches between internet gateways which causes -problems (connections break down, timeouts). OLSR lacks an IP-Tunnel-Plugin -that would users allow to select their gateways. - -In conclusion the algorithm of OLSR is too complicated for its own good and -draws too much CPU-Power. So it is time for something more simple and more -effective. - -There is a well known quotation from Antoine Saint Exupery, Author of the 'The -little prince': - -All human doing goes the way from the primitive along the complicated to the -simple. - -B.A.T.M.A.N. could be a milestone in the development of a simple yet well -performing routing algorithm for MANETs. - -B.A.T.M.A.N. is a simple set of rules a node has to comply with. - - - -########################## -# B.A.T.M.A.N. ALGORITHM # -########################## - - -NOTE: -A firewall must not block B.A.T.M.A.N. traffic. B.A.T.M.A.N. sends its -packets on Port 1966 UDP. This port must be open for incoming and outgoing -UDP traffic. - - -B.A.T.M.A.N. detects neighbors and distant nodes by transmitting, receiving -and repeating broadcasts according to the rules of the B.A.T.M.A.N. -algorithm. These broadcasts travel through the mesh-cloud until they are -lost or nobody has to rebroadcast them any more. Once a node receives a -broadcast message initiated from a distant node it is aware of the existence -of the node. - - -ORIGINATOR MESSAGES - -A broadcast (we will call it originator message from now on) contains -at least the originator address, a sequence number and a TTL. TTL or -Time-To-Live is a counter that is decremented by 1 every time before -the packet is rebroadcasted. If the TTL value reaches 0 the packet is -dropped. The TTL is used in IP packets to avoid packets endlessly -travelling around. This is a common mechanism. If the initial -TTL-Value is known, the TTL does also tell the receiver how often a originator -message has been rebroadcasted. - -Particular important for B.A.T.M.A.N. is the sequence number. Originators -number their broadcasts so other nodes can decide whether they receive a -originator message the first time or repeatedly. - -Originator messages are initiated from every node at a given interval and -forwarded by all other nodes according to the rules of the algorithm. If a -broadcast gets lost it is not resend. - -Imagine we have a chain of mesh nodes (A,B,C,D): - - A <--> B <--> C <--> D - -Imagine further that every node can only see its direct neighbors. Now node A -broadcasts a originator-message. Node B receives the message and rebroadcasts it. - -Thereby node C receives the information: Message from node A, forwarded from -node B, sequence number 0, TTL 49 - -Node C forwards the message again. Thus node D receives the information: -message from node A, forwarded by node C, sequence number 0, TTL 48 - -Now node D knows: - -There is a node A that is three hops away. In order to communicate with node -A I have to send packets to node C. Node D does not need to know more than -that. - -The first example was of course very simple. So what happens if the network -looks like this: - - - *------- B --------- C ------* - | | - A --+-------------- D -----------+-- F - | | - *-------------- E -----------* - -What does B.A.T.M.A.N. do now? - -Node A broadcasts an originator-message with sequence number 0. B, C, D and E -all forward this message. - -Node F receives the originator-message sequence number 0 from node A -forwarded by node D first and memorizes that it has seen A over D. Node F -ignores the originator-message with sequence number 0 from A, that it -receives from node C because it receives the same message again. The message -forwarded by node E may get lost or come too late to be the first, too. - -Using the best path between node A and F the packets travel more -reliable and/or quicker. B.A.T.M.A.N.. nodes consider the best path to -a destination only as far as to the best next hop (or neighbor) -towards the destination. The best next hop is simply identified by -gathering statistics about how often and via which neighbor a certain -originator and sequence number has been received first. - -For the above given scenario, all node F has to do is memorize where it -gets most originator messages from. Speed is decisive, because node F -is only memorizing who is forwarding the packet first. If node F wants -to communicate with node A it simply sends its packets to the node -with the best statistic. - -If the statistic is equal amongst two or more neighbors the biggest -TTL is decisive. If also the TTL is equal the last received originator -packet is decisive. - - - -TABLES MAINTAINED BY B.A.T.M.A.N. - -1.) Table of symmetric single hop neighbors - -Each node maintains a list of direct neighbors that contains all nodes that -it has a direct bidirectional (symmetric) communication link to. -Bidirectional links are detected when a originator receives its -self-initiated originator messages getting directly repeated by its -neighbors. - -2.) Table of Originators and Ranking - -This table contains all nodes that are detected by receiving their -originator messages and the number of originator-sequence-number -packets received first via the particular neighbor. The best neighbor -for each originator is added to the kernel routing table of the -underlying operating system as router to the originator. - -Example: Ranking table in Node Q - -List of Originator packets received from -Originators Neighbor A Neighbor B Neighbor C Neighbor D - -A 12 9 7 3 - -B 3 7 17 4 - -C 0 3 27 1 - -D 0 2 17 8 - -X 3 3 9 4 - -Y 9 1 12 2 - - -According to the ranking table Q would route payload traffic to: - -A via A -B via C -C via C -D via C -X via C -Y via C - - -ORIGINATOR MESSAGE RANKING POLICY - -If a originator message with a unknown sequence number is received first via -a bidirectional neighbor the packet count is increased for this neighbor. - - -ORIGINATOR MESSAGE FORWARDING POLICY - -(Sorry if this sounds like program code :) - -Only originator packets that are received via the best ranking -neighbor are rebroadcasted. This must also be -done if the originator-sequence-number tuple has already been seen via -another (non-best) neighbor as long as the TTL does not differ to the -last originator-sequence-number tuple that has been seen from the best -neighbor first. - - -BIDIRECTIONAL NEIGHBOR DETECTION AND UNIDIRECTIONAL FLAG - -Originator messages initiated from single hop neighbors are always -re-broadcasted. If we don't receive our own self-initiated originator -messages getting rebroadcasted by a neighbor we add a unidirectional -flag before rebroadcasting the originator message of this neighbor. - -There is one exception where the unidirectional flag is used in -response to originator packets from bidirectional single-hop -neighbors: - -If a bidirectional neighbor is not the best ranking neighbor to itself -(ah, you're getting confused now, eh?!) we rebroadcast the originator -packet containing the unidirectional flag. - -Originator messages with unidirectional flag that were not initiated by us -are always ignored. If we see a neighbor directly repeat our self-initiated -originator messages there is obviously a bidirectional link between -us. - -Happy testing! - -Elektra \ No newline at end of file

Modified: branches/bmx-0.3.x/batman.h =================================================================== --- trunk/batman-experimental/batman.h 2010-06-18 21:20:58 UTC (rev 1706) +++ branches/bmx-0.3.x/batman.h 2010-06-19 12:06:34 UTC (rev 1707) @@ -61,7 +61,7 @@ * Global Variables and definitions */

-#define SOURCE_VERSION "0.3-rc1" //put exactly one distinct word inside the string like "0.3-pre-alpha" or "0.3-rc1" or "0.3" +#define SOURCE_VERSION "0.3" //put exactly one distinct word inside the string like "0.3-pre-alpha" or "0.3-rc1" or "0.3"

#define COMPAT_VERSION 10

Modified: branches/bmx-0.3.x/control.c =================================================================== --- trunk/batman-experimental/control.c 2010-06-18 21:20:58 UTC (rev 1706) +++ branches/bmx-0.3.x/control.c 2010-06-19 12:06:34 UTC (rev 1707) @@ -227,7 +227,7 @@ dbgf_all( DBGT_INFO, "activated level %d", debug_level); - dbg( DBGL_CHANGES, DBGT_INFO, "BatMan-eXp %s%s (compatibility version %d): %s", + dbg( DBGL_CHANGES, DBGT_INFO, "BMX %s%s (compatibility version %d): %s", SOURCE_VERSION, strncmp( REVISION_VERSION, "0", 1 ) != 0 ? REVISION_VERSION : "", COMPAT_VERSION, init_string); @@ -3163,7 +3163,7 @@ } else if ( !strcmp(opt->long_name, ARG_VERSION) ) { - dbg_printf( cn, "BatMan-eXp %s%s (compatibility version %i)\n", + dbg_printf( cn, "BMX %s%s (compatibility version %i)\n", SOURCE_VERSION, ( strncmp( REVISION_VERSION, "0", 1 ) != 0 ? REVISION_VERSION : "" ), COMPAT_VERSION ); #ifndef NOTRAILER

Modified: branches/bmx-0.3.x/posix/tunnel.c =================================================================== --- trunk/batman-experimental/posix/tunnel.c 2010-06-18 21:20:58 UTC (rev 1706) +++ branches/bmx-0.3.x/posix/tunnel.c 2010-06-19 12:06:34 UTC (rev 1707) @@ -463,8 +463,7 @@ static void get_gw_speeds( unsigned char class, int *down, int *up ) {

char sbit = (class&0x80)>>7; -// char dpart = (class&0x7C)>>3; - char dpart = (class&0x78)>>3; + char dpart = (class&0x78)>>3; char upart = (class&0x07);

*down= 32*(sbit+2)*(1<<dpart);