Fuzzy/Thick directed paths

[redxdev]

Right now if you send a direct message if you previously have known a path then you depend on every repeater in that path being available. This is not super reliable, especially when sending with a spotty connection, and means that you end up having to fall back to a flood message. On larger meshes it is best to reduce flood traffic wherever possible, so I'm proposing a step in between direct and flood routing, using "fuzzy" or "thick" paths instead of direct paths.

The problem with anything that is in between direct and flood is, of course, the lack of routing information in the mesh. But repeaters already collect one extra bit of routing info that isn't currently used: direct (0-hop) neighbors. Thus, my proposal is that a "fuzzy" path would not just have repeaters directly in the path repeat the packet, but also any 0-hop neighbors of those repeaters.

To illustrate, let's say we have repeaters A, B, and C - all neighbors of each other, and my destination companion of D. I send a message with a path of A,B,D but B fails to respond. On my second try, I send using a "fuzzy" path of A,B,D - B still fails to respond but C, knowing that it is itself a neighbor of B, repeats (making the resulting path A,C,D).

The repeater's logic would effectively be this:

• If fuzzy path
  • If I'm part of the path - > repeat
  • If I'm not part of the path, but a known neighbor is -> repeat
  • Otherwise -> don't repeat

The effect is sort of localized/directed flood routing that doesn't require any new routing information or communication beyond what repeaters already collect, and in theory it raises the chances that contact with the destination is made if the direct path previously failed.

The immediate problems that come to mind that would need solving:

• Figuring out how to flag a packet as requesting a fuzzy path, without breaking backwards compatibility.
  • Ideally old firmware would be able to treat fuzzy paths the same as direct paths, but this might simply not be possible with the current protocol.
  • One "easy" (but maybe not good) option for flagging a fuzzy path would be to use FF or 00 as the first or last member of a path. Though I'm not sure if those were reserved for some other purpose.
• When should fuzzy paths be used?
  • The first thing that comes to mind is to use it as part of retry logic when a DM isn't ack'd, after attempting a direct path and before a flood. But maybe there are other times it'd be useful to use.
• How should a packet's path be modified when a different repeater than intended repeats the message?
  • I would assume it should replace the neighbor it repeated for, but this begs the question of how to handle a path where the repeater is neighbors with multiple others in the path - which does it replace? All neighbors? The first? The last? I don't think there's info about how far a packet has traveled on a path so it becomes difficult to figure out where in the path a repeater has been changed.
• Should a fuzzy path result in a companion updating the path it has to another companion?
• What kind of settings should repeaters have for fuzzy paths?
  • We would probably want controls over the max age of neighbors to consider (don't repeat messages for neighbors if you haven't heard from them in over x days - there's a point at which new paths should be established) and minimum RSSI (don't repeat messages for neighbors if you haven't heard them strongly enough, as that might mean you're pretty far away from the path).

I'm not super knowledgeable about designing mesh networks and maybe there's something problematic I've overlooked with this idea, but I wanted to start a discussion on whether this is something reasonable to look further into.

[redxdev]

Having thought about this some more, I have an idea to solve how packet paths should be modified.

First, the issue:

Let's say I send a fuzzy-pathed packet with a path of A,B,C. Repeater D is a neighbor of both A and B. My companion sends the packet with the path FF,A,B,C - using the FF to signify that the path is intended to be fuzzy.

Repeater A is busy, but repeater D hears the packet and repeats it, modifying the path to be FF,D,B,C. So far so good, however this causes a problem: neighbors of repeater D are now going to hear this packet and repeat it as a fuzzy path even if they're more than one hop away from the original path (as they think the path now has a D in it, with no way to know that it was originally A). This would mean the fuzzy path turns into a normal flood - not what we want!

Here's my solution: we move the FF fuzzy signifier to denote what parts of the path are allowed to be fuzzy. Every time a repeater rebroadcasts a packet, it moves the FF ahead of itself in the path. To illustrate with the same situation:

Repeater A is busy, but repeater D hears the packet and repeats it, modifying the path to be D,FF,B,C. Any repeater hearing this newly repeated packet now knows NOT to do a fuzzy repeat for anything before the FF, thereby preventing the packet from turning into a flood.

[redxdev]

I'm actually realizing now that repeaters seem to remove themselves from paths as they receive them, so moving the FF isn't actually necessary and this implementation may actually be way simpler... maybe as simple as just having FF at the end of the path. Need to test it.

[redxdev]

Ok yeah, my misunderstanding of how direct paths get repeated means this is actually a lot simpler than I thought, though at the same time fuzzy paths will require that the receiving end of a fuzzy-path-packet must be up to date (as annoyingly the target of a packet seems to ignore that packet if it isn't down to 0 hops).

[redxdev]

So actually... this means that paths don't need any kind of replacement when a "fuzzy" repeater picks up the repeat. Which does make this idea much simpler to implement, but it also removes the possibility of updating a path via an ACK back to the sender with the newly found fuzzy path. Oh well.

[redxdev]

I've made a draft PR that contains an initial implementation of fuzzy paths: #2648

I still want to come back to the idea of the entire path being present instead of removing one hop every time there's a repeat, but this is good enough to start soliciting feedback on.