Fifth generation (5G) mobile networks will lead to a deep integration between networks and applications. Through novel paradigms like network functions virtualization and edge computing, the new classes of heterogeneous application services will be enabled to run close to the mobile end-user devices with zero-perceived latency and fully-cognitive dynamic reconfiguration capabilities. Such “vertical” applications exhibit diverse performance/scalability requirements, and will rely on highly distributed, extremely virtualized, multi-tenant, and software-defined infrastructures. In such a context, handling the required operations in a scalable and dynamic fashion will be of paramount importance. A specific aspect, addressed by software-defined networking (SDN), regards the provision of suitable communication channels, once resource allocation mechanisms have performed the most efficient deployment of virtual network function instances, and VNF chaining needs to be implemented to enable network services. In this respect, this paper introduces the multi-cluster overlay (MCO) network paradigm: a tunnel-less SDN scheme for scalable realization of virtual tenant networks across the 5G distributed infrastructure, able to support (bulk) migrations of software instances among geo-distributed computing resources in a seamless and effective fashion. The numerical simulation and experimental results show that the MCO achieves up to over one order of magnitude smaller number of forwarding rules than the other state-of-the-art SDN mechanisms, while also assuring high performance during reconfiguration operations.