21
$\begingroup$

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?

Two robots one asymmetric network

$\endgroup$
10
  • 5
    $\begingroup$ See Clock synchronization in a network with asymmetric delays (which asks for something doable with typical Internet infrastructure). I think from what we saw when discussing wrong answers to that question the answer to your question is that it's impossible. $\endgroup$ Mar 21, 2012 at 13:14
  • $\begingroup$ Should we merge the questions, or are they different enough in target to keep separate? $\endgroup$ Mar 21, 2012 at 13:48
  • $\begingroup$ No, they are different questions. Your question establishes that it's impossible in a two-machine setting with just message passing. I'm hoping for solutions based on, say, latency information being available for some intermediate links on the route between the client and the server and having some way to propagate this information to the client. $\endgroup$ Mar 21, 2012 at 13:57
  • 3
    $\begingroup$ If there were a way to do this, Einstein's theory of relativity wouldn't work, since it depends on the fact that two observers who are space-like separated and have unknown one-way latencies cannot agree on a proper time. $\endgroup$
    – Peter Shor
    Mar 22, 2012 at 15:07
  • $\begingroup$ NTP does indeed allow/implement measuring this differential delay based on machines sending each other their time & not merely tracking send/receipt time of their own msgs but also the other servers via msg contents, see answer on gilles question $\endgroup$
    – vzn
    Oct 1, 2012 at 21:53

4 Answers 4

14
$\begingroup$

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

Sliding the clock skew exactly offset by latency asymmetry

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:

Sea sickness

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!

$\endgroup$
8
  • $\begingroup$ What's your opinion about this? software.internet2.edu/owamp $\endgroup$ Mar 20, 2015 at 6:25
  • $\begingroup$ @CMCDragonkai Keep in mind that the puzzle statement is more restrictive than reality. In practice you have options like measuring the length of fiber optic lines, logging at intermediate points, using knowledge of the network topology, slowly carrying a clock from one place to the other, etc. For example, GPS satellites move in known orbits and you can use that to remove degrees of freedom when solving. So on the surface I don't see any issue with a one-way ping tool, as long it or the clocks it is relying on are exploiting some of that sweet sweet tertiary information. $\endgroup$ Mar 20, 2015 at 17:12
  • $\begingroup$ Oh in that case, could you update your answer with possible work arounds then? $\endgroup$ Mar 21, 2015 at 2:44
  • $\begingroup$ @CMCDragonkai Having them in the comments is enough. They're beyond the scope of the puzzle. $\endgroup$ Mar 21, 2015 at 4:44
  • $\begingroup$ One-way latency does matter, for example for game networking. Also, everyone says impossible, but I can easily solve the puzzle on paper - once you synchronize clocks, all you do is measure the delay from A to B by sending A's time to B, with A->B delay being equal to B's time - A's sent time, and B->A being equal to latency - A->B delay $\endgroup$ Dec 11, 2015 at 15:03
1
$\begingroup$

I think it is impossible to figure out one-way latency just by comparing stopwatches.

$A$ sends $B$ his clock $C_{A1}$, let's say its value is 5.
$B$ acknowledges the message at time $C_{B1}=1$
$A$ sends his clock again, $C_{A2}=9$ (initial + round-trip latency).
$B$ receives at time $C_{B2}=5$.
And so on. Neither $A$ or $B$ can figure out when the other robot received a message with respect to their watches.

Maybe if you make it a bounty question someone will crack it. Until then, kudos.

$\endgroup$
0
$\begingroup$

I have found a way to BOTH discover which node is who (i.e. who has the longer message delay) AND estimate the one way trip delay. While the other answers are correct they are ONLY considering direct clock measurement approached which of course cannot work. However as I am proving here this is only part of the story as here is my working algorithm for the above:

Assume as in real life:

  • Links of finite bandwidth b

  • Each node has unique address (e.g. A and B)

  • Packet size p much smaller than the bandwidth*latency product

  • Nodes A and B are able to fill the channel

  • Nodes have a random() function

Each node fills the channel with its own packets (marked A or B respectively) OR forwards the packets it received from other nodes as follows:

Always fill the channel with my own packets except:
if I receive a packet from another node then
   Randomly choose to 
          either forward that packet from the other node
          or discard that packet and forward my own packet

Intuitive Explanation Since A's bandwidth*latency product is higher (because latency is higher) A will manage to have more packets received than B, therefore each Node can know who they are in the diagram.

Furthermore, with enough convergence time of running above algorithm the ratio of packets of A to B will denote the actual ratio of RTT delay of A to B and therefore the desired OTT.

SIMULATION RESULT TRACE Here is a simulation that proves the above and shows how A successfully converging toward 3 second delay and B converging around 1 second delay:

First seconds of Simulation

Subsequent seconds of Simulation

Explanation of Figures: Each line represents 1 second of time (packet size is chosen to have 1 second transmission time for clarity). Note that each node can start the algo at any time not in any particular sequence or time. The columns are as follows:

  • NODE A receives : What node A sees in its receiving side (this is also P4 below)

  • NODE A injects : What node A sends out (note this is A, or randomly A or B)

  • P1, P2, P3 : The three packets that are in transit (in order) between A and B (1 second transmission means 3 packets are in transit for a latency of 3)

  • NODE B receives : What B sees in its receiving side (this is P3)

  • NODE B injects : What B sends out (note this is B, or randomly A or B per algo)

  • P4 : The packet in transit from B to A (see also P1, P2, P3)

  • A counts A : What A counts for the A packets it has seen

  • A counts B : What A counts for the B packets it has seen

  • B counts A : What B counts for the A packets it has seen

  • B counts B : What B counts for the B packets it has seen

  • A->B : The latency that A estimates towards B (ratio of RTT of 4 seconds based on packets seen)

  • B->A : The latency that B estimates towards A (ratio of RTT of 4 seconds based on packets seen)

