[RFC,2/2] batman-adv: Better half duplex penalty estimation

  Let's consider the below topology

+-------+               +-------+          +-------+
| OrigA | <--- ... ---- | OrigB | <------- | OrigC |
+-------+      PT_ab    +-------+   LT_bc  +-------+

Where OrigA's OGM is received on same WiFi (non full duplex) interface
as the one used to forward it to OrigC. And where LT_bc is the estimated
throughput for the direct link between OrigB and OrigC. And where PT_ab
is the end-to-end B.A.T.M.A.N-Adv path throughput estimation of OrigB to
reach OrigA.

Let's note PT_ac the B.A.T.M.A.N-Adv path throughput estimation of OrigC
to reach OrigA in this topology.

PT_ac was estimated by dividing by two the minimal value between PT_ab and
LT_bc because of store & forward characteristic of OrigB wifi interface.

However the following formula seems to be a more realistic approximation
of PT_ac:

PT_ac =  PT_ab * LT_bc / (PT_ab * LT_bc)

This patch change the half duplex penalty to match the formula above.

NB: OrigB still sets PT_ab/2 throughput in OrigA's OGM before forwarding
it to OrigC for retrocompatibility sake, and is discarded when OrigC
computes the new estimated end-to-end path throughput.

Signed-off-by: Remi Pommarel <repk@triplefau.lt>
---
 net/batman-adv/bat_v_ogm.c | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)
  

Hi,

Thanks for taking your time to look into this and the detailed
explanations!

Generally, the issues both patches try to address make sense to me.


On Thu, Sep 28, 2023 at 02:39:36PM +0200, Remi Pommarel wrote:
> Let's consider the below topology
[...]
> However the following formula seems to be a more realistic approximation
> of PT_ac:
> 
> PT_ac =  PT_ab * LT_bc / (PT_ab * LT_bc)

Typo, I guess, as this would always be 1? What is actually
implemented makes more sense to me.

[...]
> -	return min_t(u32, lth, oth);
> +	/* OGM throughput was divided by two for retrocompatibility sake */
> +	oth *= 2;
> +	return oth * lth / (oth + lth);

Could we end up here with a (forged?) OGM that has both the new
half duplex flag set and a throughput value of 0? While also
having an lth of 0, therefore dividing by zero here?


In the following scenario:

+-------+  ch.1  +-------+   ch.2  +-------+   ch.2  +-------+ 
| Orig0 | <----- | Orig1 | <------ | Orig2 | <------ | Orig3 | 
+-------+   300  +-------+  30000  +-------+    110  +-------+ 
                     ^                                   |   
                     |                ch.3               | 
                     +-----------------------------------+ 
                                      100

Would the results on Orig2 to Orig1 be these?
- via Orig2: 300*110 / (300+110) = 80.5
- via Orig1: 100  <- selected

While it should have been this?
- via Orig2: 30000*110 / (30000+110) = 109.6 <- selected
- via Orig1: 100

But we can't calculate the latter on Orig3, because we don't
know the two hop neighbor link throughput? Or am I missing
something?


Also, this seems to assume that time slices are divided equally.
That's probably only be true for WiFi drivers that have airtime
fairness changes integrated? So only recent versions of mt76,
ath9k and ath10k? Has anyone verified that this works fine not
only in AP but also in 11s mode?

And a third concern, but we'd probably have this issue with both
our current and your suggestion: Would we be off again 802.11be
and its "Multi-Link Operation" in the future?

Regards, Linus
  

On Sat, Oct 14, 2023 at 07:10:28AM +0200, Linus Lüssing wrote:
> In the following scenario:
> 
> +-------+  ch.1  +-------+   ch.2  +-------+   ch.2  +-------+ 
> | Orig0 | <----- | Orig1 | <------ | Orig2 | <------ | Orig3 | 
> +-------+   300  +-------+  30000  +-------+    110  +-------+ 
>                      ^                                   |   
>                      |                ch.3               | 
>                      +-----------------------------------+ 
>                                       100
> 
> Would the results on Orig2 to Orig1 be these?

Sorry, I ment "on Orig3 to Orig0" here.

> - via Orig2: 300*110 / (300+110) = 80.5
> - via Orig1: 100  <- selected
> 
> While it should have been this?
> - via Orig2: 30000*110 / (30000+110) = 109.6 <- selected
> - via Orig1: 100
  

