Meshtastic needs a routing protocol

[mkrzywonski]

Managed flooding is clever, but it does not produce an optimal network. In fact, for some users it does not produce a functional network. For example when trying to extend the network to far away nodes, it may select close nodes with poor RF reception rather than nodes that are truly far away. This is not optimal. And it ignores closer nodes who may be the only path to other clients with no direct line of site to the larger mesh, making the network completely non-functional for them. This is not functional.

We need a routing protocol to solve these problems. it should adjust dynamically as the network grows and as the topology changes.

I propose that the Meshtastic protocol be extended to include routing updates as follows:

Proposed Meshtastic Routing Protocol

Add new role: DYNAMIC to current list (CLIENT, CLIENT_MUTE, CLIENT_HIDDEN, TRACKER, LOST_AND_FOUND, SENSOR, TAK, TAK_TRACKER, REPEATER, ROUTER)

Dynamic clients shall not re-transmit any packets by default. Equivalent to CLIENT_MUTE

Dynamic Clients shall maintain a routing table with the following elements:

• NodeID - 4 byte identifier for a remote node
• Gateway - 4 byte NodeID of the next hop toward the remote node. This should be the same as the NodeID if the remote node and the local node can communicate directly (0 hops)
• Hops - Number of hops between the local node and the remote node (0-7)
• SNR - Signal-to-Noise Ratio (currently used to set the CW for flooding)
• Timestamp - The date and time that the entry was created or last updated
• Interface - The index of the radio or channel on which the NodeID was discovered. This anticipate nodes with up to 8 (indexed 0-7) radios that may act as gateways between mesh networks. For example, a node may act as a gateway between LongFast for geographically remote nodes and ShortFast for local nodes.
• Relay - 1 byte, bits mapped to unique interfaces (radios). Default = 0 (all bits off)

Upon receipt of each packet, Dynamic Clients shall check the routing table for an entry matching the sender's unique NodeID. If no entry exists, a new entry shall be created. If an entry exists, it shall be updated with current values if a) the current packet has a lower hop count and the SNR does not exceed a threshold for poor RF reception, OR b) the current packet has the same hop count and a better SNR, OR c) the current packet has a hop count of 0, in which case the SNR shall be updated to the current value. The SNR poor RF reception threshold should be user configurable.

When a packet is received, if the Sender's NodeID exists in the routing table with a Relay flag != 0, the packet shall be re-transmitted on all interfaces with 1 bits in the relay flag. Otherwise, the packet shall NOT be re-transmitted on any interface.

Entries in the routing table shall be removed when the timestamp is more than 24 hours old.

Dynamic clients should periodically send out routing advertisements on a regular interval. The advertisement interval should dynamically increase with mesh size (number of entries in the routing table). I suggest the interval be (1 minute x the number of locally connected nodes) so the total number of routing updates from all nodes in a local RF broadcast domain don't exceed about one packet per minute on average. Perhaps this interval multiplier should be configurable, defaulting to 1 minute. Routing advertisements shall be sent with a hop count of 0 and shall never be re-transmitted.

Routing advertisements should include records for each node in the local routing table. If there are too many nodes in the routing table to fit in a single packet, the client shall advertise as many nodes as will fit in a single packet and remaining nodes in the routing table shall be sent after the next advertisement interval. It may take several intervals to advertise the entire list for a large mesh.

Routing advertisement shall include the following information (9 bytes per node):

• NodeID - 4 byte identifier for a remote node
• Gateway - 4 byte identifier for next hop from the local node toward remote node
• Hops - number of hops between the local node and the remote node. May be encoded in 3 bits for values 0-7.
• SNR - Signal-to-Noise Ratio of node if 0 hops, or of the gateway if > 0 hops. (May be encoded in 5 bits giving 32 values from excellent to poor signal quality. Hops and SNR may be packed into 1 byte)

All Dynamic nodes should listen for routing advertisements and process them as follows:

The NodeID of the node sending the advertisement shall be known as the PeerID. The local routing table shall be searched for an entry with a NodeID matching the PeerID. If none exists, one should be added. If an entry exists, it shall be updated with the current information of the advertising peer.

