Next generation networks will combine many heterogeneous access technologies to provide services to a large number of highly mobile users while meeting their demands for quality of service, robustness, and security. Obviously, this is not a trivial task and many protocols fulfilling some combination of these requirements have been proposed. However, non of the current proposals meets all requirements, and the deployment of new applications and services is hindered by a patchwork of protocols. This paper presents Spontaneous Virtual Networks (SpoVNet), an architecture that fosters the creation of new applications and services for next generation networks by providing an underlay abstraction layer. This layer applies an overlay-based approach to cope with mobility, multi-homing, and heterogeneity. For coping with network mobility, it uses a SpoVNet-specific addressing scheme, splitting node identifiers from network locators and providing persistent connections by transparently switching locators. To deal with multihoming it transparently chooses the most appropriate pair of network locators for each connection. To cope with network and protocol heterogeneity, it uses dedicated overlay nodes, e.g., for relaying between IPv4 and IPv6 hosts.