On Thu, Sep 28, 2023 at 02:39:36PM +0200, Remi Pommarel wrote:
> diff --git a/net/batman-adv/bat_v_ogm.c b/net/batman-adv/bat_v_ogm.c
> index 27597f4cdf3e..9b7d4de182d0 100644
> --- a/net/batman-adv/bat_v_ogm.c
> +++ b/net/batman-adv/bat_v_ogm.c
> @@ -866,10 +866,12 @@ static u32 batadv_v_get_throughput(struct batadv_ogm2_packet *ogm,
[...]
>  
> -	return min_t(u32, lth, oth);
> +	/* OGM throughput was divided by two for retrocompatibility sake */
> +	oth *= 2;
> +	return oth * lth / (oth + lth);

Also looks like we'd have potential integer overflow issues
here as oth, lth and the return value are all u32.

In the worst case (oth + lth) could wrap around to 0 and we'd
divide by zero?
  

On Sat, Oct 14, 2023 at 07:10:28AM +0200, Linus Lüssing wrote:
> Hi,
> 
> Thanks for taking your time to look into this and the detailed
> explanations!
> 
> Generally, the issues both patches try to address make sense to me.
> 
> 
> On Thu, Sep 28, 2023 at 02:39:36PM +0200, Remi Pommarel wrote:
> > Let's consider the below topology
> [...]
> > However the following formula seems to be a more realistic approximation
> > of PT_ac:
> > 
> > PT_ac =  PT_ab * LT_bc / (PT_ab * LT_bc)
> 
> Typo, I guess, as this would always be 1? What is actually
> implemented makes more sense to me.

Correct ought to be PT_ab * LT_bc / (PT_ab + LT_bc)

> 
> [...]
> > -	return min_t(u32, lth, oth);
> > +	/* OGM throughput was divided by two for retrocompatibility sake */
> > +	oth *= 2;
> > +	return oth * lth / (oth + lth);
> 
> Could we end up here with a (forged?) OGM that has both the new
> half duplex flag set and a throughput value of 0? While also
> having an lth of 0, therefore dividing by zero here?

Yes good point will add appropriate checks for that and the other
possible integer overflow if this RFC goes further.

> 
> 
> In the following scenario:
> 
> +-------+  ch.1  +-------+   ch.2  +-------+   ch.2  +-------+ 
> | Orig0 | <----- | Orig1 | <------ | Orig2 | <------ | Orig3 | 
> +-------+   300  +-------+  30000  +-------+    110  +-------+ 
>                      ^                                   |   
>                      |                ch.3               | 
>                      +-----------------------------------+ 
>                                       100
> 
> Would the results on Orig3 to Orig0 be these?
> - via Orig2: 300*110 / (300+110) = 80.5
> - via Orig1: 100  <- selected
> 
> While it should have been this?
> - via Orig2: 30000*110 / (30000+110) = 109.6 <- selected
> - via Orig1: 100
> 
> But we can't calculate the latter on Orig3, because we don't
> know the two hop neighbor link throughput? Or am I missing
> something?
> 

No good catch thanks. I can think of a way to fix that but it would
need additionnal info in the OGM to store current half duplex link
speed (maybe to add a TVLV for that). So let's first see if the idea
seems sound enough to go further.

On a side note, the current implementation also has its own flaws for
this scenario. Let's say you consider Orig0 to Orig3 instead and packets
will also go from Orig1 to Orig3 directly instead of bouncing on Orig2.

> 
> Also, this seems to assume that time slices are divided equally.
> That's probably only be true for WiFi drivers that have airtime
> fairness changes integrated? So only recent versions of mt76,
> ath9k and ath10k? Has anyone verified that this works fine not
> only in AP but also in 11s mode?

I don't know how that would behave on setup that does not have airtime
fairness changes integrated, if you think the current dividing by two
approach is better maybe this can be made a configurable option but that
could be tricky ?

For 11s, I have also run tests using mesh points instead of AP/STA and I
have measured similar results.

> 
> And a third concern, but we'd probably have this issue with both
> our current and your suggestion: Would we be off again 802.11be
> and its "Multi-Link Operation" in the future?

This, I have hard time figuring out how MLO would play along with
B.A.T.M.A.N-Adv integration. Unfortunately right now I have no way
to experiment that yet. IIUC the link would be a mix between half and
full duplex, and this would probably complicate things a bit.

Thanks a lot for your review.
  

On Wed Oct 18, 2023 at 9:58 PM CEST, Remi Pommarel wrote:
> [...]
> > 
> > Also, this seems to assume that time slices are divided equally.
> > That's probably only be true for WiFi drivers that have airtime
> > fairness changes integrated? So only recent versions of mt76,
> > ath9k and ath10k? Has anyone verified that this works fine not
> > only in AP but also in 11s mode?
>
> I don't know how that would behave on setup that does not have airtime
> fairness changes integrated, if you think the current dividing by two
> approach is better maybe this can be made a configurable option but that
> could be tricky ?

It seems to me that airtime fairness is something that most current drivers aim
at doing. Even the mac80211 scheduler is going this route with the itxq work.
So I feel like we should assume that with time, most drivers will be.
And devices that do not respect airtime fairness will probably not match the
current TP/2 rule either.

> [...]
> > 
> > And a third concern, but we'd probably have this issue with both
> > our current and your suggestion: Would we be off again 802.11be
> > and its "Multi-Link Operation" in the future?
>
> This, I have hard time figuring out how MLO would play along with
> B.A.T.M.A.N-Adv integration. Unfortunately right now I have no way
> to experiment that yet. IIUC the link would be a mix between half and
> full duplex, and this would probably complicate things a bit.
>
> Thanks a lot for your review.

For me MLO is hard to take into account. Depending on the drivers (and probably
on the firmwares mostly) we do not know if it is/will be used as a real
aggregation mechanism or as a way to have 'free' roaming between multiple bands.

Moreover, currently all the path throughput estimation is based on the expected
throuput that the 80211 stack gives us for individual sta. I beleive that very
few drivers actually provide a value for it.

So IMHO we should do our best to have a good path estimation based on the sta
estimated throughput, and it should be the mac80211 drivers job to provide us
with an accurate estimated throughput for each sta on a link. And yes in the MLO
case it will be a hard job indeed...