[ntp:questions] Re: NTP stepping issue
brad at stop.mail-abuse.org
Wed Oct 20 13:26:08 UTC 2004
At 1:37 PM -0400 2004-10-19, Brian Utterback wrote:
> You might think that it should stop at zero, but you have to remember that
> the system is not only trying to set the offset to zero, it is also
> simultaneously trying to determine the correct clock frequency adjustment
> to keep the offset at zero.
I'm sure the implementation is more complex, but the concept is
actually fairly simple. It's similar to the Newton-Raphson method of
successive approximations, or a binary search.
In essence, the steps amount to:
1. You set initial boundaries A (low) and B (high)
2. You make a guess half way between the boundaries
3. You compare your guess against the target
4. If you were equal to the target,
you found it and you're done
5. If A is equal to B,
then the target is not here and you're done
6. If you were lower than the target,
then your guess becomes the new lower boundary A,
and you go back to step 2.
7. If you were higher than the target,
then your guess becomes the new upper boundary B,
and you go back to step 2.
So long as the target doesn't move, and the only comparisons you
can make are "equal, higher, or lower", this method will guarantee
that you always get closer to your target, and you get there as fast
as is possible (O(n*log(n)). At least within the resolution of your
ability to measure "closeness".
In the case of NTP, you end up passing the ideal target value for
the clock multiple times, but each time you miss it by less, and each
time you change the stepping value to be smaller.
After a while, you settle down to a value as accurate as you're
likely to get, given the resolution of your input data your ability
to speed up or slow down the clock by increasingly smaller amounts,
inherent changes in the system clock speed due to temperature and
other influences, etc....
> This is a rather subtle system, and somewhat counter intuitive to most
> of us with a software background, but is quite familiar to DSP and
> analog hardware types.
Sounds to me more like the Numerical Methods programming I was
doing somewhere around 1987-88, way back in College. Man, I don't
think I have even thought the term "Newton-Raphson" for something
like fifteen years.
Brad Knowles, <brad at stop.mail-abuse.org>
"Those who would give up essential Liberty, to purchase a little
temporary Safety, deserve neither Liberty nor Safety."
-- Benjamin Franklin (1706-1790), reply of the Pennsylvania
Assembly to the Governor, November 11, 1755
SAGE member since 1995. See <http://www.sage.org/> for more info.
More information about the questions