In one embodiment, an exploratory linktrace is initiated from an initiating network device with an exploratory linktrace message (ELM) having a target address. Each network device receiving the ELM may then propagate the ELM on a plurality of its ports to a plurality of downstream network devices based on the target address. In addition, each receiving network device returns an exploratory linktrace reply (ELR) for each of the plurality of ports, where each ELR is returned according to one or more mechanisms to mitigate stormed replies to the initiating network device.