[RFC,0/2] Better throughput estimation on half duplex interfaces

  Currently BATMAN_V path throughput computation algorithm takes into account
store & forward WiFi characteristics. When an originator forwards an OGM on the
same interface it received it, the path throughput is divided by two.

Let's consider the topology below

+-------+         +-------+         +-------+
| Orig0 | <------ | Orig1 | <------ | Orig2 |
+-------+   T01   +-------+   T12   +-------+

Where Orig0's OGM is received on same WiFi (non full duplex) interface as the
one used to forward it to Orig2. And where T01 is the estimated throughput
for link between Orig0 and Orig1 and T12 is the one between Orig1 and Orig2.
Let's note PT02 the B.A.T.M.A.N-Adv estimated throughput for the end-to-end
path between Orig2 and Orig0.

In this case Orig0 broadcasts its own OGM initialized with
BATADV_THROUGHPUT_MAX_VALUE. Orig1 receives it and compares it with the
estimated link throughput T01. Thus Orig1 considers the path to reach Orig0 has
an end-to-end throughput of T01, so far so good.

Then Orig1 first adapts the Orig0 OGM throughput to T01/2 then forwards it on
same interface it received it. Orig2 receives it and first thing Orig2 does is
checking if T12 is lower than the received OGM throughput (i.e. T01/2), and if
that is the case T12 is considered to be the new end-to-end path throughput.

The first issue I see here is that Orig2 does not know the path to reach Orig0
has to get half duplex penalty because it is forwarded on same WiFi interface on
Orig1, only Orig1 knows that. Thus if T12 is lower that T01/2, T12 will be
chosen as the Orig2 to Orig0 path throughput (i.e PT02) and the half duplex
penalty is lost.

The first patch of this series aims to fix that by adding a flag in OGM packets
to inform Orig2 the path to reach Orig0 shares the same half duplex interface
and that it has to apply the dividing by two penalty on its link throughput.

The other thing I think can be improved, is this dividing by 2 penalty. This
penalty seems a bit off the expected estimation most of the time. The way I
approach this half duplex penalty is by trying to compute the maximum number of
bytes that can go from Orig0 to Orig2 passing through Orig1 in one second.

And because of half duplex characteristic of WiFi you can't transfer bytes from
Orig0 to Orig1 and Orig1 to Orig2 simultaneously. So at the end it comes down to
finding the maximum number of bytes (x) that can go from Orig0 to Orig1 and then
from Orig1 to reach Orig2 within one second as below:

x / T01 + x / T12 = TotalTripTime

With x/T01 and x/T12 being the time x bytes takes to go from Orig0 to Orig1 and
Orig1 to Orig2 respectfully.

So by solving the above for x with TotalTripTime being 1second:
x = T01 * T12 / (T01 + T12)

Thus if T01 == T12 Orig1 takes the same time to receive bytes from Orig2 than to
forward them to Orig1 then dividing by two makes sense.

But if let says Orig1 forwards data to Orig0 twice as fast as it receives it
from Orig2 (e.g. T12 = 3MB/s and T01 = 6MB/s), throughput can reach up to two
third of T12 throughput (e.g. Orig2 sends 2 MB to Orig1 taking 2/3 of a second
which is then forward to Orig0 taking the remaining 1/3 of a second reaching an
overall throughput of 2MB/s).

Reasoning by recurrence the following formula can be applied to find estimated
path throughput for any half duplex chain between OrigX to OrigY through OrigZ:

PTzx = PTyx * Tzy / (PTyx + Tzy)

Where PTzx and PTyx are estimated throughput for end-to-end path between OrigZ
and OrigX, and OrigY and OrigX respectively. And where Tzy is the estimated
throughput for link between OrigZ and OrigY.

The second patch from this series moves from the divided by two forward penalty
to the one above.


Remi Pommarel (2):
  batman-adv: Keep half duplex penalty on OGM receiving side also
  batman-adv: Better half duplex penalty estimation

 include/uapi/linux/batadv_packet.h |  8 ++++++
 net/batman-adv/bat_v_ogm.c         | 44 ++++++++++++++++++++++++++----
 net/batman-adv/types.h             |  3 ++
 3 files changed, 49 insertions(+), 6 deletions(-)
  

