A provider network, comprising; a network substrate; one or more computing devices implementing an access control service configured to manage and evaluate policies on the provider network; and a plurality of host devices, wherein each host device is configured to implement one or more resource instances; wherein the one or more of the host devices are each configured to: obtain one or more network packets from a resource instance on the respective host device, wherein the resource instance is identified by security and/or authentication information; transmit a policy evaluation request to the access control service for a connection between the resource instance and a target indicated by the one or more network packets, wherein the access control service is configured to evaluate a policy associated with the resource instance to determine whether the resource instance is or is not allowed to open a connection to the target indicated by the one or more network packets according to an evaluation of a policy associated with the resource instance; receive a result of the policy evaluation request from the access control service; if the resource instance is not allowed to open a connection to the target indicated by the one or more network packets according to the policy, discard the one or more network packets without sending the one or more network packets to the target; if the resource instance is allowed to open a connection to the target indicated by the network packet according to the policy: encapsulate the one or more network packets according to an encapsulation protocol to generate one or more encapsulation packets; and tag the one or more encapsulation packets with the security and/or authentication information, and send the one or more encapsulation packets to be routed to the target via an overlay network over the network substrate according to routing information in the one or more encapsulation packets. obtain one or more network packets from a resource instance on the respective host device, wherein the resource instance is identified by security and/or authentication information; transmit a policy evaluation request to the access control service for a connection between the resource instance and a target indicated by the one or more network packets, wherein the access control service is configured to evaluate a policy associated with the resource instance to determine whether the resource instance is or is not allowed to open a connection to the target indicated by the one or more network packets according to an evaluation of a policy associated with the resource instance; receive a result of the policy evaluation request from the access control service; if the resource instance is not allowed to open a connection to the target indicated by the one or more network packets according to the policy, discard the one or more network packets without sending the one or more network packets to the target; if the resource instance is allowed to open a connection to the target indicated by the network packet according to the policy: encapsulate the one or more network packets according to an encapsulation protocol to generate one or more encapsulation packets; and tag the one or more encapsulation packets with the security and/or authentication information, and send the one or more encapsulation packets to be routed to the target via an overlay network over the network substrate according to routing information in the one or more encapsulation packets. encapsulate the one or more network packets according to an encapsulation protocol to generate one or more encapsulation packets; and tag the one or more encapsulation packets with the security and/or authentication information, and send the one or more encapsulation packets to be routed to the target via an overlay network over the network substrate according to routing information in the one or more encapsulation packets.