Meshtastic

Mesh-Routing algorithm

Welcome @benner!

Valuable discussion. :slightly_smiling_face:

DTN protocols: Routing in delay-tolerant networking - Wikipedia

DTN routing strategies: https://www.netlab.tkk.fi/opetus/s383151/articles/dtn-routing-survey.pdf

Also, please, take a look at this:
https://www.researchgate.net/publication/332241035_Delay-Tolerant-Networks_-Architecture-Routing-Congestion-and-Security-Issues

Mostly for use cases, not security

µD3TN currently supports two platforms:

  1. The STM32F4 embedded platform running FreeRTOS
  2. All POSIX-compliant operating systems (plus Linux ;-))

I think it should not be hard to port to ESP32 because of same FreeRTOS is inside esp-idf

I read this a bit, it looks nice.
Someone should be an ambassador and contact them!
They seem open to collaborate with other projects, and It’s possible that they’ll answer the call…
I like the stor-forward and custody-transfer protocol.
On a side note, they seem more focused on one-way communication, and it may be a problem.
What do you think?

DTN, per se, is not one way communication protocol set. It more like optimized to asynchronous links (e.g. with different link latency/speed or different paths between sender and receiver).

Do anyone know if this algorithm is ready to use as a package?

If so, a simple approach is to assign to the router the task of computing the shortest path where the weight of the edge is the dB received by one node.
I have a more complex idea, but if the Dijkstra algorithm is too hard to implement it makes no sense.

Dijkstra is a common algorithm to use whenever you have unknown but static environment. The challenge of meshing is to cope with both, a changing and unknown environment. Dijkstra would require a node or router to know/discover the whole Mesh.

Personally I really like the Approach DTN/Licklider/PRoPHET (ION Framework) takes, but it still seems a lot of overhead for a lightweight LoRa Mesh.

On Wikipedia I read through the Article on routing in DTNs and really liked the idea of RACOD
I don’t know wether it is allowed to implement this (I am not a lawyer neither studied anything), but I think the combination of PRoPHET and ANT Optimization might result in a pretty clever Algorithm.

Something like: whenever you receive a packet, remember the source of the packet and the transmitter of the packet and increase the probability to reach that address via the transmitter.
Once you meet a new mesh node, exchange probabilistic-routes. Maybe this is an easy optimization to the simple flooding.

Hi,
I feel like that most of it depends on the use-case that we imagine.
If the main scenario is hiking/rescuing in the mountains, with people moving around a lot, i believe a DTN approach is appropriate.
Instead if the main use is similar to ham-radio, where most nodes are static and only few moving, the best approach may be a ‘shortest-path’ one.
In any case we need to define the goal, then we can tackle the right algorithm.
What direction we want to take?
How can I help?

I had a thought for a very simple and resource-aware implementation of the Dijkstra algorithm:

  • new node transmit a ‘welcome’ message
  • each node re-transmit after a time proportional to the dB intensity
  • the first train of messages reaching the router is the best one.
    This can allow for a self-managed resources: if a node is low on battery, has too many messages passing trough, ecc ecc it simply delays more the re-transmission, signaling that it is not the best path anymore.
    Give it a thought…

You could also make stationary nodes (the ones that hypothetically have more power and less battery conservation needs) send out welcome messages hourly (or some other interval) to re-optimize their understanding of the nodes around them that moved. Although this could cause moving nodes to use more battery by hourly replying. (Total noob to the current algorithm running commenting, please inform if my conjectures are way off)

Just kidding why send out a welcome hourly when you can simply re-optimize the network map based on the acknowledge responses every time you pass or send a message.

I plan on mounting routers to drones and having a mobile network used for disasters

3 Likes

Yes, the idea should be that the ‘router’ update the list (and therefore the paths) of nodes only when a node actively seeks to send a message.

  • node A send message
  • node B/C/… receives it, if they know a path they deliver the message to the final recipient
  • else they wait a time dT proportional to the signal intensity dB and then forward to the router
  • the router compute the shortest path for node A to all other nodes and then forwards the message

The router sends new paths only to nodes that needs updates and only when a new path is needed (eg. a node has changed position in the network/ a new node appeared)
The dT at which the message is received by the router is an empirical solution of the Dijkstra algorithm.

Furthermore this approach could be built on top of the naive-flooding structure, as flooding is what happen if no router coordinates.
If there is more than a router in the network they can prioritize themselves in the eye of the others as having a very small dT - hence we have that dT is in itself the system that all nodes use to declare their resources to the rest of the network.

This thread may be interesting to some of you. It explores mesh routing over LoRa.

It starts from LoRaLayer2/README.md at master · sudomesh/LoRaLayer2 · GitHub which Kevin looked at and decided against.

But the conversation broadens to Pro/Reative routing, Geographical routing etc.

1 Like

If you read the last post on development, reticulum is cited, and a very similar solution to the one i proposed to the path finding problem is proposed!
I thin that if we get a better function for forwarding than the one proposed in the
docs page 7 step 1 we can have a very compelling solution!

Reticulum
Despite still in alpha since 2018, Reticulum poses itself as a game changer in LoRa-based networks. Its approach resembles OTR ( off the record messaging) featuring perfect forward secrecy, self-pairing and configuration, anti-tampering and easily allowing to switch from LoRa to BLE or WiFi as transmission medium.
A con is that it needs at least 1kbps, probably a bit less if properly configured. Super low-speed data transmissions would be left over.
Read more

I have some extra wifi access points and lora esp32 devices and thought it would be cool to try Reticulum. After an hour I gave up on finding a how to for implementing a simple network. I think we would need a lot of help from Reticulum’s developer to implement it and create step by step directions for standing something up in real life.

Reading Retculum and Disaster.radio I think we could start form the git-hub of LL2 (Protocol · sudomesh/disaster-radio Wiki · GitHub) and modify it to obtain a viable code without too much hassle.
Where should I push the request?

1 Like

I haven’t followed this full thread - but if you want to make an alternate transport (possibly even replacing the current transport) for meshtastic I think that’s great. If he helps, in the early days of this project I hoped to share a common implementation with the layer2 of disaster.radio, but alas after a fair amount of investigation it seemed to me their current implementation was not suitable. This thread I started over there had some good discussion on that idea.

I have no idea on how to start the code - any tips?
Code language?
How to make a fork?
Where is the code used now for the meshtastic?
Thanks!

1 Like