A computing system having a processor and a 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 computer network from an originating network node to a target network node (111") in an underlay network, wherein the computer network has an overlay network implemented over the underlay network having a plurality of network nodes arranged into hierarchical domains (133, 135), and wherein the virtual machine has a network address in the overlay network; identifying a network path in the underlay network from the originating network node to the target network node based at least in part on a label associated with the target network node in the underlay network, the label corresponding to the network path traversing one or more of the network nodes of the underlay network between the originating network node and the target network node; and migrating the virtual machine from the originating network node to the target network node following the identified network path through the hierarchical domains of the underlay network, while maintaining the network address of the virtual machine in the overlay network: forwarding packets associated with the migrated virtual machine and encapsulated with a label of the underlay network to the target network node in the underlay network following the identified network path for a period of time until other virtual machines are updated with a new underlay network address of the migrated virtual machine, and wherein the underlay network is a label-based underlay network using multi-protocol label switching, MPLS, labels. receiving an indication to migrate a virtual machine in a computer network from an originating network node to a target network node (111") in an underlay network, wherein the computer network has an overlay network implemented over the underlay network having a plurality of network nodes arranged into hierarchical domains (133, 135), and wherein the virtual machine has a network address in the overlay network; identifying a network path in the underlay network from the originating network node to the target network node based at least in part on a label associated with the target network node in the underlay network, the label corresponding to the network path traversing one or more of the network nodes of the underlay network between the originating network node and the target network node; and migrating the virtual machine from the originating network node to the target network node following the identified network path through the hierarchical domains of the underlay network, while maintaining the network address of the virtual machine in the overlay network: forwarding packets associated with the migrated virtual machine and encapsulated with a label of the underlay network to the target network node in the underlay network following the identified network path for a period of time until other virtual machines are updated with a new underlay network address of the migrated virtual machine, and wherein the underlay network is a label-based underlay network using multi-protocol label switching, MPLS, labels. forwarding packets associated with the migrated virtual machine and encapsulated with a label of the underlay network to the target network node in the underlay network following the identified network path for a period of time until other virtual machines are updated with a new underlay network address of the migrated virtual machine, and wherein the underlay network is a label-based underlay network using multi-protocol label switching, MPLS, labels.