patternModerate
Clock synchronization in a network with asymmetric delays
Viewed 0 times
asymmetricsynchronizationwithdelaysclocknetwork
Problem
Assume a computer has a precise clock which is not initialized. That is, the time on the computer's clock is the real time plus some constant offset. The computer has a network connection and we want to use that connection to determine the constant offset $B$.
The simple method is that the computer sends a query to a time server, noting the local time $B + C_1$. The time server receives the query at a time $T$ and sends a reply containing $T$ back to the client, which receives it at a time $B + C_2$. Then $B + C_1 \le T \le B + C_2$, i.e. $T - C_2 \le B \le T - C_1$.
If the network transmission time and the server processing time are symmetric, then $B = T - \dfrac{C_1 + C_2}{2}$. As far as I know, NTP, the time synchronization protocol used in the wild, operates on this assumption.
How can the precision be improved if the delays are not symmetric? Is there a way to measure this asymmetry in a typical Internet infrastructure?
The simple method is that the computer sends a query to a time server, noting the local time $B + C_1$. The time server receives the query at a time $T$ and sends a reply containing $T$ back to the client, which receives it at a time $B + C_2$. Then $B + C_1 \le T \le B + C_2$, i.e. $T - C_2 \le B \le T - C_1$.
If the network transmission time and the server processing time are symmetric, then $B = T - \dfrac{C_1 + C_2}{2}$. As far as I know, NTP, the time synchronization protocol used in the wild, operates on this assumption.
How can the precision be improved if the delays are not symmetric? Is there a way to measure this asymmetry in a typical Internet infrastructure?
Solution
Inability to measure asymmetry
No, you can't measure the asymmetry. Consider these two communication diagrams, the first with a negative clock offset and equal delays and the second with no clock offset and entirely asymmetric delays (but the same round trip time).
The important thing to notice is that, from the perspective of both the PC and the server, the two interactions are exactly identical. They receive messages at the same time. They send messages at the same time.
You can create more cases by 'grabbing' the PC timeline and 'sliding' it, holding the message send/receive points fixed relative to their respective timelines. The asymmetries you cause are exactly negated by the clock offset. In fact, you can even make messages go BACKWARDS IN TIME one way (as long as the round trip time is still the same) and the server/client STILL can't tell!
Therefore it is impossible to measure latency asymmetries. In the worst case, where you have no information other than that one way latencies are positive and sum to the round trip time, the accuracy of clock synchronization is limited to the round trip time.
Can intermediate infrastructure help?
Whether or not the intermediate infrastructure can help will be heavily dependent upon your theoretical model of the situation.
If the asymmetry is constant and the intermediate infrastructure is the routers on the communication path between you and the server, then no. Even if each router synchronized their clock with the adjacent router, the errors would compound in the same way as if you had synchronized with the server via communication across the routers.
In the real world you can rely on delays being somewhat symmetric for architectural reasons, repeated synchronizations to reduce asymmetry due to queuing delays (etc), and multiple communication paths to reduce other sorts of asymmetry.
If you put your model's assumptions somewhere in between (because it's interesting to explore model space, of course) I expect the result should also be somewhere in between.
No, you can't measure the asymmetry. Consider these two communication diagrams, the first with a negative clock offset and equal delays and the second with no clock offset and entirely asymmetric delays (but the same round trip time).
The important thing to notice is that, from the perspective of both the PC and the server, the two interactions are exactly identical. They receive messages at the same time. They send messages at the same time.
You can create more cases by 'grabbing' the PC timeline and 'sliding' it, holding the message send/receive points fixed relative to their respective timelines. The asymmetries you cause are exactly negated by the clock offset. In fact, you can even make messages go BACKWARDS IN TIME one way (as long as the round trip time is still the same) and the server/client STILL can't tell!
Therefore it is impossible to measure latency asymmetries. In the worst case, where you have no information other than that one way latencies are positive and sum to the round trip time, the accuracy of clock synchronization is limited to the round trip time.
Can intermediate infrastructure help?
Whether or not the intermediate infrastructure can help will be heavily dependent upon your theoretical model of the situation.
If the asymmetry is constant and the intermediate infrastructure is the routers on the communication path between you and the server, then no. Even if each router synchronized their clock with the adjacent router, the errors would compound in the same way as if you had synchronized with the server via communication across the routers.
In the real world you can rely on delays being somewhat symmetric for architectural reasons, repeated synchronizations to reduce asymmetry due to queuing delays (etc), and multiple communication paths to reduce other sorts of asymmetry.
If you put your model's assumptions somewhere in between (because it's interesting to explore model space, of course) I expect the result should also be somewhere in between.
Context
StackExchange Computer Science Q#103, answer score: 12
Revisions (0)
No revisions yet.