In one embodiment, a trigger is signaled to protect a tunnel from a head-end node to one or more tail-end nodes in a computer network via one or more intermediate nodes along the tunnel. One or more receiving nodes along the tunnel receive the trigger, and in response, establish a tunnel connectivity verification session from the receiving node to a corresponding downstream next-next-hop (NNHOP) node along the tunnel. Illustratively, the head-end node may thus recompute a new tunnel path excluding a path segment corresponding to a particular failed tunnel connectivity verification session.