Hey Linus & Antonio,
On Sat, May 25, 2013 at 11:42:19PM +0200, Antonio Quartulli wrote:
On Sat, May 25, 2013 at 11:07:48PM +0200, Linus Lüssing wrote:
> Hi Simon,
> I'm currently wondering whether changing the protocol in the way
> you described is sufficient.
> I think it still has the problem of not converging to the optimal
> solution in various scenarios, for instance:
> B1 ---------
> / \
> A C1 ---- D
> \ / /
> B2 - C2 ----
> A-B1: 10%, 0ms
> A-B2: 100%, 0ms
> B2-C1: 5%, 0ms
> B2-C2: 100%, 5ms
> B1-D: 100%, 0ms
> C1-D: 100%, 0ms
> C2-D: 100%, 0ms
> ('link': 'link-quality', 'link-delay')
> Obviously, here the path A-B2-C2 is the best, having a 100% link
> quality. However with this patch, it will select A-B1-D, having
> only a 10% link quality (I'm not considering asym/hop-penalty or
> that 0ms delay is unrealistic, and I'm not considering that the
> link quality will cause lost OGMs - just to keep things simple):
> The OGM from D gets forwarded to B1 and then to A instantly; A
> notes a path quality of 10% towards D via B1.
> The OGM from D reaches B2 via C1 first, so B2 first forwards an
> OGM with a path quality of 5% to A first. A notes a path quality
> of 5% towards D via B2.
> Then the OGM from D reaches B2 via C2, too. Now, with this patch
> B2 will correctly choose the path via C2, B2 notes a 100% path
> quality towards D via C2 instead of ignoring this OGM.
This was true also before this patch.
I agree - actually A would have not gotten any (valid) packets from B2
because B2 would got the packets first from C1, discard them (not best
nexthop), and then from C2 (best nexthop) but don't forward it because
it was a duplicate. Antonio pointed out the same thing below ...
Then A would always have to choose B1 because it gets no valid OGMs via
B2. The patch actually solves this situation, even not in optimal time
as Antonio pointed out ...
> And B2 will
> also rebroadcast this OGM.
> However, A will ignore this second OGM from D via B2 because it
> came from the same neighbor even though it came from the best,
> optimal, 100% link-quality path.
> While converging to a path after applying this patch is obviously
> better than the starvation which can currently happen I'm
> still wondering whether the issue could be solved better.
> What if we were always rebroadcasting/forwarding an OGM even from
> the same neighbor, too, if the sequence number is the same but the
> TQ better (so similar to what is specified for BATMAN V)?
If I am not wrong this is what is going to happen, but with one originator
interval of delay.
If I correctly got your example, this happens the first time only, but from the
next originator interval B2 will only rebroadcast the OGM coming from C2 since
this is the best next hop for it. So yes, this can happen but only the first
time. As soon as B2 learns the best route via C2.
Agreed here too - B2 should select C2 "soon" as the best nexthop and then only
forward Ds OGMs via C2, but not via C1. Then A will get the good OGMs via C2-B2
and - voila - will select it as best route.
The situation you describe happens for the first "few" OGMs (not sure if
the first), when only OGMs from C1 have been received at B2 but not from C2.
Regarding your suggestion to forward multiple packets with the same seqno, but
better TQ: We currently would ignore them in A for beeing a duplicate. If we were
to change that, we would have to change the TQ ring buffer as well. However this ring
buffer currently has no specific order, so it's not so easy to update a specific
in this ring buffer because we don't know which TQ value belongs to which seqno.
If packets arrive out of order, they will be saved in the ring buffer in the
order they come in, regardless of the seqno. Have a look at batadv_iv_ogm_orig_update(),
maybe you can find a decent solution for that. :)
Apart from this technical issue, I don't think it's that critical to save a single
cycle by sending (many) more OGMs, that's pretty much an overhead vs speed
What this patch is changing is to make B2 rebroadcast the OGM coming from C2
(best next hop) in case the latter arrived after the OGM coming from C1 (which
is not rebroadcasted because C1 is not best next hop). Actually the fix is only
acting on the duplicate detection only (which affect forwarding).
So, without this patch, in this case I described, we were having a real
There is no change in the route selection. The routes are still selected the
same way as before.
Yup, see above.
Thanks for you comments and thoughts,