[ntp:questions] Asymmetric Delay and NTP

Magnus Danielson magnus at rubidium.dyndns.org
Mon Mar 24 03:20:27 UTC 2014


On 23/03/14 23:20, Joe Gwinn wrote:
> 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]
>>> 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.



More information about the questions mailing list