On Thursday, 28 September 2023 14:39:34 CEST Remi Pommarel wrote:
> Then Orig1 first adapts the Orig0 OGM throughput to T01/2 then forwards it
> on same interface it received it. Orig2 receives it and first thing Orig2
> does is checking if T12 is lower than the received OGM throughput (i.e.
> T01/2), and if that is the case T12 is considered to be the new end-to-end
> path throughput.
> 
> The first issue I see here is that Orig2 does not know the path to reach
> Orig0 has to get half duplex penalty because it is forwarded on same WiFi
> interface on Orig1, only Orig1 knows that. Thus if T12 is lower that T01/2,
> T12 will be chosen as the Orig2 to Orig0 path throughput (i.e PT02) and the
> half duplex penalty is lost.

I am not quite following where you see the problem. 

The half duplex / store & forward penalty is for situations in which batman-
adv has to forward packets from an interface to another. In your scenario that 
only is Orig1.

Why should Orig2 need to care whether Orig1 does store & forward or not?

If the direct path from Orig0 to Orig2 is better than the path over Orig1 the 
metric should reflect that.

Maybe you can add throughput metric values to your example and then expand on 
what you find problematic?

Cheers,
Marek
  

On Thu, Sep 28, 2023 at 05:33:46PM +0200, Marek Lindner wrote:
> On Thursday, 28 September 2023 14:39:34 CEST Remi Pommarel wrote:
> > Then Orig1 first adapts the Orig0 OGM throughput to T01/2 then forwards it
> > on same interface it received it. Orig2 receives it and first thing Orig2
> > does is checking if T12 is lower than the received OGM throughput (i.e.
> > T01/2), and if that is the case T12 is considered to be the new end-to-end
> > path throughput.
> > 
> > The first issue I see here is that Orig2 does not know the path to reach
> > Orig0 has to get half duplex penalty because it is forwarded on same WiFi
> > interface on Orig1, only Orig1 knows that. Thus if T12 is lower that T01/2,
> > T12 will be chosen as the Orig2 to Orig0 path throughput (i.e PT02) and the
> > half duplex penalty is lost.
> 
> I am not quite following where you see the problem. 
> 
> The half duplex / store & forward penalty is for situations in which batman-
> adv has to forward packets from an interface to another. In your scenario that 
> only is Orig1.
> 
> Why should Orig2 need to care whether Orig1 does store & forward or not?

Because if Orig2 wanted to reach Orig0 through Orig1 the overall throughput
would be impacted but it is not if the expected throughput of its link
to Orig1 is lower than the expected throughput of the received OGM.
> 
> If the direct path from Orig0 to Orig2 is better than the path over Orig1 the 
> metric should reflect that.

In the example there is no direct path from Orig0 to Orig2, the only
way for Orig2 to reach Orig0 is by going through Orig1.

> 
> Maybe you can add throughput metric values to your example and then expand on 
> what you find problematic?

Ok here is an example:

+-------+         +-------+         +-------+
| Orig0 | <------ | Orig1 | <------ | Orig2 |
+-------+    300  +-------+    110  +-------+
    ^                                   |
    |                                   |
    +-----------------------------------+
                     100

Let's say that :

  - Orig0 and Orig1 are connected via a 200Mbps WiFi mesh link (mesh0)
  - Orig1 and Orig2 are connected via a 110Mbps WiFi mesh link (mesh0)
  - Orig0 and Orig2 are connected via a 100Mbps WiFi mesh link (mesh0)

With the current implementation the originator table of Orig2 will show
something like the following:

$ batctl o
   Originator     last-seen ( throughput)  Nexthop         [outgoingIF]
 * Orig0-Main-Mac   0.220s  (        110)  Orig1-mesh0-Mac [  mesh0 ]
   Orig0-Main-Mac   0.220s  (        100)  Orig1-mesh0-Mac [  mesh0 ]

So best path for Orig2 to Orig0 would go through Orig1 with an expected
throughput of 110Mbps. But such a throughput cannot be reached because
Orig1 has to forward packet from and to the same WiFi interface.

If the throughput between Orig1 and Orig2 were to be 160Mbps instead of
previous 110Mbps then the originator table on Orig2 will look like that:

