Overlay-based services are a popular approach for providing functionality like multicast, quality of service or security in the Internet without requiring infrastructure support. This talk presents an overview of the Spontaneous Virtual Networks (SpoVNet) architecture and its Underlay Abstraction layer that enables easy and flexible creation of such services. Also building on an overlay approach, the Underlay Abstraction provides generic functionality to cope with mobility, multi-homing, and heterogeneity. It manages node mobility by separating node identifiers from network locators and it provides persistent connections by transparently switching locators. Multi-homing is supported by choosing the most appropriate pair of network locators for each connection. In order to cope with network and protocol heterogeneity, it uses dedicated overlay nodes, e.g., for relaying between IPv4 and IPv6 hosts. Since the functionality provided by the Underlay Abstraction can be used by several overlay-based services in parallel, redundant functionality is removed from services and applications.