Mesh Broadcast Algorithm
Current Algorithm
The routing protocol for Meshtastic is really quite simple (and sub-optimal). If you want to test its theoretical performance, you can have a look at the simulator. The protocol is heavily influenced by the mesh routing algorithm used in RadioHead (which was used in very early versions of this project). It has four conceptual layers.
A Note About Protocol Buffers
Because we want our devices to work across various vendors and implementations, we use Protocol Buffers pervasively. For purposes of this document you mostly only need to consider the MeshPacket and Sub-packet message types.
Layer 0: LoRa Radio
All data is converted into LoRa symbols which are sent to the radio for transmission. The details are described elsewhere, but it is worth noting that in addition to the converted packet bytes described below, there is also a preamble sent at the start of any data packet.
This preamble allows receiving radios to synchronize clocks and start framing. We use a preamble length of 16, which is longer than the minimum preamble length of 8, to let SX126x LoRa receivers sleep for a while, which lowers power consumption.
After the preamble comes the LoRa Physical Header, which contains information about the packet length as well as a sync word to distinguish networks. For Meshtastic, it is set to 0x2B.
Layer 1: Unreliable Zero Hop Messaging
This layer is conventional non-reliable LoRa packet transmission. A packet generated by a Meshtastic device has the following representation before encoding for transmission:
| Offset | Length | Type | Usage |
|---|---|---|---|
| 0x00 | 4 bytes | Integer | Packet Header: Destination. The destination's unique NodeID. 0xFFFFFFFF for broadcast. |
| 0x04 | 4 bytes | Integer | Packet Header: Sender. The sender's unique NodeID. |
| 0x08 | 4 bytes | Integer | Packet Header: The sending node's unique packet ID for this packet. |
| 0x0C | 1 byte | Bits | Packet Header: Flags. See the header flags for usage. |
| 0x0D | 1 byte | Bits | Packet Header: Channel hash. Used as hint for decryption for the receiver. |
| 0x0E | 2 bytes | Bytes | Packet Header: Reserved for future use. |
| 0x10 | Max. 237 bytes (excl. protobuf overhead) | Bytes | Actual packet data. Unused bytes are not transmitted. |
Packet Header Flags
| Index | # of Bits | Usage |
|---|---|---|
| 0 | 3 | HopLimit (see note in Layer 3) |
| 3 | 1 | WantAck |
| 4 | 1 | ViaMQTT (packet came via MQTT) |
| 5 | 3 | HopStart (original HopLimit) |
Usage Details
-
Packet Header: is described directly by the
PacketHeaderclass in the C++ source code. But indirectly it matches the first portion of theMeshPacketprotobuf definition. Note that the packet header is not encoded using a protobuf, but is sent as raw bytes. This both saves airtime and allows receiving radio hardware to optionally filter packets before waking the main CPU. -
Packet Header - NodeIDs: are constructed from the bottom four bytes of the MAC address of the Bluetooth address. Because the OUI is assigned by the IEEE, and we currently only support a few CPU manufacturers, the upper byte is de-facto guaranteed unique for each vendor. The bottom 3 bytes are guaranteed unique by that vendor.
-
Packet Header - Unique ID: The ID is a large, 32 bit ID to ensure there is enough unique state to protect an encrypted payload from attack.
-
Payload: An encrypted and packed protobuf encoding of the SubPacket protobuf. Only the SubPacket is encrypted, while headers are not. This allows the option of eventually allowing nodes to route packets without knowing anything about the encrypted payload. For more information, see the encryption and Protobuf API Reference. Any data past the maximum length is truncated.
Carrier-Sense Multiple Access with Collision Avoidance (CSMA/CA)
Meshtastic adopts CSMA/CA, similar as to what is used in WiFi. This means that all transmitters must perform Channel Activity Detection (CAD) before attempting to transmit. If the channel is considered busy, the node will wait until it is not anymore. Since once the channel becomes idle multiple nodes might want to start transmitting, a node has to wait a random multiple of slot times. The slot time is the time needed to reliably perform CAD. The amount of slot times to wait is randomly picked from a contention window (CW), which size depends on the current channel utilization. The contention window is larger for a higher channel utilization, in order to limit the chance of collisions.
Layer 2: Reliable Zero Hop Messaging
This layer adds reliable messaging between the node and its immediate neighbors only.
The default messaging provided by Layer 1 is extended by setting the WantAck flag in the MeshPacket protobuf. If WantAck is set, the following documentation from mesh.proto applies:
This packet is being sent as a reliable message, we would prefer it to arrive at the destination. We would like to receive an ACK packet in response.
Broadcast messages treat this flag specially: Since ACKs for broadcasts would rapidly flood the channel, the normal ACK behavior is suppressed. Instead, the original sender listens to see if at least one node is rebroadcasting this packet (because naive flooding algorithm). If it hears that, the odds (given typical LoRa topology) are very high that every node should eventually receive the message. So FloodingRouter.cpp generates an implicit ACK which is delivered to the original sender. If after some time we don't hear anyone rebroadcast our packet, we will timeout and re-transmit, using the regular resend logic.
If a transmitting node does not receive an ACK (or NAK) packet after a certain expiration time, it will use Layer 1 to attempt a re-transmission of the sent packet. A reliable packet (at this 'zero hop' level) will be resent a maximum of three times. If no ACK or NAK has been received by then the local node will internally generate a NAK (either for local consumption or use by higher layers of the protocol). The re-transmission expiration time is based on the maximum time it would take to receive an (implicit) ACK, taking the airtime of the sent packet and any processing delay into account. For direct messages, the intended recipient will also send a real ACK all the way back to the original sender, but the device will only retransmit when it received no ACK at all.
Layer 3: (Naive) Flooding for Multi-Hop Messaging
Given our use-case for the initial release, most of our protocol is built around flooding. The implementation is currently 'naive' and doesn't try to optimize flooding, except by abandoning re-transmission once a node has seen a nearby receiver ACK the packet it's trying to flood. This means that up to N re-transmissions of a packet could occur in an N node mesh.
If any mesh node sees a packet with a HopLimit other than zero, it will decrement that HopLimit and attempt re-transmission on behalf of the original sending node. In order to promote letting nodes that are further away flood the message, such that the message eventually reaches farther, the contention window (see Layer 1) for a flooding message depends on the Signal-to-Noise Ratio (SNR) of the received packet. The CW size is small for a low SNR, such that nodes that are further away are more likely to flood first and closer nodes that hear this will refrain from flooding.
Example
Below you see an example topology consisting of four nodes, where at a certain point node 0 wants to send a broadcast message. Due to limited coverage, it only reaches nodes 1 and 2. Since node 2 is farther away, its SNR is lower and therefore starts rebroadcasting earlier than 1. After node 0 received this rebroadcast, its message is acknowledged. Note that a message is already acknowledged once a rebroadcast from any Meshtastic node (whether or not it has the same encryption key) is received. Since node 1 heard the rebroadcast by 2, it will not rebroadcast again. Node 3 heard the message for the first time and the HopLimit is not yet zero, so it starts a rebroadcast for potential other receivers.
