[ntp:questions] Asymmetric Delay and NTP

Charles Elliott elliott.ch at verizon.net
Sat Mar 22 17:31:11 UTC 2014


>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.net at lists.ntp.org
[mailto:questions-bounces+elliott.ch=verizon.net at lists.ntp.org] On Behalf Of
Joe Gwinn
Sent: Friday, March 21, 2014 12:04 PM
To: questions at lists.ntp.org
Subject: Re: [ntp:questions] Asymmetric Delay and NTP

Magnus,

In article <532B5AB9.4070502 at rubidium.dyndns.org>, Magnus Danielson
<magnus at rubidium.dyndns.org> wrote:

> Joe,
> 
> On 19/03/14 11:55, Joe Gwinn wrote:
> > In article <5328AAA6.70200 at rubidium.dyndns.org>, Magnus Danielson 
> > <magnus at rubidium.dyndns.org> wrote:
> >
> >> On 18/03/14 01:36, Joe Gwinn wrote:
> >>> In article <5327757E.5040504 at rubidium.dyndns.org>, Magnus 
> >>> Danielson <magnus at 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 at lists.ntp.org
http://lists.ntp.org/listinfo/questions



More information about the questions mailing list