Technologies for estimating network round-trip times include a sender computing node in network communication with a set of neighboring computing nodes. The sender computing node is configured to determine the set of neighboring computing nodes, as well as a plurality of subsets of the set of neighboring computing nodes. Accordingly, the sender computing node generates a message queue for each of the plurality of subsets, each message queue including a probe message for each neighboring node in the subset to which the message queue corresponds. The sender computing node is further configured to determine a round-trip time for each message queue (i.e., subset of neighboring computing nodes) based on a duration of time between the first probe message of the message queue being transmitted and an acknowledgment being received in response to the last probe message of the message queue being transmitted. Additionally, the sender computing node is configured to estimate a round-trip time for each of the neighboring computing nodes based on the round-trip times determined for each message queue. Other embodiments are described and claimed.