[ntp:questions] Asymmetric Delay and NTP

Joe Gwinn joegwinn at comcast.net
Sun Mar 23 22:20:27 UTC 2014


Magnus,

In article <532E45DB.5000902 at rubidium.dyndns.org>, Magnus Danielson
<magnus at 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



More information about the questions mailing list