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

Methodology
Illustration of the MP protocol. A number in cell <i,j> indicates the calculated OWD (e.g., in millisecond) from the node indicated at row i to node X to the node indicated at column j.

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:

  • A → X → B and B → X → A
  • A → X → C and C → X → A
  • B → X → C and C → X → B

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.

Numerical Example

Assume the actual delays (e.g., in millisecond) to node X from nodes A, B and C and vice versa are as follows:

ABC
To node X 582
From node X 644

Those are the unknown delays. We need to estimate the smaller of the forward and reverse on each of the three links. In this example, the smaller is 5ms, 4ms, and 2ms on the links between X and the three trusted nodes respectively (A, B, and C). When the nodes exchange the timestamp messages, they can only see the following:

  • A → X → B = 9ms and B → X → A = 14ms (9ms is the smaller)
  • A → X → C = 9ms and C → X → A = 8ms (8ms is the smaller)
  • B → X → C = 12ms and C → X → B = 6ms (6ms is the smaller)

The system of equations thus becomes:

which results in estimates to the smaller OWDs of:

In this case, the absolute errors are , , and on all three links respectively. In comparison, the average RTT would calculate the OWD on all three links as 5.5ms, 6ms, and 3ms, resulting in absolute errors of 0.5ms, 2ms, and 1ms respectively. Therefore, the MP protocol is more accurate in this example.

Analysis

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. For example, if the estimated delays (forward or reverse) were 30ms, 40ms, and 50ms, the actual cannot be 60ms, 70ms and 80ms because that means the untrusted node managed to reduce all three together, which is hard to achieve since delays are bound by the physical characteristics of the transmission media. Note however that the untrusted node may in some case be able to reduce a subset of the links, but not all, by selectively delaying some of the links.

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. Additionally, the probability distribution of absolute error for the MP protocol has been derived[2] as a function of the underlying delay distribution. 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.

See also

References
  1. Abdou, AbdelRahman (2015). "4". Internet Location Verification: Challenges and Solutions (Ph.D.). Carleton University.
  2. Abdou, AbdelRahman; Matrawy, Ashraf; van Oorschot, Paul (May 2015). "Accurate One-Way Delay Estimation with Reduced Client-Trustworthiness". IEEE Communications Letters. 19 (5): 735–738. CiteSeerX 10.1.1.696.7425. doi:10.1109/LCOMM.2015.2411591.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.