Message ID | 09c086e5e68055e52d1f92ba17d0e921084107e7.1695904299.git.repk@triplefau.lt (mailing list archive) |
---|---|
State | RFC |
Delegated to: | Simon Wunderlich |
Headers |
Return-Path: <b.a.t.m.a.n-bounces+patchwork=open-mesh.org@lists.open-mesh.org> X-Original-To: patchwork@open-mesh.org Delivered-To: patchwork@open-mesh.org Received: from diktynna.open-mesh.org (localhost [IPv6:::1]) by diktynna.open-mesh.org (Postfix) with ESMTP id 52EF68359E for <patchwork@open-mesh.org>; Thu, 28 Sep 2023 15:52:20 +0200 (CEST) ARC-Seal: i=2; cv=pass; a=rsa-sha256; d=open-mesh.org; s=20121; t=1695909140; b=D4kyFrQ4M3rAX37PaY6CqKuRaJQRHH6f99TF+CaV8b6HExspuxhnj1RrE/WAlvDohVKwH syNItLr3Fd9xLDGRaukBGEbx9qjDmxYpD8/xje/sT08EAeGxNgdB89bNoNsYdZfvq4qSsuJ rJ+u7bQOrFcjdzmbU3E8LrnxedyjpkY= ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=open-mesh.org; s=20121; t=1695909140; h=from : sender : reply-to : subject : date : message-id : to : cc : mime-version : content-type : content-transfer-encoding : content-id : content-description : resent-date : resent-from : resent-sender : resent-to : resent-cc : resent-message-id : in-reply-to : references : list-id : list-help : list-unsubscribe : list-subscribe : list-post : list-owner : list-archive; bh=ZhX1o4UmndOpZvway/9WTvP/GJW+Irk2ZupNKK2HL0Y=; b=s+4Z5XiaItAOC5bonKkyOwrb+ogFgaip9IbMgqnHGLNRIsp2dA0Xfa3kS6CwsmoWj61YZ dBd92kB8DZSU8z5CY0TKw+19C47RV6sGPo1+iY8tCjx/3AhO10HiRI0Cn/2exOv5vkpDQNi tPOck/oBDEBJ32p4w3LVXA7mdJLMa0w= ARC-Authentication-Results: i=2; open-mesh.org; dkim=fail; arc=pass; dmarc=fail (Used From Domain Record) header.from=triplefau.lt policy.dmarc=quarantine Authentication-Results: open-mesh.org; dkim=fail; arc=pass; dmarc=fail (Used From Domain Record) header.from=triplefau.lt policy.dmarc=quarantine Received: from relay1-d.mail.gandi.net (relay1-d.mail.gandi.net [IPv6:2001:4b98:dc4:8::221]) by diktynna.open-mesh.org (Postfix) with ESMTPS id E6A068324D for <b.a.t.m.a.n@lists.open-mesh.org>; Thu, 28 Sep 2023 14:40:41 +0200 (CEST) ARC-Seal: i=1; s=20121; d=open-mesh.org; t=1695904842; a=rsa-sha256; cv=none; b=C+IwYvI7w0ciQSanJizfslhTTOhZ7OLab046a/+DR0q+ELYgWkI6g3KdM2uo8b0q7Fdwmz oanP3PrO85W43uXmnxV1uv3Kjkvwh541gXsVxdYovxmTAkr8PdBIWzXSou2kAwWBwscjNo ZtYia0PZJ1+mKTQ0Q1+Nvp6shN8bZSE= ARC-Authentication-Results: i=1; diktynna.open-mesh.org; dkim=none; dmarc=none; spf=pass (diktynna.open-mesh.org: domain of repk@triplefau.lt designates 2001:4b98:dc4:8::221 as permitted sender) smtp.mailfrom=repk@triplefau.lt ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=open-mesh.org; s=20121; t=1695904842; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=ZhX1o4UmndOpZvway/9WTvP/GJW+Irk2ZupNKK2HL0Y=; b=2CnXfz0fpfalr6zxTAC+TtEH3sjnshz+c02NwP0UCnZb1mdaNkGm+1uYyWjbBZuScysWYl qwgDt2G+H4FgXxBufk975E3w/o0VxjGq1Ga8qy1twMusMauwvUu1xM4LY8SHzP2V8EUROc nYt2VRZnr3//5ZtxbMTMi61cdB5uYqc= Received: by mail.gandi.net (Postfix) with ESMTPSA id 5361F24000B; Thu, 28 Sep 2023 12:40:41 +0000 (UTC) From: Remi Pommarel <repk@triplefau.lt> To: b.a.t.m.a.n@lists.open-mesh.org Subject: [PATCH RFC 2/2] batman-adv: Better half duplex penalty estimation Date: Thu, 28 Sep 2023 14:39:36 +0200 Message-Id: <09c086e5e68055e52d1f92ba17d0e921084107e7.1695904299.git.repk@triplefau.lt> X-Mailer: git-send-email 2.40.0 In-Reply-To: <cover.1695904299.git.repk@triplefau.lt> References: <cover.1695904299.git.repk@triplefau.lt> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-GND-Sasl: repk@triplefau.lt X-MailFrom: repk@triplefau.lt X-Mailman-Rule-Hits: nonmember-moderation X-Mailman-Rule-Misses: dmarc-mitigation; no-senders; approved; emergency; loop; banned-address; member-moderation; header-match-b.a.t.m.a.n.lists.open-mesh.org-0; header-match-b.a.t.m.a.n.lists.open-mesh.org-1 Message-ID-Hash: NFD5JGXOTVUD2YQCK6TC24XGTTSFHRAB X-Message-ID-Hash: NFD5JGXOTVUD2YQCK6TC24XGTTSFHRAB X-Mailman-Approved-At: Thu, 28 Sep 2023 15:50:50 +0200 CC: Remi Pommarel <repk@triplefau.lt> X-Mailman-Version: 3.3.8 Precedence: list List-Id: The list for a Better Approach To Mobile Ad-hoc Networking <b.a.t.m.a.n.lists.open-mesh.org> Archived-At: <https://lists.open-mesh.org/mailman3/hyperkitty/list/b.a.t.m.a.n@lists.open-mesh.org/message/NFD5JGXOTVUD2YQCK6TC24XGTTSFHRAB/> List-Archive: <https://lists.open-mesh.org/mailman3/hyperkitty/list/b.a.t.m.a.n@lists.open-mesh.org/> List-Help: <mailto:b.a.t.m.a.n-request@lists.open-mesh.org?subject=help> List-Owner: <mailto:b.a.t.m.a.n-owner@lists.open-mesh.org> List-Post: <mailto:b.a.t.m.a.n@lists.open-mesh.org> List-Subscribe: <mailto:b.a.t.m.a.n-join@lists.open-mesh.org> List-Unsubscribe: <mailto:b.a.t.m.a.n-leave@lists.open-mesh.org> |
Series |
Better throughput estimation on half duplex interfaces
|
|
Commit Message
Remi Pommarel
Sept. 28, 2023, 12:39 p.m. UTC
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(-)
Comments
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...
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, oth = ntohl(ogm->throughput); lth = ewma_throughput_read(&neigh->bat_v.throughput); - if ((ogm->flags & BATADV_V_HALF_DUPLEX) && lth > 10) - lth /= 2; + if (!(ogm->flags & BATADV_V_HALF_DUPLEX)) + return min_t(u32, lth, oth); - return min_t(u32, lth, oth); + /* OGM throughput was divided by two for retrocompatibility sake */ + oth *= 2; + return oth * lth / (oth + lth); } /**