As we can see both nodes converge and stay around their true latency (actually we do not see that for A because more seconds are needed to converge but it does converge same behavior as B)

Better filters could converge faster but we can clearly see how they both converge around the correct values for their delays, therefore they can exactly know know their delay (even though I am showing their estimation only for illustration).

Also, even if bandwidths between the links are different the above method could still hold (although one will have to think about it more to be more certain) by using packet pairs to figure out bandwidth estimates and then just apply to the proportion equation above.

Conclusion We provided an algorithm for both A and B to know their position in the network and know their latency to the other node for the above diagram. We used a network measurement estimation method rather than clock-based approaches which indeed cannot lead to a solution due to recursive clock sync issue.

Note I now edited this answer providing all the simulations because no one would believe me I solved it so far as you can see in the first comments. Hopefully with these results someone can be more convinced and approve to help everyone at least find one error or correctness in this network measurement puzzle!

$\endgroup$
9
  • 3
    $\begingroup$ I don't think this works. Since the bandwidth is the same, the only difference that A and B see is that, if they started at the same time, B would wait 3s before receiving any data and A would wait 1s. But they don't have a shared clock so they don't know that they started at the same time. Maybe A doesn't hear anything for 10s because he started to run the protocol first. $\endgroup$ Dec 28, 2014 at 9:32
  • $\begingroup$ There is no requirement to start at the same time anyone can start at anytime.They just both have to run for some time. I appreciate you taking the time to review but please read again. This is statistical method and involves convergence. I am not saying I am 100% it is absolutely correct since I have not simulated but just the comment you made does not really apply in my opinion. Maybe this explains the idea more generally: if you accept that bandwidth*delay product is different for the two links then one link will in fact contain more packets - and that may be sensed by algo above... $\endgroup$ Dec 28, 2014 at 14:01
  • $\begingroup$ I don't think I've misunderstood but it's possible. Do you agree that the bandwidth is the same so both A and B receive data at the same rate? If so, won't they both converge to exactly the same thing? $\endgroup$ Dec 28, 2014 at 20:11
  • $\begingroup$ Yes of course they receive at the same rate, that does not mean they converge at the same thing. There are A and B packets in the network the question is what is the ratio of A vs B packets seen. I did run some simple simulation now and I do get the bias all the time. To get an idea since I guess I cannot post the whole thing here assume b is such that 1 packet takes one second transmission. Then there are always 4 packets in transit. Apply algorithm and boom we managed to measure OTT by avoiding synchronized clock/events methods which do not work with statistical convergence methods! $\endgroup$ Dec 28, 2014 at 21:00
  • $\begingroup$ What is “the proportion of packets of A vs B”? $\endgroup$ Dec 29, 2014 at 17:46
0
$\begingroup$

This is an answer to @user3134164 but is too big for a comment.

Here's my attempt at showing why this can't work (mathematical approach). Let's call $P_x$ the probability that robot $x$ chooses its own packets when it receives one of the other robot's packets, and $R_x$ the probability that a packet robot $x$ received is its own. After stationary regime has been achieved (that is, after an "infinite" amount of time, ie all convergence is done), we have the following :

  • $R_1 = (1 - R_2) \times (1 - P_2)$, and similarly $R_2 = (1 - R_1) \times (1 - P_1)$. The idea is that if a robot receives one of its own packets, it means the other robot received it instead of one of its own (hence the $1 - R_2$) and that it still chose to send it instead of one of its own (hence the product by $1 - P_2$).
  • This gives a system of two equations with two unknowns, $R_1$ and $R_2$. You might want to solve it, but it doesn't really matter. In fact, the ratios you're looking for are respectively $\frac{R_1}{1 - R_1}$ and $\frac{R_2}{1 - R_2}$. As you can notice, the only terms that appear in those expressions are the probabilities at which each robot chooses their own packet over the other's. The latencies don't even appear in the formula simply because both robots are pumping out packets constantly, so both are constantly receiving packets. They will indeed receive different ratios of packets, but it will only depend on the aforementionned probabilities.

This is why I believe this will lead you nowhere. Please do point out any mistake I could have made during this reasoning.

$\endgroup$
3
  • $\begingroup$ Welcome to Computer Science! Your answer looks nice but is, as you state, actually in depth commentary on @user3134164 's remark. I think you can resolve this issue in the following ways 1) Try to expand your answer such that this is also an answer to the actual question. or 2) Create a new question that essentially states the key misconception from user3134164 's comment and self-answer with an answer similar to this. Which one is appropriate is up to you. I think perhaps making a new question is a good idea, but maybe you can expand more than I think. Do ask if you have any further questions. $\endgroup$
    – Discrete lizard
    Mar 21, 2018 at 22:12
  • $\begingroup$ Of course, @user3134164 is also free to 'promote' the comment into a question, $\endgroup$
    – Discrete lizard
    Mar 21, 2018 at 22:12
  • $\begingroup$ "Px the probability that robot x chooses its own packets when it receives one of the other robot's packets" comes from a computer random() function as in the assumption - for example for two kinds of packets it will be always 0.5. If the random() function is a uniform enough then the "actual ratio of RTT delay of A to B " can be calculated. By your R definition I think R1 = (1-R2)*0.5 so the ratio is known. So I still believe my answer works fine. Thank you so much for taking the time to look into it. $\endgroup$ May 4, 2019 at 11:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.