On Thursday, June 7, 2012 4:19:31 PM UTC+10, unruh wrote:
On 2012-06-07, skillz...@gmail.com <skillz...@gmail.com> wrote:
On Jun 5, 6:46?pm, Julien Ridoux <jul...@synclab.org> wrote:
On Tuesday, June 5, 2012 9:12:42 AM UTC+10, E-Mail Sent to this address will be
added to the BlackLists wrote:
Thanks for response. It would be great to have a simplified
description of the algorithm. I've read most of the docs on the
synclab site.
That is a very impressive effort :)
I'm trying to synchronize several devices to a reference
clock of a similar device rather than to a true wall clock time of a
real NTP server. I can't use the RADclock code directly because it's
GPL so I'd like distill the algorithm down to something I can
implement from scratch. I'd like to adapt my current NTP client and
server code to use RADclock so I can compare performance. I'm aiming
Why not just use the reference implimentation of radclock for the tests?
The next version of RADclock is likely to be released under a BSD licence. This
should save you the trouble of reimplementing the algorithm.
for 10 microseconds or less of sync on a wireless LAN with a fast
Not going to work.
initial sync time (less than 5 seconds, but I can send many packets
In 5 sec you could set the time, but you cannot get a good estimate of
the rate.
close together if needed). I haven't been able to get even close to
this with my current NTP code (Ethernet is close, but WiFi introduces
a lot of variability). Some of the key points seem to be:
Precisely. And Radclock will not help with that. It uses the same ( or
perhaps much slower) synchronization algorithm.
I agree with Unruh, you are going to bump into quite a few issues and the much
noisier characteristic of the WiFi channel makes it much harder for any
synchronisation algorithm. RADclock however does a pretty good job at filtering
noise but there is no magic involved. If the overall noise characteristics of
all packets is bad, then you cannot do much about it.
I have run RADclock over WiFi, but I would not dare quoting any achievable
clock error value at this stage: we do not have an independent hardware time
reference over WiFi at this stage so we would have to rely on more convoluted
setups to do an objective assessment of RADclock there. I'll put this on my
TODO list.
1. Feed forward: Use raw TSC instead of the time value adjusted by the
algorithm. Is there more to this? Should raw TSC values be used for
offset sync calculations or should the raw TSC be scaled by the latest
adjusted rate (which would seem to be partially feed-back vs fully
feed forward)?
The "time" of the remote clock is measured with the TSC/HPET/.... raw
clock. The packets exchanged are filtered to get the best ones (takes
time) and the rate and offset of the TSC calculated. If you want a
difference clock, only the rate is used. to make the transfer from TSC
differences to time differences.
Actually, the time of the local clock is measured in counter units (that is Ta and
Tf in NTP jargon). The RTT of NTP request/reply is measured in counter units, and
filtering of RTTs is made in counter units. This prevents new inputs to the
algorithm from being "polluted' by wrong estimates of drift based on past NTP
exchanges. This is a simplified example of the feed-forward approach.
Of course, raw counter values have to be converted to time in seconds at one
stage, but this is done when a consumer of time request the creation of a
timestamp (a kernel sub-system or a userland application).
Note that you do not have to convert the counter values. You can store them, as
well as radclock outputs and delay the conversion.
2. Separate offset sync from rate sync. What I wasn't sure about is
why the rate sync would be so much more stable than offset sync since
they seem to both come from the same packet exchanges. Is the
advantage that the rate sync is smoothed over time whereas the offset
sync isn't?
If you correct the clock for offset, the only way you can do that is to
somehow shift the time. Thus if you want the difference in times from t0
to t2 when you corrected the offset at t1, that offset correction will
affect the time difference between t2 and t0. Thus, if you only correct
determine the rate, the difference in raw times times the rate will
directly give you the time difference.
Unruh's explication is pretty much accurate. I would add that the algorithm is
layered. The rate is estimated first in a very reliable way (that is the easy
task) and is used for the difference clock, where drift error cancel out if the
interval measured is small enough. For the purpose of absolute time (that is
the hard bit, and as Unruh pointed out, very much error prone), the drift
estimation algorithm is built on top of the rate estimate one.
Last piece of information: the rate estimation has been designed to change very
slowly to guarantee that the case describe by Unruh does not happen (again if
you measure small intervals).
A little disclaimer, the 'rate' defined in radclock is computed and defined in a very different way than the way ntpd does. Taking the risk to oversimplify, radclock sees the rate and drift as 2 different components of the clock. Radclock does not 'adjust the rate'. I am well aware that this can create confusion, but it is hard to come up with a better wording. Please refer to the papers mentioned earlier for the nitty gritty details.
3. Use only the lowest RTT samples. NTP also does this so I wasn't
sure where the advantage was here.
Their algorithm seems, in the hints in the paper, to be more
sophisticates/complex than the simple "best of 8" algorithm of NTP.
Indeed. Radclock maintains a much longer history of NTP exchanges. This is
particularly useful to provide a stable rate estimate and adjust the minimum
RTT filtering if it 'jumps up'. A typical case would be a network
reconfiguration where the previous minimum RTT is never observed again.
The obvious tradeoff here is memory. However, on Linux and FreeBSD, radclock
and ntpd have comparable memory footprint. I am well aware that this could be a
limitation for embedded systems, and something we will work on if/when someone
shows interest with such needs.
Coming back to one of Unruh's comment, the algorithm is not "slower" than ntpd.
Unruh, I am actually not sure what you meant by this, but if that clarifies things,
radclock does need to wait for the history to fill in to provide rate and drift estimates.
4. Weight samples by their RTT. There's some mention of this in the
documents, but I wasn't sure what the algorithm was for determining
the weights or adapting them as conditions change (e.g. if network
load increased for a long period of time, which would also cause RTT's
to increase due to queuing in routers, etc.).
Then those samples would be thrown out, and the clock allowed to
freewheel until the samples settled down again.
Pretty much. The weight reflect the increase of RTT and translate into a quality measure.
See page 9 of "Robust Synchronization of Absolute and Difference Clocks over
Networks" for the details of the exponential weights assigned.
Then, there are a few different cases. If the input is very bad, then freewheel
for a little while (based on older but good input) is better than believing bad
input. But of course, after a long time, poor input is better than on input at
all. This is really getting into the details of the algo, calibration of
quality thresholds and the like. Here I would refer you to the code for the
details.
Are there other key aspects of the algorithm that I'm missing?
I think these are the key points.
I do not know it, the above are my conclusions from reading the docs I
have read. They could be all wrong.
Unruh, you definitely did a pretty good job ;-).
Julien Ridoux
_______________________________________________
questions mailing list
questions@lists.ntp.org
http://lists.ntp.org/listinfo/questions
