1. A computer-implemented method, comprising: providing, by one or more configured computing systems, a virtual computer network for a client in accordance with configuration information that indicates one or more networking devices interconnecting multiple computing nodes of the virtual computer network, the providing including overlaying the virtual computer network on a distinct substrate computer network and emulating functionality of the one or more networking devices to enable communications between the multiple computing nodes to be forwarded over the substrate computer network; assigning, by the one or more configured computing systems, network addresses for the virtual computer network to represent the one or more networking devices; receiving, by the one or more configured computing systems, one or more routing communications that are each directed to at least one of the one or more networking devices using the assigned network addresses for the at least one networking devices, the one or more routing communications being sent via a connection between the virtual computer network and one or more remote computing systems of the client and including network routing information corresponding to the one or more remote computing systems; and forwarding, by the one or more configured computing systems, one or more subsequent communications from the multiple computing nodes to the one or more remote computing systems over the connection based on the included network routing information from the received one or more routing communications.