Re: [B.A.T.M.A.N.] Routing decisions

[Sven Eckelmann <sven@narfation.org>]

[-- Attachment #1: Type: Text/Plain, Size: 3387 bytes --]

Ed Okerson wrote:
> On Thu, May 5, 2011 at 12:35 PM, Sven Eckelmann <sven@narfation.org> wrote:
> > Ed Okerson wrote:
> >> On Thu, May 5, 2011 at 10:44 AM, Marek Lindner <lindner_marek@yahoo.de>
> > 
> > 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

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 836 bytes --]