Minimum-Pairs

The minimum-pairs (or MP) is an active measurement protocol to estimate in real-time the smaller of the forward and reverse one-way network delays (OWDs). It is designed to work in hostile environments, where a set of three network nodes can estimate an upper-bound OWDs between themselves and a fourth untrusted node. All four nodes must cooperate, though honest cooperation from the fourth node is not required. The objective is to conduct such estimates without involving the untrusted nodes in clock synchronization, and in a manner more accurate than simply half the Round-Trip Time (RTT). The MP protocol can be used in delay-sensitive applications (such as placing CDN replicas) or for secure Internet geolocation.

The MP protocol requires the three trusted network nodes to synchronize their clocks, and securely have access to their public keys, which could be achieved through a closed public-key infrastructure (PKI) system. The untrusted node needs not follow suit because it is not assumed to cooperate honestly. To estimate an upper bound to the smaller of the forward and reverse OWD between node A and the untrusted node X (see figure for notation), X first establishes an application-layer connection to all three nodes. This could be done transparently over the browser using, e.g., Web-sockets. The three nodes then take turns in exchanging digitally-signed timestamps.

Assuming node A begins, it sends a signed timestamp to X. Node X forwards that message to the other two nodes. When the message is received, its receiving time is recorded. The receiving node then verifies the signature, and calculates the time it took the message to traverse the network from its originator to the recipient passing by the untrusted node. This is done by subtracting the timestamp in the message from the receiving time. Node B then repeats the process, followed by node C. After all three nodes have taken turns, they end-up with six delay estimates corresponding to the links:

To estimate the smaller of the forward and reverse OWDs on the three network links between A, B, C and X, the minimum of each such pairs above is taken (i.e., the larger is discarded). Each of the three pairs then represents an approximate to the smaller OWD on each link, which generates a system of three equations in three unknowns. Solving those simultaneously for a, b, and c (see figure) gives the delay estimate.

...
Wikipedia