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

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

[Ed Okerson]

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.

Ed Okerson

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

[Marek Lindner]

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

Regards,
Marek

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

[Ed Okerson]

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.

Thanks
Ed Okerson

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

[Sven Eckelmann]

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

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.

Kind regards,
	Sven

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

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

[Sven Eckelmann]

[-- 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 --]