Patent ID: 8224971

Claim:
A computer-implemented method comprising: under control of one or more computing systems of a configurable network service that provides virtual computer networks to clients, receiving one or more requests to provide a first virtual computer network for a first client in accordance with specified configuration information, the configuration information indicating one or more specified networking devices of the first virtual computer network that interconnect multiple computing nodes of the first virtual computer network; and automatically providing the first virtual computer network in accordance with the configuration information by overlaying the first virtual computer network on a distinct substrate network without physically providing the one or more specified networking devices, the providing of the first virtual computer network including: forwarding multiple communications between the multiple computing nodes over the substrate network in a manner that emulates functionality that would be provided by the one or more specified networking devices if the one or more specified networking devices were physically provided; after the forwarding of the multiple communications, receiving one or more routing communications that are each directed to at least one of the specified networking devices and include network routing information for the first virtual computer network that is specified in accordance with one or more predefined network routing protocols, the one or more routing communications being sent by one or more nodes controlled by the first client that facilitate handling communications for at least part of the first virtual computer network; automatically analyzing the network routing information included in the one or more routing communications to identify one or more changes to make for the first virtual computer network while the first virtual computer network is operating that are not related to forwarding of communications between the multiple computing nodes of the first virtual computer network as part of the providing of the first virtual computer network; and automatically initiating the identified one or more changes.