Re: [B.A.T.M.A.N.] [Battlemesh] Battlemesh v5 tests

Gabriel Kerneis
2012-03-07T22:18:48Z

[CC: b.a.t.m.a.n@lists.open-mesh.org, see note 3 in particular]

Antonio,

On Wed, Mar 07, 2012 at 06:17:52PM +0100, Antonio Quartulli wrote:
> Technical details about what? Interface-alternating? It is there!
> Gabriel wrote the link.

No. Please re-read my email carefuly. The wiki contains a rough explanation of
the general principle (ie. “same interface = bad, different interface = good”).
Not the actual algorithm used by batman-adv (quoting from the wiki: “the
algorithm tries to avoid forwarding packets on the interface which just received
the packet”).

Note that the wiki has been updated since then, by Simon with a few more
details [1], and by Marek with benchmark results from WBMv3.

> Gabriel said he has not enough time to look into it. I'm sorry, but I don't think
> this is a good reason to blame batman-adv devs :P

I finally decided to settle this issue and spent my breakfast reading
batman-adv/routing.c [2] instead of my favorite newspaper. Here is what I
understood:

At all times, batman-adv maintains a list of "bonding candidates" for each
node (bonding_candidate_add, called from bat_iv_ogm.c:699).
Some node "neigh" is a bonding candidate for another node "orig" if and only
if:
- neigh and orig have the same primary address, ie. are in fact the same
router,
- the links to reach them have the same quality up to some additive
constant (BONDING_TQ_THRESHOLD = 50) [3],
- orig does not already have another bonding candidate for the same
interface, because it could interfere – but what if the neigh has a better
link quality, isn’t it a pity to ignore it?

Then, assuming that "interface alternating" is enabled, the list of bonding
candidates is used on every route selection (find_ifalter_router, called
from routing.c:769).
More precisely, once batman has chosen a next-hop router for a packet based
on its classical routing algorithm, it walks the list of the bonding
candidates associated to the primary interface for this router [4]. It
selects the actual next-hop on the following criteria:
- it must not be on the same interface as the packet came in,
- its quality must be as high as possible (given the previous constraint).

This is the kind of explanation I would have loved to find on the wiki. By the
way, consider it public domain and feel free to copy/paste/correct it if you
wish.

It is still not clear to me exactly why this works, but I believe this is what
the code does, and is definitely easier to discuss than generic, unsubstantiated
claims.

Best regards,
Gabriel

[1] “Interface alternating is only performed if the two candidate links to the
next hop have a similar quality.”
http://www.open-mesh.org/wiki/batman-adv/Multi-link-optimize

[2] http://www.open-mesh.org/projects/batman-adv/repository/revisions/master/entry/routing.c

[3] By the way, there is something I don’t understand: neigh_node->tq_avg will be
accepted event if it is far greater than router->tq_avg + BONDING_TQ_THRESHOLD.
Shouldn’t it be: abs(neigh_node->tq_avg - router->tq_avg) > BONDING_TQ_THRESHOLD?
http://www.open-mesh.org/projects/batman-adv/repository/revisions/master/entry/routing.c#L166

[4] Why the primary and not the chosen router directly? Is the bonding
candidates list always associated to the primary interface?