Systems, methods, and non-transitory computer-readable storage media for managing routing information in overlay networks. A first tunnel endpoint in an overlay network may receive an encapsulated packet from a second tunnel endpoint. The encapsulated packet may have been encapsulated at the second tunnel endpoint based on another packet originating from a source host that is associated with the second tunnel endpoint. The encapsulated packet can include a source host address for the source host and a source tunnel endpoint address for the second tunnel endpoint. The first tunnel endpoint can then update a lookup table based on an association between the source host address and the source tunnel endpoint address.