TIME SYNCHRONIZATION METHOD BETWEEN NODES IN NETWORK AND APPARATUS FOR IMPLEMENTING THE SAME

• US 20080175275A1
• Filed: 08/28/2007
• Published: 07/24/2008
• Est. Priority Date: 01/22/2007
• Status: Abandoned Application

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Jeong, Hong Kyu, Den Hollander, Cornelis Johannis, GARNER, Geoffrey M.
• Application Number:
  US11/846,031
• Publication Number:
  US 20080175275A1
• Time in Patent Office: Days
• US Class Current: 370/503
• CPC Class Codes: H04J 3/0667 Bidirectional timestamps, e.g. NTP or PTP for compensation of clock drift and for compensation of propagation delays arrangements for monitoring round trip delays in packet switching networks H04L43/0864

Abstract

A time synchronization method between nodes in a network and an apparatus for implementing the same, the time synchronization method including: measuring a value of a propagation time from a slave node to a master node using a time stamp for each of one or more predetermined time units; calculating an estimate of an actual propagation time using the one or more measured values and a sliding window; and computing an offset using a message transmission time corresponding to a sending of a message from the master node, a message receipt time corresponding to an arrival of the message at the slave node, and the estimate of the actual propagation time.

Claims

1. A time synchronization method between nodes in a network, the time synchronization method comprising:

measuring a value of a propagation time from a slave node to a master node using time stamps for each of one or more messages sent from the slave node to the master node;

calculating an estimate of an actual propagation time using the one or more measured values and a sliding window; and

computing an offset using a message transmission time corresponding to a sending of a message from the master node, a message receipt time corresponding to an arrival of the message at the slave node, and the estimate of the actual propagation time.

2. The time synchronization method as claimed in claim 1, wherein the calculating of the estimate comprises:

maintaining a number of the one or more measured values corresponding to a length of the sliding window.

3. The time synchronization method as claimed in claim 2, wherein the calculating of the estimate further comprises:

calculating the estimate of the actual propagation time using a current measured value and a first estimate that is calculated from an average of the maintained measured values excluding the current measured value.

4. The time synchronization method as claimed in claim 2, wherein the maintaining of the number of the measured values comprises maintaining a number of most recently measured values corresponding to the length of the sliding window.

5. The time synchronization method as claimed in claim 3, wherein the calculating of the estimate using the current measured value and the first estimate comprises calculating the estimate according to an equation:

$D_k=D_{k-1}+\frac{d_k-d_{k-M}}{M}$

where d_k is the measured value corresponding to a k^th message, D_k is the estimate, D_k-1 is the first estimate, and M is the length of the sliding window.

6. The time synchronization method as claimed in claim 5, wherein the calculating of the estimate using the current measured value and the first estimate further comprises calculating the estimate according to another equation:

$H<br><br>\left(z\right)=\frac{1}{M}·<br><br>\frac{1-z^{-M}}{1-z^{-1}}$

where H(z) is a transfer function for a difference equation for D_k.

7. The time synchronization method as claimed in claim 1, wherein the measuring of the value comprises:

storing a first time stamp corresponding to a transmission time of a first message in the first message and transmitting the first message from the slave node to the master node;

confirming a second time stamp corresponding to a receipt time of the first message received by the master node;

storing the first time stamp, the second time stamp, and a third time stamp corresponding to a transmission time of a second message in the second message and transmitting the second message from the master node to the slave node;

confirming a fourth time stamp corresponding to a receipt time of the second message received by the slave node; and

measuring the value of the propagation time using the first time stamp and the fourth time stamp.

8. The time synchronization method as claimed in claim 7, wherein the measuring of the value of the propagation time using the first time stamp and the fourth time stamp comprises measuring the value of the propagation time according to an equation:

$d_k=\frac{\left(T_{2,k}-T_{1,k}\right)+\left(T_{4,k}-T_{3,k}\right)}{2}$

where d_k is the measured value, T_1,k is the first time stamp, T_2,k is the second time stamp, T_3,k is the third time stamp, and T_4,k is the fourth time stamp.

9. The time synchronization method as claimed in claim 1, wherein the computing of the offset comprises computing the offset according to an equation:

Offset=T2−

T1−

D1

where T1 is the message transmission time, T2 is the message receipt time, and D1 is the estimate.

23. A computer-readable recording medium encoded with the method of claim 1 and implemented by a computer.

10. A time synchronization method between nodes in a network, the time synchronization method comprising:

