A latency floor between two nodes of a packet-switched network is estimated using transit times of a group of packets traversing the two nodes. In particular, a periodically generated histogram of packet transit times is used to estimate the latency floor. In some packet-switched networks, the behavior of some network elements changes drastically when the network is congested. Because latency floor cannot be accurately estimated under such conditions, packet transit times collected during a congested state of the network are discarded.