In general, techniques are described for extending network connectivity software utilities, such as traceroute, to provide complete visibility into a network topology between a source device and a destination device, even when an intermediate network device may be actively utilizing multiple network links when forwarding packets toward the destination. In one example, a network device coupled to a plurality of paths and positioned between a source network device and destination network device may receive a traceroute packet. The network device may also, for each of the plurality of paths, modify a payload of the traceroute packet to include a respective identifier for a corresponding path of the plurality of paths to construct a respective modified traceroute packet for the corresponding path. The network device may also forward the respective modified traceroute packets on the corresponding paths.