Re: [ntp:questions] Asymmetric Delay and NTP
Joe Gwinn wrote:
William Unruh un...@invalid.ca wrote:
Joe Gwinn joegw...@comcast.net wrote:
We have a more direct diagnostic available
-- abruptly turn the background traffic off while observing
time slew with respect to a free-running rubidium.
Sure. As I said if you have a different clock then you can do more.
The Rb unit will not tell us the time, but will tell us
how much our sense of time slewed when the interference
was removed.
See Also: Chip Scale Atomic Clock
Cesium vapor cell microwave laser beam oscillator reference RTC in a Chip
e.g. symmetricom.com/csac Time of day, PPS, ...
{Accuracy / Stability to a few pico sec isn't cheap though}
--
E-Mail Sent to this address blackl...@anitech-systems.com
will be added to the BlackLists.
___
questions mailing list
questions@lists.ntp.org
http://lists.ntp.org/listinfo/questions
Re: [ntp:questions] Asymmetric Delay and NTP
In article lh9fe1$plc$2...@dont-email.me, William Unruh un...@invalid.ca wrote: On 2014-03-30, Joe Gwinn joegw...@comcast.net wrote: Magnus, In article 53375aba.5070...@rubidium.dyndns.org, Magnus Danielson mag...@rubidium.dyndns.org wrote: On 24/03/14 14:38, Joe Gwinn wrote: [snip] [MD] The *one* thing you can figure out with more measurements is how non-zero-mean noise such as network traffic contribute to asymmetry. You can do pretty good approximations of that contribution. However, if there is an underlying asymmetry in static delay sources, they won't disclose themselves with more measurements of the set measurements. [JG] Yes. One way to think of it is to describe the delay asymmetry as a random process having a mean and a standard deviation. One can estimate the standard deviation, but not the mean, from received timestamp packets. IF there is another source to compare it with. If you only have one source of time, you cannot differentiate the fluctuations in the assymetry from the fluctuations in the remote or local clock. With more than one source you can, but as you say, you cannot discover the mean. While for short term fluctuations in the asymmetery you could probably assume that they are path, not clocks, for longer term ones you cannot. We generally assume that the clocks are good, which is to say that they don't jump around nearly as rapidly the the delay asymmetry. So one can tease clock offset from standard deviation of delay asymmetry by their spectra. Joe Gwinn ___ questions mailing list questions@lists.ntp.org http://lists.ntp.org/listinfo/questions
Re: [ntp:questions] Asymmetric Delay and NTP
On 24/03/14 14:38, Joe Gwinn wrote: Magnus, In article 532fa47b.7060...@rubidium.dyndns.org, Magnus Danielson mag...@rubidium.dyndns.org wrote: Joe, On 23/03/14 23:20, Joe Gwinn wrote: Magnus, In article 532e45db.5000...@rubidium.dyndns.org, Magnus Danielson mag...@rubidium.dyndns.org wrote: Joe, On 21/03/14 17:04, Joe Gwinn wrote: [snip] It is interesting. I've now read it reasonably closely. The basic approach is to express each packet flight in a one-line equation (a row) in a linear-system matrix equation, where the system matrix (the A in the traditional y=Ax+b formulation, where b is zero in the absence of noise), where A is 4 columns wide by a variable number of rows long (one row to a packet flight), and show that one column of A can always be computed from the two other columns that describe who is added and subtracted from who. In other words, these three columns are linearly dependent on one another. The forth column contains measured data. This dependency means that A is always rank-deficient no matter how many packets (including infinity) and no matter the order, so the linear system cannot be solved. It is just another formulation of the same equations I provided. For each added link, one unknown and one measure is added. For each added node, one unknown is added. True, but there is more. Let's come back to that. As you do more measures, you will add information about variations the delays and time-differences between the nodes, but you will not disclose the basic offsets. Also true. The advantage of the matrix formulation is that one can then appeal to the vast body of knowledge about matrixes and linear systems. It's not that one cannot prove it without the matrixes, it's that the proof is immediate with them - less work. And the issue was to prove that no such system could work. As much as I like matrix formulation, it ain't giving you much more in this case, rather than a handy notation. The trouble is that beyond the properties of the noise, there is no information leakage about the static time-errors and asymmetries. You end up having free variables. Yes. You correctly noted the mathematical equivalence of the two approaches, and I agree. My point was that the matrix approach is less work to get to the desired proof because by formulation as a linear solution with matrixes, one immediately inherits lots of properties and proofs. The problem is that the unknown and the relationships builds up in an uneven rate, and the observations only relate to two unknowns. The only trustworthy fact we get is the sum of the delays, but no real hint about its distribution. If you do more observations along the same paths, you can do some statistics, but you won't get un-biased result without adding a prior knowledge one way or another. Formulate it as you wish, but as you add more observations, those will be reduced to by their linear properties to equations existing and noise. You need to add observations which does not fully reduce in order for your equation system to grow to such size that you can solve it. Yes, this is a good statement of the consequences of the proof. Thanks. Show me how you achieve it, and I listen. I don't understand the challenge. There is no dispute. It's not a personal challenge, it's a wide-spread challenge. If someone worked something out I'm really keen to learn about it. I've spent quite some time about figuring these things out as I need to understand them. The *one* thing you can figure out with more measurements is how non-zero-mean noise such as network traffic contribute to asymmetry. You can do pretty good approximations of that contribution. However, if there is an underlying asymmetry in static delay sources, they won't disclose themselves with more measurements of the set measurements. What you *can* do is bring a precise time to the first slave, measure the time-error, compensate for it and then step-by-step calibrate a path. The trouble is that you know adds the a prior assumption of stable asymmetry, which may not be true. I've experienced it not to be true. It is only by cheating that you can overcome the limits of the system. Is GPS cheating? That's our usual answer, but GPS isn't always available or possible. If you are trying to solve it within a network, it is. You can convert your additional GPS observation into an a prior knowledge, and once you done enough of those, then you can solve it completely. The estimated variables better stay static thought, or you have to start over again. GPS is the usual answer, but isn't always available or useful. I know, I know. Recall that the original question was random asymmetry due to asymmetric background traffic in a PTP network. If the network is controllable, a lab experiment is to simply turn the background traffic off and see how much the clocks change with respect to one another. But this tells one how much trouble one is in,
Re: [ntp:questions] Asymmetric Delay and NTP
Magnus, In article 532fa47b.7060...@rubidium.dyndns.org, Magnus Danielson mag...@rubidium.dyndns.org wrote: Joe, On 23/03/14 23:20, Joe Gwinn wrote: Magnus, In article 532e45db.5000...@rubidium.dyndns.org, Magnus Danielson mag...@rubidium.dyndns.org wrote: Joe, On 21/03/14 17:04, Joe Gwinn wrote: [snip] It is interesting. I've now read it reasonably closely. The basic approach is to express each packet flight in a one-line equation (a row) in a linear-system matrix equation, where the system matrix (the A in the traditional y=Ax+b formulation, where b is zero in the absence of noise), where A is 4 columns wide by a variable number of rows long (one row to a packet flight), and show that one column of A can always be computed from the two other columns that describe who is added and subtracted from who. In other words, these three columns are linearly dependent on one another. The forth column contains measured data. This dependency means that A is always rank-deficient no matter how many packets (including infinity) and no matter the order, so the linear system cannot be solved. It is just another formulation of the same equations I provided. For each added link, one unknown and one measure is added. For each added node, one unknown is added. True, but there is more. Let's come back to that. As you do more measures, you will add information about variations the delays and time-differences between the nodes, but you will not disclose the basic offsets. Also true. The advantage of the matrix formulation is that one can then appeal to the vast body of knowledge about matrixes and linear systems. It's not that one cannot prove it without the matrixes, it's that the proof is immediate with them - less work. And the issue was to prove that no such system could work. As much as I like matrix formulation, it ain't giving you much more in this case, rather than a handy notation. The trouble is that beyond the properties of the noise, there is no information leakage about the static time-errors and asymmetries. You end up having free variables. Yes. You correctly noted the mathematical equivalence of the two approaches, and I agree. My point was that the matrix approach is less work to get to the desired proof because by formulation as a linear solution with matrixes, one immediately inherits lots of properties and proofs. The problem is that the unknown and the relationships builds up in an uneven rate, and the observations only relate to two unknowns. The only trustworthy fact we get is the sum of the delays, but no real hint about its distribution. If you do more observations along the same paths, you can do some statistics, but you won't get un-biased result without adding a prior knowledge one way or another. Formulate it as you wish, but as you add more observations, those will be reduced to by their linear properties to equations existing and noise. You need to add observations which does not fully reduce in order for your equation system to grow to such size that you can solve it. Yes, this is a good statement of the consequences of the proof. Show me how you achieve it, and I listen. I don't understand the challenge. There is no dispute. The no matter the order part comes from the property of linear systems that permuting the rows and/or columns has no effect, so long as one is self-consistent. So far, I have not come up with a refutation of this approach. Nor have the automatic control folk - this proof was first published in 2004 into a community that knows their linear systems, and one would think that someone would have published a critique by now. The key mathematical issue is if there are message exchange patterns that cannot be described by a matrix of the assumed pattern. If not, the proof is complete. If yes, more work is required. So far, I have not come up with a counter-example. It takes only one to refute the proof. It is only by cheating that you can overcome the limits of the system. Is GPS cheating? That's our usual answer, but GPS isn't always available or possible. If you are trying to solve it within a network, it is. You can convert your additional GPS observation into an a prior knowledge, and once you done enough of those, then you can solve it completely. The estimated variables better stay static thought, or you have to start over again. GPS is the usual answer, but isn't always available or useful. Recall that the original question was random asymmetry due to asymmetric background traffic in a PTP network. If the network is controllable, a lab experiment is to simply turn the background traffic off and see how much the clocks change with respect to one another. But this tells one how much trouble one is in, but does not solve the problem. The solution will be found in better choice
Re: [ntp:questions] Asymmetric Delay and NTP
Magnus, In article 532e45db.5000...@rubidium.dyndns.org, Magnus Danielson mag...@rubidium.dyndns.org wrote: Joe, On 21/03/14 17:04, Joe Gwinn wrote: [snip] Will see if I can find Dave's reference. I hit pay dirt yesterday, while searching for data on outliers in 1588 systems. Dave's reference may well be in the references of the following article. Fundamental Limits on Synchronizing Clocks Over Networks, Nikolaos M. Freris, Scott R. Graham, and P. R. Kumar, IEEE Trans on Automatic Control, v.56, n.6, June 2011, pages 1352-1364. Sounds like an interesting article. Always interesting to see different peoples' view of fundamental limits. It is interesting. I've now read it reasonably closely. The basic approach is to express each packet flight in a one-line equation (a row) in a linear-system matrix equation, where the system matrix (the A in the traditional y=Ax+b formulation, where b is zero in the absence of noise), where A is 4 columns wide by a variable number of rows long (one row to a packet flight), and show that one column of A can always be computed from the two other columns that describe who is added and subtracted from who. In other words, these three columns are linearly dependent on one another. The forth column contains measured data. This dependency means that A is always rank-deficient no matter how many packets (including infinity) and no matter the order, so the linear system cannot be solved. It is just another formulation of the same equations I provided. For each added link, one unknown and one measure is added. For each added node, one unknown is added. True, but there is more. As you do more measures, you will add information about variations the delays and time-differences between the nodes, but you will not disclose the basic offsets. Also true. The advantage of the matrix formulation is that one can then appeal to the vast body of knowledge about matrixes and linear systems. It's not that one cannot prove it without the matrixes, it's that the proof is immediate with them - less work. And the issue was to prove that no such system could work. To achieve that, you would need to bring correct time to one node and then observe that offset. Once measured the system increases. As you do this for all nodes, then calibration can be performed and the system be fully resolved. The no matter the order part comes from the property of linear systems that permuting the rows and/or columns has no effect, so long as one is self-consistent. So far, I have not come up with a refutation of this approach. Nor have the automatic control folk - this proof was first published in 2004 into a community that knows their linear systems, and one would think that someone would have published a critique by now. The key mathematical issue is if there are message exchange patterns that cannot be described by a matrix of the assumed pattern. If not, the proof is complete. If yes, more work is required. So far, I have not come up with a counter-example. It takes only one to refute the proof. It is only by cheating that you can overcome the limits of the system. Is GPS cheating? That's our usual answer, but GPS isn't always available or possible. Yes. In closed networks, the biggest cause of asymmetry I've found is interference between NTP traffic and heavy background traffic in the operating system kernels of the hosts running application code. Another big hitter was background backups via NFS (Network File System). The network switches were not the problem. What greatly helps is to have a LAN for the heavy applications traffic, and a different LAN for NTP and the like, forcing different paths in the OS kernel to be taken. If you can get your NIC to hardware time-stamp your NTP, you will clean things up a lot. True, but these were never much available, and the rise of PTP may obviate the need. Today PTP has made it available also for NTP. Hardware-timestamped NTP also exists and is commercially available. Although, if one goes to the trouble to make a NIC PTP-capable, it wouldn't be so hard to have it recognize and timestamp passing NTP packets. The hard part would be figuring out how to transfer this timestamp data from collection in the NIC to point of use in the NTP daemon, and standardizing the answer. The Linux-kernel has such support. NTPD has already some support for such NICs included. All true. But I'm reluctant to recommend a solution that lacks a common standard and/or has fewer than three credible vendors supporting that standard. I have no doubt that these things will come to pass, but we are not there just yet. Joe Gwinn ___ questions mailing list questions@lists.ntp.org http://lists.ntp.org/listinfo/questions
Re: [ntp:questions] Asymmetric Delay and NTP
On 2014-03-23, Joe Gwinn joegw...@comcast.net wrote: Magnus, In article 532e45db.5000...@rubidium.dyndns.org, Magnus Danielson mag...@rubidium.dyndns.org wrote: Joe, On 21/03/14 17:04, Joe Gwinn wrote: [snip] Will see if I can find Dave's reference. I hit pay dirt yesterday, while searching for data on outliers in 1588 systems. Dave's reference may well be in the references of the following article. Fundamental Limits on Synchronizing Clocks Over Networks, Nikolaos M. Freris, Scott R. Graham, and P. R. Kumar, IEEE Trans on Automatic Control, v.56, n.6, June 2011, pages 1352-1364. Sounds like an interesting article. Always interesting to see different peoples' view of fundamental limits. It is interesting. I've now read it reasonably closely. The basic approach is to express each packet flight in a one-line equation (a row) in a linear-system matrix equation, where the system matrix (the A in the traditional y=Ax+b formulation, where b is zero in the absence of noise), where A is 4 columns wide by a variable number of rows long (one row to a packet flight), and show that one column of A can always be computed from the two other columns that describe who is added and subtracted from who. In other words, these three columns are linearly dependent on one another. The forth column contains measured data. This dependency means that A is always rank-deficient no matter how many packets (including infinity) and no matter the order, so the linear system cannot be solved. It is just another formulation of the same equations I provided. For each added link, one unknown and one measure is added. For each added node, one unknown is added. True, but there is more. As you do more measures, you will add information about variations the delays and time-differences between the nodes, but you will not disclose the basic offsets. Also true. The advantage of the matrix formulation is that one can then appeal to the vast body of knowledge about matrixes and linear systems. It's not that one cannot prove it without the matrixes, it's that the proof is immediate with them - less work. And the issue was to prove that no such system could work. To achieve that, you would need to bring correct time to one node and then observe that offset. Once measured the system increases. As you do this for all nodes, then calibration can be performed and the system be fully resolved. The no matter the order part comes from the property of linear systems that permuting the rows and/or columns has no effect, so long as one is self-consistent. So far, I have not come up with a refutation of this approach. Nor have the automatic control folk - this proof was first published in 2004 into a community that knows their linear systems, and one would think that someone would have published a critique by now. The key mathematical issue is if there are message exchange patterns that cannot be described by a matrix of the assumed pattern. If not, the proof is complete. If yes, more work is required. So far, I have not come up with a counter-example. It takes only one to refute the proof. It is only by cheating that you can overcome the limits of the system. Is GPS cheating? That's our usual answer, but GPS isn't always available or possible. Not cheating but it is a source that violates the assumptions. The assumption is that all sources of time have an unknown assymmetric round trip time and an unkown one way trip time. -- say time back is 1 sec longer than time out. Given that assumption, then there is no way that any system of measurements can tell the difference between that assymetric path and time offset of 1/2 the difference. If, as with GPS, you know the one way time delay (because you know where the sattelite is, you know where you are, and you know the velocity of light), then those assumptions are violated. Yes. In closed networks, the biggest cause of asymmetry I've found is interference between NTP traffic and heavy background traffic in the operating system kernels of the hosts running application code. Another big hitter was background backups via NFS (Network File System). The network switches were not the problem. What greatly helps is to have a LAN for the heavy applications traffic, and a different LAN for NTP and the like, forcing different paths in the OS kernel to be taken. If you can get your NIC to hardware time-stamp your NTP, you will clean things up a lot. True, but these were never much available, and the rise of PTP may obviate the need. Today PTP has made it available also for NTP. Hardware-timestamped NTP also exists and is commercially available. Although, if one goes to the trouble to make a NIC PTP-capable, it wouldn't be so hard to have it recognize and timestamp passing NTP packets. The hard part would be figuring out how to
Re: [ntp:questions] Asymmetric Delay and NTP
Joe, On 23/03/14 23:20, Joe Gwinn wrote: Magnus, In article 532e45db.5000...@rubidium.dyndns.org, Magnus Danielson mag...@rubidium.dyndns.org wrote: Joe, On 21/03/14 17:04, Joe Gwinn wrote: [snip] It is interesting. I've now read it reasonably closely. The basic approach is to express each packet flight in a one-line equation (a row) in a linear-system matrix equation, where the system matrix (the A in the traditional y=Ax+b formulation, where b is zero in the absence of noise), where A is 4 columns wide by a variable number of rows long (one row to a packet flight), and show that one column of A can always be computed from the two other columns that describe who is added and subtracted from who. In other words, these three columns are linearly dependent on one another. The forth column contains measured data. This dependency means that A is always rank-deficient no matter how many packets (including infinity) and no matter the order, so the linear system cannot be solved. It is just another formulation of the same equations I provided. For each added link, one unknown and one measure is added. For each added node, one unknown is added. True, but there is more. Let's come back to that. As you do more measures, you will add information about variations the delays and time-differences between the nodes, but you will not disclose the basic offsets. Also true. The advantage of the matrix formulation is that one can then appeal to the vast body of knowledge about matrixes and linear systems. It's not that one cannot prove it without the matrixes, it's that the proof is immediate with them - less work. And the issue was to prove that no such system could work. As much as I like matrix formulation, it ain't giving you much more in this case, rather than a handy notation. The trouble is that beyond the properties of the noise, there is no information leakage about the static time-errors and asymmetries. You end up having free variables. The problem is that the unknown and the relationships builds up in an uneven rate, and the observations only relate to two unknowns. The only trustworthy fact we get is the sum of the delays, but no real hint about it's distribution. If you do more observations along the same paths, you can do some statistics, but you won't get un-biased result without adding a prior knowledge one way or another. Formulate it as you wish, but as you add more observations, those will be reduced to by their linear properties to equations existing and noise. You need to add observations which does not fully reduce in order for your equation system to grow to such size that you can solve it. Show me how you achieve it, and I listen. The no matter the order part comes from the property of linear systems that permuting the rows and/or columns has no effect, so long as one is self-consistent. So far, I have not come up with a refutation of this approach. Nor have the automatic control folk - this proof was first published in 2004 into a community that knows their linear systems, and one would think that someone would have published a critique by now. The key mathematical issue is if there are message exchange patterns that cannot be described by a matrix of the assumed pattern. If not, the proof is complete. If yes, more work is required. So far, I have not come up with a counter-example. It takes only one to refute the proof. It is only by cheating that you can overcome the limits of the system. Is GPS cheating? That's our usual answer, but GPS isn't always available or possible. If you are trying to solve it within a network it is. You can convert your additional GPS observation into an a prior knowledge, and once you done enough of those, then you can solve it completely. The estimated variables better stay static thought, or you have to start over again. Although, if one goes to the trouble to make a NIC PTP-capable, it wouldn't be so hard to have it recognize and timestamp passing NTP packets. The hard part would be figuring out how to transfer this timestamp data from collection in the NIC to point of use in the NTP daemon, and standardizing the answer. The Linux-kernel has such support. NTPD has already some support for such NICs included. All true. But I'm reluctant to recommend a solution that lacks a common standard and/or has fewer than three credible vendors supporting that standard. I have no doubt that these things will come to pass, but we are not there just yet. Indeed. Cheers, Magnus ___ questions mailing list questions@lists.ntp.org http://lists.ntp.org/listinfo/questions
Re: [ntp:questions] Asymmetric Delay and NTP
The basic approach is to express each packet flight in a one-line equation (a row) in a linear-system matrix equation, where the system matrix (the A in the traditional y=Ax+b formulation, where b is zero in the absence of noise), where A is 4 columns wide by a variable number of rows long (one row to a packet flight), and show that one column of A can always be computed from the two other columns that describe who is added and subtracted from who. In other words, these three columns are linearly dependent on one another. The forth column contains measured data. What are the columns of your A matrix, and why do you assume they are linearly related? My point is that y=Ax+b can be solved even if it is rank-deficient, and the solution may even be unique. See http://en.wikipedia.org/w/index.php?title=Moore%E2%80%93Penrose_pseudoinvers eoldid=600094895, the section entitled Obtaining all solutions of a linear system. Have you considered what might happen if some entity, such as the US Naval Observatory, broadcast the time every second, on the second. Obviously, this would eliminate the asymmetrical delay problem. (It is known that time distribution on a LAN can be made substantially more accurate by broadcasting the time from a local server, in lieu of waiting for clients to ask for it. Broadcast mode works well on a LAN, and there is a special IP address for it, as there may also be for time broadcast over the Internet. It is in the NTP RFC.) Other factors you might consider is that every second has a name, and seconds have constant time apart. The first second this year was named Jan. 1, 2014 00:00:01, then a second later came second named Jan. 1, 2014 00:00:02, etc. Since the distance between the Naval Observatory and any given receiver is constant (as long as the receiver is not mobile), and the speed of light (s) is constant, let the distance between the Observatory and the receiver (dist) be measured in light-seconds. Then every packet received from the Observatory is essentially just a repeated measure of Jan. 1, 2014 00:00:01 since every second afterwards is related to that one by an integral multiple. Let d = the time received by the receiver minus the name of the second broadcast by the Observatory. Then let d^ be the mean of all the d's received so far. d^ is related to the physical distance (dist) by some constant factor a since the speed of light and the physical distance between the receiver and the Observatory are constant. Hence, isn't a*d^ + the name of the second broadcast by the Observatory the best estimate of the correct time the packet was received, and d^ - d an estimate of the flight time error? What I am trying to say here is IF you could get the government to broadcast the time over the Internet (and that is a big IF since all routers may not propagate NTP broadcasts) then could you not use the fact that the seconds are a constant second apart to get rid of a lot of the uncertainty in your equation y=Ax+b? Charles Elliott -Original Message- From: questions-bounces+elliott.ch=verizon@lists.ntp.org [mailto:questions-bounces+elliott.ch=verizon@lists.ntp.org] On Behalf Of Joe Gwinn Sent: Friday, March 21, 2014 12:04 PM To: questions@lists.ntp.org Subject: Re: [ntp:questions] Asymmetric Delay and NTP Magnus, In article 532b5ab9.4070...@rubidium.dyndns.org, Magnus Danielson mag...@rubidium.dyndns.org wrote: Joe, On 19/03/14 11:55, Joe Gwinn wrote: In article 5328aaa6.70...@rubidium.dyndns.org, Magnus Danielson mag...@rubidium.dyndns.org wrote: On 18/03/14 01:36, Joe Gwinn wrote: In article 5327757e.5040...@rubidium.dyndns.org, Magnus Danielson mag...@rubidium.dyndns.org wrote: Is that formal enough for you? It may be. This I did know, and would seem to suffice, but I recall a triumphant comment from Dr. Mills in one of his documentation pieces. Which I cannot recall well enough to find. It may be the above analysis that was being referred to, or something else. I can't recall. The above I came up with myself some 10 years ago or so. When I awoke the day after writing the above, I saw two problems with the above analysis. First is that with added message-exchange volleys, one does not get added variables and equations, one instead gets repeats of the equations one already has. If there is no noise, the added volleys convey no new information. If there is noise, multiple volleys allows one to average random noise out. True. What does happen over time is: 1) Clocks drift away from each other due to systematics and noises 2) The path delay shifts, sometimes because of physical distance shifts, but also due to shift of day and season. These require continuous tracking to handle Yes. Second is that what is proven is that a specific message-exchange protocol cannot work, not that there is no possible protocol that can work. The above analysis only assumes a way
Re: [ntp:questions] Asymmetric Delay and NTP
Magnus, In article 532b5ab9.4070...@rubidium.dyndns.org, Magnus Danielson mag...@rubidium.dyndns.org wrote: Joe, On 19/03/14 11:55, Joe Gwinn wrote: In article 5328aaa6.70...@rubidium.dyndns.org, Magnus Danielson mag...@rubidium.dyndns.org wrote: On 18/03/14 01:36, Joe Gwinn wrote: In article 5327757e.5040...@rubidium.dyndns.org, Magnus Danielson mag...@rubidium.dyndns.org wrote: Is that formal enough for you? It may be. This I did know, and would seem to suffice, but I recall a triumphant comment from Dr. Mills in one of his documentation pieces. Which I cannot recall well enough to find. It may be the above analysis that was being referred to, or something else. I can't recall. The above I came up with myself some 10 years ago or so. When I awoke the day after writing the above, I saw two problems with the above analysis. First is that with added message-exchange volleys, one does not get added variables and equations, one instead gets repeats of the equations one already has. If there is no noise, the added volleys convey no new information. If there is noise, multiple volleys allows one to average random noise out. True. What does happen over time is: 1) Clocks drift away from each other due to systematics and noises 2) The path delay shifts, sometimes because of physical distance shifts, but also due to shift of day and season. These require continuous tracking to handle Yes. Second is that what is proven is that a specific message-exchange protocol cannot work, not that there is no possible protocol that can work. The above analysis only assumes a way to measure some form of signal. The same equations is valid for TWTFTT as for NTP, PTP or whatever uses the two-way time-transfer. What will differ is they way they convey the information and the noise-sources they see. It's certainly true that the two-way time transfer (including bouncing-packet) approach works well, and is widely used, but all are sensitive to asymmetry, and the overarching question was if this limitation is fundamental and thus unavoidable. As discussed later, it appears that the limitation is fundamental. Will see if I can find Dave's reference. I hit pay dirt yesterday, while searching for data on outliers in 1588 systems. Dave's reference may well be in the references of the following article. Fundamental Limits on Synchronizing Clocks Over Networks, Nikolaos M. Freris, Scott R. Graham, and P. R. Kumar, IEEE Trans on Automatic Control, v.56, n.6, June 2011, pages 1352-1364. Sounds like an interesting article. Always interesting to see different peoples' view of fundamental limits. It is interesting. I've now read it reasonably closely. The basic approach is to express each packet flight in a one-line equation (a row) in a linear-system matrix equation, where the system matrix (the A in the traditional y=Ax+b formulation, where b is zero in the absence of noise), where A is 4 columns wide by a variable number of rows long (one row to a packet flight), and show that one column of A can always be computed from the two other columns that describe who is added and subtracted from who. In other words, these three columns are linearly dependent on one another. The forth column contains measured data. This dependency means that A is always rank-deficient no matter how many packets (including infinity) and no matter the order, so the linear system cannot be solved. The no matter the order part comes from the property of linear systems that permuting the rows and/or columns has no effect, so long as one is self-consistent. So far, I have not come up with a refutation of this approach. Nor have the automatic control folk - this proof was first published in 2004 into a community that knows their linear systems, and one would think that someone would have published a critique by now. The key mathematical issue is if there are message exchange patterns that cannot be described by a matrix of the assumed pattern. If not, the proof is complete. If yes, more work is required. So far, I have not come up with a counter-example. It takes only one to refute the proof. I also took the next step, which is to treat d_AB and d_BA as random variables with differing means and variances (due to interference from asymmetrical background traffic), and trace this to the effect on clock sync. It isn't pretty on anything like a nanosecond scale. The required level of isolation between PTP traffic and background traffic is quite stringent. It's even worse when you get into packet networks, as the delays contain noise sources of variable mean and variable deviation, besides being asymmetrical. NTP combats some of that, but doesn't get deep enough due to too low packet rate. PTP may do it, but it's not in the standard so it will be propritary algorithms. The PTP standard is a protocol framework. ITU have
Re: [ntp:questions] Asymmetric Delay and NTP
Joe, On 19/03/14 11:55, Joe Gwinn wrote: In article 5328aaa6.70...@rubidium.dyndns.org, Magnus Danielson mag...@rubidium.dyndns.org wrote: On 18/03/14 01:36, Joe Gwinn wrote: In article 5327757e.5040...@rubidium.dyndns.org, Magnus Danielson mag...@rubidium.dyndns.org wrote: Is that formal enough for you? It may be. This I did know, and would seem to suffice, but I recall a triumphant comment from Dr. Mills in one of his documentation pieces. Which I cannot recall well enough to find. It may be the above analysis that was being referred to, or something else. I can't recall. The above I came up with myself some 10 years ago or so. When I awoke the day after writing the above, I saw two problems with the above analysis. First is that with added message-exchange volleys, one does not get added variables and equations, one instead gets repeats of the equations one already has. If there is no noise, the added volleys convey no new information. If there is noise, multiple volleys allows one to average random noise out. True. What does happen over time is: 1) Clocks drift away from each other due to systematics and noises 2) The path delay shifts, sometimes because of physical distance shifts, but also due to shift of day and season. These require continuous tracking to handle Second is that what is proven is that a specific message-exchange protocol cannot work, not that there is no possible protocol that can work. The above analysis only assumes a way to measure some form of signal. The same equations is valid for TWTFTT as for NTP, PTP or whatever uses the two-way time-transfer. What will differ is they way they convey the information and the noise-sources they see. Will see if I can find Dave's reference. I hit pay dirt yesterday, while searching for data on outliers in 1588 systems. Dave's reference may well be in the references of the following article. Fundamental Limits on Synchronizing Clocks Over Networks, Nikolaos M. Freris, Scott R. Graham, and P. R. Kumar, IEEE Trans on Automatic Control, v.56, n.6, June 2011, pages 1352-1364. Sounds like an interesting article. Always interesting to see different peoples view of fundamental limits. I also took the next step, which is to treat d_AB and d_BA as random variables with differing means and variances (due to interference from asymmetrical background traffic), and trace this to the effect on clock sync. It isn't pretty on anything like a nanosecond scale. The required level of isolation between PTP traffic and background traffic is quite stringent. It's even worse when you get into packet networks, as the delays contain noise sources of variable mean and variable deviation, besides being asymmetrical. NTP combats some of that, but doesn't get deep enough due to too low packet rate. PTP may do it, but it's not in the standard so it will be propritary algorithms. The PTP standard is a protocol framework. ITU have spent time to fill in more of the empty spots. Yes. In closed networks, the biggest cause of asymmetry I've found is interference between NTP traffic and heavy background traffic in the operating system kernels of the hosts running application code. Another big hitter was background backups via NFS (Network File System). The network switches were not the problem. What greatly helps is to have a LAN for the heavy applications traffic, and a different LAN for NTP and the like, forcing different paths in the OS kernel to be taken. If you can get your NIC to hardware time-stamp your NTP, you will clean things up a lot. Cheers, Magnus ___ questions mailing list questions@lists.ntp.org http://lists.ntp.org/listinfo/questions
Re: [ntp:questions] Asymmetric Delay and NTP
Joe Gwinn wrote: What greatly helps is to have a LAN for the heavy applications traffic, and a different LAN for NTP and the like, forcing different paths in the OS kernel to be taken. If you see a difference, I would have though it more likely to be different usage of the IP stacks than anything significantly different happening in the kernel? If NTP is important enough, create a NTP VLAN set to a higher priority than all other traffic, to isolate NTP traffic from the effects of other network traffic? -- E-Mail Sent to this address blackl...@anitech-systems.com will be added to the BlackLists. ___ questions mailing list questions@lists.ntp.org http://lists.ntp.org/listinfo/questions
Re: [ntp:questions] Asymmetric Delay and NTP
In article lgcoq8$b4j$1...@dont-email.me, E-Mail Sent to this address will be added to the BlackLists Null@BlackList.Anitech-Systems.invalid wrote: Joe Gwinn wrote: What greatly helps is to have a LAN for the heavy applications traffic, and a different LAN for NTP and the like, forcing different paths in the OS kernel to be taken. If you see a difference, I would have though it more likely to be different usage of the IP stacks than anything significantly different happening in the kernel? Yes, the protocol stacks are where in the kernel that the problem most likely happens. If NTP is important enough, create a NTP VLAN set to a higher priority than all other traffic, to isolate NTP traffic from the effects of other network traffic? I'm not so sure that the kernel implements such priorities all the way through. We opted for two physically distinct LANs, each with their own NIC card, plugged into different processors of the enterprise server class machine that needed the time. Joe Gwinn ___ questions mailing list questions@lists.ntp.org http://lists.ntp.org/listinfo/questions
Re: [ntp:questions] Asymmetric Delay and NTP
On 18/03/14 01:36, Joe Gwinn wrote: In article 5327757e.5040...@rubidium.dyndns.org, Magnus Danielson mag...@rubidium.dyndns.org wrote: Joe, On 16/03/14 23:16, Joe Gwinn wrote: I recall seeing something from Dr. Mills saying that a formal proof had been found showing that no packet-exchange protocol (like NTP) could tell delay asymmetry from clock offset. Can anyone provide a reference to this proof? It's relative simple. You have two nodes (A and B) and a link in each direction (A-B and B-A). You have three unknowns, the time-difference between the nodes (T_B - T_A), the delay from node A to B (d_AB) and the delay from node B to A (d_BA). You make two observations of the pseudo-range from node A to node B (t_AB) and from node B to node A (t_BA). These are made by the source announcing it's time and the receiver time-stamping in it's own time when it occurs. t_AB = T_B - T_A + d_AB t_BA = T_A - T_B + d_BA We thus have three unknowns and two equations. You can't solve that. For each link you add, you add one observation and one unknown. For each node and two links you add, you add three unknowns and two observations. You can't win this game. There are things you can do. Let's take out observations and add them, then we get RTT = t_AB + t_BA = (T_B - T_A) + d_AB + (T_A - T_B) + d_BA = d_AB + d_BA Now, that is useful. If we diff them we get /|T = t_AB - t_BA = (T_B - T_A) + d_AB - (T_A - T_B) - d_BA = 2(T_B - T_A) + d_AB - d_BA TE = /|T / 2 = T_B - T_A + (d_AB - d_BA)/2 So, diffing them gives the time-difference, plus half the asymmetric delay. If we assume that the delay is symmetric, then we can use these measures to compute the time-difference between the clocks, and if there is an asymmetry, it *will* show up as a bias in the slave clock. The way to come around this is to either avoid asymmetries like the plague, find a means estimate them (PTPv2) or calibrate them away. Is that formal enough for you? It may be. This I did know, and would seem to suffice, but I recall a triumphant comment from Dr. Mills in one of his documentation pieces. Which I cannot recall well enough to find. It may be the above analysis that was being referred to, or something else. I can't recall. The above I came up with myself some 10 years ago or so. Will see if I can find Dave's reference. I also took the next step, which is to treat d_AB and d_BA as random variables with differing means and variances (due to interference from asymmetrical background traffic), and trace this to the effect on clock sync. It isn't pretty on anything like a nanosecond scale. The required level of isolation between PTP traffic and background traffic is quite stringent. It's even worse when you get into packet networks, as the delays contain noise sources of variable mean and variable deviation, besides being asymmetrical. NTP combats some of that, but doesn't get deep enough due to too low packet rate. PTP may do it, but it's not in the standard so it will be propritary algorithms. The PTP standard is a protocol framework. ITU have spent time to fill in more of the empty spots. Cheers, Magnus ___ questions mailing list questions@lists.ntp.org http://lists.ntp.org/listinfo/questions
Re: [ntp:questions] Asymmetric Delay and NTP
Joe Gwinn wrote: I recall seeing something from Dr. Mills saying that a formal proof had been found showing that no packet-exchange protocol (like NTP) could tell delay asymmetry from clock offset. Can anyone provide a reference to this proof? This is similar to Einstein's relativity example/proof: He claimed that there was no possible method to differentiate between gravity and the force you would experience within an elevator box (i.e. rocket) with constant acceleration. Likewise, there is absolutely no way to differentiate between an actual clock offset and a _constant_ delay asymmetry: Both cause a constant difference in the measured (by ntpd) clock offset. When things are not constant, including spurious packets that suffer little or no extra delay, then you _might_ be able to see a difference between the two possible causes. Terje -- - Terje.Mathisen at tmsw.no almost all programming can be viewed as an exercise in caching ___ questions mailing list questions@lists.ntp.org http://lists.ntp.org/listinfo/questions
Re: [ntp:questions] Asymmetric Delay and NTP
Joe, On 16/03/14 23:16, Joe Gwinn wrote: I recall seeing something from Dr. Mills saying that a formal proof had been found showing that no packet-exchange protocol (like NTP) could tell delay asymmetry from clock offset. Can anyone provide a reference to this proof? It's relative simple. You have two nodes (A and B) and a link in each direction (A-B and B-A). You have three unknowns, the time-difference between the nodes (T_B - T_A), the delay from node A to B (d_AB) and the delay from node B to A (d_BA). You make two observations of the pseudo-range from node A to node B (t_AB) and from node B to node A (t_BA). These are made by the source announcing it's time and the receiver time-stamping in it's own time when it occurs. t_AB = T_B - T_A + d_AB t_BA = T_A - T_B + d_BA We thus have three unknowns and two equations. You can't solve that. For each link you add, you add one observation and one unknown. For each node and two links you add, you add three unknowns and two observations. You can't win this game. There are things you can do. Let's take out observations and add them, then we get RTT = t_AB + t_BA = (T_B - T_A) + d_AB + (T_A - T_B) + d_BA = d_AB + d_BA Now, that is useful. If we diff them we get /|T = t_AB - t_BA = (T_B - T_A) + d_AB - (T_A - T_B) - d_BA = 2(T_B - T_A) + d_AB - d_BA TE = /|T / 2 = T_B - T_A + (d_AB - d_BA)/2 So, diffing them gives the time-difference, plus half the asymmetric delay. If we assume that the delay is symmetric, then we can use these measures to compute the time-difference between the clocks, and if there is an asymmetry, it *will* show up as a bias in the slave clock. The way to come around this is to either avoid asymmetries like the plauge, find a means estimate them (PTPv2) or calibrate them away. Is that formal enough for you? Cheers, Magnus ___ questions mailing list questions@lists.ntp.org http://lists.ntp.org/listinfo/questions
Re: [ntp:questions] Asymmetric Delay and NTP
In article 5327757e.5040...@rubidium.dyndns.org, Magnus Danielson mag...@rubidium.dyndns.org wrote: Joe, On 16/03/14 23:16, Joe Gwinn wrote: I recall seeing something from Dr. Mills saying that a formal proof had been found showing that no packet-exchange protocol (like NTP) could tell delay asymmetry from clock offset. Can anyone provide a reference to this proof? It's relative simple. You have two nodes (A and B) and a link in each direction (A-B and B-A). You have three unknowns, the time-difference between the nodes (T_B - T_A), the delay from node A to B (d_AB) and the delay from node B to A (d_BA). You make two observations of the pseudo-range from node A to node B (t_AB) and from node B to node A (t_BA). These are made by the source announcing it's time and the receiver time-stamping in it's own time when it occurs. t_AB = T_B - T_A + d_AB t_BA = T_A - T_B + d_BA We thus have three unknowns and two equations. You can't solve that. For each link you add, you add one observation and one unknown. For each node and two links you add, you add three unknowns and two observations. You can't win this game. There are things you can do. Let's take out observations and add them, then we get RTT = t_AB + t_BA = (T_B - T_A) + d_AB + (T_A - T_B) + d_BA = d_AB + d_BA Now, that is useful. If we diff them we get /|T = t_AB - t_BA = (T_B - T_A) + d_AB - (T_A - T_B) - d_BA = 2(T_B - T_A) + d_AB - d_BA TE = /|T / 2 = T_B - T_A + (d_AB - d_BA)/2 So, diffing them gives the time-difference, plus half the asymmetric delay. If we assume that the delay is symmetric, then we can use these measures to compute the time-difference between the clocks, and if there is an asymmetry, it *will* show up as a bias in the slave clock. The way to come around this is to either avoid asymmetries like the plague, find a means estimate them (PTPv2) or calibrate them away. Is that formal enough for you? It may be. This I did know, and would seem to suffice, but I recall a triumphant comment from Dr. Mills in one of his documentation pieces. Which I cannot recall well enough to find. It may be the above analysis that was being referred to, or something else. I also took the next step, which is to treat d_AB and d_BA as random variables with differing means and variances (due to interference from asymmetrical background traffic), and trace this to the effect on clock sync. It isn't pretty on anything like a nanosecond scale. The required level of isolation between PTP traffic and background traffic is quite stringent. Joe Gwinn ___ questions mailing list questions@lists.ntp.org http://lists.ntp.org/listinfo/questions
Re: [ntp:questions] Asymmetric Delay and NTP
On 16/03/14 22:16, Joe Gwinn wrote: I recall seeing something from Dr. Mills saying that a formal proof had been found showing that no packet-exchange protocol (like NTP) could tell delay asymmetry from clock offset. Can anyone provide a reference to this proof? I would have thought it was obvious. ___ questions mailing list questions@lists.ntp.org http://lists.ntp.org/listinfo/questions
Re: [ntp:questions] Asymmetric Delay and NTP
On 2014-03-16, Joe Gwinn joegw...@comcast.net wrote: In article lg5bug$682$1...@dont-email.me, David Woolley david@ex.djwhome.demon.invalid wrote: On 16/03/14 22:16, Joe Gwinn wrote: I recall seeing something from Dr. Mills saying that a formal proof had been found showing that no packet-exchange protocol (like NTP) could tell delay asymmetry from clock offset. Can anyone provide a reference to this proof? I would have thought it was obvious. It was generally believed that this was true, but what was lacking was the mathematical proof that no message-exchange protocol, however clever, could overcome delay asymmetry. I recall that someone finally found a proof. A single equation with two variables. The proof IS obvious. Of course if the delay assymetry changes from one packet to the next, then there is a possibility. Joe Gwinn ___ questions mailing list questions@lists.ntp.org http://lists.ntp.org/listinfo/questions
