Markov connection algorithm

MuWire uses a Markov based algorithm to control connectivity between nodes.

We consider three states that MuWire connections can be in at any given time:

• (S)UCCESSFUL
• (R)EJECTED
• (F)AILED

Every state has 3 transition probabilities to reach any state ( fully meshed ).

• S->S, S->R and S->F
• R->S, R->R and R->F
• F->S, F->R and F->F

The 9 state transition probabilities ( STP ) are adjusted during runtime and initially have the following values:

• 0.5, 0.0 and 0.5
• 0.5, 0.0 and 0.5
• 0.5, 0.0 and 0.5

We record state transitions in a database histogram and continuously adjust them according to their relative frequency ( non-stationary distribution )

A) We take the current state ( initially SUCCESSFUL )

B) We predict the next connection attempt and initiate it.

C) The result ( observed state ) gets recorded into the db creating a sequence of transition states.

D) We update the current state to be the observed state.

E) Finally we re-calculate the 9 STP's according to their frequency in the db history.

we then start at A) again

The general characteristics of this algorithm are:

• Starts out with a stationary distribution
• After a certain amount of samples have been recorded STP's are being updated constantly
• Nodes with good connectivity are favored as connection attempts with higher STP's are more likely to occur
• Accommodates for short and long term connectivity characteristics
• Nodes that fail constantly will eventually reach a FF STP of 1.0 so they will not be connected any more

After a node has reached a certain FF STP threshold ( currently fixed at 95% ) it is considered to be hopeless and is therefore purged from the history connection table.

No further outgoing connection attempts are made to this node.

If however at any point in the future the hopeless node is able to reconnect with us ( incoming connection ) it will be treated according to the initial SUCCESSFUL state conditions.