[LXMF] Making the Propgation Net Better and More Scalable

[LinuxinaBit]

I've been thinking about ways the LXMF propagation node system could be improved and beyond #837 I think I have a pretty good idea of how I can be made better, faster, more efficient, and more scalable.

Right now the propagation net relies entirely upon store-and-forward flood routing which is incredibly inefficient and (in most cases) entirely unnecessary because of the network layer Reticulum provides.
Plus it runs counter the entire concept of Reticulum.

My idea revolves around avoiding any use of the propagation node peering system wherever possible (and disabling it by default).
Instead an LXMF peer would somehow append their own preferred/trusted propagation node(s?) onto their announces, and a node attempting to send that peer a message while they are offline would not send it to their own trusted propagation node, but to the recipient's instead.
Messages sent in that way would then no longer be propagated beyond that single node.
This helps relieve the exponentially ballooning size of a propagation network and makes message reception much faster as nobody has to wait for messages to sync across a propagation net.
This is the best way I see for LXMF propagation nets to be scalable without a ton of manual configuration.

[LinuxinaBit]

This assumes, of course, that there aren't any glaring privacy/security flaws with doing it this way, but assuming trust systems are employed properly, I don't see how there would be any more than the current propagation net system.

This concept would also work well alongside other propagation node peering improvements because those improvements still help whenever propagation node peering is used as a fallback!

[ghost]

Meshtastic has amply demonstrated what flood routing can lead to in larger mesh networks.
I don't understand much about the internal programming, but I expressly support this idea so that RNS will still be usable in the future.

[markqvist]

See post below - don't worry, LXMF does not use flood routing :)

[markqvist]

I think you may have some general misconceptions of how LXMF works, which is understandable, since the only way to know it right now is to actually read the code ;)

LXMF propagation nodes do not use flood routing. That would imply that everything is broadcast multiple times, which would indeed be very inefficient and stupid.

Instead, the LXMF propagation node sync protocol is designed so that every node that wants a particular kind of message actually gets it from someone in a way that tends toward the highest amount of efficiency and lowest latency. Messages themselves are never transmitted to a node more than once, and before messages are transferred between nodes, they run a precursory negotiation to establish which messages need to be transferred.

Currently, the possible configuration space of what determines which messages a node actually wants is a bit shallow though, and it was always the intention to expand this to a more complex system that would allow automatic network stratification and load-sharing once the core protocol had its kinks worked out - a point we are now reaching.

The 0.9.0 release of LXMF adds the groundwork for this, with a more dynamic peer signalling system embedded in destination announces, specifically from LXMF.py:

# Optional propagation node metadata fields. These
# fields may be highly unstable in allocation and
# availability until the version 1.0.0 release, so use
# at your own risk until then, and expect changes!
PN_META_VERSION        = 0x00
PN_META_NAME           = 0x01
PN_META_SYNC_STRATUM   = 0x02  # <-- Relevant target strata structure for node
PN_META_SYNC_THROTTLE  = 0x03
PN_META_AUTH_BAND      = 0x04
PN_META_UTIL_PRESSURE  = 0x05
PN_META_CUSTOM         = 0xFF

The idea of naively embedding a preferred PN in LXMF delivery endpoint announces would run counter to the idea of LXMF, since it would:

• Have pretty big privacy issues, if everyone had to broadcast to the entire network where they want their messages to end up
• Become an easy attack vector. If you want to mess with a user, it's now very easy to single out a DDoS target.
• Centralize the currently distributed nature of LXMF, and introduce single points of failure to message delivery. The whole point is to have an automated, distributed message store, where people don't have to "pick" a single point of failure like in e-mail, Internet-based instant messaging, and other similar system. You want to be able to download your messages from a large number of nodes, so that if one or many go down, you can still get messages sent to you.
• Require manual hand-holding and configuration for all users. Ideally, we want a system where most users can just fire up an LXMF client, and it will automatically find suitable nodes to send and receive messages through, and simply switch these out on demand if the network topology changes, nodes become unavailable, or the user moves to a completely different network segment.

LXMF aims to have as many messages stored and ready for download as possible within the resource limits specified by the node operator. As I've discussed before, this is the true "concept of Reticulum" - to use allocated resources as intelligently and efficiently as possible, and when resources are exhausted to make intelligent decisions on how to deal with such situations; automatically as long as possible, but when necessary with human intervention.

