<p>I'm building a mesh network where i need to detect the unexpected disappearance of a peer.</p>

<p>Each node attempts to stay in communication with at least X peers. A node refuses connection from another peer if it already has at least Y neighbours. Nodes communicate the IP addresses of their peers on every connection attempt. If a peer disconnects, it will be noted by keep-alives from its neighbours and the disconnection message will make its way around the network.</p>

<p>I'm a little worried about the case where there are two large clusters of nodes with a single node in the middle. If the sole 'bridge' node between two clusters disappears, the clusters will retain out-of-date information about peers in the other cluster.</p>

<p>Are there values of X and Y i can choose, or replacement strategies for choosing peers to connect to, such that this behaviour is made impossible or very unlikely? i.e. There are always at least two paths between any pair nodes.</p>

<p>I expect the network to grow to such a size where walking every edge is infeasible..</p>

CC BY-SA 3.0
2012-01-28T16:44:02.607Z
For those of us not fluent in the language of mesh networks, could you please define "peer" and "neighbor"?  (Does "peer" just mean "vertex"?  Does "neighbor" just mean "another vertex one edge away"?)  What, if anything, are you assuming about how peers (nodes?) appear and disappear?  (Randomly, adversarially, or something else?)  How does one peer know which other peers exist, so that it can attempt to connect to them?
Jeffε
CC BY-SA 3.0
2012-01-28T20:20:26.333Z
Terribly sorry, thank you for helping me make this clear.

Peer is vertex, Neighbour means another vertex one edge away. Peers disappear without warning (removing all their edges). My current approach to discovery and connectivity is to have peers start with a short pre-shared list of known peers, attempt to connect to them, (probably) find out they're full (Y neighbours already) but receive a list of their neighbours, and proceed to sort of spiral outward from the 'center' in this way (until they have at least X neighbours). Then, the known-peer list is cached between sessions.
mappu
CC BY-SA 3.0
2012-01-28T22:02:02.303Z
Without a specific discovery protocol, I don't think your question is answerable.  (What does "sort of spiral outward" mean?)  What is the initial graph, before any nodes disappear?  Can nodes appear, or only disappear?
Jeffε
CC BY-SA 3.0
2012-01-29T10:00:21.753Z
I agree my worries are based around the discovery protocol.. I had envisaged a system where nodes will appear at random intervals, attempting to form edges with whatever nodes they recall from their previous session, and was trying to consider a discovery techniques that would ensure no nodes become isolated. I realise now that probably means there are too many variables to find a solution, so perhaps i will look into relevant papers and heuristic simulation of discovery protocols from here on. Thank you for helping me understand my own question! :(
mappu
<graph-algorithms><network-modeling>
Strategies for preventing isolated nodes in a dynamically changing undirected cyclic graph
mappu
# Strategies for preventing isolated nodes in a dynamically changing undirected cyclic graph

(Asked by: username_0 on 2012-01-28)

I'm building a mesh network where i need to detect the unexpected disappearance of a peer.

Each node attempts to stay in communication with at least X peers. A node refuses connection from another peer if it already has at least Y neighbours. Nodes communicate the IP addresses of their peers on every connection attempt. If a peer disconnects, it will be noted by keep-alives from its neighbours and the disconnection message will make its way around the network.

I'm a little worried about the case where there are two large clusters of nodes with a single node in the middle. If the sole 'bridge' node between two clusters disappears, the clusters will retain out-of-date information about peers in the other cluster.

Are there values of X and Y i can choose, or replacement strategies for choosing peers to connect to, such that this behaviour is made impossible or very unlikely? i.e. There are always at least two paths between any pair nodes.

I expect the network to grow to such a size where walking every edge is infeasible..

**Tags:** graph-algorithms, network-modeling

> **Comments:**
> **username_1**: For those of us not fluent in the language of mesh networks, could you please define "peer" and "neighbor"?  (Does "peer" just mean "vertex"?  Does "neighbor" just mean "another vertex one edge away"?)  What, if anything, are you assuming about how peers (nodes?) appear and disappear?  (Randomly, adversarially, or something else?)  How does one peer know which other peers exist, so that it can attempt to connect to them?  
> **username_0**: Terribly sorry, thank you for helping me make this clear.  Peer is vertex, Neighbour means another vertex one edge away. Peers disappear without warning (removing all their edges). My current approach to discovery and connectivity is to have peers start with a short pre-shared list of known peers, attempt to connect to them, (probably) find out they're full (Y neighbours already) but receive a list of their neighbours, and proceed to sort of spiral outward from the 'center' in this way (until they have at least X neighbours). Then, the known-peer list is cached between sessions.  
> **username_1**: Without a specific discovery protocol, I don't think your question is answerable.  (What does "sort of spiral outward" mean?)  What is the initial graph, before any nodes disappear?  Can nodes appear, or only disappear?  
> **username_0**: I agree my worries are based around the discovery protocol.. I had envisaged a system where nodes will appear at random intervals, attempting to form edges with whatever nodes they recall from their previous session, and was trying to consider a discovery techniques that would ensure no nodes become isolated. I realise now that probably means there are too many variables to find a solution, so perhaps i will look into relevant papers and heuristic simulation of discovery protocols from here on. Thank you for helping me understand my own question! :(  

---

## 0 answers

