Skip to main content

Mesh broadcast algorithm

Current Algorithm

The routing protocol for Meshtastic is really quite simple (and suboptimal). 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 Subpacket 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 preable length of 32, which is longer than the minimum preamble length of 8, to maximize the amount of time the LoRa receivers can stay asleep, which dramatically lowers power consumption.

Layer 1: Unreliable Zero Hop Messaging

This layer is conventional non-reliable LoRa packet transmission. The transmitted packet has the following representation before encoding for transmission:

OffsetLengthTypeUsage
0x001 byteIntegersyncWord, always 0x2B.
0x014 bytesIntegerPacket header: Destination. The destination's unique NodeID. 0xFFFFFFFF for broadcast.
0x054 bytesIntegerPacket Header: Sender. The sender's unique NodeID.
0x094 bytesIntegerPacket Header: The sending node's unique packet ID for this packet.
0x0D32 bitsBitsPacket Header: Flags. See the header flags for usage.
0x11 .. 0xFDVaries, maximum of 237 bytes.BytesActual packet data. Unused bytes are not transmitted.
0xFE .. 0xFF2 BytesBytesUnused.

Packet Header Flags

Index# of BitsUsage
03HopLimit (see note in Layer 3)
31WantAck
4 .. 3228Currently unused

Usage Details

  • Packet Header: is described directly by the PacketHeader class in the C++ source code. But indirectly it matches the first portion of the MeshPacket protobuf 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 defacto 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 protobufs documentation. 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 Wi-Fi. 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 topologies) 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 retransmit, 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 retransmission 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 retransmission 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.

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 retransmission once a node has seen a nearby receiver ACK the packet it's trying to flood. This means that up to N retransmissions 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 retransmission 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.

Mesh algorithm example