Replace Path Hashing in Packets with Repeater-Side Hashtables for Scalable Flood Routing

[Thevandermeij]

RFC: Efficient Flood Routing with Repeater-Side Hashtables for MeshCore

Title: Replace Path Hashing in Packets with Repeater-Side Hashtables for Scalable Flood Routing

Date: August 19, 2026
Status: Draft (Open for Community Feedback)
Target Version: MeshCore Firmware v1.18.0+

---

1. Abstract

This proposal suggests replacing path hashing in packets with a repeater-side hashtable for flood routing in MeshCore. This change aims to reduce:

• Packet size (up to 57 bytes for long paths).
• Network load (up to 90% in large networks).
• Battery usage (up to 50% by reducing redundancy).
• Scalability limitations (no limit on the number of hops).

The proposal maintains backward compatibility through a dual-mode implementation and introduces configuration options for network administrators.

---

2. Motivation

2.1 Current Issues

MeshCore’s current path hashing in packets has the following limitations:

Issue	Impact
Growing packet size	Each hop adds 1-3 bytes to the path field.
High network load	Flood routing sends multiple copies of the same packet through the network.
Limited scalability	Max. 64 bytes for path → limited number of hops (21-64, depending on hash size).
Battery wastage	Nodes process multiple copies of the same packet → higher power consumption.

2.2 Goals

Goal	Metric	Current	Target
Reduce packet size	Bytes per packet (10 hops)	~77B	<20B
Reduce network load	% redundant traffic (100 nodes)	~100%	<10%
Improve scalability	Max. number of hops	64	Unlimited
Reduce battery usage	Power consumption per packet	High	-50%
Maintain backward compatibility	Success rate old/new nodes	N/A	>99%

---

3. Proposed Solution

3.1 Core Idea

Replace path hashing in packets with a local hashtable in each repeater that tracks:

• Which packets have already been processed? (via Packet ID).
• From which previous node did the packet arrive? (via Previous Node Hash).

3.2 New Packet Structure

Current (Path Hashing)

[Header (1B)] [Path Length (1B)] [Path (max 64B)] [Payload (max 184B)]

• Total: 1 + 1 + 64 + payload = payload + 66B (max).

Proposed (Hashtable)

[Header (1B, incl. routing_mode)] [Packet ID (4B)] [Previous Node Hash (4B)] [Payload (max 184B)]

• Total: 1 + 4 + 4 + payload = payload + 9B (fixed).
• Savings: Up to 57 bytes for long paths.

Header Changes

Add a routing_mode bit to the header to indicate whether the packet uses path hashing or hashtable:

Header Format: 0bVVPPPPRRM
- Bits 0-1: Route Type (FLOOD/DIRECT)
- Bits 2-5: Payload Type
- Bits 6-7: Payload Version
- Bit 8: Routing Mode (0 = Path Hashing, 1 = Hashtable)

3.3 Repeater Hashtable Structure

Each repeater maintains a local hashtable as follows:

#define MAX_CACHE_ENTRIES 100  // Configurable (10-200).
#define CACHE_TTL_MS 300000    // 5-minute TTL.

struct PacketCacheEntry {
    uint32_t packet_id;       // Unique ID of the packet.
    uint32_t prev_node_hash;  // Hash of the previous node.
    uint32_t timestamp;       // Timestamp of receipt.
};

std::unordered_map<uint32_t, PacketCacheEntry> packet_cache;

3.4 Packet ID Generation

The Packet ID is generated as:

uint32_t generatePacketID(uint8_t* payload, size_t payload_len, uint32_t sender_hash) {
    uint32_t crc = crc32(payload, payload_len);
    return crc ^ sender_hash ^ (millis() & 0xFFFF); // Combine payload, sender, and timestamp.
}

• Unique per packet (even if the same payload is sent multiple times).
• Deterministic: The same input produces the same Packet ID.

---

4. Protocol Changes

