Techniques are described for configuring communications between multiple computing nodes, such as computing nodes that are separated by one or more physical networks. In some situations, the techniques may be used to provide a virtual network between multiple computing nodes that are separated by one or more intermediate physical networks, such as from the edge of the one or more intermediate physical networks by modifying communications that enter and/or leave the intermediate physical networks so as to provide an overlay network without encapsulation of the communications. In some situations, the computing nodes may include virtual machine nodes hosted on one or more physical computing machines or systems, such as by or on behalf of one or more users (e.g., users of a program execution service).