The incremental adoption of IPv6, middle boxes (e.g., NATs, Firewalls) as well as completely new network types and protocols paint a picture of a Future Internet that consists of extremely heterogeneous edge networks (e.g. IPv4, IPv6, Industrial Ethernet, sensor networks) that are not supposed or able to communicate directly. This increasing heterogeneity imposes severe challenges for overlay networks, which are considered as a potential migration strategy towards the Future Internet since they can add new functionality and services in a distributed and self-organizing manner. Unfortunately, overlays are based on end-to-end connectivity and, thus, their deployment is hindered by network heterogeneity. In this paper, we take steps towards a solution to enable overlay connections in such heterogeneous networks. Building upon a model of heterogeneous networks that comprises several emph{connectivity domains} with direct connectivity, interconnected by relays. As major contribution, we present a distributed protocol that detects the boundaries of connectivity domains as well as relays using a gossiping approach. Furthermore, the protocol can efficiently handle splitting and merging of connectivity domains due to underlay changes. Simulation studies indicate that the algorithm can handle connectivity domain split and merge in reasonable time and is scalable with respect to control overhead.