1. A non-transitory computer-readable storage medium whose contents configure a computing system to perform a method, the method comprising: under control of the configured computing system, receiving information from a first client for use in configuring a first virtual computer network for the first client, the configuring including specifying inter-connections between multiple first computing nodes of the first virtual computer network, the configuring further including specifying a first connection between the multiple first computing nodes and a virtual peering router that enables interactions with one or more other second virtual computer networks that have multiple second computing nodes; and automatically providing the first virtual computer network in accordance with the configuring by overlaying the first virtual computer network on a distinct substrate network, the providing of the first virtual computer network including: establishing the first connection between the first virtual computer network and the virtual peering router; after the one or more second virtual computer networks have established one or more second connections to the virtual peering router, and after one or more routing communications are received from at least one of the second virtual computer networks that are directed to the virtual peering router via at least one of the established second connections, forwarding the received one or more routing communications to the first virtual computer network based at least in part on configuration information associated with the virtual peering router that includes first peering configuration information supplied by the first client for the virtual peering router, the first peering configuration information preventing routing communications from any virtual computer networks other than the one or more second virtual computer networks to be sent to the first computing nodes of the first virtual computer network via the virtual peering router, the forwarding being performed without physically providing the virtual peering router and including automatically determining whether to perform the forwarding based at least in part on the first peering configuration information; and automatically determining to not forward one or more additional routing communications to the first virtual computer network that are directed to the virtual peering router by one or more third virtual computer networks distinct from the one or more second virtual computer networks.