[ntp:questions] Re: NTP stepping issue
Richard B. Gilbert
rgilbert88 at comcast.net
Wed Oct 20 15:59:04 UTC 2004
Brad Knowles wrote:
> 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
>> 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.
Try this model of what's going on. It, too, is over simplified but I
think it might lead to a better feel for what's actually going on.
You have two potential, and, almost always both are real errors, to
correct; the time and the clock frequency. Both errors must be
corrected by changing the clock frequency, either temporarily or
Step 1. Record the present offset of the clock from the reference
Step 2. Wait ten minutes and record the offset of the clock from the
Step 3. Find the difference between the two offsets
Step 4. Calculate the correction to the frequency that should cause the
advance exactly ten minutes in exactly ten minutes.
Step 5 Apply twice that correction (f=f+2*deltaf)
Step 6 Wait ten minutes and record the offset which should be close to
Step 7. Remove the over correction of frequency (that corrected the time)
( f = f - deltaf)
Step 8 Go to step 2
The interval that I gave as ten minutes will have to increase as the
frequency error decreases. I have assumed that the time error is
sufficiently small that it can be corrected with the available frequency
adjustment. If this explanation convinces you that I should stick to
counting on my fingers, you are probably right!!
More information about the questions