measuring a value of a propagation time from a slave node to a master node using time stamps for each of one or more messages sent from the slave node to the master node;

calculating an estimate of an actual propagation time using the one or more measured values and a linear digital filter; and

computing an offset using a message transmission time corresponding to a sending of a message from the master node, a message receipt time corresponding to an arrival of the message at the slave node, and the estimate of the actual propagation time.

11. The time synchronization method as claimed in claim 10, wherein the calculating of the estimate comprises:

maintaining an n number of measured values;

maintaining an m number of first estimates, each first estimate being calculated from previous measured values; and

calculating the estimate of the actual propagation time using the n number of measured values, the m number of first estimates, and the linear digital filter,

wherein the linear digital filter provides the n number of measured values and the m number of first estimates with a plurality of filter coefficients, and calculates a sum as the estimate, the sum corresponding to a sum of the n number of measured values and the m number of first estimates where the plurality of filter coefficients are provided.

12. The time synchronization method as claimed in claim 11, wherein the calculating of the estimate using the n number of measured values, the m number of first estimates, and the linear digital filter comprises calculating the estimate according to an equation:

D_k=a₁D_k-1+a₂D_k-2+ . . . +a_nD_k-n+b₀d_k+b₁d_k-1+ . . . +b_md_k-m

where d_k is the measured value corresponding to a k^th message, D_k is the estimate, D_k-1 is one of the first estimates, and a_i(1<

i<

n) and b_j(0<

j<

m) are the plurality of filter coefficients.

13. The time synchronization method as claimed in claim 12, wherein the calculating of the estimate using the n number of measured values, the m number of first estimates, and the linear digital filter further comprises calculating the estimate according to another equation:

$H<br><br>\left(z\right)=\frac{b_0+b_1<br><br>z^{-1}+\mathrm{\cdots <br><br>}+b_m<br><br>z^{-m}}{1-a_1<br><br>z^{-1}-a_2<br><br>z^{-2}-\mathrm{\cdots <br><br>}-a_n<br><br>z^{-n}}$

where H(z) is a filter transfer function.

14. The time synchronization method as claimed in claim 12, wherein a_i(1<

i<

n) and b_j(0<

j<

m) satisfy another equation;

a₁+a₂+ . . . +a_n+b₀+b₁+ . . . +b_m=1.

15. The time synchronization method as claimed in claim 10, wherein the measuring of the value comprises:

storing a first time stamp corresponding to a transmission time of a first message in the first message and transmitting the first message from the slave node to the master node;

confirming a second time stamp corresponding to a receipt time of the first message received by the master node;

storing the first time stamp, the second time stamp, and a third time stamp corresponding to a transmission time of a second message in the second message and transmitting the second message from the master node to the slave node;

confirming a fourth time stamp corresponding to a receipt time of the second message received by the slave node; and

measuring the value of the propagation time using the first time stamp and the fourth time stamp.

16. The time synchronization method as claimed in claim 15, wherein the measuring of the value using the first time stamp and the fourth time stamp comprises measuring the value according to an equation:

$d_k=\frac{\left(T_{2,k}-T_{1,k}\right)+\left(T_{4,k}-T_{3,k}\right)}{2}$

where d_k is the measured value, T_1,k is the first time stamp, T_2,k is the second time stamp, T_3,k is the third time stamp, T_4,k is the fourth time stamp, and k identifies a message, of the one or more messages, for when the first time stamp, the second time stamp, the third time stamp, and the fourth time stamp are measured.

17. The time synchronization method as claimed in claim 10, wherein the computing of the offset comprises computing the offset according to an equation:

Offset=T2−

T1−

D1

where T1 is the message transmission time, T2 is the message receipt time, and D1 is the estimate.

24. A computer-readable recording medium encoded with the method of claim 10 and implemented by a computer.

18. A time synchronization method between nodes in a network, the time synchronization method comprising:

computing a first offset from a master node using one or more time stamps for each of one or more messages sent from the master node to a slave node; and

computing a second offset using the one or more first offsets and a linear digital filter.

19. The time synchronization method as claimed in claim 18, wherein the computing of the first offset comprises:

storing a first time stamp corresponding to a transmission time of a message in the first message and transmitting the message from the master node to the slave node;

storing, in the message, a value accumulating a first propagation time from the master node to a relay node and a residence time in the relay node, the relay node receiving the message;

confirming a second time stamp corresponding to a receipt time of the message received by the slave node, and a second propagation time from a last relay node to the slave node; and

