Techniques and architecture are described for providing a service, e.g., a security service such as a firewall, across different virtual networks/VRFs/VPN IDs. The techniques and architecture provide modifications in enterprise computing fabrics by modifying pull-based overlay protocols such as, for example, locator/identifier separation protocol (LISP), border gateway protocol ethernet virtual private network (BGP EVPN), etc. A map request carries additional information to instruct a map-server that even though mapping (destination prefix and firewall service RLOC for the destination) is known within the map-server's own virtual network/VRF for firewall service insertion, the map-server still should do a lookup across virtual networks/VRFs and discover the final destination's DGT (destination group tag) and include that in the map reply.