A first service of a provider network obtains an identification of one or more substrate addressable devices included in an extension of the provider network. Based on the identification, a launch of one or more compute instances within the provider network is initiated. The one or more compute instances are to connect the provider network to the extension of the provider network across at least a third-party network by receiving a first control plane message directed to a first substrate addressable device of the one or more substrate addressable devices, by updating a message state data store based at least in part on the first control plane message, and by sending a second control plane message to the first substrate addressable device via a secure tunnel.