Mapping Networks using Trees

So here's an idea:

Say we have a network of four computers: A, B, C, and D. We'll model the connections using an array structure like this (that's not the idea yet, though it's still pretty cool):

    A   B   C   D 
A   0
B   1   0
C   1   1   0
D   0   1   1   0

Where 1 represents a connection, and we'll say nodes aren't connected to themselves. Try drawing it out, because I'll reference the topology later.

Now let's say A wants to make a map of the network.  In this case, there's no central node connected to everybody and keeping track of all connections.  However, we can assume that there's some path between any two computers in the network.  That is, even though A is not connected directly to D, it can find out about D through a common connection, like B or C.

Obviously, to map the network A should ask all its neighbors which machines they're connected to, and for them to pass the message along.  The problem is that because unordered networks usually form circular connections (e.g. B connects to C connects to D connects back to B) each node would get the message from each of its connections, and replying to all of them would artificially increase the tally.

Well the easy solution is to attach an ID to each request, or maybe sign it with a private key. This way, when a message gets to a machine that has already received it, that machine can just reject all subsequent same-id messages and only reply to the first one. Then it could look like this:

[A, [B, [D, [C]]], [C, [D]]]
#I expanded it out to make it readable, hope it helps
[A, 
  [B,
    [C],
    [D, 
      [C]
    ]
  ], 
  [C, 
    [B],
    [D]
  ]
]

Where the 0th node of the list is the queried machine, and the following lists are its active connections.

Notice that even if nobody replies to a node as it's passing on the message (meaning it's at the 'end' of the tree) it will still report all of its active connections, so some items will appear in the tree twice. In this case, the order was A->B, A->C, B->D (followed by a bunch of failed requests, like B->C).

The above list would look different, though, depending on the order in which a node receives the message.  For example, if the connection between A and B were really shotty, but the rest of the connections were good, the tree would look like this:

[A, 
  [C, 
    [B,
      [D]
    ], 
    [D,
      [B]
    ]
  ],
  [B]
]

This kind of stuff can be useful in larger-scale networks to trace the shortest path to a desired node.  We could even add time-to-travel between nodes (like a traceroute) to make sure we pick the most efficient path.

Of course, this model assumes that every node is totally trustworthy, which is a horrible assumption to make for any real-world tech. I imagine you could get some sort of public key crypto going on over here, but that's a topic for a later post.

Anyway, hope you thought this was as neat as i did!