$ batctl o
   Originator     last-seen ( throughput)  Nexthop         [outgoingIF]
   Orig0-Main-Mac   0.220s  (         80)  Orig1-mesh0-Mac [  mesh0 ]
 * Orig0-Main-Mac   0.220s  (        100)  Orig1-mesh0-Mac [  mesh0 ]

Best path being the direct one as it should be.

Thanks
  

And of course I messed up both batctl o outputs.

On Thu, Sep 28, 2023 at 06:48:21PM +0200, Remi Pommarel wrote:
> On Thu, Sep 28, 2023 at 05:33:46PM +0200, Marek Lindner wrote:
> > 
> > Maybe you can add throughput metric values to your example and then expand on 
> > what you find problematic?
> 

[ ... ]

> 
> $ batctl o
>    Originator     last-seen ( throughput)  Nexthop         [outgoingIF]
>  * Orig0-Main-Mac   0.220s  (        110)  Orig1-mesh0-Mac [  mesh0 ]
>    Orig0-Main-Mac   0.220s  (        100)  Orig1-mesh0-Mac [  mesh0 ]

Is in fact

 $ batctl o
    Originator     last-seen ( throughput)  Nexthop         [outgoingIF]
  * Orig0-Main-Mac   0.220s  (        110)  Orig1-mesh0-Mac [  mesh0 ]
    Orig0-Main-Mac   0.220s  (        100)  Orig0-mesh0-Mac [  mesh0 ]

(The last line nexthop was wrong)

and

> 
> So best path for Orig2 to Orig0 would go through Orig1 with an expected
> throughput of 110Mbps. But such a throughput cannot be reached because
> Orig1 has to forward packet from and to the same WiFi interface.
> 
> If the throughput between Orig1 and Orig2 were to be 160Mbps instead of
> previous 110Mbps then the originator table on Orig2 will look like that:
> 
> $ batctl o
>    Originator     last-seen ( throughput)  Nexthop         [outgoingIF]
>    Orig0-Main-Mac   0.220s  (         80)  Orig1-mesh0-Mac [  mesh0 ]
>  * Orig0-Main-Mac   0.220s  (        100)  Orig1-mesh0-Mac [  mesh0 ]
> 

Is in fact

 $ batctl o
    Originator     last-seen ( throughput)  Nexthop         [outgoingIF]
  * Orig0-Main-Mac   0.220s  (         80)  Orig1-mesh0-Mac [  mesh0 ]
    Orig0-Main-Mac   0.220s  (        100)  Orig0-mesh0-Mac [  mesh0 ]

(Same error here)

Sorry about that,
  

On Thursday, 28 September 2023 18:48:20 CEST Remi Pommarel wrote:
> > If the direct path from Orig0 to Orig2 is better than the path over Orig1
> > the metric should reflect that.
> 
> In the example there is no direct path from Orig0 to Orig2, the only
> way for Orig2 to reach Orig0 is by going through Orig1.

If there is only one path, the computed metric does not matter at all. 

