undirected graph loop detection (simulator)

[michielbdejong]

This issue tracks the goal of writing a PoC implementation of the loop finding according to ledgerloops/ledgerloops.com#92

As a PoC, it will require all code to run with access only node-bound data, but it will not require nodes to exist on different hosts. So the network will be simulated and all nodes will run in the same memory space, but we will refrain taking advantage of this. So the data structure is entirely per-node.

Each node has neighbours. Let's use numbers to uniquely identify nodes, we will take this shortcut to abstract the naming and addressing.
Each node has a list of exchange rates. In real life these would be complex and depend on the specific trade pair and trade size, but let's start with the relaxed requirements that exchange rates are assumed to be transitive.

To avoid picking one neighbour as special, use a random unit as the reference, and then the node needs to keep linear exchange rates between each neighbour and that special random reference.

Apart from this exchange rate, each neighbour should have a min and a max balance, and the value of a zero balance is zero.

To run a simulation, generate neighbour connections and exchange rates at random, and then start sending probes.

As a node, it is natural you don't want your neighbour to owe you too much, so you want to limit how much they owe you, so you want to set a max balance.

Your neighbour probably sets a limit that translates into a min balance for you.

Network csv format columns:

• lower node number
• lower node number max balance
• lower node number exchange rate
• higher node number
• higher node number max balance
• higher node number exchange rate

[michielbdejong]

• first simple network generator #21
• Read testnet into memory structure #23
• Make one new link appear every 10 sim rounds #29
• Trigger probe when link is added #25
• Send probe message from node to node #26
• Pick best pair for forwarding a probe #27
• Batched simulation of how probes get forwarded #28