For each node in the advertisement, if no entry exists AND the Gateway value in the advertisement is NOT the same as the local NodeID, a new entry for the advertised node shall be added to the routing table. If an entry already exists, it shall be updated.

The NodeID field shall contain the NodeID from the advertisement.

The Gateway field in the local routing table shall contain the PeerID that sent the advertisement

The Hops field shall contain the Hops from the advertisement + 1. If this value exceeds the maximum hop count for the local node, no entry shall be created or updated and the advertisement shall be ignored. If an entry exists in the routing table for the advertised NodeID with a lower hop count and a different gateway, the existing entry shall not be updated and the advertisement shall be ignored. If an existing entry exists with a Gateway matching the PeerID, the Hops field for that entry shall be updated.

The SNR field shall contain the SNR value for the received advertisement packet. If there is an existing entry with the same hop count and a better SNR, the existing entry shall not be updated and the advertisement shall be ignored. If an entry exists with a lower hop count, but with an SNR that exceeds the SNR poor RF reception threshold, the existing entry shall be updated from the advertisement.

The Timestamp field shall contain the current time

The Interface field shall contain the index number for the interface where the advertisement was received.

If the Gateway value in the advertisement is the same as the NodeID of the Dynamic Client, that indicates that the advertising peer has determined that this Dynamic Client node is the best next hop towards the advertised node. We should forward all packets originating from the advertised NodeID to the interface of the peer. We should also forward all packets from the advertising peer's NodeID to the interface facing the advertised node.

• The Relay field in the NodeID's routing table entry shall be updated with the bit mapped to the Interface that received the advertisement set to 1.
• The Relay field for the routing table entry with a NodeID matching the PeerID for the advertisement shall be updated with the bit mapped to the Interface of the routing table entry for the advertised (if such and entry exists) node set to 1.

---

In plain english:

1. After booting up, nodes do NOT forward any packets by default. They passively listen and learn about other nodes, building a routing table which is essentially an extension of the existing node list. The routing should include the node ID of all known nodes. This should include data like hop-count, sending node, SNR, etc. The local node should update the table as conditions change and determine the best next-hop to each node in the table.
2. Nodes should periodically broadcast routing advertisements containing all of the other nodes in their routing table, along with their prefered next-hop to each node. This essentially means that nodes are 'asking nicely' for the best connected intermediate nodes to act as relays for traffic from each specific node in their routing tables. These advertisements should have a hop count of 0 and only be seen by locally connected nodes.
3. Each node that hears a routing advertisement listing themselves as a next hop for a remote node should update their routing table with a flag to forward traffic from that remote node toward the requesting node.

This results in a mesh where the member nodes are dynamically calculating the shortest paths to each other node in the mesh and only forwarding traffic that has been requested by their peers. I believe this will reduce the overall amount of congestion on a mesh by reducing needless flooding, which more than makes up for the additional traffic comprising routing updates. It also means that nodes with obstructed line of sight to the larger mesh can request an intermediate node start forwarding traffic to them. These nodes will often have limited or no connectivity using the managed flooding model.

[garthvh]

Control messages and routing tables add way more overhead than lora can really manage. Paths change all the time with mostly moving nodes, a plan like this has come up every two weeks for 5 years and this is the only one even remotely close to being implemented meshtastic/firmware#2856

[mc-hamster]

@mkrzywonski If you'd like to prototype something and contribute it to the project, we'll gladly accept it.

Please keep in mind that we have a broadcast medium and not a switched medium, so there is no real concept of a "direct path".

[ikearat]

I tried to discuss this (Meshtastic) with a friend who provides network support where he lives. Has all the credentials, works for a company that spends a lot of money on their infrastructure. I'm trying to drum up collaborators in my new activity. I couldn't get past the first few parts of how Meshtastic is set up before the "thought firewall" went up full strength. Perhaps the word "network" should be reviewed so that the commonly assumed conditions don't jump right in front of any serious discussion. How about "mesh interconnection" or "radio distributed data". Maybe a new acronym or initialism would separate the hard network precepts from what Meshtastic is doing. Mesh Blanket Local Area Communication, MBLaC or Meshtastic Flood Protocol, MTFP. Or just substitute the word "interconnect" for network.