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(-)