Techniques are described for determining latency in a physical network that includes a number of network devices over which packets travel. A virtual network controller receives a plurality of messages from a plurality of network devices in a network, each of the messages including a packet signature comprising a hash of an invariant portion of an original packet that uniquely identifies the original packet, an identifier of one of the plurality of network devices from which the respective message was received, and a timestamp indicating a time an original packet was processed by the network device from which the respective message was received. The virtual network controller determines a latency of a physical network path in the network based on analysis of contents of the identified messages having a common packet signature.