computing the first offset using the first time stamp, the second time stamp, the accumulated value, and the second propagation time.

20. The time synchronization method as claimed in claim 19, wherein the computing of the first offset using the first time stamp, the second time stamp, the accumulated value, and the second propagation time comprises computing the first offset according to an equation:

First offset=T2−

T1−

R1−

D1

where T2 is the second time stamp, T1 is the first time stamp, R1 is the accumulated value, and D1 is the second propagation time.

21. The time synchronization method as claimed in claim 18, wherein the computing of the second offset comprises computing the second offset using the one or more first offsets according to an equation:

y_k=a₁y_k-1+a₂y_k-2+ . . . +a_ny_k-n+b₀u_k+b₁u_k-1+ . . . +b_mu_k-m

where u_k is one of the first offsets, y_k is the second offset, and a_i(1<

i<

n) and b_j(0<

j<

m) are filter coefficients of the linear digital filter.

22. The time synchronization method as claimed in claim 21, wherein the computing of the second offset further comprises computing the second offset according to another equation:

$H<br><br>\left(z\right)=\frac{b_0+b_1<br><br>z^{-1}+\mathrm{\cdots <br><br>}+b_m<br><br>z^{-m}}{1-a_1<br><br>z^{-1}-a_2<br><br>z^{-2}-\mathrm{\cdots <br><br>}-a_n<br><br>z^{-n}}$

where H(z) is a filter transfer function.

25. A computer-readable recording medium encoded with the method of claim 18 and implemented by a computer.

29. The apparatus as claimed in claim 19, wherein the second estimate calculation unit calculates the second estimate according to equations:

$D_k=D_{k-1}+\frac{d_k-d_{k-M}}{M}$ $H<br><br>\left(z\right)=\frac{1}{M}·<br><br>\frac{1-z^{-M}}{1-z^{-1}}$

where d_k is the measured value corresponding to a k^th message, D_k is the estimate, D_k-1 is the first estimate, M is the length of the sliding window, and H(z) is a transfer function for a difference equation for D_k.

26. An apparatus for performing a time synchronization between nodes in a network, the apparatus comprising:

a measured value measurement unit to measure a value of propagation time from a slave node to a master node using time stamps for each of one or more messages sent from the slave node to the master node;

an estimate calculation unit to calculate an estimate of an actual propagation time using the one or more measured values and a sliding window; and

an offset computation unit to compute an offset using a message transmission time corresponding to a sending of a message from the master node, a message receipt time corresponding to an arrival of the message at the slave node, and the estimate of the actual propagation time.

27. The apparatus as claimed in claim 26, wherein the estimate calculation unit comprises:

a measured value maintenance unit to maintain a number of the one or more measured values corresponding to a length of the sliding window; and

a second estimate calculation unit to calculate a second estimate of the actual propagation time as the estimate using a current measured value and a first estimate that is calculated from an average of the maintained measured values excluding the current measured value.

28. The apparatus as claimed in claim 27, wherein the measured value maintenance unit maintains a number of the most recently measured values corresponding to the length of the sliding window.

30. The apparatus as claimed in claim 26, wherein the measured value measurement unit:

stores a first time stamp corresponding to a transmission time of a first message in the first message and transmits the first message from the slave node to the master node;

receives a second message storing the first time stamp, a second time stamp corresponding to a receipt time of the first message by the master node, and a third time stamp corresponding to a transmission time of the second message from the master node to the slave node;

confirms a fourth time stamp corresponding to a receipt time of the second message received by the slave node; and

measures the value of the propagation time using the first time stamp and the fourth time stamp.

31. The apparatus as claimed in claim 26, wherein the apparatus is the slave node.

32. An apparatus for performing a time synchronization between nodes in a network, the apparatus comprising:

a measured value measurement unit to measure a value of a propagation time from a slave node to a master node using time stamps for each of one or more messages sent from the slave node to the master node;

an estimate calculation unit to calculate an estimate of an actual propagation time using the one or more measured values and a linear digital filter; and

an offset computation unit to compute an offset using a message transmission time corresponding to a sending of a message from the master node, a message receipt time corresponding to an arrival of the message at a slave node, and the estimate of the actual propagation time.

33. The apparatus as claimed in claim 32, wherein the estimate calculation unit comprises:

a measured value maintenance unit to maintain an n number of measured values,

a first estimate maintenance unit to maintain an m number of first estimates, each first estimate being calculated from previous measured values; and

