I have a network of nodes, subject to the following properties:
- The global set contains N nodes.
- Each node is capable of discovering X neighbors, where X << N.
- Discovering a neighbor is a unidirectional operation (that is, the neighbor doesn't necessarily know its been discovered and may not discover the original node).
What I need to accomplish is for these nodes to self-assemble an efficient network topology such that all nodes can communicate with a minimal number of hops (I'm interested in a pragmatic minimum, not a theoretical optimized minimum if it requires the solution to carry extra complexity). Is this already a generally-solved problem? That is, is there a standard best-practice solution?
If I were to assemble nodes manually, I'd probably create a hierarchy with some nodes acting as gateways between other node groups. However, I'm not sure quite what the best approach is to getting this nodes to self-assemble; the group/hierarchy topology is not a requirement, it's just an intuitive example.
Note that I am not looking for an efficient message routing algorithm once the topology is in place (although I'd certainly like the topology to be as efficient as possible and for each node to use as close to X communication channels as possible).
It sounds like you're looking for a Distributed Hash Table. Despite the name, they can be used for more than storage - they serve as a generic routing mesh, with O(log n) expected hops to route messages between any two nodes.
Although the basics remain the same, there are at least a couple of distinct approaches to how to implement them; you'll probably want to checkout Kademlia and Chord as examples. Kademlia is simpler to implement but focuses on data storage and retrieval; Chord is more complex but more versatile.