In general, techniques are described for determining a physical network path taken by packets of a network packet flow. The techniques may be applied to determine, or “trace,” a physical network path in the virtualized network domain. In some examples, a network device includes one or more processors and a switch executed by the processors to forward packets of a packet flow to a physical network path. The network device also includes a flow trace module to generate one or more flow trace packets having incrementally increasing respective time-to-live (TTL) values, wherein the switch module forwards the flow trace packets on an outbound interface of the network device for the physical network path, and wherein the flow trace module receives corresponding time exceeded messages for the flow trace packets, wherein each of the time exceeded message includes a source network address of a network element on the physical network path.