Autonomous detection of connectivity

This paper contributes a protocol that measures underlay connectivity properties of nodes in an overlay network. The protocol autonomously assigns a unique random identifier to each subset of nodes that can communicate transitively using arbitrary underlay routing protocols (e.g., IPv4, IPv6, RFCOMM), denoted connectivity domain. We denote nodes in more than one connectivity domains relays, as they can forward messages between connectivity domains. This information is useful for overlay construction, as possible overlay neighbors must be in the same connectivity domain while relays enable communication between nodes in different connectivity domains. The general problem of identifying maximal connectivity domains is equivalent to the problem of finding all maximal cliques. We show that it can be efficiently approximated in an overlay setting with only partial knowledge of the network connectivity graph. The key observation is that in such scenario once all we discovered all relays remaining nodes can agree on a unique identifier per connectivity domain. We show by theoretical analysis and extensive simulations that the approach is accurate, scalable, resilient, and reactive to connectivity changes in the underlay network.