Techniques for network latency estimation in a computer network are disclosed herein. One example technique includes instructing first and second nodes in the computer network to individually perform traceroute operations along a first round-trip route and a second round-trip route between the first and second nodes. The first round-trip route includes an inbound network path of an existing round-trip route between the first and second nodes and an outbound network path that is a reverse of the inbound network path. The second round-trip route has an outbound network path of the existing round-trip route and an inbound network path that is a reverse of the outbound network path. The example technique further includes upon receiving traceroute information from the additional traceroute operations, determine a latency difference between the inbound and outbound network paths of the existing round-trip route based on the received additional traceroute information.