Measuring one way network latency

Problem Detail: 

This is a puzzle about measuring network latency that I created. I believe the solution is that it's impossible, but friends disagree. I'm looking for convincing explanations either way. (Though it is posed as a puzzle I think it fits on this web site because of its applicability to the design and experience of communication protocols such as in online games, not to mention NTP.)

Suppose two robots are in two rooms, connected by a network with differing one-way latencies as shown in the graphic below. When robot A sends a message to robot B it takes 3 seconds for it to arrive, but when robot B sends a message to robot A it takes 1 second to arrive. The latencies never vary.

The robots are identical and do not have a shared clock, though they can measure the passage of time (e.g. they have stop watches). They do not know which of them is robot A (whose messages are delayed 3s) and which is robot B (whose messages are delayed by 1s).

A protocol to discover the round trip time is:

whenReceive(TICK).then(send TOCK)  // Wait for other other robot to wake up send READY await READY send READY  // Measure RTT t0 = startStopWatch() send TICK await TOCK t1 = stopStopWatch() rtt = t1 - t0  //ends up equalling 4 seconds 

Is there a protocol to determine the one way trip delays? Can the robots discover which of them has the longer message sending delay?

Asked By : Craig Gidney

Answered By : Craig Gidney

The following diagram, from a blog post I wrote, is a visual proof that it's impossible:

Notice how the packet arrival times on each side stay the same, even as the one-way latencies change (and even become negative!). The first packet always reaches the server at 1.5s on the server's clock, the second always reaches the client at 2s on the client's clock, etc. The packet contents and local arrival times are the only things a protocol could be based on, but the contents and arrival times can be held constant as the asymmetry varies by also varying the initial clock skew.

Basically, asymmetry in the one-way latencies looks exactly like clock skew. Since the problem states we don't start off knowing the initial clock skew or the one-way latency asymmetry, and varying one looks like varying the other so their effects are indistinguishable, we can't separate their contributions in order to solve for the one-way latency asymmetry. It's impossible.

More formally, you can't solve for edge lengths when given only the lengths of the cycles. The cycle basis has $n-1$ degrees of freedom, corresponding to $n-1$ unknown clock skews relative to one of the participants. You can always hide the one-way latencies, even when there are many participants:

If you're not so visually inclined, I have another intuitive argument. Imagine a time portal to a hundred years in the future. As you chat across it to someone on the other side, you realize the conversation is totally normal despite the hundred year asymmetry in one-way delays. Any observable effect would have been obvious on that scale!

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/602