Re: [B.A.T.M.A.N.] Routing decisions - B.A.T.M.A.N - lists.open-mesh.org

5 May 2011

Ed Okerson wrote:
...
  On Thu, May 5, 2011 at 12:35 PM, Sven Eckelmann
&lt;sven(a)narfation.org&gt; wrote:
  Ed Okerson wrote:
  On Thu, May 5, 2011 at 10:44 AM, Marek Lindner
&lt;lindner_marek(a)yahoo.de&gt;  
 wrote:
   Hi,

> We are evaluating using Batman in an environment where there could be
> 200-300 devices in a single building.  We started out setting up 10
> devices in our office to figure out how everything works and do some
> throughput testing.  We have noticed that the routing decisions
> always send the packet to the node towards the destination with the
> highest signal strength.  This causes the packet to always traverse
> the network with the maximum possible number of hops, which causes
> performance to degrade quickly.  Is it possible to use a different
> routing algorithm?  It would seem that sending to the node closest
> to the destination that the source node can still communicate with
> directly would minimize the number of hops.

 if you wish to minimize the number of hops you have to increase the
 hop penalty. Check the "hop penalty" section here:
 http://www.open-mesh.org/wiki/batman-adv/Tweaking  
 That seems to indicate that it is a per node setting, i.e. "using this
 node will incur a penalty of x".  That is also not the desired
 behavior.  For our installation all nodes are in a fixed location, so
 using a particular node as a next hop in the route may incur a penalty
 for one source node, but not another.  This should be dynamically
 determined for each route from each source to each destination to
 minimize hops.  
 So you have to increase the hop penalty everywhere to force the routing
 algorithm to reduce the number of hops and prefer worse routes with less
 hops.  
 If I increase the hop penalty on all nodes, they will all still be
 equal.  If all nodes have a hop penalty of 128, will it not make the
 same routing decisions as it does if they are all 10? 
No, the wiki explains it quite well, but I'll try to explain it a little bit 
different. Lets assume that you have perfect links (quality = 255) between all 
nodes in a route. Each one would say: "hey, I can reach the following 
neighbors with the quality of 255".... now introduce a penalty in each hop (10 
for example) which is just substracted from the incoming value. So after a 
distance of 5 hops only a quality of 205 would be announced. Therefore a node 
with only a distance of 2 (quality = 235) would be prefered as next hop in 
this case and not the one with the distance of 5.

Target - X1 - X2 - X3 - X4 - X5 - (Announces route with quality 205 to Target)
      \
       \ Y1 - Y2 - (Announces route with quality 235 to Target)

This is a quite abstract and not 100% correct explanation of the hop penalty, 
but should help to understand the implications a little bit better. You have 
to do the calculations yourself to find a good value for hop penalty.

You should have a look at send.c to find more information about it. You should 
see that it is not really substracted in a linear fashion and that the actual 
quality is calculation is also more complex,... but the idea is similar to the 
example mentioned before.

Kind regards,
	Sven