[ntp:questions] [Thumbgps-devel] good paper on timing and delay

unruh unruh at invalid.ca
Wed May 23 14:21:19 UTC 2012


On 2012-05-22, Eric S. Raymond <esr at thyrsus.com> wrote:
> Dave Hart <hart at ntp.org>:
>> > So, the possibly simplistic question is, if our network time sync programs
>> > used the same algorithm that the GPS receivers use to read their "servers",
>> > ie satellites, which all have variable and perhaps somewhat asymmetric
>> > propagation delays, which can be substantial, would we be able to achieve
>> > much greater levels of accuracy doing synchronization via the internet?
>> 
>> GPS birds tell the receiver the flight plans of all birds, so the
>> receiver knows the dominant factor in the propagation delay, the
>> distance between transmitter and receiver.  With WAAS reception, even
>> more information about delay is provided in the form of atmospheric
>> conditions.  NTP has a much more difficult row to hoe.
>
> This is true, but Ron might nevertheless be onto something here. 
> The solver algorithm for position given a bunch of pseudoranges
> is irrelevant to anything NTP does. It's straight-up spherical
> trigonometry.  But...
>
> GPSes also use Kalman filtering to try to back out the effects of
> variable ionospheric delay, which manifests as noise in the
> pseudorange measurements.  The pseudorange noise behaves a lot like
> jitter in network packet latencies.

It is however at the ns level, not the ms level. 

>
> It's possible that Kalman filtering could be useful for cleaning noise
> from an NTP server's measurements of propagation delay.  It's a general
> technique used for all kinds of noisy time series.

Could be. Ntpd's handling of noise has always been primative. Mills
would probably claim that it is thus for robustness, but I think the
evidence is sparse. chrony uses least squares fitting to try to
eliminate the random noise, and tends to do much better than ntpd at
keeping the time near the true time ( about 2-3 times better in my
tests). It does this by retaining more information about the past
behaviour, rather than simply retaining one number or two (current time
and rate).

Note that reading that Wikipedia entry, the current ntpd scheme is a
Kalman filter it would seem.  

If you are in a situation of limited memory, so that saving say the last
60 measurements is far too expensive, then a markovian model is good. We
are not in that state with modern computers. 




>
> From Wikipedia:
>
> The Kalman filter, also known as linear quadratic estimation (LQE), is
> an algorithm which uses a series of measurements observed over time,
> containing noise (random variations) and other inaccuracies, and
> produces estimates of unknown variables that tend to be more precise
> than those that would be based on a single measurement alone. More
> formally, the Kalman filter operates recursively on streams of noisy
> input data to produce a statistically optimal estimate of the
> underlying system state.



More information about the questions mailing list