4.1 Packet Transmission (Sender Side)

Current (Path Hashing)

1. Node A adds its hash to the path field.
2. Node A sends the packet to all neighbors.

Proposed (Hashtable)

1. Node A generates a Packet ID (via generatePacketID).
2. Node A sets Previous Node Hash = hash(A).
3. Node A sends the packet to all neighbors (with routing_mode = 1).

4.2 Packet Processing (Repeater Side)

Current (Path Hashing)

1. Repeater B receives the packet.
2. Repeater B checks if its hash is in the path field:
   • If yes: Ignore the packet (loop prevention).
   • If no: Add its hash to path and forward.

Proposed (Hashtable)

1. Repeater B receives the packet.
2. Repeater B checks the hashtable:
   • Look up Packet ID:
     • If found and prev_node_hash == hash(B): Ignore (loop prevention).
     • If found but prev_node_hash != hash(B): Ignore (already processed via another path).
     • If not found:
       • Add to hashtable:

         packet_cache[packet_id] = {packet_id, hash(A), millis()};

       • Forward to all neighbors except A (previous node).

4.3 Loop Prevention

Mechanism	Current	Proposed
Method	Path hashing in packet.	Hashtable in repeater.
Detection	Hash of node in path.	Packet ID + Previous Node Hash in cache.
Complexity	Low (in packet).	High (cache management).

4.4 Flood Routing vs. Direct Routing

Routing Type	Current	Proposed
Flood Routing	Path hashing in packet.	Hashtable in repeater.
Direct Routing	Path in packet.	Unchanged (explicit path).

---

5. Firmware Changes

5.1 New Data Structures

// In src/Packet.h
#define MAX_CACHE_ENTRIES 100  // Configurable (10-200).
#define CACHE_TTL_MS 300000    // 5-minute TTL.

struct PacketCacheEntry {
    uint32_t packet_id;
    uint32_t prev_node_hash;
    uint32_t timestamp;
};

std::unordered_map<uint32_t, PacketCacheEntry> packet_cache;

5.2 New Functions

A. Cache Management

// Add a packet to the cache.
void addToCache(uint32_t packet_id, uint32_t prev_node_hash) {
    if (packet_cache.size() >= MAX_CACHE_ENTRIES) {
        // Remove the oldest entry (LRU).
        auto oldest = std::min_element(packet_cache.begin(), packet_cache.end(),
            [](const auto& a, const auto& b) { return a.second.timestamp < b.second.timestamp; });
        packet_cache.erase(oldest->first);
    }
    packet_cache[packet_id] = {packet_id, prev_node_hash, millis()};
}

// Check if a packet is already in the cache.
bool isInCache(uint32_t packet_id, uint32_t prev_node_hash) {
    auto it = packet_cache.find(packet_id);
    if (it == packet_cache.end()) return false;
    // Check TTL.
    if (millis() - it->second.timestamp > CACHE_TTL_MS) {
        packet_cache.erase(it);
        return false;
    }
    // Check if it came from the same previous node (loop prevention).
    return (it->second.prev_node_hash == prev_node_hash);
}

// Remove outdated entries.
void cleanupCache() {
    uint32_t now = millis();
    for (auto it = packet_cache.begin(); it != packet_cache.end(); ) {
        if (now - it->second.timestamp > CACHE_TTL_MS) {
            it = packet_cache.erase(it);
        } else {
            ++it;
        }
    }
}

B. Packet Processing

// In src/Mesh.cpp
void handleIncomingPacket(Packet* packet) {
    if (packet->header.route_type == ROUTE_TYPE_FLOOD) {
        bool use_hashtable = (packet->header.routing_mode == 1);

        if (use_hashtable) {
            // New method: hashtable.
            if (isInCache(packet->packet_id, packet->prev_node_hash)) {
                return; // Ignore the packet.
            }
            addToCache(packet->packet_id, packet->prev_node_hash);
            forwardPacketToAllNeighborsExcept(packet, packet->prev_node_hash);
        } else {
            // Old method: path hashing.
            if (isHashInPath(packet->path, packet->path_length, getNodeHash())) {
                return; // Ignore the packet.
            }
            addHashToPath(packet);
            forwardPacketToAllNeighbors(packet);
        }
    } else {
        // Direct routing: unchanged.
        handleDirectRouting(packet);
    }
}

