Minimum-Pairs Protocol

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).

[1] It is designed to work in hostile environments, where a set of three network nodes can estimate an upper-bound OWD between themselves and a fourth untrusted node.

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 content delivery network 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 need not follow suit because it is not assumed to cooperate honestly.

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.

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.

When the nodes exchange the timestamp messages, they can only see the following: The system of equations thus becomes:

Injecting artificial delays by, e.g., holding onto the message for a little while instead of promptly forwarding it, enables the untrusted node to increase the estimated OWDs.

The MP protocol can thus estimate an upper bound for OWDs on all three links collectively between the trusted nodes and the untrusted one.

Compared to the average (i.e., RTT/2), the MP protocol never returns an estimate to the smaller of the forward and reverse OWD that is larger than that returned by the average method.

This is useful as it enables the calculation of expected error knowing the nature of delays on the links between the untrusted node and the trusted ones.