[B.A.T.M.A.N.] How does BATMAN work?

[B.A.T.M.A.N.] How does BATMAN work?

[Hendrik]

Hi,
I'm currently writing my Masterthesis (Performance of MANET  
Protocols)  and I want to write a little bit about BATMAN. Now I'm  
running into some Problems, since it's not very well documented :(.
I got the informations from https://www.open-mesh.net/batman/ 
documentation/ and the man-page from last Newsletter and figured some  
stuff about how to populate the routingtable.
But a few points are still missing and I would be happy on getting an  
answer on them ;oP (Or is there an even better page to find some  
informations on BATMAN?)

1. From open-mesh Docu: "Originators number their OGMs?, so other  
nodes can decide whether they receive an originator-sequence-number  
touple (OGSN) the first time or repeatedly"
	What's the differens between in OGM and an OGSN? As far as I got to  
know the protocol, there are just OGM-messages, aren't there?!?
2. Does a Node somehow send back a message (what message?) to the  
originator of an OGM when ist first gets the message (so that the  
originator also can populate his Routingtable) or does the originator  
has to wait for the other nodes to send their OGM?
3. How can a node tell, that a route is broken? Is there some sort of  
timeout in every entry in the routingtable or what?
4. How does the algorithm for the best neighbor work? (I dont need  
details here, just what factors are taken for computing)

Thanks!

Greetz
Hendrik

Re: [B.A.T.M.A.N.] How does BATMAN work?

[elektra]

Hello Hendrik -

> 1. From open-mesh Docu: "Originators number their OGMs?, so other 
> nodes can decide whether they receive an originator-sequence-number 
> touple (OGSN) the first time or repeatedly"
>     What's the differens between in OGM and an OGSN? As far as I got 
> to know the protocol, there are just OGM-messages, aren't there?!?
You are right. Batman uses Originator messages, that contain at least a 
Originator address, a TTL and a Sequence Number. So to name it 
Originator Sequence Number tuple is somehow redundant and confusing. The 
term was introduced to describe what is going on in the daemon.

>
> 2. Does a Node somehow send back a message (what message?) to the 
> originator of an OGM when ist first gets the message (so that the 
> originator also can populate his Routingtable) or does the originator 
> has to wait for the other nodes to send their OGM?
Not in the way I guess you mean. Batman nodes never send routing 
information to others in the way that a message contains routing 
information about the topology - well, there is one special case when a 
node sends information about its local view to a visualisation server. 
But this has nothing to do with the routing algorithm as such, this is 
just to provide information necessary to build topology graphs. Batman 
nodes just rebroadcast Originator messages according to a set of rules.

A node rebroadcasts a Originator message, if:

a.) The Originator is a single hop neighbor. If the Originator is a 
bidirectional neighbor and the best ranking router to route traffic to 
itself the Originator message gets re-broadcasted after decreasing TTL by 1

b.) The Originator is a single hop neighbor. If the Originator is a 
bidirectional neighbor but not the best ranking router to route traffic 
to itself the Originator message is re-broadcasted with the 
unidirectional flag added and - you guessed it  - TTL decreased by 1.

c.) The Originator is a single hop neighbor. If the Originator is not a 
bidirectional neighbor the Originator message is re-broadcasted with the 
unidirectional flag added and - you know it - TTL decreased by 1.

d.) The Originator is not a single hop neighbor.  If we receive a 
re-broadcasted message from a single hop neighbor repeating a OGM from 
someone in the distance it gets repeated if our single hop neighbor is 
bidirectional and the best ranking neighbor on route to that Originator 
which created the message. And - of course - TTL decreased by 1.

In all other cases OGMs are not repeated.

A Originator will see others repeating its Originator messages if the 
radio conditions provide a bidirectional link. This is the only case 
when we send feedback to others - btw. we are not addressing them as 
such cause radio is a broadcast medium ;) Of course a OGM with 
unidirectional flag is only helpful for its Originator, to learn: Hey, 
this node has seen me and I have seen it. So we have a bidirectional link!