C. Packet Generation (Sender Side)

// In src/Node.cpp
void sendFloodPacket(uint8_t* payload, size_t payload_len) {
    Packet packet;
    packet.header.route_type = ROUTE_TYPE_FLOOD;
    packet.header.routing_mode = 1; // Hashtable mode.
    packet.header.payload_type = PAYLOAD_TYPE_TXT_MSG;
    packet.packet_id = generatePacketID(payload, payload_len, getNodeHash());
    packet.prev_node_hash = getNodeHash(); // Hash of the sender.
    memcpy(packet.payload, payload, payload_len);
    sendPacket(&packet);
}

---

6. Backward Compatibility

6.1 Dual-Mode Support

• routing_mode bit in the header:
  • 0: Path hashing (old method).
  • 1: Hashtable (new method).
• Old nodes: Ignore packets with routing_mode = 1 (or attempt to use path hashing, which will fail).
• New nodes: Support both methods (path hashing and hashtable).

6.2 Transition Period

Phase	Action	Duration
Phase 1	New firmware supports both methods.	2 weeks
Phase 2	Field tests with dual-mode.	8 weeks
Phase 3	Gradual rollout (new nodes use hashtable).	12 weeks
Phase 4	Path hashing is deprecated (only hashtable).	6 months after rollout

---

7. Configuration Options

Add new CLI commands to configure the cache:

# Set the maximum cache size (10-200 entries).
set cache.max_entries <10-200>

# Set the TTL (in seconds, default 300).
set cache.ttl <30-3600>

# Enable/disable the new flood routing.
set routing.flood_mode [path_hashing | hashtable]

# Show cache statistics.
get cache.stats

Example Output:

Cache Stats:
- Entries: 42/100
- Oldest Entry: 120s ago
- Memory Usage: 528B

---

8. Performance Analysis

8.1 Packet Size Comparison

Number of Hops	Current (Path Hashing)	Proposed (Hashtable)	Savings
1 hop	payload + 3B	payload + 9B	❌ -6B
5 hops	payload + 7B	payload + 9B	✅ +2B
10 hops	payload + 12B	payload + 9B	✅ +3B
20 hops	payload + 22B	payload + 9B	✅ +13B
64 hops (max)	payload + 66B	payload + 9B	✅ +57B

8.2 Network Load Comparison

Scenario	Current	Proposed	Reduction
Flood traffic (10 nodes)	~10 copies	~3-5 copies	✅ ~50-70%
Flood traffic (100 nodes)	~100 copies	~10-20 copies	✅ ~80-90%
Battery usage	High	Low	✅ ~30-50%

8.3 Memory Usage

Component	Current	Proposed	Increase
Packet size	~66B (max)	9B (fixed)	❌ -57B
Repeater Cache	0B	~1.2KB	❌ +1.2KB
Total	~66B	~1.2KB + 9B	❌ +~1.1KB

---

9. Testing Plan

9.1 Test Phases

Phase	Goal	Activities	Duration	Success Criteria
Phase 1: Simulation	Validate the concept.	Test in NS-3/OMNeT++ with 100+ nodes.	2 weeks	Packet delivery >99%, latency <1s.
Phase 2: Lab Tests	Test on real hardware.	Test on ESP32/RAK4631 with 10-20 nodes.	4 weeks	No packet loss, memory usage <2KB.
Phase 3: Field Tests	Test in real-world conditions.	Test in Dordrecht Oost mesh network.	8 weeks	Network load -80%, battery life +50%.
Phase 4: Backward Compatibility	Ensure smooth transition.	Test dual-mode with old and new nodes.	4 weeks	Success rate >99%.
Phase 5: Rollout	Deploy in production.	Gradual rollout with monitoring.	12 weeks	No critical bugs, positive feedback.

