[Feature Request]: Client Nodes Neighbors and Neighbor`s Neighbors Used to Determine if Rebroadcast is Done

[Ryu945]

Platform

Cross-Platform

Description

Instead of having Client nodes always silence rebroadcasting if someone else does it first, what if we made this decision based on the actual network configuration?

A node will keep a list of all their neighbors (Nodes they can directly communicate with). A node will share its neighbors with its neighbors. A node will save not only a list of its own neighbors but the neighbors around it neighbors. If a message is broadcasted while this neighbor data is empty, Meshtastic would work the same way it does now. If a message is broadcasted from Node A and Node B rebroadcast it first (Based on SNR); Node C which also heard the message will check to see if it knows any nodes that Node B doesn't know. If it does then it will broadcast anyway and not be silenced by Node B. If it doesn't then it will not rebroadcast.

SNR based timings are still used but whether a Node is silenced can be overrided based on who Node C knows and who Node B doesn't know.

A node will probably have to be on for so long before it starts using the override based on neighbor information.

[fifieldt]

Neighbor Information is massive, relatively speaking :) We had to turn default neighbour info sharing way down because it severely loaded the mesh. For this idea to work well, neighbour info would need to be shared very frequently. It seems there just isn't enough bandwidth for this kind of idea.

[Ryu945]

This idea would need that information to be transferred. Maybe some sort of message sent periodically of neighbors.

This is what fifieldt was referring to. We have the NeighborInfo Module, but it generates relatively quite some traffic, especially if you need to send it frequently to support moving nodes.

From my understanding, that module gives more information then one hop deep. It gives you what is needed to map out the entire network. This idea doesn't need that much information. The only thing new needed is for every node to periodically broadcast to everyone its 0 hop neighbors.

I am curious how I know all my 1 hop neighbors now. I don't know if my node knows which 0 hop neighbor gave them that information though.

You mean it knows which nodes were received with 1 hop? That's from the hopStart - hopLimit calculation, and indeed you don't know which 0-hop neighbor relayed that packet to you. (Although since 2.6 there is a relay_node byte in the header, but it's only 1 of the 4 bytes of a NodeNum).

Is there any sort of periodic communications in the network already that would get this hopStart - hopLimit information broadcasted on a regular basis as things are now? If hopStart - hopLimit already?

Also, I assume you need the full NodeNum is needed to identify a node. Is there anything in the system that would periodically give that information? We may be able to use the relay_node byte to do the verification and potentially avoid needing to do this periodic broadcast. Thus there would be no bandwidth penalty for implementing this.

I ask because I commonly see nodes communicating how many hops away they are from me and I believe there is no active communication between people occurring. It shows the full four byte name. This implies there is passive data being exchanged and this passive data could be enough to implement this idea.

[GUVWAF]

The only thing new needed is for every node to periodically broadcast to everyone its 0 hop neighbors.

This is exactly what the NeighborInfo module does. When you receive this information from all nodes, you can map out the entire network.

I ask because I commonly see nodes communicating how many hops away they are from me and I believe there is no active communication between people occurring. It shows the full four byte name.

Every time a node sends out any kind of packet (NodeInfo, telemetry, position, etc.), it sets the from field of the packet to its NodeNum, and starts with hopStart = hopLimit. Hence, any node receiving this packet with hopLimit = x can determine how many hops it took to get to it. This does not mean we know which nodes some other node can receive directly. For this you always need to transmit a dedicated packet with this information, or a full NodeNum of the relayer. The latter is something that's considered for Meshtastic 3.0.
For NeighborInfo, let's do a back-of-the-envelope calculation. When transmitting all your neighbors, on LongFast this packet quickly uses 1 second of airtime. A node then on average experiences around 3 seconds of channel utilization for each NeighborInfo packet transmitted (receiving, rebroadcasting and hearing the next node rebroadcast). Let's say every node transmits its NeighborInfo every 15 min., which is still not enough for highly mobile nodes, but is a good start. Then at 300 nodes, already 100% of the channel utilization is used up purely by NeighborInfo (15 min. * 60 seconds / (300 nodes * 3 seconds) = 100%).

[Ryu945]

The only thing new needed is for every node to periodically broadcast to everyone its 0 hop neighbors.

This is exactly what the NeighborInfo module does. When you receive this information from all nodes, you can map out the entire network.

If that is all the module does then no node should ever receive this information from all nodes. It should only know its 0 hop neighbor`s information. Unless the information from each node propagates through the network somehow. Then that is more information then is needed.

