Rewriting communication headers to manage virtual networks of virtual machines

A system, comprising:

• one or more computing systems that implement a network-accessible service, configured to:
• manage, by a communication manager, communications to and from a computing node in a virtual computer network of computing nodes provided for a client,
• wherein the computing nodes are virtual machine instances hosted on physical hosts in a substrate network, and
• wherein the managing includes to:
• obtain, from a system manager of the network-accessible service, mapping information that maps a virtual network address of the computing node in the virtual computer network to a substrate network address in the substrate network;
• receive communication for the computing node on the substrate network;
• identify substrate network addresses for a sending node and a destination node of the communication from a header of the communication;
• perform one or more interactions with the system manager to verify that the substrate network address of the sending node identified from the header of the communication is mapped to a known virtual network address in the virtual computer network;
• retrieve, from the mapping information, the virtual network address of the computing node that is mapped to the substrate network address of the destination node of the communication;
• rewrite the header of the communication to indicate the virtual network address of the computing node;
• and
• provide the rewritten communication to the computing node.

One or more non-transitory computer-readable media having stored program instructions that when executed on or across one or more computing systems implement a communication manager of a network-accessible service and cause the communication manager to:

• manage communications to and from a computing node in a virtual computer network of computing nodes provided for a client,
• wherein the computing nodes are virtual machine instances hosted on physical hosts in a substrate network, and
• wherein the managing includes to:
• obtain, from a system manager of the network-accessible service, mapping information that maps a virtual network address of the computing node in the virtual computer network to a substrate network address in the substrate network;
• receive a communication for the computing node on the substrate network;
• identify substrate network addresses for a sending node and a destination node of the communication from a header of the communication;
• perform one or more interactions with the system manager to verify, that the substrate network address of the sending node identified from the header of the communication is mapped to a known virtual network address in the virtual computer network;
• retrieve, from the mapping information, the virtual network address of the computing node that is mapped to the substrate network address of the destination node of the communication;
• rewrite the header of the communication to indicate the virtual network address of the computing node;
• and
• provide the rewritten communication to the computing node.