Routing messages between virtual networks using a mapping of virtual addresses from one virtual network to a virtual address of the other virtual network. Each virtual network has a valid set of virtual addresses, some of which being assigned to virtual nodes within the corresponding network. When a virtual network identifies a message to be sent, it identifies a destination for the message. Some destinations may be within the same virtual network and thus may be routed to virtual nodes within the virtual network. Other destinations may instead be mapped to a virtual address of another virtual network. In that case, routing information may also be obtained and the message may be dispatched to the virtual address of the other virtual network. This may be performed without the need for a gateway, which publishes a public address that is globally unique.