Proposal: Limit Floods by a geo-coord-defined Corridor Approach

[usrflo]

Motivation / Problem

The region management that was introduced in revision 1.11.x tries to reduce the spreading of floods to limit network congestion.
It's a static approach that requires individual configuration that matches some but not all needs depending on the location of senders and receivers. I think this approach allows too much flood spreading in areas where packages are not intended and blocks flood spreading to areas that should be covered intentionally by the sender.

I'd like to see a more flexible approach that limits the number of flooding repeaters without a fixed definition of allowed regions and local limitations.

Problem Solution

Currently I don't see that the adverted geo-coordinates of companions and repeaters are used as part of flooding decisions; I think geo-coordinates should be included:
Looking at paths of received adverts the package route reflects real world corridors between sender and receiver. Geo formations like valleys, mountains or shore lines change direct corridors to corridors with multiple edges. Looking at paths of incoming adverts I currently can define working path lists for direct messaging or tracing. This information can be used as well to predefine a corridor my flood packages should take. Besides an individual, manual definition a "rich device" (MeshCore App on a smartphone) could auto-define reasonable corridors using past communication and information from maps (corridor along shorelines ...).

A repeater would re-transmit the flood package only if it's inside the defined corridor that is sent as part of the package header.

Corridor Definition

Think about the corridor is defined as a list of triples: latitude, longitude, radius.

A single triple could be compressed to 4 bytes:

• 14 bit for the latitude (precision below 1 km)
• 14 bit for the longitude (precision below 1 km)
• 4 bit for a radius: 16 values with a fixed stretch factor to support for example 2 km up to 200 km

So the corridor in the following image could be defined with 12 bytes. Only the repeaters marked in green inside the corridor re-transmit the sent packet.

Samples for Corridor Usage to reduce Flood Traffic

1. send out a flood advert to a remote location where you expect a communication partner to be without a regional limitation and without too much load on the whole network.
2. re-transmit a direct message that was not ACKed to a companion with a known target position; use a direct corridor with (own_position, radius_small) (target_position, radius_small) if there is no detailed corridor with multiple edges.
3. re-transmit a direct message that was not ACKed within an increased corridor (own_position, radius_large) (target_position, radius_large) before falling back to a common flood.

Repeater Corridor Check

The following source code demonstrates how a repeater could check very efficiently if its own position is inside the corridor definition from the package header:

#include <iostream>

// g++ -o isPointInCorridorTest isPointInCorridorTest.cpp

struct Circle
{
    float x;   // lat
    float y;   // lon
    float r;   // radius
};

inline bool isPointInsideConnectedCirclesN(
    float px,
    float py,
    const Circle* circles,
    int count
)
{
    // Special case: no circles
    if (count <= 0)
        return false;

    // Special case: exactly one circle
    if (count == 1)
    {
        float dx = px - circles[0].x;
        float dy = py - circles[0].y;
        return (dx * dx + dy * dy) <= (circles[0].r * circles[0].r);
    }

    // Iterate over all segments
    for (int i = 0; i < count - 1; ++i)
    {
        const Circle& c1 = circles[i];
        const Circle& c2 = circles[i + 1];

        // Connection vector
        float vx = c2.x - c1.x;
        float vy = c2.y - c1.y;

        // Squared length
        float len_sq = vx * vx + vy * vy;

        // Degenerate case: identical centers
        if (len_sq == 0.0f)
        {
            float dx = px - c1.x;
            float dy = py - c1.y;
            if ((dx * dx + dy * dy) <= (c1.r * c1.r))
                return true;
            continue;
        }

        // Vector from first center to point
        float wx = px - c1.x;
        float wy = py - c1.y;

        // Projection parameter
        float t = (wx * vx + wy * vy) / len_sq;

        // Clamp to [0, 1]
        if (t < 0.0f) t = 0.0f;
        else if (t > 1.0f) t = 1.0f;

        // Projected point on the axis
        float ax = c1.x + t * vx;
        float ay = c1.y + t * vy;

        // Interpolated radius
        float r = c1.r + t * (c2.r - c1.r);

        // Distance from point to axis
        float dx = px - ax;
        float dy = py - ay;

        if ((dx * dx + dy * dy) <= (r * r))
            return true;
    }

    return false;
}