9.2 Test Scenarios

Scenario	Goal	Metrics	Expected Results
Small network (10 nodes)	Validate functionality.	Packet delivery, latency, memory usage.	100% delivery, <100ms latency.
Large network (100 nodes)	Test scalability.	Network load, packet loss.	<10% redundancy, 0% loss.
High traffic load	Test performance under stress.	Throughput, CPU usage.	2x higher throughput.
Battery test	Measure power consumption.	Battery life, power per packet.	+50% battery life.
Backward compatibility	Test dual-mode.	Success rate old/new nodes.	>99% success rate.

9.3 Test Tools

Tool	Purpose
NS-3/OMNeT++	Network simulation.
ESP32/RAK4631	Hardware testing.
Wireshark	Packet analysis.
MeshCore CLI	Configuration and monitoring.
Grafana/Prometheus	Performance monitoring.

---

10. Implementation Roadmap

10.1 Phase 1: Design and Simulation (2 weeks)

• Activities:
  • Finalize protocol specifications.
  • Implement in NS-3/OMNeT++ for simulation.
  • Validate performance in large networks.
• Deliverables:
  • Simulation code.
  • Performance report.

10.2 Phase 2: Firmware Implementation (4 weeks)

• Activities:
  • Implement hashtable cache in MeshCore firmware.
  • Add dual-mode support.
  • Add CLI commands for configuration.
• Deliverables:
  • Firmware patch (Pull Request).
  • Documentation updates.

10.3 Phase 3: Lab Tests (4 weeks)

• Activities:
  • Test on ESP32/RAK4631 with 10-20 nodes.
  • Measure packet size, network load, battery usage.
• Deliverables:
  • Test report.
  • Bug fixes.

10.4 Phase 4: Field Tests (8 weeks)

• Activities:
  • Test in Dordrecht Oost mesh network.
  • Monitor performance and stability.
• Deliverables:
  • Field test report.
  • Community feedback.

10.5 Phase 5: Rollout (12 weeks)

• Activities:
  • Gradual rollout (start with small networks).
  • Monitor performance and bugs.
  • Gather community feedback.
• Deliverables:
  • Stable firmware release.
  • Documentation and tutorials.

---

11. Expected Impact

11.1 Performance Improvements

Metric	Current	Proposed	Improvement
Packet size (64 hops)	~77B	~14B	✅ 82% smaller
Network load (100 nodes)	100+ copies	~10-20 copies	✅ 80-90% less
Battery life	~24h	~36-48h	✅ 50% longer
Scalability	Limited (64 hops)	Unlimited	✅ Better scalability

11.2 Community Impact

• Benefits for Users:

  • Larger networks possible (100+ nodes).
  • Longer battery life for portable nodes.
  • Less network congestion in busy conditions.

• Benefits for Developers:

  • Simpler scalability.
  • Less complexity in packet processing.

---

12. Open Questions & Community Feedback

12.1 Open Questions

1. What is the optimal cache size?

   • Proposed: 100 entries (configurable).
   • Question: Is this sufficient for large networks?

2. What is the optimal TTL?

   • Proposed: 5 minutes.
   • Question: Should this be dynamic (e.g., based on network load)?

3. How to handle memory constraints?

   • Question: Should we implement a fallback to path hashing if the cache is full?

4. How to test backward compatibility?

   • Question: Should we set up a test network with old and new nodes?

12.2 Community Feedback

We invite the MeshCore community to provide feedback on:

• Technical feasibility (Is the implementation realistic?).
• Performance improvements (Are the expected improvements realistic?).
• Backward compatibility (How can we ensure a smooth transition?).
• Alternative approaches (Are there better solutions?).

