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
Hello Hendrik -
- 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.
- 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.
- 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.
- 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
b.a.t.m.a.n@lists.open-mesh.org
-
elektra -
Hendrik