int main()
{
    // Test data: 3 circles
    Circle circles[] = {
        {52.0f, 13.0f, 0.5f},  // Circle 1
        {52.5f, 13.2f, 0.4f},  // Circle 2
        {53.0f, 13.5f, 0.6f}   // Circle 3
    };
    int circleCount = sizeof(circles) / sizeof(circles[0]);

    // Test points
    float testPoints[][2] = {
        {52.0f, 13.0f},  // exactly Circle 1
        {52.4f, 13.15f}, // inside corridor between Circle 1 and 2
        {54.1f, 14.6f},  // outside all circles/corridors
        {52.75f, 13.35f} // inside corridor between Circle 2 and 3
    };

    for (int i = 0; i < 4; ++i)
    {
        float px = testPoints[i][0];
        float py = testPoints[i][1];

        bool inside = isPointInsideConnectedCirclesN(px, py, circles, circleCount);
        std::cout << "Point (" << px << ", " << py << ") is "
                  << (inside ? "INSIDE" : "OUTSIDE")
                  << " the connected body." << std::endl;
    }

    return 0;
}

Conclusion

With the corridor approach:

• network traffic could be reduced within local and targeted long range communication
• routes can be predefined to travel in areas with network coverage (along shore lines, outside of specific countries, ...)
• repeater downstream compatibility can be kept: repeaters not checking their relative position keep to re-transmit flood packages like today
• the approach can be used as an intermediate step between direct communication and the flood fallback

[gordol]

This is an interesting idea, and I appreciate the work you put into explaining it.

Do you expect the corridor width to vary with latitude? Lat/lon is not a flat Cartesian plane, the planet is an oblate spheroid.

Related to that, this turning a 3-dimensional RF problem into a 2-dimensional inclusion test (lat/lon inside a corridor). There seems to be an assumption that good forwarding paths are geographically near some path between endpoints. This doesn't consider terrain (third dimension). This proposal won't work in a valley + mountain-top repeater situation. The best RF path could be a big 2D detour in the opposite direction (mountain far outside the corridor pathway) but a great link because of line-of-sight and height. "Inside the corridor" doesn't equate to "is a good relay". Link quality and elevation matter more than 2D distance.

[usrflo]

@gordol, only the most simple corridor between sender and receiver with known positions could be IMHO defined by a MeshCore device itself with simplified assumptions.
The real strength of a corridor (a list of [lat, lon, radius] triples) comes with its determination by a client on a "rich device", for example the MeshCore App on a smartphone that can keep context data regarding

• available contact list: most repeaters advert their lat/lon position; so a smart device can calculate a corridor for an assumed path by enough dense repeaters between the local position and the desired target position. Assumed that there is some area without coverage between sender and desired receiver because of geological barriers or any other reason: if the target is reachable in principal the MeshCore contact list will reveal another corridor with repeater positions dense enough to give it try.
• manual configuration: I am myself in a valley and I know that I can exclude some directions because there are no reachable repeaters; so I could exclude specific locations manually that could change the corridor definition.
• writing on https://github.com/usrflo/MeshCore-Reachability I saved ingoing paths of adverts and followed them the other way round to test their stability. This kind of information also provides the data basis for a corridor definition on a smart device.
• calculations like https://github.com/usrflo/itm-linux can be used to pre-calculate location specific requirements about repeater density
• real repeater positions from MeshCore maps on the Internet could downloaded and used offline for corridor calculations
• finally using map data with DEM information/topography can be used on a smart device to check likely corridors before using them; btw: https://github.com/Brent-A/mcsim is doing a MeshCore simulation potentially with DEM data, this could be done on a smart device as well in principle.

