Question about broadcast suppression in the flooding mesh algorithm

[XinyuTan1985]

Hi,

I'm trying to understand the logic of the flooding algorithm in Meshtastic versions after 1.3. My understanding is as follows:

• Prioritized Rebroadcast: A node farther from the original sender (with a lower Signal-to-Noise Ratio, or SNR) will schedule its rebroadcast sooner than a closer node.
• Redundancy Suppression: A node will cancel its scheduled rebroadcast if it hears the same packet from another node before it transmits.

This leads me to a question about a potential edge case, as illustrated in the diagram below.

1. Node 0 sends a broadcast.
2. Nodes 1 and 2 both receive it. Node 1 is farther from Node 0 than Node 2 is.
3. Following the rules, Node 1 will rebroadcast the packet first.
4. Node 2 hears this rebroadcast from Node 1 and, to avoid redundancy, cancels its own scheduled transmission.
5. As a result, Node 3, which is only in range of Node 2, never receives the message.

Is my understanding of the algorithm correct? If so, is this scenario a known and tolerated limitation, similar to the hidden node problem, or is there another mechanism that addresses this situation?

[korbinianbauer]

Correct, Node 3 would not get the message.

The solution here would be to make Node 2 a Router or (likely a better idea) Router_Late.

Router would rebroadcast before Node 1.

However, that will keep Node 1 from rebroadcasting, so another node within reach of only Node 1 would now not get the message.

[korbinianbauer]

In a scenario without node 4, setting node 2 to ROUTER is enough to reach everyone

In practice there almost certainly is a node 4, and more nodes beyond that, and the Router owner has no way to determine otherwise.

Tiny mesh simulations might make it seem like a Router can be a good idea, by ignoring 99% of a real mesh.

Unnecessary retransmissions can also be considered broken routing

It's inefficient. "Broken" is whatever keeps messages from reaching its recipient.

There simply is no better way to reduce channel utilization than getting rid of duplicate packets.

Getting rid of unnecessary packets in the first place is a better way.

Getting rid of unnecessary retransmissions of useful packets is the second best way, but the current approach is a terrible way of determining which ones are unnecessary duplicates.

It makes delivery unreliable to save a little bit of airtime, while every node is clogging the mesh with unsolicited NodeInfos and Telemetry.

Every Router should be a Router_Late, every transmission should be triggered by a user (directly or through polling), and every node that spams too much should be automatically temporarily blocked from retransmissions.

[GUVWAF]

In practice there almost certainly is a node 4, and more nodes beyond that, and the Router owner has no way to determine otherwise. Tiny mesh simulations might make it seem like a Router can be a good idea, by ignoring 99% of a real mesh.

So a "real" mesh is when it is extended indefinitely with nodes beyond the range of a well-placed central node?
The idea is to assign node 2 as ROUTER if its range is larger than the others, e.g. because it's elevated. Then letting node 1 rebroadcast would create (almost) no additional coverage.

"Broken" is whatever keeps messages from reaching its recipient.

Yes, and one of the biggest cause of that are collisions, which is a result of a congested channel, e.g due to unnecessary rebroadcasts. With your reasoning we'd better let everyone rebroadcast unconditionally "just in case".

Getting rid of unnecessary packets in the first place is a better way.

You're using a shared medium. We can't decide what others deem useful packets, but duplicate packets are certainly not interesting for anyone.
Telemetry is now disabled by default already anyway, and you could've disabled this already before. NodeInfo is definitely very useful for discovery and even required for secure DMs; its default broadcast interval is already very low.

but this is a terrible way of determining what packets are unnecessary.

This is a rather bold statement without telling how it should be done. Or else please show that letting every node rebroadcast unconditionally would be better overall.

to save a little bit of airtime

It might be only a little bit of airtime on average, but the timing of it is also important. Mesh traffic happens in bursts, because nodes try to rebroadcast at roughly the same time. And when a packet triggers an ACK or response, having other nodes trying to still rebroadcast the original message makes the delivery of ACKs/responses unreliable.

every transmission should be triggered by a user (directly or through polling)

So if the battery of my node almost runs out because its solar panel got covered by snow, I should have asked it to tell me that?
If I want to discover new nodes, I should ask around if there is anyone around that I do not yet know? If I want to track my dog I should ask for its position every minute? If I want to know how the temperature changed over time I should ask the sensor node for this every hour?

[korbinianbauer]

So a "real" mesh is when it is extended indefinitely with nodes beyond the range of a well-placed central node?

Not indefinitely, but up to the the hop limit. Otherwise the simulation just masks the downsides of the Router-Role: At the edge of their coverage, they suppress nodes which should be allowed to retransmitt according to the hop_limit.

Yes, and one of the biggest cause of that are collisions, which is a result of a congested channel, e.g due to unnecessary rebroadcasts.

It's one of the two reasons, yes. Congestion and preempting desirable retransmissions.

