1. A computer-implemented method comprising: providing, by one or more configured computing systems, networking functionality for a first virtual computer network overlaid on a substrate network, the first virtual computer network having a specified virtual local area network logically interconnecting multiple computing nodes, the providing of the networking functionality including: tracking, by the one or more configured computing systems, an identifier specific to the specified virtual local area network; modifying, by the one or more configured computing systems, a communication sent to a destination computing node of the multiple computing nodes from another of the multiple computing nodes, the modifying being performed before the communication is forwarded over the substrate network and including removing the identifier from the communication if the communication includes the identifier; forwarding the modified communication over the substrate network to the destination computing node; after the forwarding of the modified communication, further modifying, by the one or more configured computing systems, the modified communication to include the identifier; and initiating providing, by the one or more configured computing systems, the further modified communication to the destination computing node.