Regarding the simplification of a 2-dim-raster: a smart device could in addition use the locations to adapt the radius (different on the poles / equator).

There seem to be lots of options. Maybe it would be the most simple thing to harvest the lat/lon information from the contact list. What do you think?

[gordol]

Sender-supplied forwarding constraints are certainly an interesting idea (declarative routing, basically) but I wonder if this goes against any core principles of meshcore? Should the repeaters be in control, or edge clients? 🤷

Could corridors exist only as a repeater policy? So packets don't carry constraints, but instead, repeaters could probabilistically forward floods without requiring new packet semantics, so authority stays with repeaters?

Is there a way to approximate this corridor effect through emergence, instead of declaration?

---

from https://buymeacoffee.com/ripplebiz/meshcore-philosophy:

The Division of Labour, Rights and Responsibilities

Like Reticulum, MeshCore clearly shifts the responsibility of packet routing to repeaters, and repeaters only. Edge nodes, like chat clients or sensor nodes, don't pollute the airwaves. Repeaters are mounted typically in good, elevated locations, and have a fixed location. Edge nodes can roam (* however, protocol extensions to aid/optimise roaming nodes is still being developed).

As repeaters do 'the work' of the mesh, it is the right of a repeater admin to refuse or allow traffic. This might be a little controversial, or could be seen as an avenue for discrimination by repeater admins, but the privacy built into the core protocol intentionally makes this difficult. Currently, there are no restrictions imposed in the standard repeater firmware, but there could be many repeater firmwares, some with more admin controls, with things like rate-limiting, custom priority boosts (or penalties) for packet types, or patterns of usage observed.

A more organic strategy to weed-out bad nodes is, I believe, a better approach vs top-down policy dictates. With more options, choice of firmwares, individual areas/meshes will find their own solutions to things like channel saturation, etc. It's unlikely there is one solution for every mesh, in every jurisdiction. (However, good/sensible defaults go a long way to limiting the chaos)

Paths

The general strategy is: 'direct paths when possible, flood as fallback'. Every packet goes in either Flood mode or Direct mode. To stay frugal, the path discovery piggy-backs onto normal packets, like messaging. So, when A doesn't have a path to B, sending a message goes Flood mode, and if B is found, they get the message + path in one. In the context of messaging, the Ack + path is then returned to A.

Paths are asymmetrical. B also has to discover a path to A, and the Ack example also does a two-for one, in returning the Ack + out path, it also results in A receiving: Ack, out path, and return path. The only packet overhead in this exchange is a 3rd, direct-only packet that sends return path back to B. After this sequence, both A and B store direct paths (to the other) in their storage.

One side-effect of this, is that senders can store paths and actually choose which one to use. Liam's app actually takes this a step further and lets you manually construct paths yourself. If you are admin to a set of repeaters and know a particular route is optimal, this can be beneficial, and result in less flooding.

[usrflo]

The corridor approach fully complies to the MeshCore philosophy:

• a defined corridor is an offer to the repeater to limit its flood activities; regarding flood packages the corridor never means "do more" but always "do less". And this less processing is desired from the perspective of the repeater administrator.
• a defined corridor does not need to be considered by a repeater. If it's either ignored or repeating is temporarily disabled (for example for power saving reasons or air time restrictions), it's always up to the repeater administrator.
• so with the corridor approach the edge devices / companions are never in control. But they can help to reduce flood traffic that is not useful from the sender perspective.
• just to be clear: the corridor approach does not replace direct packages; instead it limits floods.

[MGJ520]

emmm，I think this is a pretty good idea, but as mentioned earlier, the signals from nearby devices may not necessarily be strong. I think a simulator is needed to model these complex network behaviors before deployment. Only after comparison can we determine whether this is reasonable.