A computing system having a processor and a memory coupled to the processor, the memory containing instructions that when executed by the processor, cause the processor to perform a method comprising: receiving an indication to migrate a virtual machine in a virtual network from a first network node of a underlay network to a second network node of the underlay network, the virtual network being implemented over the underlay network having a plurality of network nodes and the underlay network including multiple physical network nodes interconnected with one another and with physical end points; in response to receiving the indication to migrate the virtual machine, determining a network path in the underlay network between the first and second network nodes, the network path being different than a shortest path computed by a corresponding routing protocol, the routing protocol being MPLS and the routing protocol being used to pre-compute a network route for routing communications based on addresses of a source of the communication and the destination; migrating the virtual machine from the first network node to be hosted by the second network node following the determined network path in the underlay network; and during migration of the virtual machine, forwarding one or more messages from another virtual machine in the virtual network to the migrated virtual machine from the first network node to the second network node along the determined network path; the method further comprising relocating the virtual machine from a first server to a second server interconnected by the network nodes; wherein, during relocation, the IP address of the virtual machine in the underlay network changes from the IP address of the first server to the IP address of the second server; wherein an address of the virtual machine in an overlay network is decoupled from the IP address of the virtual machine in the underlay network, the overlay network being an abstracted network implemented over and operating on top of the underlay network and including one or more virtual networks implemented over the underlay network; wherein the virtual machine is identified by an end point identifier including a tenant virtual network identifier, a tenant address being an IP address in the virtual network, and an underlay network address, wherein the tenant virtual network identifier identifies the virtual network to which the virtual machine is attached to; wherein, in response to the relocation, the tenant virtual network identifier and the tenant address are maintained and the underlay network address is adjusted to correspond to the second server; wherein the network path is established in forwarding tables in the network nodes of the underlay network and the underlay network address is utilized to identify the network path in the underlay network. receiving an indication to migrate a virtual machine in a virtual network from a first network node of a underlay network to a second network node of the underlay network, the virtual network being implemented over the underlay network having a plurality of network nodes and the underlay network including multiple physical network nodes interconnected with one another and with physical end points; in response to receiving the indication to migrate the virtual machine, determining a network path in the underlay network between the first and second network nodes, the network path being different than a shortest path computed by a corresponding routing protocol, the routing protocol being MPLS and the routing protocol being used to pre-compute a network route for routing communications based on addresses of a source of the communication and the destination; migrating the virtual machine from the first network node to be hosted by the second network node following the determined network path in the underlay network; and during migration of the virtual machine, forwarding one or more messages from another virtual machine in the virtual network to the migrated virtual machine from the first network node to the second network node along the determined network path; the method further comprising relocating the virtual machine from a first server to a second server interconnected by the network nodes; wherein, during relocation, the IP address of the virtual machine in the underlay network changes from the IP address of the first server to the IP address of the second server; wherein an address of the virtual machine in an overlay network is decoupled from the IP address of the virtual machine in the underlay network, the overlay network being an abstracted network implemented over and operating on top of the underlay network and including one or more virtual networks implemented over the underlay network; wherein the virtual machine is identified by an end point identifier including a tenant virtual network identifier, a tenant address being an IP address in the virtual network, and an underlay network address, wherein the tenant virtual network identifier identifies the virtual network to which the virtual machine is attached to; wherein, in response to the relocation, the tenant virtual network identifier and the tenant address are maintained and the underlay network address is adjusted to correspond to the second server; wherein the network path is established in forwarding tables in the network nodes of the underlay network and the underlay network address is utilized to identify the network path in the underlay network.