Filter jitter to measure clock skew

Hello,

A colleague told me I need to filter out network jitter in order to 
measure the clock skew between two clocks.

Computer A sends packets with period T.
Packet i is sent at date i.
E(i) = i*T

Packets travel over a network that introduces random delays.
Packet i arrives at computer B at R(i).
R(i) = E(i) + delta(i) = i*T + delta(i)
0 <= delta(i) <= delta_max
(Assume delta_max is on the order of 50*T)
(Is the distribution of delays important?)

Computer B uses timestamps provided with each packet to re-send the 
stream at the same rate. But the clocks on A and B do not run at exactly 
the same speed. Assume clock skew is on the order of 10^-5.

What I've done so far is to plot the amount of data in a de-jittering 
buffer against time, and perform a linear regression "every once in a 
while". The A in Y = A*X + B is an approximation of the average clock 
skew over that period.

I was told there are much better methods than this to find the clock 
skew despite the imprecision introduced by the network jitter. My 
colleague told me network jitter was high-frequency noise while clock 
skew was low-frequency, so all I needed was an efficient, and properly 
configured low-pass filter. Is that correct?

I'm open to all suggestions. How can I improve the current approach?

Regards.

Hi!

Spoon schrieb:
> What I've done so far is to plot the amount of data in a de-jittering 
> buffer against time, and perform a linear regression "every once in a 
> while". The A in Y = A*X + B is an approximation of the average clock 
> skew over that period.
> 
> I was told there are much better methods than this to find the clock 
> skew despite the imprecision introduced by the network jitter. My 
> colleague told me network jitter was high-frequency noise while clock 
> skew was low-frequency, so all I needed was an efficient, and properly 
> configured low-pass filter. Is that correct?

Yes. Uncorrelated, random noise is white noise. The clock skew in 
comparsion is nearly 0Hz. However your regression is something like a 
low-pass filter similar to a moving average.

> I'm open to all suggestions. How can I improve the current approach?

To get results with higher precision yo need only one thing: /time/
The longer the measuring points are away the higher is the effect of the 
clock skew.

You may have a look at the ntpd sources. The do the correction of the 
local clock and the external synchronization simultanuously.


Marcel

Spoon wrote:
> Hello,
> 
> A colleague told me I need to filter out network jitter in order to 
> measure the clock skew between two clocks.

   ...

