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