I ask because I commonly see nodes communicating how many hops away they are from me and I believe there is no active communication between people occurring. It shows the full four byte name.

Every time a node sends out any kind of packet (NodeInfo, telemetry, position, etc.), it sets the from field of the packet to its NodeNum, and starts with hopStart = hopLimit. Hence, any node receiving this packet with hopLimit = x can determine how many hops it took to get to it. This does not mean we know which nodes some other node can receive directly. For this you always need to transmit a dedicated packet with this information, or a full NodeNum of the relayer. The latter is something that's considered for Meshtastic 3.0. For NeighborInfo, let's do a back-of-the-envelope calculation. When transmitting all your neighbors, on LongFast this packet quickly uses 1 second of airtime. A node then on average experiences around 3 seconds of channel utilization for each NeighborInfo packet transmitted (receiving, rebroadcasting and hearing the next node rebroadcast). Let's say every node transmits its NeighborInfo every 15 min., which is still not enough for highly mobile nodes, but is a good start. Then at 300 nodes, already 100% of the channel utilization is used up purely by NeighborInfo (15 min. * 60 seconds / (300 nodes * 3 seconds) = 100%).

If I understand it correctly, I can see the full name only because of the NodeInfo packets that originate from each node already get propagated through the network at some long time frame. You used 15 minutes as an example but I don't know if that is the current broadcast interval. Is it correct to assume that none of this (NodeInfo, telemetry, position, etc.) sends any kind of ack back? It is just broadcasted and whoever receives it will receive it?

Taking this further, if there is one node that always gets picked to rebroadcast NodeInfo first for "reasons" then the other node in the area will remain 100% quiet and never route a neighbor`s NodeInfo through it. It will only ever transmit its own NodeInfo. Thus, the node can give the illusion to its neighbors that it is connected to no other nodes

Furthermore, the first byte of the full four byte relayer name is always transmitted in every rebroadcast as of right now. Since the number of 0 hop relays will be relatively small, a node should be able to determine which 0 hop node transmitted the 1 hop node nodeinfo from the first byte of the name alone. Thus with the (NodeInfo, telemetry, position, etc.) packets sent now, you should be able to map out neighbor`s neighbors but only for the packets they actually relay.

The problem comes from the fact that a node that is never chosen to relay NodeInfo will appear disconnected to other nodes so we never know who they are really connected to.

Is there any other relevant information? Does (NodeInfo, telemetry, position, etc.) send ack packets back?

[Ryu945]

Thoughts?

[Ryu945]

I was thinking about this question in terms of mapping the network up to 1 hop. What would be the minimum transmission and receiving of packets that can be done to establish to both nodes that a bidirectional link has been established. The end goal being to improve message routing. A thought that crossed my mind is that if we can make very small network mapping packets, we could could make multiple network mapping transmissions in a standard message width. We can then assign a set period of time between sending messages for doing network mapping between all the nodes. Thus we only give up one message windows to do a flurry of network mapping communication. For example, the outgoing packet would look something like this:

This idea is for version 3.

Preamble
2 bits: Special Code showing it is network Mapping Request
4 byte: Sender

Every 0 Hop nodes would reply with:

Preamble
2 bits: Special Code showing it is network Mapping 0 Hop Response
4 byte: Original Sender
4 byte: 0 hop Node

This 0 hop response will let 1 hop nodes know that they need to send a 1 hop response. It would look something like this.

Preamble
2 bits: Special Code showing it is network Mapping 1 Hop Response
4 byte: Original Sender
4 byte: 0 hop Node
4 byte: 1 hop Node

This will then tell the 0 hop node only relay that exact packet again. Thus the original sender now knows you they have two way communication but the replying nodes do not know if they have anything more then one way communication. Thus, the original sender needs to send a message back.

Preamble
2 bits: Special Code showing it is network Mapping Response from Original Sender
4 byte: Original Sender
4 byte: 0 hop Node
4 byte: 1 hop Node

Thus the 0 hop node now knows there is two way communication. The mentioned 0 hop node only will relay this packet. Thus the 1 hop node knows there is two way communication. Every node will respond to network mapping request in the network mapping window only.

[Ryu945]

A better system to improve network reliability was discovered so closing this.