1. A computer-implemented method comprising: providing, by one or more programmed computing systems, a first virtual computer network by overlaying the first virtual computer network on a distinct substrate network; receiving an indication of a first communication that is directed to a first network address from a first computing node of the first virtual computer network at a first geographical location, the first network address being associated with a first external destination that is not at the first geographical location; before forwarding the first communication over the substrate network from the first computing node, selecting, by the one or more programmed computing systems, an edge device from a group of multiple alternative edge devices connected to the substrate network at the first geographical location to use for the first communication, the selecting being performed in a configured manner that is based at least in part on the first network address; and initiating forwarding, by the one or more programmed computing systems, of the first communication over the substrate network from the first computing node to the selected edge device, to enable further forwarding of the first communication by the selected edge device to the first external destination.