Discussion: MeshCore GitHub Discussions
Pull Request: MeshCore GitHub PR

---

13. References

1. MeshCore Packet Format Documentation
2. MeshCore FAQ
3. MeshCore CLI Commands
4. NS-3 Network Simulator
5. OMNeT++ Network Simulator

---

14. Appendix: Code Examples

14.1 Complete Packet Format (Hex)

Current (Path Hashing):

Header: 0x01 (FLOOD)
Path Length: 0x03
Path: [0xA1, 0xB2, 0xC3]
Payload: "Hello"

Total: 1 + 1 + 3 + 5 = 10 bytes.

Proposed (Hashtable):

Header: 0x81 (FLOOD + routing_mode=1)
Packet ID: 0x12345678
Previous Node Hash: 0xA1B2C3D4
Payload: "Hello"

Total: 1 + 4 + 4 + 5 = 14 bytes (for 1 hop).

• Advantage: For 10 hops, it remains 14 bytes (vs. 17 bytes in current implementation).

14.2 Example: Cache Management in C++

// In src/Repeater.cpp
#include <unordered_map>
#include <algorithm>

#define MAX_CACHE_ENTRIES 100
#define CACHE_TTL_MS 300000

struct PacketCacheEntry {
    uint32_t packet_id;
    uint32_t prev_node_hash;
    uint32_t timestamp;
};

std::unordered_map<uint32_t, PacketCacheEntry> packet_cache;

void addToCache(uint32_t packet_id, uint32_t prev_node_hash) {
    if (packet_cache.size() >= MAX_CACHE_ENTRIES) {
        auto oldest = std::min_element(packet_cache.begin(), packet_cache.end(),
            [](const auto& a, const auto& b) { return a.second.timestamp < b.second.timestamp; });
        packet_cache.erase(oldest->first);
    }
    packet_cache[packet_id] = {packet_id, prev_node_hash, millis()};
}

bool isInCache(uint32_t packet_id, uint32_t prev_node_hash) {
    auto it = packet_cache.find(packet_id);
    if (it == packet_cache.end()) return false;
    if (millis() - it->second.timestamp > CACHE_TTL_MS) {
        packet_cache.erase(it);
        return false;
    }
    return (it->second.prev_node_hash == prev_node_hash);
}

void cleanupCache() {
    uint32_t now = millis();
    for (auto it = packet_cache.begin(); it != packet_cache.end(); ) {
        if (now - it->second.timestamp > CACHE_TTL_MS) {
            it = packet_cache.erase(it);
        } else {
            ++it;
        }
    }
}

14.3 Example: Packet Processing in Repeater

// In src/Mesh.cpp
void handleIncomingPacket(Packet* packet) {
    if (packet->header.route_type == ROUTE_TYPE_FLOOD) {
        bool use_hashtable = (packet->header.routing_mode == 1);

        if (use_hashtable) {
            if (isInCache(packet->packet_id, packet->prev_node_hash)) {
                return; // Ignore the packet.
            }
            addToCache(packet->packet_id, packet->prev_node_hash);
            forwardPacketToAllNeighborsExcept(packet, packet->prev_node_hash);
        } else {
            if (isHashInPath(packet->path, packet->path_length, getNodeHash())) {
                return; // Ignore the packet.
            }
            addHashToPath(packet);
            forwardPacketToAllNeighbors(packet);
        }
    } else {
        // Direct routing: unchanged.
        handleDirectRouting(packet);
    }
}

---

15. Call to Action

This proposal is ready for community feedback and implementation. We invite the MeshCore community to:

1. Provide feedback on the proposal (via GitHub Discussions).
2. Test the code in simulation and real-world networks.
3. Collaborate on the implementation (via Pull Requests).

Goal: A more efficient, scalable MeshCore protocol that improves large networks, battery life, and network load.

---

End of RFC 🚀