The following commit has been merged in the master branch: commit 818a20cc93191191221d78c9d199bdb87bcd6d76 Author: Axel Neumann neumann@cgws.de Date: Sun Oct 1 15:20:11 2006 +0200

commit message missing

diff --git a/README b/README index 9f5b7de..3f2465a 100755 --- a/README +++ b/README @@ -6,24 +6,25 @@ 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 (linkstate -algorithms) calculate routes proactively from all nodes to all nodes in the -mesh-cloud, whether they are necessary or not. B.A.T.M.A.N doesn't calculate -routes - it continuously detects the existence of routes by forwarding and -receiving broadcast packets. 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 neighbour 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 +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 (link-state algorithms) calculate routes proactively from all +nodes to all nodes in the mesh-cloud, whether they are necessary or +not. B.A.T.M.A.N doesn't calculate routes - it continuously detects +the existence of routes by forwarding and receiving broadcast +packets. 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 busybox (a multicall 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 +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>

@@ -33,32 +34,35 @@ 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-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! - -Axel Neumann proved theoretically that the algorithm of B.A.T.M.A.N-II still -had its flaws. He has simulated 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. Internet gateway -detection and auto-negotiation of IP-Tunnels has been added, too. Last but -not least support for multiple interfaces per node has been implemented as -well. And we have a feature 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 +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 @@ -68,10 +72,10 @@ further testing to improve maturity, of course. We'll have a party at c-base in Berlin soon, to celebrate when this milestone will finally be released as B.A.T.M.A.N-III-0.10!

-B.A.T.M.A.N. will have a hard time to gain the same popolarity like olsrd +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 +German brand that produces handkerchiefs. Germans with a cold rather ask for a 'Tempo' than for a 'Taschentuch' (= handkerchief).

The formula: @@ -90,9 +94,9 @@ the way that B.A.T.M.A.N. goes :)

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 -multihop range, and which single hop neighbour it has to choose as a router -to a certain destination. To communicate with a node in multihop range a -B.A.T.M.A.N node only needs to know which single hop neighbour is the best +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 @@ -127,7 +131,7 @@ 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 neighbour on the path that it +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 @@ -135,7 +139,7 @@ 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 neighbour that it hands a packet to. Second +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 @@ -154,7 +158,7 @@ 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 algoritm of OLSR is too complicated for its own good and +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.

@@ -182,7 +186,7 @@ packets on Port 1966 UDP. This port must be open for incoming and outgoing UDP traffic.

-B.A.T.M.A.N detects neighbours and distant nodes by transmitting, receiving +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 @@ -192,27 +196,28 @@ 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 forwarded. If the TTL value reaches 0 the packet is dropped. The -TTL is used in TCP to avoid packets endlessly roaming around. This is a -common mechanism. The TTL does also tell how often a originator message has -been forwarded if the initial TTL-Value is known. +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 deceide whether they receive a +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: +Imagine we have a chain of mesh nodes (A,B,C,D):

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

-Imagine further that every node can only see its direct neighbours. Now node A +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 @@ -231,11 +236,11 @@ The first example was of course very simple. So what happens if the network looks like this:

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

What does B.A.T.M.A.N do now?

@@ -243,45 +248,52 @@ 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 memorises that it has seen A over D. Node F -ignores the originator-message with sequence number 0 from A, that he +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. All node F has to do is memorise where it gets most originator messages -from. Speed is decisive, because node F is only memorising 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. +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.

-If the statistic is equal amongst two or more neighbours the biggest TTL is -decisive. If TTL is equal the last received orginator packet from -destination host is decisive. +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 AND LISTS MAINTAINED BY B.A.T.M.A.N.

-1.) List of symmetric single hop neighbours +TABLES MAINTAINED BY B.A.T.M.A.N.

-Each node maintains a list of direct neighbours that contains all nodes that +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 -neighbours. +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 pakets received via each -bidirectional neighbour. The best neighbour for each originator is added to -the kernel routing table of the underlying operating system as router to the -originator. +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 Originatorpackets received from -Originators Neighbour A Neighbour B Neighbour C Neighbour D +List of Originator packets received from +Originators Neighbor A Neighbor B Neighbor C Neighbor D

A 12 9 7 3

@@ -308,42 +320,40 @@ Y via C

ORIGINATOR MESSAGE RANKING POLICY

-(Sorry if this sounds like programm code :) - If a originator message with a unknown sequence number is received first via -the best ranking neighbour the packet count is increased for the best -neighbour. - -If a originator message with a unknown sequence number is not received via -the best ranking neighbour but from another bidirectional neighbour the -packet count is increased for that neighbour. +a bidirectional neighbor the packet count is increased for this neighbor.

-If a originator message with a unknown sequence number is received via the -best ranking neighbour but received first from another bidirectional -neighbour the packet count is increased for the best ranking neighbour as -long as the TTL of the originator message from the best neighbour and...

-Uff - if you want to read further check out the programm code ;) +ORIGINATOR MESSAGE FORWARDING POLICY

+(Sorry if this sounds like program code :)

-ORIGINATOR MESSAGE FORWARDING POLICY +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.

-Only originator packets that are received via the best ranking neighbour are -forwarded - that means rebroadcasted.

-That was easy... +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.

-BIDIRECTIONAL NEIGHBOUR DETECTION AND UNIDIRECTIONAL FLAG +There is one exception where the unidirectional flag is used in +response to originator packets from bidirectional single-hop +neighbors:

-Originator messages originated from single hop neighbours are repeated -always, but if we don't receive our own self-initiated originator messages -getting rebroadcasted by a neighbour we add a unidirectional flag in -response to his self-initiated broadcasts. +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 neighbour directly repeat our self-initiated -originator messages then there is obviously a bidirectional link between +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!