Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for implementing virtual network pairs between virtual machines and other devices. In one aspect, a method includes receiving a plurality of outgoing packets from one or more source virtual machines executing on the data processing apparatus, each source virtual machine being a hardware virtualization of the data processing apparatus and each packet destined for a destination virtual machine; establishing a plurality of virtual network pairs, one for each unique pair of source and destination virtual machines, wherein establishing the plurality of virtual network pairs comprises obtaining, from an external data processing apparatus, a different network address for each destination virtual machine; encapsulating each outgoing packet in a message; and sending each message to the destination virtual machine for the respective packet by sending the message to the respective network destination address.