Server software running at a provider substrate extension 224 may be designed by the cloud provider to run on the cloud provider substrate network, and this software may be enabled to run unmodified in a provider substrate extension 224 by using local network manager(s) 242 to create a private replica of the substrate network within the edge location (a “shadow substrate”). The local network manager(s) 242 can run on provider substrate extension 224 servers and bridge the shadow substrate with the provider substrate extension 224 network, for example, by acting as a virtual private network (VPN) endpoint or endpoints between the provider substrate extension 224 and the proxies 245, 248 in the cloud provider network 203 and by implementing the mapping service (for traffic encapsulation and decapsulation) to relate data plane traffic (from the data plane proxies 248) and control plane traffic (from the control plane proxies 245) to the appropriate server(s). By implementing a local version of the provider network's substrate-overlay mapping service, the local network manager(s) 242 allow resources in the provider substrate extension 224 to seamlessly communicate with resources in the cloud provider network 203. In some implementations, a single local network manager 242 can perform these actions for all servers hosting compute instances in a provider substrate extension 224. In other implementations, each of the server hosting compute instances may have a dedicated local network manager 242. In multi-rack edge locations, inter-rack communications can go through the local network managers 242, with local network managers maintaining open tunnels to one another.