According to an example embodiment, a technique for operating a virtual private network (VPN) service in a multi-tenant data center is provided, the technique comprising operating, in the data center, a multi-tenant VPN server to relay data packets between a VPN tunnel that connects the multi-tenant VPN server to a remote network of a tenant and an overlay network service that implements the VPN for said tenant within the data center, wherein the data packets between the multi-tenant VPN server and the overlay network service are carried in a virtual local area network, VLAN, assigned for said tenant, and wherein the multi-tenant VPN server stores a multi-tenant forwarding table that stores a mapping between a tenant and a VLAN assigned for the tenant for a plurality of tenants.