1. A computer-implemented method comprising: receiving configuration information for a first virtual computer network having a plurality of computing nodes and having a first virtual local area network that includes a first computing node and one or more other computing nodes of the plurality of computing nodes, the configuration information further specifying that the first computing node uses a first communication link configured to be associated with multiple virtual local area networks; and providing, by one or more configured computing systems, the first virtual computer network in accordance with the received configuration information by overlaying the first virtual computer network on a distinct substrate network and by emulating functionality corresponding to the first virtual local area network by: initiating, by the one or more configured computing systems, forwarding of a communication over the substrate network to the first computing node without the forwarded communication including an identifier specific to the first virtual local area network; after the forwarding of the communication over the substrate network, modifying, by the one or more configured computing systems, the communication to include the identifier specific to the first virtual local area network based on the first computing node being included in the first virtual local area network and based on the first communication link being configured to be associated with multiple virtual local area networks; and providing, by the one or more configured computing systems, the modified communication to the first computing node.