If there are alternative paths (as you saying below "Orig0 and Orig2 are 
connected via a 100Mbps"), batman-adv has to find the best of the existing 
paths.


> Let's say that :
> 
>   - Orig0 and Orig1 are connected via a 200Mbps WiFi mesh link (mesh0)
>   - Orig1 and Orig2 are connected via a 110Mbps WiFi mesh link (mesh0)
>   - Orig0 and Orig2 are connected via a 100Mbps WiFi mesh link (mesh0)
> 
> With the current implementation the originator table of Orig2 will show
> something like the following:
> 
> $ batctl o
>    Originator     last-seen ( throughput)  Nexthop         [outgoingIF]
>  * Orig0-Main-Mac   0.220s  (        110)  Orig1-mesh0-Mac [  mesh0 ]
>    Orig0-Main-Mac   0.220s  (        100)  Orig1-mesh0-Mac [  mesh0 ]
> 
> So best path for Orig2 to Orig0 would go through Orig1 with an expected
> throughput of 110Mbps. But such a throughput cannot be reached because
> Orig1 has to forward packet from and to the same WiFi interface.

Correct. Looking at your example where is the problem with the store & forward 
penalty?

Or in other words: What scenario are your patches aiming to improve?

Cheers,
Marek
  

On Thu, Sep 28, 2023 at 08:10:48PM +0200, Marek Lindner wrote:
> On Thursday, 28 September 2023 18:48:20 CEST Remi Pommarel wrote:
> > > If the direct path from Orig0 to Orig2 is better than the path over Orig1
> > > the metric should reflect that.
> > 
> > In the example there is no direct path from Orig0 to Orig2, the only
> > way for Orig2 to reach Orig0 is by going through Orig1.
> 
> If there is only one path, the computed metric does not matter at all. 
> 
> If there are alternative paths (as you saying below "Orig0 and Orig2 are 
> connected via a 100Mbps"), batman-adv has to find the best of the existing 
> paths.

Yes and it currently fails to do that as explained below.

> 
> 
> > Let's say that :
> > 
> >   - Orig0 and Orig1 are connected via a 200Mbps WiFi mesh link (mesh0)
> >   - Orig1 and Orig2 are connected via a 110Mbps WiFi mesh link (mesh0)
> >   - Orig0 and Orig2 are connected via a 100Mbps WiFi mesh link (mesh0)
> > 
> > With the current implementation the originator table of Orig2 will show
> > something like the following:
> > 
> > $ batctl o
> >    Originator     last-seen ( throughput)  Nexthop         [outgoingIF]
> >  * Orig0-Main-Mac   0.220s  (        110)  Orig1-mesh0-Mac [  mesh0 ]
> >    Orig0-Main-Mac   0.220s  (        100)  Orig1-mesh0-Mac [  mesh0 ]
> > 
> > So best path for Orig2 to Orig0 would go through Orig1 with an expected
> > throughput of 110Mbps. But such a throughput cannot be reached because
> > Orig1 has to forward packet from and to the same WiFi interface.
> 
> Correct. Looking at your example where is the problem with the store & forward 
> penalty?

The problem is that the wrong path is selected.

The best one should be the direct one. Because going through Orig1, 110Mbps
would never be bereached due to the store & forward penalty on Orig1 and
the real throughput will be below the direct path (around 80Mbps).

> 
> Or in other words: What scenario are your patches aiming to improve?
> 

With both patches this

 * Orig0-Main-Mac   0.220s  (        110)  Orig1-mesh0-Mac [  mesh0 ]
   Orig0-Main-Mac   0.220s  (        100)  Orig0-mesh0-Mac [  mesh0 ]

will instead be

   Orig0-Main-Mac   0.220s  (         80)  Orig1-mesh0-Mac [  mesh0 ]
 * Orig0-Main-Mac   0.220s  (        100)  Orig0-mesh0-Mac [  mesh0 ]

Fixing the best path selection.

Thanks
  

On Thursday, 28 September 2023 21:16:36 CEST Remi Pommarel wrote:
> > > $ batctl o
> > > Originator     last-seen ( throughput)  Nexthop         [outgoingIF]
> > > * Orig0-Main-Mac   0.220s  (        110)  Orig1-mesh0-Mac [  mesh0 ]
> > > Orig0-Main-Mac   0.220s  (        100)  Orig1-mesh0-Mac [  mesh0 ]
> > > 
> > > So best path for Orig2 to Orig0 would go through Orig1 with an expected
> > > throughput of 110Mbps. But such a throughput cannot be reached because
> > > Orig1 has to forward packet from and to the same WiFi interface.
> > 
> > Correct. Looking at your example where is the problem with the store &
> > forward penalty?
> 
> The problem is that the wrong path is selected.
> 
> The best one should be the direct one. Because going through Orig1, 110Mbps
> would never be bereached due to the store & forward penalty on Orig1 and
> the real throughput will be below the direct path (around 80Mbps).

To summarize the problem you see: A path traversing a half duplex node might 
not be penalized enough when the weaker throughput link lies before a stronger 
throughput link because the half duplex penalty is not be applied before the 
packet is forwarded.

The underlying assumption is that this indeed is an issue in terms of 
(measurable) throughput. Are there any numbers / papers / experiments you are 
basing this on? Is the store & forward throughput limit determined by the 
throughput of the weakest link?

Cheers,
Marek
  

On Tue, Oct 03, 2023 at 11:06:45PM +0200, Marek Lindner wrote:
> On Thursday, 28 September 2023 21:16:36 CEST Remi Pommarel wrote:
> > > > $ batctl o
> > > > Originator     last-seen ( throughput)  Nexthop         [outgoingIF]
> > > > * Orig0-Main-Mac   0.220s  (        110)  Orig1-mesh0-Mac [  mesh0 ]
> > > > Orig0-Main-Mac   0.220s  (        100)  Orig1-mesh0-Mac [  mesh0 ]
> > > > 
> > > > So best path for Orig2 to Orig0 would go through Orig1 with an expected
> > > > throughput of 110Mbps. But such a throughput cannot be reached because
> > > > Orig1 has to forward packet from and to the same WiFi interface.
> > > 
> > > Correct. Looking at your example where is the problem with the store &
> > > forward penalty?
> > 
> > The problem is that the wrong path is selected.
> > 
> > The best one should be the direct one. Because going through Orig1, 110Mbps
> > would never be bereached due to the store & forward penalty on Orig1 and
> > the real throughput will be below the direct path (around 80Mbps).
> 
> To summarize the problem you see: A path traversing a half duplex node might 
> not be penalized enough when the weaker throughput link lies before a stronger 
> throughput link because the half duplex penalty is not be applied before the 
> packet is forwarded.

Yes, in fact currently it is even not penalized at all. This is what the
first patch proposes to fix.

This issue could also be looked at from a different angle, which is
maybe more convincing.

Let's say there is the following setup:

sta1 <-------> AP <---------> sta2
      275Mbps       720Mbps

Then the BATMAN_V current routing algorithm is going to compute the
following:

 - a 275Mbps path towards sta2 on sta1
 - a 137.5Mbps path towards sta1 on sta2

IMO, there is no real reason to have such an asymetry.

While the first patch fixes this asymetry by estimating both paths to
be 137.5Mbps, the second patch is a proposition for a better throughput
estimation.

> 
> The underlying assumption is that this indeed is an issue in terms of 
> (measurable) throughput. Are there any numbers / papers / experiments you are 
> basing this on? Is the store & forward throughput limit determined by the 
> throughput of the weakest link?
> 

I haven't found any paper on that matter, if you have one that shows
that dividing by two is a sound estimation I would be genuinely
interessted though.

However to support the theory of the second patch I did run some iperf3
tests on the setup above.

Results from iperf3 measurements:

    - sta1 --> AP   : 275Mbps
    - AP --> sta1   : 221Mbps

    - AP --> sta2   : 720Mbps
    - sta2 --> AP   : 704Mbps

    - sta1 --> sta2 : 193Mbps
    - sta2 --> sta1 : 152Mbps

The sta* --> AP and AP --> sta* asymetry comes from the different WiFi
hardwares characteristics (i.e. AP WiFi card is better at TX than RX).

Now let say that B.A.T.M.A.N-Adv has perfect throughput estimation for
direct neighbour links (e.g. sta1 <--> AP and sta2 <--> AP).

Here are the path throughput estimations with different methods for
sta1 <--> sta2.

Estimation from current B.A.T.M.A.N-adv BATMAN_V:
    - sta1 --> sta2 : 137.5Mbps
    - sta2 --> sta1 : 221Mbps

Estimation with Patch 1:
    - sta1 --> sta2 : 137.5 Mbps
    - sta2 --> sta1 : 110.5 Mbps

Estimation with both patches:
    - sta1 --> sta2 : 199Mbps
    - sta2 --> sta1 : 168Mbps

I have created a NS3 simulation test [0] that also seems to show the
proposed throughput estimation is a closer estimation most of the time.

Here is an example output of this simulation:

 $ ns3-dev-wifi-duplex-penalty-default --pos=10
  NS3 simulated throughput sta2 ---> AP:                  156.321 Mbit/s
  NS3 simulated throughput AP ---> sta1:                  323.139 Mbit/s
  NS3 simulated throughput sta2 --> sta1:                 102.888 Mbit/s
  Current BATMAN_V estimated throughput sta2 --> sta1:    156.321 Mbit/s
  Patch 1 estimated throughput sta2 --> sta1:             78.1603 Mbit/s
  Both patches estimated throughput sta2 --> sta1:        105.355 Mbit/s


[0]: http://ix.io/4IG4

Anyway thanks a lot for your time.