>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 e&oldid=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 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 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. True, but these were never much available, and the rise of PTP may obviate the need. 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. Joe Gwinn _______________________________________________ questions mailing list questions@lists.ntp.org http://lists.ntp.org/listinfo/questions _______________________________________________ questions mailing list questions@lists.ntp.org http://lists.ntp.org/listinfo/questions