a second estimate calculation unit to calculate a second estimate as the estimate of the actual propagation time using the n number of measured values, the m number of first estimates, and the linear digital filter,

wherein the linear digital filter provides the n number of measured values and the m number of first estimates with a plurality of filter coefficients, and calculates a sum as the second estimate, the sum corresponding to a sum of the n number of measured values and the m number of first estimates where the plurality of filter coefficients are provided.

34. The apparatus as claimed in claim 33, wherein the second estimate calculation unit calculates the second estimate according to equations:

$\begin{array}{c}{D}_k=<br><br>a_1<br><br>D_{k-1}+a_2<br><br>D_{k-2}+\mathrm{\cdots <br><br>}+\\ <br><br>a_n<br><br>D_{k-n}+b_0<br><br>d_k+b_1<br><br>d_{k-1}+\mathrm{\cdots <br><br>}+b_m<br><br>d_{k-m}\end{array}$ $H<br><br>\left(z\right)=\frac{b_0+b_1<br><br>z^{-1}+\mathrm{\cdots <br><br>}+b_m<br><br>z^{-m}}{1-a_1<br><br>z^{-1}-a_2<br><br>z^{-2}-\mathrm{\cdots <br><br>}-a_n<br><br>z^{-n}}$

where d_k is the measured value corresponding to a k^th message, D_k is the estimate, H(z) is a filter transfer function, and a_i(1<

i<

n) and b_j(0<

j<

m) are the plurality of filter coefficients.

35. The apparatus as claimed in claim 34, wherein the a_i(1<

i<

n) and the b_j(0<

j<

m) satisfy another equation;

a₁+a₂+ . . . +a_n+b₀+b₁+ . . . +b_m=1

36. The apparatus as claimed in claim 32, wherein the measured value measurement unit:

stores a first time stamp corresponding to a transmission time of a first message in the first message and transmits the first message from the slave node to the master node;

receives a second message storing the first time stamp, a second time stamp corresponding to a receipt time of the first message by the master node, and a third time stamp corresponding to a transmission time of the second message from the master node to the slave node;

confirms a fourth time stamp corresponding to a receipt time of the second message received by the slave node; and

measures the value of the propagation time using the first time stamp and the fourth time stamp.

37. The apparatus as claimed in claim 32, wherein the apparatus is the slave node.

38. An apparatus for performing a time synchronization between nodes in a network, the apparatus comprising:

a first offset computation unit to compute a first offset from a master node using one or more time stamps for each of one or more messages sent from the master node to a slave node; and

a second offset computation unit to compute a second offset using the one or more first offsets and a linear digital filter.

39. The apparatus as claimed in claim 38, wherein the first offset computation unit comprises:

a first time stamp confirmation unit to confirm a first time stamp corresponding to a transmission time of a message by receiving the message from the master node;

an accumulated value confirmation unit to confirm an accumulated value, stored in the message, of a first propagation time of the message from the master node to a relay node and a residence time of the message in the relay node;

a receipt time confirmation unit to confirm a second time stamp corresponding to a receipt time of the message received by the slave node;

a second propagation time confirmation unit to confirm a second propagation time of the message from a last relay node to the slave node; and

a computation unit to compute the first offset using the first time stamp, the second time stamp, the accumulated value, and the second propagation time.

40. The apparatus as claimed in claim 38, wherein the second offset computation unit computes the second offset according to equations:

$\begin{array}{c}{y}_k=<br><br>a_1<br><br>y_{k-1}+a_2<br><br>y_{k-2}+\mathrm{\cdots <br><br>}+a_n<br><br>y_{k-n}+\\ <br><br>b_0<br><br>u_k+b_1<br><br>u_{k-1}+\mathrm{\cdots <br><br>}+b_m<br><br>u_{k-m}\end{array}$ $H<br><br>\left(z\right)=\frac{b_0+b_1<br><br>z^{-1}+\mathrm{\cdots <br><br>}+b_m<br><br>z^{-m}}{1-a_1<br><br>z^{-1}-a_2<br><br>z^{-2}-\mathrm{\cdots <br><br>}-a_n<br><br>z^{-n}}$

where u_k is the first offset, y_k is the second offset, a_i(1<

i<

n) and b_j(0<

j<

m) are filter coefficients of the linear digital filter, and H(z) is a filter transfer function.

41. The apparatus as claimed in claim 38, wherein the apparatus is the slave node.