NIST has an internet service for setting computer clocks. Google NISTime 
to find the client program (settime.exe for Windows?) ant try to track 
down the source (or disassemble it. The "About" button under "Help" will 
give you a start for doing that.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

"Spoon" <root@localhost> wrote in message 
news:45eb38a4$0$16582$426a74cc@news.free.fr...
> Hello,
>
> A colleague told me I need to filter out network jitter in order to 
> measure the clock skew between two clocks.
>
> Computer A sends packets with period T.
> Packet i is sent at date i.
> E(i) = i*T
>
> Packets travel over a network that introduces random delays.
> Packet i arrives at computer B at R(i).
> R(i) = E(i) + delta(i) = i*T + delta(i)
> 0 <= delta(i) <= delta_max
> (Assume delta_max is on the order of 50*T)
> (Is the distribution of delays important?)
>
> Computer B uses timestamps provided with each packet to re-send the stream 
> at the same rate. But the clocks on A and B do not run at exactly the same 
> speed. Assume clock skew is on the order of 10^-5.
>
> What I've done so far is to plot the amount of data in a de-jittering 
> buffer against time, and perform a linear regression "every once in a 
> while". The A in Y = A*X + B is an approximation of the average clock skew 
> over that period.
>
> I was told there are much better methods than this to find the clock skew 
> despite the imprecision introduced by the network jitter. My colleague 
> told me network jitter was high-frequency noise while clock skew was 
> low-frequency, so all I needed was an efficient, and properly configured 
> low-pass filter. Is that correct?
>
> I'm open to all suggestions. How can I improve the current approach?
>
> Regards.

You might learn the definition of skew.  It would probably help you out a 
lot!

http://en.wikipedia.org/wiki/Skew

or Google on "clock skew definition"

As you can see, it's generally a constant or so slowly moving as to be 
considered to be constant.  Like a fixed delay or phase shift.

Fred 

Fred Marshall wrote:

> Spoon wrote:
>
>> A colleague told me I need to filter out network jitter in order to 
>> measure the clock skew between two clocks.
>>
>> Computer A sends packets with period T.
>> Packet i is sent at date i.
>> E(i) = i*T
>>
>> Packets travel over a network that introduces random delays.
>> Packet i arrives at computer B at R(i).
>> R(i) = E(i) + delta(i) = i*T + delta(i)
>> 0 <= delta(i) <= delta_max
>> (Assume delta_max is on the order of 50*T)
>> (Is the distribution of delays important?)
>>
>> Computer B uses timestamps provided with each packet to re-send the stream 
>> at the same rate. But the clocks on A and B do not run at exactly the same 
>> speed. Assume clock skew is on the order of 10^-5.
>>
>> What I've done so far is to plot the amount of data in a de-jittering 
>> buffer against time, and perform a linear regression "every once in a 
>> while". The A in Y = A*X + B is an approximation of the average clock skew 
>> over that period.
>>
>> I was told there are much better methods than this to find the clock skew 
>> despite the imprecision introduced by the network jitter. My colleague 
>> told me network jitter was high-frequency noise while clock skew was 
>> low-frequency, so all I needed was an efficient, and properly configured 
>> low-pass filter. Is that correct?
>>
>> I'm open to all suggestions. How can I improve the current approach?
> 
> You might learn the definition of skew.  It would probably help you out
> a lot!

Are you saying I have misconceptions about clock skew?

> As you can see, it's generally a constant or so slowly moving as to be 
> considered to be constant.  Like a fixed delay or phase shift.

Clock skew can vary with temperature and supply voltage.
One cannot assume it remains constant.
cf. http://www.ntp.org/ntpfaq/NTP-s-sw-clocks-quality.htm#AEN1164

Regards.

Jerry Avins wrote:

> Spoon wrote:
>
>> A colleague told me I need to filter out network jitter in order to 
>> measure the clock skew between two clocks.
> 
> NIST has an internet service for setting computer clocks. Google NISTime 
> to find the client program (settime.exe for Windows?) and try to track 
> down the source or disassemble it. The "About" button under "Help" will 
> give you a start for doing that.

I'm slightly confused. Are you saying I need to reverse-engineer binary 
code in order to learn how to write a good low-pass filter?

Regards.

Spoon wrote:
> Jerry Avins wrote:
> 
>> Spoon wrote:
>>
>>> A colleague told me I need to filter out network jitter in order to 
>>> measure the clock skew between two clocks.
>>
>> NIST has an internet service for setting computer clocks. Google 
>> NISTime to find the client program (settime.exe for Windows?) and try 
>> to track down the source or disassemble it. The "About" button under 
>> "Help" will give you a start for doing that.
> 
> I'm slightly confused. Are you saying I need to reverse-engineer binary 
> code in order to learn how to write a good low-pass filter?

I'm suggesting that the problem you want to deal with has been addressed 
by the most highly qualified group of scientists who deal in picoseconds 
in the country, probably the world, and you might learn of some pitfalls 
and approaches you hadn't considered by asking them what they did and 
why they did it.

Since the code they freely give can be decompiled, it is unlikely to be 
something they won't talk about. The work was paid for by taxes, so it 
ought to belong to everybody, including you. If you're sure that a 
low-pass filter is the way to go, don't bother to ask them.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

Jerry Avins wrote:
> Spoon wrote:
>> Jerry Avins wrote:
>>> Spoon wrote:
>>>
>>>> A colleague told me I need to filter out network jitter in order to 
>>>> measure the clock skew between two clocks.
>>>
>>> NIST has an internet service for setting computer clocks. Google 
>>> NISTime to find the client program (settime.exe for Windows?) and try 
>>> to track down the source or disassemble it. The "About" button under 
>>> "Help" will give you a start for doing that.
>>
>> I'm slightly confused. Are you saying I need to reverse-engineer 
>> binary code in order to learn how to write a good low-pass filter?
> 
> I'm suggesting that the problem you want to deal with has been addressed 
> by the most highly qualified group of scientists who deal in picoseconds 
> in the country, probably the world, and you might learn of some pitfalls 
> and approaches you hadn't considered by asking them what they did and 
> why they did it.
> 
> Since the code they freely give can be decompiled, it is unlikely to be 
> something they won't talk about. The work was paid for by taxes, so it 
> ought to belong to everybody, including you. If you're sure that a 
> low-pass filter is the way to go, don't bother to ask them.

If I have to recode NTP in my app, I'm toast.
That math is way over my head.
I'll take a look nonetheless.
Thanks for the suggestion.

On Mar 5, 9:20 am, Spoon <devn...@localhost.com> wrote:

> If I have to recode NTP in my app, I'm toast.
> That math is way over my head.

Have you tried going back to David Mills' papers about the
fundamentals of how NTP works?  I think he writes well.   He also has
talk slides online, but I think papers tend to give more background
than talk slides alone.

Also, you may not need to do a full-blown re-implementation of the NTP
clock synchronization algorithm in order to benefit from some of the
NTP ideas.

I don't have experience working with clock synch but given the success
of NTP, it seems to me time studying NTP is likely to be well spent.

Marcel M�ller wrote:

> Spoon schrieb:
> 
>>What I've done so far is to plot the amount of data in a de-jittering 
>>buffer against time, and perform a linear regression "every once in a 
>>while". The A in Y = A*X + B is an approximation of the average clock 
>>skew over that period.
>>
>>I was told there are much better methods than this to find the clock 
>>skew despite the imprecision introduced by the network jitter. My 
>>colleague told me network jitter was high-frequency noise while clock 
>>skew was low-frequency, so all I needed was an efficient, and properly 
>>configured low-pass filter. Is that correct?
> 
> Yes. Uncorrelated, random noise is white noise. The clock skew in 
> comparsion is nearly 0Hz. However your regression is something like a 
> low-pass filter similar to a moving average.

I've been experimenting with exponentially weighted moving averages.
Do you know how they are related to linear regressions?

In what range do good smoothing factors lie?
(I sample the buffer level every T = 1 ms).

Would I need to sample more often than every T?

>>I'm open to all suggestions. How can I improve the current approach?
> 
> To get results with higher precision yo need only one thing: /time/
> The longer the measuring points are away the higher is the effect of the 
> clock skew.
> 
> You may have a look at the ntpd sources. The do the correction of the 
> local clock and the external synchronization simultanuously.

I'll take a look. Thanks.