With your reasoning we'd better let everyone rebroadcast unconditionally "just in case".

Not at all. You can't do better than $c \cdot O( (\mathtt{hop_start})^2 )$ transmissions for a broadcast to reach all nodes in a mesh of diameter hop_start, and Managed Flooding is probably as good as it gets by selecting a sparse sub-mesh to reduce $c$.

But as things are now, Routers mess with that SNR-based thining out process and cut off parts of the mesh that should be reachable within hop_start hops.

You're using a shared medium. We can't decide what others deem useful packets, but duplicate packets are certainly not interesting for anyone.

Agreed.

This is a rather bold statement without telling how it should be done.

Fair. My position here is that Routers must not interfere with the SNR-based selection process.

I can think of 2 ways to achieve this.

A) Make Client roles not abort due to Router retransmissions, as proposed by #8112
B) Have Router not behave differently from Clients for broadcast packets at first.

• Retransmit just like Clients do first (Client contention window CW, SNR based timing, abort on Dupe)
• Then wait for hop_limit * Client CW to make sure the flooding has finished
• Only if they didn't retransmit yet, retransmit now.

The ROUTER role is supposed to make sure a packet is retransmitted from a selected Node that is known to be able to reach parts of the Mesh that the other Nodes might not, right?

I don't think it was intended as a tool to reduce channel congestion. I understand it is being used, even recommended for that for lack of better measures right now, but it's not a good solution.

I believe the way to go is to have a better throttling algorithm, one that manages airtime budgets that smoothly adapt to channel congestion and the number of nodes. One that assigns a fair cost to high values for hop_start and represents the strain this puts on the mesh.

Token Bucket is probably the right starting point, but it has to be adapted to work with broadcasting in a mesh.

So if the battery of my node almost runs out because its solar panel got covered by snow, I should have asked it to tell me that?

On second thought and some napkin math I take that proposal back. I think proper throttling will be more effective than switching to polling.

[GUVWAF]

I don't think it was intended as a tool to reduce channel congestion. I understand it is being used, even recommended for that for lack of better measures right now, but it's not a good solution.

It was certainly taking into account and ROUTER was even deliberately put in its own early rebroadcast window: #2542.
Refraining from rebroadcasting when you hear others do so already is the main idea behind “managed flooding”. Routers are more aggressive with this, but that’s also why there is a big warning when enabling it.

Then wait for hop_limit * Client CW to make sure the flooding has finished

Flooding is not finished after hop_limit * Client CW; you need to take airtime into account as well. But this would be ridiculously long; you waste a lot of airtime and it will certainly lead to dropped packets just like ROUTER_LATE is suffering from already.

• Only if they didn't retransmit yet, retransmit now.

Huh, then you’re describing a CLIENT with more delay?

The ROUTER role is supposed to make sure a packet is retransmitted from a selected Node that is known to be able to reach parts of the Mesh that the other Nodes might not, right?

No, that’s exactly what ROUTER_LATE is for (https://meshtastic.org/blog/demystifying-router-late/). ROUTER gets priority to immediately serve the many nodes it can reach without causing rebroadcasts by CLIENTs that contribute only very little.

I believe the way to go is to have a better throttling algorithm, one that manages airtime budgets that smoothly adapt to channel congestion and the number of nodes.

I’m all for that and there have been many PRs doing exactly that (#5264, #8059, etc.), but on the original transmitter’s side.
Like I said, “channel congestion” is something measured as average over time, but we have to act immediately when flooding is happening. Refraining from rebroadcasting when there are more nodes seems to do the opposite of what you want, because it will lead to less nodes being served.
Also, if all nodes do the same kind of throttling (because their congestion/#nodes statistics are roughly similar), no packet will get through. You’ll need to have some coordination, which comes for free when canceling after hearing duplicates.

A) Make Client roles not abort due to Router retransmissions, as proposed by #8112

Let’s discuss this in that issue.

[korbinianbauer]

Only if they didn't retransmit yet, retransmit now.

Huh, then you’re describing a CLIENT with more delay?

No, it would still always rebroadcast, because if it refrained on a Dupe before (like a client), it would do it after that ridiculous :) long delay.

But I'd much prefer the simpler solution of #8112 anyways, no need to go further into this.

I believe the way to go is to have a better throttling algorithm, one that manages airtime budgets that smoothly adapt to channel congestion and the number of nodes.

I’m all for that and there have been many PRs doing exactly that (#5264, #8059, etc.), but on the original transmitter’s side.

Fantastic, because I'd love to help on that

Also, if all nodes do the same kind of throttling (because their congestion/#nodes statistics are roughly similar), no packet will get through.

Yeah, no, I'm also thinking about getting the origin side right first.

Throttling by refraining from rebroadcasting (beyond what the core SNR-based managed flooding does) should be a secondary layer (if at all) for when nodes are misbehaving or underestimating the congestion further away.