A method for provisioning a virtual private gateway, VGW, the method comprising: receiving, by a VGW provisioning service, a request to establish a VGW from a customer of a service provider, the request specifying a service provided by the service provider to the customer to be accessible through the VGW and a customer-configurable policy configured to restrict access to the specified service to requests sent via the VGW to the specified service, the specified service having a public Internet Protocol, IP, address; and responsive to the request, establishing the VGW by the VGW provisioning service, including: instantiating a VGW virtual machine on a compute device; providing the customer-configurable policy to the specified service for compliance; causing route data for the specified service to be provided to the VGW virtual machine; and configuring a VGW application on the VGW virtual machine to: establish a secure channel over a public network to a remote node; receive an encrypted packet from the remote node over the secure tunnel and the encrypted packet containing a service request for the service: decrypt the encrypted packet to obtain the service request; using information in headers of the service request, access the route data to determine a route to the service targeted by the service request; and forward the service request across the determined route to the service targeted by the request receiving, by a VGW provisioning service, a request to establish a VGW from a customer of a service provider, the request specifying a service provided by the service provider to the customer to be accessible through the VGW and a customer-configurable policy configured to restrict access to the specified service to requests sent via the VGW to the specified service, the specified service having a public Internet Protocol, IP, address; and responsive to the request, establishing the VGW by the VGW provisioning service, including: instantiating a VGW virtual machine on a compute device; providing the customer-configurable policy to the specified service for compliance; causing route data for the specified service to be provided to the VGW virtual machine; and configuring a VGW application on the VGW virtual machine to: establish a secure channel over a public network to a remote node; receive an encrypted packet from the remote node over the secure tunnel and the encrypted packet containing a service request for the service: decrypt the encrypted packet to obtain the service request; using information in headers of the service request, access the route data to determine a route to the service targeted by the service request; and forward the service request across the determined route to the service targeted by the request instantiating a VGW virtual machine on a compute device; providing the customer-configurable policy to the specified service for compliance; causing route data for the specified service to be provided to the VGW virtual machine; and configuring a VGW application on the VGW virtual machine to: establish a secure channel over a public network to a remote node; receive an encrypted packet from the remote node over the secure tunnel and the encrypted packet containing a service request for the service: decrypt the encrypted packet to obtain the service request; using information in headers of the service request, access the route data to determine a route to the service targeted by the service request; and forward the service request across the determined route to the service targeted by the request establish a secure channel over a public network to a remote node; receive an encrypted packet from the remote node over the secure tunnel and the encrypted packet containing a service request for the service: decrypt the encrypted packet to obtain the service request; using information in headers of the service request, access the route data to determine a route to the service targeted by the service request; and forward the service request across the determined route to the service targeted by the request decrypt the encrypted packet to obtain the service request; using information in headers of the service request, access the route data to determine a route to the service targeted by the service request; and forward the service request across the determined route to the service targeted by the request