Techniques for determining a problem location or otherwise characterizing a network comprising a plurality of processing elements, including at least one processing element associated with performance of a packet encapsulation operation of an encapsulation protocol. The packet encapsulation operation is performed on a test packet to generate an encapsulated packet, the test packet having a time to live (TTL) value and an identifier. In conjunction with performance of the packet encapsulation operation, the TTL value and the identifier of the test packet are copied to a header of the encapsulated packet. The encapsulated packet is transmitted, and a determination is made as to whether a reply packet has been received responsive to transmission of the encapsulated packet. The reply packet, if any, is processed to obtain information utilizable in determining the problem location or otherwise characterizing the network. By way of example, these operations may be repeated, for subsequent test packets with increasing TTL values, until an amount of router hop information sufficient to determine the problem location is obtained.