A method implemented by a sending host implemented as a network element (NE) comprises receiving, by a receiver of the sending host, a set of locators from a distributed mapping system, each of the locators in the set of locators being an address associated with the receiving host, storing, in a memory of the sending host, the set of locators in an entry of a local identifier (ID)-to-locator database in association with an ID of the receiving host, transmitting, by a transmitter of the sending host, a plurality of packets to a plurality of endpoint routers (xTRs), each of the xTRs associated with each of the locators in the set of locators, and receiving, by the receiver of the sending host, a response from one of the xTRs in response to sending the plurality of packets to the plurality of xTRs, a locator associated with the one of the xTRs being an address of a current location of the receiving host.