The strength of B.A.T.M.A.N. is it doesn't rely on other nodes 
opinions/informations about topology that would have to be synchronized. 
A process known to fail and create confusion in a wireless network...  
B.A.T.M.A.N. learns from the fact that broadcasts are received or 
missing, not from information about routing topology contained in 
broadcasts. The information who is the Originator is the only 
information in the package about topology as such...

I guess d.) is somehow what you wondered about. We won't send our 
knowledge back to the Originator in the distance. It will receive our 
OGMs containing only the information that we exist - if radio conditions 
/ topology allow it.

> 3. How can a node tell, that a route is broken? Is there some sort of 
> timeout in every entry in the routingtable or what?
Right, it is the timeout of the last valid OGM-message when we delete a 
route.

> 4. How does the algorithm for the best neighbor work? (I dont need 
> details here, just what factors are taken for computing)
Best ranking neighbor is the neighbor that gives us the Originator 
message with unknown sequence number more reliable and quicker than others.

HTH,

cu elektra

Re: [B.A.T.M.A.N.] How does BATMAN work?

[Hendrik]

Hi,
first of all thanks for the quick and good help! It realy helped a  
lot (and gave me about 3 more pages to write about BATMAN ;oP)!
Now I got two more Question (hope I don't bother you too much)
1. What Fields are there in the OGM-Package/Header? As to this point  
I got:
	- TTL
	- Seq.No.
	- Orig.IP
	- Unidrectional Flag
   and as possible extension
	- "Reachable Subnets"
	- "Is willing to Serve as a gateway".
Are there any others?

2. Electra wrote:
"A Originator will see others repeating its Originator messages if  
the radio conditions provide a bidirectional link. This is the only  
case when we send feedback to others [..] Of course a OGM with  
unidirectional flag is only helpful for its Originator, to learn:  
Hey, this node has seen me and I have seen it. So we have a  
bidirectional link!" about retransmitting an OGM.
Can the Originator of an OGM use this Information to put his direct  
neighbor in his routingtable (since that is nessesary for knowing "So  
we have a bidirectional link" ;o) ), or does it has to wait for the  
OGM of his direct neighbor (neighbor is the originator) to arrive? (I  
guess waiting is the answer, I just want to be sure)

Thanks
Hendrik

Re: [B.A.T.M.A.N.] How does BATMAN work?

[elektra]

Hello Hendrik -
>
> 1. What Fields are there in the OGM-Package/Header? As to this point I 
> got:
>     - TTL
>     - Seq.No.
>     - Orig.IP
>     - Unidrectional Flag
>   and as possible extension
>     - "Reachable Subnets"
>     - "Is willing to Serve as a gateway".
> Are there any others?
>
You have omitted gateway class. We use one byte to communicate gateway 
class and unidirectional flag.
> 2. Electra wrote:
> "A Originator will see others repeating its Originator messages if the 
> radio conditions provide a bidirectional link. This is the only case 
> when we send feedback to others [..] Of course a OGM with 
> unidirectional flag is only helpful for its Originator, to learn: Hey, 
> this node has seen me and I have seen it. So we have a bidirectional 
> link!" about retransmitting an OGM.
> Can the Originator of an OGM use this Information to put his direct 
> neighbor in his routingtable (since that is nessesary for knowing "So 
> we have a bidirectional link" ;o) ), or does it has to wait for the 
> OGM of his direct neighbor (neighbor is the originator) to arrive? (I 
> guess waiting is the answer, I just want to be sure)
It doesn't have to wait - since a working bidirectional radio link is 
already verified. We don't have to wait for our neighbor to add 
ourselves into his routing table since a single hop neighbor is link 
local anyway. However in our implementation we wait for incoming OGMs 
from the neighbor. There is no harm doing it this way it is just a tiny 
bit slower when establishing a route to a single hop neighbor. But don't 
forget: Only if the single hop neighbor is the best ranking neighbor to 
route traffic to itself it will be added as a gateway to itself into the 
routing table. A node may have a weak but direct link to a single hop 
neighbor, while we get more OGMs re-broadcasted from another single hop 
neighbor.

Would you send us your work, even if it is written in German?

cu elektra