Techniques are described for providing managed virtual computer networks that have a configured logical network topology with virtual networking devices, such as by a network-accessible configurable network service, with corresponding networking functionality provided for communications between multiple computing nodes of the virtual computer network by emulating functionality that would be provided by the virtual networking devices if they were physically present. In some situations, the networking functionality provided for a managed computer network of a client includes receiving routing communications directed to the virtual networking devices and using included routing cost information to update the configuration of the managed computer network, and/or includes determining actual cost information corresponding to use of an underlying substrate network and providing routing cost information to the client that reflects the determined actual cost information, so as to enable the client to modify the configuration of the managed computer network accordingly.