Proposal: Use re-transmission for direct messages for more reliability and less floods

[usrflo]

Problem Definition / Motivation

My tests with repeated direct messages show an unreliability of approximately 45% from my location as soon as the path length is greater than or equal to 2. This means that almost half of the direct messages fail via a partially functioning path with more than 2 nodes.

Ultimately, my client too often resorts to flooding on the last attempt, generating a lot of traffic.

Problem solution 1, neighbours/repeater swarm

For greater resilience, I suggest including a repeater's neighbor list in direct messages: if there are two neighbors listed at positions 1 and 2 of the path, a repeater could repeat a packet.
Along the path, a "swarm of repeaters" would thus ensure more reliable delivery and reduce the final floods.

Currently:

  if (pkt->isRouteDirect() && pkt->path_len >= PATH_HASH_SIZE) {
    if (self_id.isHashMatch(pkt->path) && allowPacketForward(pkt)) {
...

Swarm approach modification to give an idea:

  if (pkt->isRouteDirect() && pkt->path_len >= PATH_HASH_SIZE) {
    if ((self_id.isHashMatch(pkt->path) || (pkt->path_len > PATH_HASH_SIZE && twoNeighboursMatch(pkt->path, $neigbours))) && allowPacketForward(pkt)) {
...

The function "removeSelfFromPath(pkt)" could still be used more common as "removeFirstFromPath(pkt)" to shorten the path.
As the neighbor list contains SNR information the noise ratio could be used in addition to decide about a valid neighbor match.

Visualization of the Swarm Approach

[rvleij]

I think the issue would be with this proposal that it's not necessary around the original discovered path, right? Sometimes I see paths going completely around the other way, which is what would be used in flood. This approach would use something close enough to the original path, but that would only work in very dense deployments I think, where there are alternative repeaters around and within reach.

Maybe an alternative approach would be to "remember" the original path length and then do the flooding with a max hops set to slightly higher than the original path, to at least optimize this traffic? Also would become an issue if the alternative path is much longer of course, so I'm not sure what we can win here. I kind of believe in the original fundamentals of the protocol as it is, even though it's not perfect. Unless I misunderstand something.

BTW Not sure if MC has a max_hops in the protocol, I'm coming from MT. :)

[usrflo]

This proposal addresses the following problems:

(A) repeaters on the path cannot receive because of a temporary radio interference
(B) repeaters on the path don't listen because they are sending or the airtime is reduced
(C) direct sending must be used multiple times to succeed because of (A) and (B)
(D) too many floods are sent out after (C), direct sending via a given path, fails multiple times

The use of neighboring repeaters that know the first and second node on the path would improve the reliability in a transparent way.
I agree the success of this approach clearly depends on the density of repeaters along the path.

[rvleij]

Interesting scenario and potential solutions I think, happy to think a bit about this as well.

A potential risk with the swarm approach would be that you create more collisions since now multiple neighboring nodes are also (re)transmitting those packets in the fail scenario. Since this only works in dense deployments, it also introduces that risk, right?

Also, how would the sending node know that for the Xth attempt it'd send it to the other neighbor? Wouldn't this require control traffic on the air to indicate for each neighbor if they're also seeing commonalities along the whole path? So I mean, how would the blue guy know to send it to the yellow guy (i.e adjust the path) and where is this SNR and neighbor info shared across the whole path, since I think we're lacking telemetry?

Maybe as an alternative: "Delayed Opportunistic Forwarding" (DOF)?
Instead of a simultaneous swarm, MeshCore should implement a coordinated local repair mechanism. This provides the redundancy of a swarm but uses timing to prevent collisions and minimize airtime.

Instead of a node simply checking if it's a neighbor, it should use a Backoff Timer based on its role.

Primary Forwarder (Designated Next-Hop): Forwards the packet immediately (after the standard tx_delay).

Helper Candidate (The "Swarm"): If a node hears a packet and is not the designated next-hop, but its neighbor table shows it can reach the next-next hop, it enters "Helper Mode": It caches the packet and sets a Helper_Timer (e.g., 3 * tx_delay).

It listens to the airwaves. If it hears the Primary Forwarder transmit the packet within that window, it discards its own cached copy.

If the timer expires and the air stayed silent, the Helper assumes the primary link failed and transmits the packet, skipping the failed node.

One other idea could be to listen of the next-next hop (which is also reachable otherwise we wouldn't trigger this functionality in the first place), if the next-next hop doesn't retransmit, that could also trigger the "helper retransmit".

Disclaimer: I'm not a mesh expert, just have been spending too much time on MT and now MC :)

[usrflo]

@rvleij , thanks for your valuable input; I am short in time so just a short answer, more will follow:

Each repeater knows its neighbors and saves the last snr value, see

struct NeighbourInfo {
  mesh::Identity id;
  uint32_t advert_timestamp;
  uint32_t heard_timestamp;
  int8_t snr; // multiplied by 4, user should divide to get float value
};

The path of the direct message doesn't need to be adapted in my view but yes, a neighbor could re-transmit a delayed package if it has both neighbors from path position 1 and position 2 in its neighbor list but doesn't recognize the package sending of the repeater at position 2 as a potential error correction. This kind of dependency would require another queue that saves packages and processes them as long as they are not seen again from the expected downstream repeater. I will re-think on this.

[usrflo]

Problem solution 2, direct re-transmission by sender

While trying to implement the approach to resend a package by a well connected neighbor if it was not seen from the next repeater (=same checksum and one path element shorter) I started to think about using the repeaters on the path only and let them re-send already sent packages if they don't recognize the same package being sent by the next repeater. This would mean a potential error correction inside one transmission but wouldn't use the resilience of a "swarm".

Scenarios for repeated sending with a defined path (DIRECT)

A)

B)

Error rate consideration

Just for a rough estimation: let's assume the error rate p_error between the n nodes involved in a communication is equal.

So the total success rate of a direct sending with the current implementation is:

P_total_success(n)=(1−p_error)^n

If a node tries to send a packet for 2 more times if it doesn't recognize the package being sent by the next repeater this probability would be changed to:

P_total_success(n)=(1−p_error^3)^n

Sample data

Assumed the error rate p_error is 10%:

#nodes	1 sending attempt	3 sending attempts
1	0,9000	0,9990
2	0,8100	0,9980
3	0,7290	0,9970
4	0,6561	0,9960
5	0,5905	0,9950
6	0,5314	0,9940
7	0,4783	0,9930
8	0,4305	0,9920
9	0,3874	0,9910
10	0,3487	0,9900

Conclusion

Besides the idea to include well connected neighbors in a "repeater swarm" the simpler repetition of an already sent package for max. 2 times may considerably increase the delivery success.

Question

Is a repeater fast enough to switch back to "receive" after sending to recognize the downstream package?

[usrflo]

I implemented the proposal of a repeated sending of packages (solution 2, see above) in https://github.com/usrflo/MeshCore/tree/repeated-sending

Please check the files changed at usrflo@37b1d92 and the differences to the MeshCore/dev branch at dev...usrflo:repeated-sending
It would be great to get some feedback.

@rvleij, thanks for your input to listen on downstream re-transmissions; the implementation removes direct packages that are prepared for re-transmit if they are heard (again). I proposed 3 attempts at max. The re-sending happens between repeaters on the path only. A re-sending to the final/target node is suppressed as this node should confirm via ACK IMHO.

BTW: I changed the way package hashes are saved on the queue(s). That way multiple calculations should be prevented.