In one embodiment, a method includes receiving a packet at a tunnel end point in a multi-tenant network, the packet comprising a destination, performing a lookup for the destination in a database comprising a mapping of global identifiers to local tenant identifiers for different hosting locations, each of the global identifiers uniquely identifying a tenant across all of the hosting locations, identifying a destination tunnel end point and a local tenant identifier for the destination, and inserting the destination tunnel end point and the local tenant identifier into the packet and forwarding the packet. An apparatus and logic are also disclosed herein.