In one embodiment, a supervisory device designates a particular networking device among a set of networking devices as a seed device and one or more interfaces of the seed device as discovery interfaces. The supervisory device coordinates, starting from the one or more discovery interfaces of the seed device, discovery of a Layer 2 topology of the set of networking devices, by designating one or more interfaces of a discovered networking device as discovery interfaces. The supervisory device converts, starting from at least one of the network devices farthest from the seed device in the Layer 2 topology and ending with the seed device, links of the Layer 2 topology into Layer 3 links, to form an underlay network.