In one embodiment, a head-end node of a tunnel, relative to a tail-end node, receives a trace request, and in response, generates an out-of-tunnel trace request based on the trace-request. The trace request is transmitted in-tunnel to the tail-end node, while also transmitting the out-of-tunnel trace request to at least one subsequent node. The head-end node may then receive a trace response from the tail-end node based on the in-tunnel trace request, as well as a trace response from each of the subsequent nodes based on the out-of-tunnel trace request.