Ideally, any given area of a physical network should have all relevant LXMF messages available in a distributed store, with some level of redundancy. That does not mean that every node has to store every message, but we want a situation where at least every local network area has as good an approximation towards that as physically possible within resource constraints.

All of this is entirely possible within the limits of current technology, even on relatively modest hardware.

[LinuxinaBit]

That makes sense, thanks for explaining 👍

[joakim]

Thanks for the explanation!

As I've discussed before, this is the true "concept of Reticulum" - to use allocated resources as intelligently and efficiently as possible, and when resources are exhausted to make intelligent decisions on how to deal with such situations; automatically as long as possible, but when necessary with human intervention.

"The concept of Reticulum" should be in the manual :) It already is inbetween the lines, but having it spelled out like that really helps with understanding Reticulum.

[ghost]

That sounds completely different than I had previously thought. I have had terrible experiences with Meshtastic, where the way it was distributing (especially with LoRa devices and the limited airtime) rendered it unusable.

However, I am pleased that this does not seem to be the case with Reticulum.

[markqvist]

Yes, and when sending messages to a device, they will always be delivered directly by default, and this of course happens directly over Reticulum's routing, using the most efficient path currently available (or, Reticulum's best guess as to what that is - we can't know the best path, in absolute certainty of course, but in practice it is pretty close).

If a device you want to send to is not available on the network for direct delivery, LXMF can try to deliver it via the propagation nodes instead. In this case, the following happens:

• Your device encrypts the message with the destinations ratchet keys. Only the final destination hash of the message is visible, and no information about where the message was sent from, or anything else for that matter, is revealed in the data.
• Your device computes a propagation stamp and attaches it to the message (this makes spamming the network very costly, but is negligible for normal use)
• Your device establishes a direct and efficient connection with a propagation node. This could be a preferred node you have chosen yourself, or a node selected automatically based on network topology or other parameters.
• The connection to the PN is established anonymously, and does not reveal your identity or address. The PN has no idea where the message is coming from, or if the device delivering it is even the originator, or simply passing it on from someone else.
• Your device hands the message over to the PN, and the PN verifies if the propagation stamp is correct. If the stamp is correct, the message is scheduled for distribution queue mapping.
• The PN now determines which other nodes it is peered with would want to have a copy of this message, and adds it do distribution queues for these nodes.
• The PN periodically connects with other nodes, offering them messages they might want, and only transfer the messages if they actually want them
• No messages are ever transferred to a given propagation node more than once.
• Distribution queues between nodes are prioritized according to a weighting algorithm, ensuring that large messages don't hog up the network.
• After some time, messages expire and are removed from the message store of propagation nodes.
• When messages are downloaded by a client, they are removed from the message store (full distributed signalling of this across the entire PN network is not implemented yet, since it depends on another primitive related to sync stratification, but it is coming soon).
• If the resource limits of a node is reached, it cleans out messages according to a weighting algorithm, and tries to keep as many relevant messages as possible, while staying within the defined resource limits.

Now, the main problem that had occurred over the past few months was that while stamps were required to message users directly, making it hard to spam individual users, it was essentially "free" to deliver invalid messages to the propagation network.

Of course, you couldn't actually get unstamped or invalidly stamped messages to be accepted by a destination, even if they were delivered over the propagation network, but what you could do, was just upload massive amounts of random or invalid messages to the network, which would waste a lot of resources for all the involved PNs. Some of my nodes were processing millions of messages a week, for "users" that probably didn't even exist, since the network never saw any announces for them.

With LXMF 0.9.0, this has now been solved, since it would be exceedingly expensive (computationally) to send that many messages to the propagation network, while it is still essentially free (computationally) to validate and process them.

[ghost]

"Yes, and when sending messages to a device, they will always be delivered directly by default, and this of course happens directly over Reticulum's routing, using the most efficient path currently available ..."

That's quite different to Meshtastic. MT sends (till today?) mostly by a watering can principle. One of the drops (sent messages) will eventually reach the right recipient. And don't forget the many redirects.

That of course takes resources (airtime). 🙄

Thank you for the detailed explanation.