Skip to content

SubPub Mesh routing

Jump to bottom
Pau edited this page May 22, 2020 · 6 revisions

On WiFi Mesh networks the Dynamic Routing protocol is the component that allows reaching non direct neighbours.

Obviously there is a big difference between WiFi Mesh and a Internet p2p overlay network, on the first case a node is physically not connected to most of the nodes while on the second Internet makes most of the connections physically possible (unless those behind a NAT or a Firewall). However keep the connection permanently open to a big DHT network such as the libp2p DHT is very expensive in terms of network and resources consumption. Thus it makes sense to create small overlay network for a specific application purpose.

So the principles are:

  1. Use the big libp2p DHT network for bootstraping
  2. Keep a minimum/maximum number of peer connections (disconnect from the DHT when possible)
  3. Use the mesh overlay network for distributing packages

To this purpose we could create a small DHT network (i.e kademlia) between the small set of nodes as an overlay network. However the routing mechanisms provided by most of DHTs are poor while the routing provided and implemented on the dynamic Mesh routing protocols are rich, resilient and efficient (they must work on small embedded devices on a very hostile environment).

For instance on a Kademlia DHT network the routing does not have into account any latency or connection loss metric, nodes just determine their position using their address bytes. When a packet is sent, it will be routed probably by the shortest path but it does not mean it will be the best in terms of networking.

On Mesh networks we have mainly two kind of dynamic routing protocols:

  • link state (every node knows about the state of the whole network)
  • distance vector (every node only knows its best direct neighbour to fetch a destination)

The second kind is the one that gives better results. Babel, Bmx7 and Batman-adv are three well known, widely used, routing protocols that use such mechanism.

The basics would be something like:

  1. A node uses the libp2p Kademlia DHT for bootsraping (find nodes to connect)
  2. Once a number of connections have been made (i.e 10 peers), disconnect from the DHT
  3. Every node sends a very small packet (named Originator Message or OGM) to its neighbours which will be broadcasted to the whole network
  4. With this mechanism all nodes know the existence of all nodes in the network
  5. These OGMs are sent constantly by all nodes, i.e every 500ms and have a tracking number (1, 2, 3, 4....)
  6. Node A will receive the same OGM (from B with the tracking number) probably from all its neighbours
  7. Using the latency and packet loss, node A will determine that the best way to reach B is through her neighbour C
  8. This is done by all nodes, so every node will keep a table with a very simple relation: For reaching node X my best neighbour is Y
  9. Once a packet is sent, it will reach its destination by the best path because every node will make its best choice.

This is a very simplified version on how this could work. More information here:

subpubmesh diagram

Clone this wiki locally