[Feature Request]: Add a single mechanism for approximating the mesh size

[NomDeTom]

Platform

Cross-Platform

Description

The maximum number of active nodes is used in default.cpp, but it is limited by the maximum number of nodes in the nodeDB. For very large meshes, this means that a node has no way to know whether they have an audience of 200 or 2000 nodes when they send a broadcast telemetry packet, for example.

A more effective way to estimate the number of nodes is needed. Following discussion, this could take one of the following forms:

1. Bloom filter with a modest 12-bit hash, and a function to iterate periodically.
2. As above, but much larger hash to give a more accurate number
3. Other estimates using advanced techniques, e.g. LogLog
4. Count a representative sample and apply a logical scaling function to give the estimated mesh size.

Other important KPIs for the mesh size would be (in no particular order):

1. Estimated mesh size (as above)
2. Number of immediate neighbours (zero hops)
3. Number of approximate neighbours (one or zero hops away - to account for varying RF signal causing assymetric links)
4. Each of the above would need to be repeated for various time intervals, to allow the node and/or operator to consider the overall trends and decide how to act based on that.

Counts 2 & 3 (zero & "near-zero") neighbour counts could be used to help #8114 get closed, by deciding how to spend airtime based on adjacent nodes.

[erayd]

I'm on it, as per our discussion earlier today.

Are you able to expand a bit more on what you're wanting with KPI 3?

[NomDeTom]

I'm on it, as per our discussion earlier today.

❤️❤️❤️

Are you able to expand a bit more on what you're wanting with KPI 3?

I mis-typed for the numbering in the original.

One of the other project items is increasing the CR with each initial broadcast attempt (because CR increases airtime in the range 125-200% "base airtime") so that each attempt has a higher chance to be heard - see #8114. I was trying to work out if there's a way to use the neighbours and neighbour-of-neighbours count (zero and 1 hop) to influence whether we use CR8 for transmissions. We want to save airtime but an unheard attempt is just noise.

Another thing I discussed with @thebentern was trying to estimate the "shape" of the mesh - or the visible mesh at least. There's a (not unreasonable) view that frequent telemetry or position should be limited to lower hop counts. OTOH, if the mesh is all within 1 hop of you, lowering the hop count won't make any difference.

Edit: and actually now I think about it some more, the idea might be better looked at the other way around: how many hops can I set before the number of receiving nodes goes over X? The current throttling algorithm is flat up to 40 nodes, and then starts to diminish frequency based on each node over 40 (up to nodeDB size 🙃), so you could auto-set the telemetry and position hops to keep it under 40 nodes without throttling, and then you could have the user make some trade-offs between frequency and hopcount. This would also suit @GPSFan and his "GPS-as-fast-as-you-can use-case", and might also help @fifieldt with his "last known position" use-case.

[NomDeTom]

This shows various nodes total or active node counts by hops-away.

[erayd]

I'll need to think on how best to optimise that. The requirement to know the number at each hop count is new, and has memory implications.

[NomDeTom]

Yes, I realised that as soon as I started down this road...

However! There's a couple of get-outs:

• It doesn't need to be very persistent - the current active node count is based on (IIRC) the last 3 hours.
• It may not even need to go much beyond the current nodeDB if a yardstick of 40 nodes is used.

So, to circle back to your original idea (which is still needed for your particular use case) - that count could be used to augment the hops-histogram to trigger a "you're in a mega-mesh" flag, or conversely activate the "small mesh" flag.

I'll keep simmering this set of ideas for a bit - it feels like the edge of a workable plan.

[korbinianbauer]

the current active node count is based on (IIRC) the last 3 hours.

2 hours, unless you mean a different thing:

firmware/src/mesh/NodeDB.cpp

Line 1603 in fb6d199

#define NUM_ONLINE_SECS (60 * 60 * 2) // 2 hrs to consider someone offline

trigger a "you're in a mega-mesh" flag, or conversely activate the "small mesh" flag.

Yeah, sounds a bit like the mesh-topology estimation parameter thing I've been playing with in simulations. The number of reached nodes grows between linearly and quadratic with # of hops, depending on where you are, so that parameter is somewhere between 1 and 2.

[NomDeTom]

@korbinianbauer I was thinking of this:

firmware/src/mesh/Default.h

Line 28 in bfaf6c6

#define default_node_info_broadcast_secs 3 * 60 * 60

Which, when combined with the active node window of 2 hours, means there's some interesting sample-window questions to answer.

[korbinianbauer]

@NomDeTom

there's some interesting sample-window questions to answer.

Indeed. I remember one of my first thoughts when starting with meshtastic was "what does 'online' mean though [conceptually]?".

My expectation was it means someone is actively using their node, i.e. texting, checking for new messages etc. because that's how messengers like WhatsApp use the term.

Never found an answer, just a definition: The - afaik arbitrary - 2h window.

If "online" is defined as a window, it should probably be larger than the maximum possible broadcast intervall, after throttling. With how throttling works now, that might be >1 week though.

Also- sry for the tangent - if a packet travels like this

A (original sender) → B (relay node) → C (receiver)

Node C updates the last_seen timestamp for A, but not B. I think both should be considered last_heard = rx_time. That's only possible if we assume identifying B by the single byte mp.relay_node is good enough though. That might be a stretch on larger meshes, but as long as there's only one match in the NodeDB, it should be ok.

[NomDeTom]

sry for the tangent

Yes, I agree with your tangent, but I've already buried this request in extra cruft, so I'll move the throttling things to a new issue.