A first network node of a computer network discovers a host route by leveraging a temporary host route on the control plane of the computer network. The first network node receives, from a source host, a request for a host route associated with a destination host. The first network node determines that it has not previously stored the host route associated with the destination host, and generates a temporary host route associated with the destination host. The first network node propagates the temporary host route across the control plane of the computer network, causing each respective network node to discover if the destination host is connected to the respective network node.