METHODS AND SYSTEMS FOR ESTIMATING OFFSET AND SKEW USING LINEAR PROGRAMMING

Abstract

This invention relates to methods and systems for estimating offset and skew using linear programming. Embodiments of the invention relate to methods and systems which apply linear programming principles to links with asymmetric transmission rates which are estimated from an exchange of timing messages (for example under IEEE 1588 PTP). Further embodiments provide for the estimation of clock offsets using linear programming techniques when the skew is known or estimated.

Claims

1. A slave device connected to a master device having a master clock over a network, wherein the slave device includes a slave clock and a processor, and wherein the processor is arranged to: exchange with the master device, timing messages and record timestamps which are: the time of sending of said timing messages from the master device according to the master clock; the time of receipt of said timing messages according to the slave clock; the time of sending of said timing messages according to the slave clock; and the time of receipt of said timing messages according to the master clock; formulate a linear programming problem which includes in its constraints said timestamps along with variables relating to: the skew and offset of the slave clock compared to the master clock; and the relationship between the forward and reverse transmission speeds in the network between the master device and the slave device; solve the linear programming problem to derive an estimate of the skew and offset of the slave clock relative to the master clock; and synchronize the slave clock to the master clock based on the estimated skew and offset to produce a master time estimate.

2. A slave device according to claim 1 wherein the linear programming problem comprises two problems, in which: the first problem seeks to minimize the expression $\frac{a}{2}.Math.\left(T_{2,1}^2-T_{2,L}^2\right)+b_1\left(T_{2,1}-T_{2,L}\right)$ subject to the constraint that aT.sub.2,n+b.sub.1≦.sub.n, n∈{1,2, . . . , L} wherein a is the negative of the skew of the slave clock relative to the master clock, T.sub.2,n is the time of receipt of the nth timing message from the master device according to the slave clock, b.sub.1 is the negative of the offset of the slave clock compared to the master clock as adjusted by the transmission delay and the physical link delay in the downstream direction from master to slave and τ.sub.n=T.sub.2,n−T.sub.1,n is the transport delay between the master and the slave with T.sub.1,n being the time of sending of the nth timing message from the master device according to the master clock, and the second problem seeks to minimize the expression $\frac{a}{2}.Math.\left(T_{4,1}^2-T_{4,L}^2\right)+b_2\left(T_{4,1}-T_{4,L}\right)$ subject to the constraint that aT.sub.4,n+b≦τ.sub.n, n∈{1,2, . . . , L} wherein a is the negative of the skew of the slave clock relative to the master clock, T.sub.4,n is the time of receipt of the nth timing message from the slave device according to the master clock, b.sub.2 is the negative of the offset as adjusted by the transmission delay and the physical link delay in the upstream direction from slave to master and τ.sub.n=T.sub.4,n−T.sub.3,n is the transport delay between the master and the slave with T.sub.3,n being the time of sending of the nth timing message from the slave device according to the slave clock.

3. A slave device according to claim 2 wherein b.sub.1=θ+t.sub.ds+p.sub.ds and b.sub.2=−θ−ξt.sub.ds−p.sub.us wherein θ is the offset of the slave clock compared to the master clock, t.sub.ds is the transmission delay in the downstream direction, p.sub.ds is the physical link delay in the downstream direction, p.sub.us is the physical link delay in the upstream direction and ξ is the speed ratio of the transmission rate in the downstream direction to the transmission rate in the upstream direction.

4. A slave device according to claim 1 wherein the linear programming problem seeks to minimize the expression β.sub.1−β.sub.2 in which β.sub.1 is the offset of the slave clock compared to the master clock as adjusted by the transmission delay and the physical link delay in the downstream direction from master to slave and β.sub.2 is the offset as adjusted by the transmission delay and the physical link delay in the upstream direction from slave to master, subject to the constraints that T.sub.1,n≧(1+α)T.sub.2,n+β.sub.1, T.sub.4,n≦(1+α)T.sub.3,nβ.sub.2 and β.sub.1−β.sub.2≧0 wherein: α is the skew of the slave clock compared to master clock; T.sub.1,n is the time of sending of the nth timing message from the master device according to the master clock; T.sub.2,n is the time of receipt of the nth timing message from the master device according to the slave clock; T.sub.3,n is the time of sending of the nth timing message from the slave device according to the slave clock; and T.sub.4,n is the time of receipt of the nth timing message from the slave device according to the master clock.

5. A slave device according to claim 4 wherein β.sub.1=θ−t.sub.ds−p.sub.ds and β.sub.2=θ+ξt.sub.ds+p.sub.us wherein θ is the offset of the slave clock compared to the master clock, t.sub.ds is the transmission delay in the downstream direction, p.sub.ds is the physical link delay in the downstream direction, p.sub.us is the physical link delay in the upstream direction and ξ is the speed ratio of the transmission rate in the downstream direction to the transmission rate in the upstream direction.

6. A slave device according to claim 1 wherein the slave clock includes a local free-running oscillator and a skew-adjusted free-running counter driven by the output of said local free-running oscillator, and the slave device is arranged to synchronize the frequency of the slave clock to the frequency of the master clock by adjusting the skew-adjusted free-running counter to take account of the estimated skew and applying the estimated offset to the output of the skew-adjusted free-running counter to produce the master time estimate.

7. A slave device according to claim 6 wherein the skew-adjusted free-running counter is also used to provide timestamps for the time of receipt and of sending of timing messages at/from the slave device.

8. A slave device according to claim 7 wherein the counter is initialized on receipt by the slave device of the first timing message from the master device, and the counter is reset on receipt of the first master time estimate to said first master time estimate.

9. A method of synchronizing the time and frequency of a slave clock in a slave device to a master clock in a master device which is connected to the slave device over a network, the method including the steps of: exchanging, between the master device and the slave device, timing messages and recording timestamps which are: the time of sending of timing messages from the master device according to the master clock; the time of receipt of said timing messages according to the slave clock; the time of sending of said timing messages according to the slave clock; and the time of receipt of said timing messages according to the master clock; formulating a linear programming problem which includes in its constraints said timestamps along with variables relating to: the skew and offset of the slave clock compared to the master clock; and the relationship between the forward and reverse transmission speeds in the network between the master device and the slave device; solving the linear programming problem to derive an estimate of the skew and offset of the slave clock relative to the master clock; and synchronizing the slave clock to the master clock based on the estimated skew and offset to produce a master time estimate.

10. A method according to claim 9 wherein the linear programming problem comprises two problems, in which: the first problem seeks to minimize the expression $\frac{a}{2}.Math.\left(T_{2,1}^2-T_{2,L}^2\right)+b_1\left(T_{2,1}-T_{2,L}\right)$ subject to the constraint that aT.sub.2,n+b.sub.1≦τ.sub.n, n∈{1,2, . . . , L} wherein a is the negative of the skew of the slave clock relative to the master clock, T.sub.2,n is the time of receipt of the nth timing message from the master device according to the slave clock, b.sub.1 is the negative of the offset of the slave clock compared to the master clock as adjusted by the transmission delay and the physical link delay in the downstream direction from master to slave and τ.sub.n=T.sub.2,n−T.sub.1,n is the transport delay between the master and the slave with T.sub.1,n being the time of sending of the nth timing message from the master device according to the master clock, and the second problem seeks to minimize the expression $\frac{a}{2}.Math.\left(T_{4,1}^2-T_{4,L}^2\right)+b_2\left(T_{4,1}-T_{4,L}\right)$ subject to the constraint that aT.sub.4,n+b≦τ.sub.n, n∈{1,2, . . . , L} wherein a is the negative of the skew of the slave clock relative to the master clock, T.sub.4,n is the time of receipt of the nth timing message from the slave device according to the master clock, b.sub.2 is the negative of the offset as adjusted by the transmission delay and the physical link delay in the upstream direction from slave to master and τ.sub.n=T.sub.4,n−T.sub.3,n is the transport delay between the master and the slave with T.sub.3,n being the time of sending of the nth timing message from the slave device according to the slave clock.

11. A method according to claim 10 wherein b.sub.1=−θ+t.sub.ds+p.sub.ds and b.sub.2=−θ−ξt.sub.ds−p.sub.us wherein θ is the offset of the slave clock compared to the master clock, t.sub.ds is the transmission delay in the downstream direction, p.sub.ds is the physical link delay in the downstream direction, p.sub.us is the physical link delay in the upstream direction and ξ is the speed ratio of the transmission rate in the downstream direction to the transmission rate in the upstream direction.

12. A method according to claim 9 wherein the linear programming problem seeks to minimize the expression β.sub.1−β.sub.2 in which β.sub.1 is the offset of the slave clock compared to the master clock as adjusted by the transmission delay and the physical link delay in the downstream direction from master to slave and β.sub.2 is the offset as adjusted by the transmission delay and the physical link delay in the upstream direction from slave to master, subject to the constraints that T.sub.1,n≧(1+α)T.sub.2,n+β.sub.1, T.sub.4,n≦(1+α)T.sub.3,n+β.sub.2 and β.sub.1−β.sub.2≧0 wherein: α is the skew of the slave clock compared to master clock; T.sub.1,n is the time of sending of the nth timing message from the master device according to the master clock; T.sub.2,n is the time of receipt of the nth timing message from the master device according to the slave clock; T.sub.3,n is the time of sending of the nth timing message from the slave device according to the slave clock; and T.sub.4,n is the time of receipt of the nth timing message from the slave device according to the master clock.

13. A method according to claim 12 wherein β.sub.1=θ−t.sub.ds−p.sub.ds and β.sub.2=θ+ξt.sub.ds+p.sub.us wherein θ is the offset of the slave clock compared to the master clock, t.sub.ds is the transmission delay in the downstream direction, p.sub.ds is the physical link delay in the downstream direction, p.sub.us is the physical link delay in the upstream direction and ξ is the speed ratio of the transmission rate in the downstream direction to the transmission rate in the upstream direction.

14. A method according to claim 9 wherein the slave clock includes a local free-running oscillator and a skew-adjusted free-running counter driven by the output of said local free-running oscillator, and the step of synchronizing includes the steps of: synchronizing the frequency of the slave clock to the frequency of the master clock by adjusting the skew-adjusted free-running counter to take account of the estimated skew and applying the estimated offset to the output of the skew-adjusted free-running counter to produce the master time estimate.

15. A method according to claim 14 wherein the skew-adjusted free-running counter is also used to provide timestamps for the time of receipt and of sending of timing messages at/from the slave device.

16. A method according to claim 15 further including the steps of: initializing the counter on receipt by the slave device of the first timing message from the master device, and resetting the counter to said first master time estimate on receipt of the first master time estimate.

17. A time and frequency synchronisation system for a network, the system including: a master device having a master clock; a slave device having a slave clock; and a network connecting the master and slave devices, wherein: the slave clock comprises a slave clock and a processor; and the processor is arranged to: exchange with the master device, timing messages and record timestamps which are: the time of sending of said timing messages from the master device according to the master clock; the time of receipt of said timing messages according to the slave clock; the time of sending of said timing messages according to the slave clock; and the time of receipt of said timing messages according to the master clock; formulate a linear programming problem which includes in its constraints said timestamps along with variables relating to: the skew and offset of the slave clock compared to the master clock; and the relationship between the forward and reverse transmission speeds in the network between the master device and the slave device; solve the linear programming problem to derive an estimate of the skew and offset of the slave clock relative to the master clock; and synchronize the slave clock to the master clock based on the estimated skew and offset to produce a master time estimate.

18. A system according to claim 17 wherein the linear programming problem comprises two problems, in which: the first problem seeks to minimize the expression $\frac{a}{2}.Math.\left(T_{2,1}^2-T_{2,L}^2\right)+b_1\left(T_{2,1}-T_{2,L}\right)$ subject to the constraint that aT.sub.2,n+b.sub.1≦τ.sub.n, n∈{1,2, . . . , L} wherein a is the negative of the skew of the slave clock relative to the master clock, T.sub.2,n is the time of receipt of the nth timing message from the master device according to the slave clock, b.sub.1 is the negative of the offset of the slave clock compared to the master clock as adjusted by the transmission delay and the physical link delay in the downstream direction from master to slave and τ.sub.n=T.sub.2,n−T.sub.1,n is the transport delay between the master and the slave with T.sub.1,n being the time of sending of the nth timing message from the master device according to the master clock, and the second problem seeks to minimize the expression $\frac{a}{2}.Math.\left(T_{4,1}^2-T_{4,L}^2\right)+b_2\left(T_{4,1}-T_{4,L}\right)$ subject to the constraint that aT.sub.4,n+b≦τ.sub.n, n∈{1,2, . . . , L} wherein a is the negative of the skew of the slave clock relative to the master clock, T.sub.4,n is the time of receipt of the nth timing message from the slave device according to the master clock, b.sub.2 is the negative of the offset as adjusted by the transmission delay and the physical link delay in the upstream direction from slave to master and τ.sub.n=T.sub.4,n−T.sub.3,n is the transport delay between the master and the slave with T.sub.3,n being the time of sending of the nth timing message from the slave device according to the slave clock.

19. A system according to claim 18 wherein b.sub.1=−θ+t.sub.ds+p.sub.ds and b.sub.2=−θ−ξt.sub.ds−p.sub.us wherein θ is the offset of the slave clock compared to the master clock, t.sub.ds is the transmission delay in the downstream direction, p.sub.ds is the physical link delay in the downstream direction, p.sub.us is the physical link delay in the upstream direction and ξ is the speed ratio of the transmission rate in the downstream direction to the transmission rate in the upstream direction.

20. A system according to claim 17 wherein the linear programming problem seeks to minimize the expression β.sub.1−β.sub.2 in which β.sub.1 is the offset of the slave clock compared to the master clock as adjusted by the transmission delay and the physical link delay in the downstream direction from master to slave and β.sub.2 is the offset as adjusted by the transmission delay and the physical link delay in the upstream direction from slave to master, subject to the constraints that T.sub.1,n≧(1+α)T.sub.2,n+β.sub.1, T.sub.4,n≦(1+α)T.sub.3,n+β.sub.2 and β.sub.1−β.sub.2≧0 wherein: α is the skew of the slave clock compared to master clock; T.sub.1,n is the time of sending of the nth timing message from the master device according to the master clock; T.sub.2,n is the time of receipt of the nth timing message from the master device according to the slave clock; T.sub.3,n is the time of sending of the nth timing message from the slave device according to the slave clock; and T.sub.4,n is the time of receipt of the nth timing message from the slave device according to the master clock.

21. A system according to claim 20 wherein β.sub.1=θ−t.sub.ds−p.sub.ds and β.sub.2=θ+ξt.sub.ds+p.sub.us wherein θ is the offset of the slave clock compared to the master clock, t.sub.ds is the transmission delay in the downstream direction, p.sub.ds is the physical link delay in the downstream direction, p.sub.us is the physical link delay in the upstream direction and ξ is the speed ratio of the transmission rate in the downstream direction to the transmission rate in the upstream direction.

22. A system according to claim 17 wherein the slave clock includes a local free-running oscillator and a skew-adjusted free-running counter driven by the output of said local free-running oscillator, and the slave device is arranged to synchronize the frequency of the slave clock to the frequency of the master clock by adjusting the skew-adjusted free-running counter to take account of the estimated skew and applying the estimated offset to the output of the skew-adjusted free-running counter to produce the master time estimate.

23. A system according to claim 22 wherein the skew-adjusted free-running counter is also used to provide timestamps for the time of receipt and of sending of timing messages at/from the slave device.

24. A system according to claim 23 wherein the counter is initialized on receipt by the slave device of the first timing message from the master device, and the counter is reset on receipt of the first master time estimate to said first master time estimate.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0030] Embodiments of the invention will now be described by way of example with reference to the accompanying drawings in which:

[0031] FIG. 1 shows the principles of time transfer over broadband connections to small cells and has already been described;

[0032] FIG. 2 shows the message flow in a two-step clock according to the IEEE 1588 PTP and has already been described;

[0033] FIG. 3 shows two clock models for a clock with no offset (left) and a clock with offset (right);

[0034] FIG. 4 illustrates the principles of link transmission rate asymmetry;

[0035] FIG. 5 is a graphical representation of the objective function according to an embodiment of the present invention;

[0036] FIG. 6 illustrates the two constraints in a linear programming formulation according to an embodiment of the present invention;

[0037] FIG. 7 shows, schematically, the basic transmitter clock and receiver DPLL architecture of a system according to an embodiment of the present invention;

[0038] FIG. 8 shows, schematically, the operation of a DPLL based on a phase accumulator-type digitally controlled oscillator; and

[0039] FIG. 9 shows the progression of the output of the phase accumulator shown in FIG. 8.

DETAILED DESCRIPTION

[0040] At their broadest, aspects of the present invention provide for methods and systems which are arranged to synchronize a slave clock in a slave device to a master clock by solving a linear programming problem which takes account of the asymmetry in the transmission rates between the master and slave devices to derive an estimate of the skew and offset of the slave clock relative to the master clock.

[0041] A first aspect of the present invention provides a slave device connected to a master device having a master clock over a network, wherein the slave device includes a slave clock and a processor, and wherein the processor is arranged to: exchange with the master device, timing messages and record timestamps which are: the time of sending of said timing messages from the master device according to the master clock; the time of receipt of said timing messages according to the slave clock; the time of sending of said timing messages according to the slave clock; and the time of receipt of said timing messages according to the master clock; formulate a linear programming problem which includes in its constraints said timestamps along with variables relating to: the skew and offset of the slave clock compared to the master clock; and the relationship between the forward and reverse transmission speeds in the network between the master device and the slave device; solve the linear programming problem to derive an estimate of the skew and offset of the slave clock relative to the master clock; and synchronize the slave clock to the master clock based on the estimated skew and offset to produce a master time estimate.

[0042] The network may be a packet network (using technologies such Ethernet, IP, MPLS, etc.).

[0043] The timing messages are preferably timing messages under the IEEE 1588 Precision Time Protocol (PTP).

[0044] By using the linear programming approach set out above, accurate timing information (time and frequency) may be transported from a master (server) clock in an end-to-end fashion over a packet network and accurately recovered at the slave (client) device.

[0045] The slave device of this aspect requires no assistance from the packet network in its synchronization operation and is still able to provide sub-microsecond level clock accuracies.

[0046] The slave device of this aspect uses a two-dimensional linear programming technique for estimating clock offset and skew from two-way timing message exchanges whilst taking account of transmission rate asymmetry (for example as may be found in DSL or GPON networks). It is assumed that the delay as a result of rate asymmetry could exist on top of other communication path delay asymmetries.

[0047] The proposed linear programming technique for estimating the clock offset and skew of a slave clock with respect to a master clock does not require knowledge of the measurement and process noise statistics as in Kalman filtering based techniques.

[0048] The master of this aspect may be a GrandMaster (GM) or a Boundary Clock (BC). BCs provide a means to distribute synchronization information in larger networks by building a clock hierarchy. The BC relieves the GM from handling a large number of ordinary clocks by segmenting downstream networks into areas.

[0049] In certain embodiments of the present aspect, the linear programming problem comprises two problems, in which: the first problem seeks to minimize the expression

[00001]$\frac{a}{2}.Math.\left(T_{2,1}^2-T_{2,L}^2\right)+b_1\left(T_{2,1}-T_{2,L}\right)$

subject to the constraint that aT.sub.2,n+b.sub.1≦τ, n∈{1,2, . . . , L} wherein a is the negative of the skew of the slave clock relative to the master clock, T.sub.2,n is the time of receipt of the nth timing message from the master device according to the slave clock, b.sub.1 is the negative of the offset of the slave clock compared to the master clock as adjusted by the transmission delay and the physical link delay in the downstream direction from master to slave and τ.sub.n=T.sub.2,n−T.sub.1,n is the transport delay between the master and the slave with T.sub.1,n being the time of sending of the nth timing message from the master device according to the master clock, and the second problem seeks to minimize the expression

[00002]$\frac{a}{2}.Math.\left(T_{4,1}^2-T_{4,L}^2\right)+b_2\left(T_{4,1}-T_{4,L}\right)$

subject to the constraint that aT.sub.4,n+b≦τ.sub.n, n∈{1,2, . . . , L} wherein a is the negative of the skew of the slave clock relative to the master clock, T.sub.4,n is the time of receipt of the nth timing message from the slave device according to the master clock, b.sub.2 is the negative of the offset as adjusted by the transmission delay and the physical link delay in the upstream direction from slave to master and τ.sub.n=T.sub.4,n−T.sub.3,n is the transport delay between the master and the slave with T.sub.3,n being the time of sending of the nth timing message from the slave device according to the slave clock.

[0050] In particular, the linear program may define b.sub.1 as b.sub.1=−θ+t.sub.ds+p.sub.ds and b.sub.2 as b.sub.2=−θ−ξt.sub.ds−p.sub.us wherein θ is the offset of the slave clock compared to the master clock, t.sub.ds is the transmission delay in the downstream direction, p.sub.ds is the physical link delay in the downstream direction, p.sub.us is the physical link delay in the upstream direction and ξ is the speed ratio of the transmission rate in the downstream direction to the transmission rate in the upstream direction.

[0051] Having solved this linear program, the skew and offset of the slave clock can be determined.

[0052] In further embodiments of the present aspect the linear programming problem seeks to minimize the expression β.sub.1−β.sub.2 in which β.sub.1 is the offset of the slave clock compared to the master clock as adjusted by the transmission delay and the physical link delay in the downstream direction from master to slave and β.sub.2 is the offset as adjusted by the transmission delay and the physical link delay in the upstream direction from slave to master, subject to the constraints that T.sub.1,n≧(1+α)T.sub.2,n+β, T.sub.4,n≦(1+α)T.sub.3,n+β.sub.2 and β.sub.1−β.sub.2≧0 wherein: α is the skew of the slave clock compared to master clock; T.sub.1,n is the time of sending of the nth timing message from the master device according to the master clock; T.sub.2,n is the time of receipt of the nth timing message from the master device according to the slave clock; T.sub.3,n is the time of sending of the nth timing message from the slave device according to the slave clock; and T.sub.4,n is the time of receipt of the nth timing message from the slave device according to the master clock.

[0053] In particular, the linear program may define β.sub.1 as β.sub.1=θ−t.sub.ds−p.sub.ds and β.sub.2 as β.sub.2=θ+ξt.sub.ds+p.sub.us wherein θ is the offset of the slave clock compared to the master clock, t.sub.ds is the transmission delay in the downstream direction, p.sub.ds is the physical link delay in the downstream direction, p.sub.us is the physical link delay in the upstream direction and ξ is the speed ratio of the transmission rate in the downstream direction to the transmission rate in the upstream direction.

[0054] Solving this linear program provides a value for the skew and allows the offset to be determined.

[0055] In certain circumstances, the skew of the slave clock will be known from other methods, or can be estimated separately. In such cases, the terms involving the skew in the above linear programs become constants and so can be adjusted accordingly.

[0056] For example, if the skew is known, the two-problem program of the embodiments described above can be simplified to minimizing b.sub.1(T.sub.2,1−T.sub.2,L) subject to the constraint that b.sub.1≦τ.sub.n−aT.sub.2,n, n∈{1,2, . . . , L} and minimizing b.sub.2(T.sub.4,1−T.sub.4,L) subject to the constraint that b.sub.2≦τ.sub.n−aT.sub.4,n, n∈{1,2, . . . , L} in which a is now known/estimated in advance.

[0057] Similarly the single-problem program of the embodiments described above can be simplified as the constraints now contain only β.sub.1 and β.sub.2 as unknowns.

[0058] Further simplification may be possible if frequency synchronization can be achieved using a known technique (e.g. Synchronous Ethernet or Network Timing Reference), in which case the skew can be assumed to be zero (or approximately zero), thus further simplifying the linear program(s) to be solved.

[0059] Preferably the slave clock includes a local free-running oscillator and a skew-adjusted free-running counter driven by the output of said local free-running oscillator, and the slave device is arranged to synchronize the frequency of the slave clock to the frequency of the master clock by adjusting the skew-adjusted free-running counter to take account of the estimated skew and applying the estimated offset to the output of the skew-adjusted free-running counter to produce the master time estimate.

[0060] In some embodiments, the skew-adjusted free-running counter is also used to provide timestamps for the time of receipt and of sending of timing messages at/from the slave device.

[0061] In these embodiments the counter may be initialized on receipt by the slave device of the first timing message from the master device, and the counter may be reset on receipt of the first master time estimate to said first master time estimate.

[0062] The slave device of the present aspect may include any combination of some, all or none of the above described preferred and optional features.

[0063] The processor of the slave device of the above aspect preferably operates by performing a method according to the second aspect of this invention, as described below, but need not do so.

[0064] A second aspect of the present invention provides a method of synchronizing the time and frequency of a slave clock in a slave device to a master clock in a master device which is connected to the slave device over a network, the method including the steps of: exchanging, between the master device and the slave device, timing messages and recording timestamps which are: the time of sending of timing messages from the master device according to the master clock; the time of receipt of said timing messages according to the slave clock; the time of sending of said timing messages according to the slave clock; and the time of receipt of said timing messages according to the master clock; formulating a linear programming problem which includes in its constraints said timestamps along with variables relating to: the skew and offset of the slave clock compared to the master clock; and the relationship between the forward and reverse transmission speeds in the network between the master device and the slave device; solving the linear programming problem to derive an estimate of the skew and offset of the slave clock relative to the master clock; and synchronizing the slave clock to the master clock based on the estimated skew and offset to produce a master time estimate.

[0065] The network may be a packet network (using technologies such Ethernet, IP, MPLS, etc.).

[0066] The timing messages are preferably timing messages under the IEEE 1588 Precision Time Protocol (PTP).

[0067] By using the linear programming approach set out above, accurate timing information (time and frequency) may be transported from a master (server) clock in an end-to-end fashion over a packet network and accurately recovered at the slave (client) device.

[0068] The method of this aspect requires no assistance from the packet network in its synchronization operation and is still able to provide sub-microsecond level clock accuracies.

[0069] The method of this aspect uses a two-dimensional linear programming technique for estimating clock offset and skew from two-way timing message exchanges whilst taking account of transmission rate asymmetry (for example as may be found in DSL or GPON networks). It is assumed that the delay as a result of rate asymmetry could exist on top of other communication path delay asymmetries.

[0070] The proposed linear programming technique for estimating the clock offset and skew of a slave clock with respect to a master clock does not require knowledge of the measurement and process noise statistics as in Kalman filtering based techniques.

[0071] The master of this aspect may be a GrandMaster (GM) or a Boundary Clock (BC). BCs provide a means to distribute synchronization information in larger networks by building a clock hierarchy. The BC relieves the GM from handling a large number of ordinary clocks by segmenting downstream networks into areas.

[0072] In certain embodiments of the present aspect, the linear programming problem comprises two problems, in which: the first problem seeks to minimize the expression

[00003]$\frac{a}{2}.Math.\left(T_{2,1}^2-T_{2,L}^2\right)+b_1\left(T_{2,1}-T_{2,L}\right)$

subject to the constraint that aT.sub.2,n+b.sub.1≦τ.sub.n, n∈{1,2, . . . , L} wherein a is the negative of the skew of the slave clock relative to the master clock, T.sub.2,n is the time of receipt of the nth timing message from the master device according to the slave clock, b.sub.1 is the negative of the offset of the slave clock compared to the master clock as adjusted by the transmission delay and the physical link delay in the downstream direction from master to slave and τ.sub.n=T.sub.2,n−T.sub.1,n is the transport delay between the master and the slave with T.sub.1,n being the time of sending of the nth timing message from the master device according to the master clock, and the second problem seeks to minimize the expression

[00004]$\frac{a}{2}.Math.\left(T_{4,1}^2-T_{4,L}^2\right)+b_2\left(T_{4,1}-T_{4,L}\right)$

subject to the constraint that aT.sub.4,n+b≦τ.sub.n, n∈{1,2, . . . , L} wherein a is the negative of the skew of the slave clock relative to the master clock, T.sub.4,n is the time of receipt of the nth timing message from the slave device according to the master clock, b.sub.2 is the negative of the offset as adjusted by the transmission delay and the physical link delay in the upstream direction from slave to master and τ.sub.n=T.sub.4,n−T.sub.3,n is the transport delay between the master and the slave with T.sub.3,n being the time of sending of the nth timing message from the slave device according to the slave clock.

[0073] In particular, the linear program may define b.sub.1 as b.sub.1=−θ+t.sub.ds+p.sub.ds and b.sub.2 as b.sub.2=−θ−ξt.sub.ds−p.sub.us wherein θ is the offset of the slave clock compared to the master clock, t.sub.ds is the transmission delay in the downstream direction, p.sub.ds is the physical link delay in the downstream direction, p.sub.us is the physical link delay in the upstream direction and is the speed ratio of the transmission rate in the downstream direction to the transmission rate in the upstream direction.

[0074] Having solved this linear program, the skew and offset of the slave clock can be determined.

[0075] In further embodiments of the present aspect the linear programming problem seeks to minimize the expression β.sub.1−β.sub.2 in which β.sub.1 is the offset of the slave clock compared to the master clock as adjusted by the transmission delay and the physical link delay in the downstream direction from master to slave and β.sub.2 is the offset as adjusted by the transmission delay and the physical link delay in the upstream direction from slave to master, subject to the constraints that T.sub.1,n≧(1+α)T.sub.2,n+β.sub.1, T.sub.4,n≦(1+ )T.sub.3,n+β.sub.2 and β.sub.1−β.sub.2≧0 wherein: α is the skew of the slave clock compared to master clock; T.sub.1,n is the time of sending of the nth timing message from the master device according to the master clock; T2,n is the time of receipt of the nth timing message from the master device according to the slave clock; T.sub.3,n is the time of sending of the nth timing message from the slave device according to the slave clock; and T.sub.4,n is the time of receipt of the nth timing message from the slave device according to the master clock.

[0076] In particular, the linear program may define β.sub.1 as β.sub.1=θ−t.sub.ds−p.sub.ds and β.sub.2 as β.sub.2=θ+ξt.sub.ds+p.sub.us wherein θ is the offset of the slave clock compared to the master clock, t.sub.ds is the transmission delay in the downstream direction, p.sub.ds is the physical link delay in the downstream direction, p.sub.us is the physical link delay in the upstream direction and ξ is the speed ratio of the transmission rate in the downstream direction to the transmission rate in the upstream direction.

[0077] Solving this linear program provides a value for the skew and allows the offset to be determined.

[0078] In certain circumstances, the skew of the slave clock will be known from other methods, or can be estimated separately. In such cases, the terms involving the skew in the above linear programs become constants and so can be adjusted accordingly.

[0079] For example, if the skew is known, the two-problem program of the embodiments described above can be simplified to minimizing b.sub.1(T.sub.2,1−T.sub.2,L) subject to the constraint that b.sub.1≦τ.sub.n−aT.sub.2,n, n∈{1,2, . . . , L} and minimizing b.sub.2(T.sub.4,1−T.sub.4,L) subject to the constraint that b.sub.2≦τ.sub.n−aT.sub.4,n, n∈{1,2, . . . , L} in which a is now known/estimated in advance.

[0080] Similarly the single-problem program of the embodiments described above can be simplified as the constraints now contain only β.sub.1 and) β.sub.2 as unknowns.

[0081] Further simplification may be possible if frequency synchronization can be achieved using a known technique (e.g. Synchronous Ethernet or Network Timing Reference), in which case the skew can be assumed to be zero (or approximately zero), thus further simplifying the linear program(s) to be solved.

[0082] The slave clock may include a local free-running oscillator and a skew-adjusted free-running counter driven by the output of said local free-running oscillator, and the step of synchronizing may include the steps of: synchronizing the frequency of the slave clock to the frequency of the master clock by adjusting the skew-adjusted free-running counter to take account of the estimated skew and applying the estimated offset to the output of the skew-adjusted free-running counter to produce the master time estimate.

[0083] The skew-adjusted free-running counter may also be used to provide timestamps for the time of receipt and of sending of timing messages at/from the slave device.

[0084] The method may further include the steps of: initializing the counter on receipt by the slave device of the first timing message from the master device, and resetting the counter to said first master time estimate on receipt of the first master time estimate.

[0085] The method of the present aspect may include any combination of some, all or none of the above described preferred and optional features.

[0086] The method of the above aspect is preferably implemented by a system according to the second aspect of this invention, as described below, but need not be.

[0087] Further aspects of the present invention include computer programs for running on computer systems which carry out the method of the above aspect, including some, all or none of the preferred and optional features of that aspect.

[0088] A further embodiment of the present invention provides a time and frequency synchronisation system for a network, the system including: a master device having a master clock; a slave device having a slave clock; and a network connecting the master and slave devices, wherein: the slave clock comprises a slave clock and a processor; and the processor is arranged to: exchange with the master device, timing messages and record timestamps which are: the time of sending of said timing messages from the master device according to the master clock; the time of receipt of said timing messages according to the slave clock; the time of sending of said timing messages according to the slave clock; and the time of receipt of said timing messages according to the master clock; formulate a linear programming problem which includes in its constraints said timestamps along with variables relating to: the skew and offset of the slave clock compared to the master clock; and the relationship between the forward and reverse transmission speeds in the network between the master device and the slave device; solve the linear programming problem to derive an estimate of the skew and offset of the slave clock relative to the master clock; and synchronize the slave clock to the master clock based on the estimated skew and offset to produce a master time estimate.

[0089] The network may be a packet network (using technologies such Ethernet, IP, MPLS, etc.). The timing messages are preferably timing messages under the IEEE 1588 Precision Time Protocol (PTP).

[0090] By using the linear programming approach set out above, accurate timing information (time and frequency) may be transported from a master (server) clock in an end-to-end fashion over a packet network and accurately recovered at the slave (client) device.

[0091] The slave device of this aspect requires no assistance from the packet network in its synchronization operation and is still able to provide sub-microsecond level clock accuracies.

[0092] The slave device of this aspect uses a two-dimensional linear programming technique for estimating clock offset and skew from two-way timing message exchanges whilst taking account of transmission rate asymmetry (for example as may be found in DSL or GPON networks). It is assumed that the delay as a result of rate asymmetry could exist on top of other communication path delay asymmetries.

[0093] The proposed linear programming technique for estimating the clock offset and skew of a slave clock with respect to a master clock does not require knowledge of the measurement and process noise statistics as in Kalman filtering based techniques.

[0094] The master of this aspect may be a GrandMaster (GM) or a Boundary Clock (BC). BCs provide a means to distribute synchronization information in larger networks by building a clock hierarchy. The BC relieves the GM from handling a large number of ordinary clocks by segmenting downstream networks into areas.

[0095] In certain embodiments of the present aspect, the linear programming problem comprises two problems, in which: the first problem seeks to minimize the expression

[00005]$\frac{a}{2}.Math.\left(T_{2,1}^2-T_{2,L}^2\right)+b_1\left(T_{2,1}-T_{2,L}\right)$

subject to the constraint that aT.sub.2,n+b.sub.1≦τ.sub.n, n∈{1,2, . . . , L} wherein a is the negative of the skew of the slave clock relative to the master clock, T2,n is the time of receipt of the nth timing message from the master device according to the slave clock, b.sub.1 is the negative of the offset of the slave clock compared to the master clock as adjusted by the transmission delay and the physical link delay in the downstream direction from master to slave and τ.sub.n=T.sub.2,n−T.sub.1,n is the transport delay between the master and the slave with T.sub.1,n being the time of sending of the nth timing message from the master device according to the master clock, and the second problem seeks to minimize the expression

[00006]$\frac{a}{2}.Math.\left(T_{4,1}^2-T_{4,L}^2\right)+b_2\left(T_{4,1}-T_{4,L}\right)$

subject to the constraint that aT.sub.4,n+b≦τ.sub.n, n∈{1,2, . . . , L} wherein a is the negative of the skew of the slave clock relative to the master clock, T.sub.4,n is the time of receipt of the nth timing message from the slave device according to the master clock, b.sub.2 is the negative of the offset as adjusted by the transmission delay and the physical link delay in the upstream direction from slave to master and τ.sub.n=T.sub.4,n−T.sub.3,n is the transport delay between the master and the slave with T.sub.3,n being the time of sending of the nth timing message from the slave device according to the slave clock.

[0096] In particular, the linear program may define b.sub.1 as b.sub.1=−θ+t.sub.ds+p.sub.ds and b.sub.2 as b.sub.2=−θ−ξt.sub.ds −p.sub.us wherein θ is the offset of the slave clock compared to the master clock, t.sub.ds is the transmission delay in the downstream direction, p.sub.ds is the physical link delay in the downstream direction, p.sub.us is the physical link delay in the upstream direction and ξ is the speed ratio of the transmission rate in the downstream direction to the transmission rate in the upstream direction.

[0097] Having solved this linear program, the skew and offset of the slave clock can be determined.

[0098] In further embodiments of the present aspect the linear programming problem seeks to minimize the expression β.sub.1−β.sub.2 in which β.sub.1 is the offset of the slave clock compared to the master clock as adjusted by the transmission delay and the physical link delay in the downstream direction from master to slave and β.sub.2 is the offset as adjusted by the transmission delay and the physical link delay in the upstream direction from slave to master, subject to the constraints that T.sub.1,n≧(1+α)T.sub.2,n+β.sub.1, T.sub.4,n≦(1+α)(T.sub.3,n+β.sub.2 and β.sub.1−β.sub.2≧0 wherein: α is the skew of the slave clock compared to master clock; T.sub.1,n is the time of sending of the nth timing message from the master device according to the master clock; T.sub.2,n is the time of receipt of the nth timing message from the master device according to the slave clock; T.sub.3,n is the time of sending of the nth timing message from the slave device according to the slave clock; and T.sub.4,n is the time of receipt of the nth timing message from the slave device according to the master clock.

[0099] In particular, the linear program may define β.sub.1 as β.sub.1=θ−t.sub.ds−p.sub.ds and β.sub.2 as β.sub.2=θ+ξt.sub.ds+p.sub.us wherein θ is the offset of the slave clock compared to the master clock, t.sub.ds is the transmission delay in the downstream direction, p.sub.ds is the physical link delay in the downstream direction, p.sub.us is the physical link delay in the upstream direction and ξ is the speed ratio of the transmission rate in the downstream direction to the transmission rate in the upstream direction.

[0100] Solving this linear program provides a value for the skew and allows the offset to be determined.

[0101] In certain circumstances, the skew of the slave clock will be known from other methods, or can be estimated separately. In such cases, the terms involving the skew in the above linear programs become constants and so can be adjusted accordingly.

[0102] For example, if the skew is known, the two-problem program of the embodiments described above can be simplified to minimizing b.sub.1(T.sub.2,1−T.sub.2,L) subject to the constraint that b.sub.1≦τ.sub.n−aT.sub.2,n, n∈{1,2, . . . , L} and minimizing b.sub.2 (T.sub.4,1−T.sub.4,L) subject to the constraint that b.sub.2≦τ.sub.n−aT.sub.4,n, n∈{1,2, . . . , L} in which a is now known/estimated in advance.

[0103] Similarly the single-problem program of the embodiments described above can be simplified as the constraints now contain only β.sub.1 and β.sub.2 as unknowns.

[0104] Further simplification may be possible if frequency synchronization can be achieved using a known technique (e.g. Synchronous Ethernet or Network Timing Reference), in which case the skew can be assumed to be zero (or approximately zero), thus further simplifying the linear program(s) to be solved.

[0105] Preferably the slave clock includes a local free-running oscillator and a skew-adjusted free-running counter driven by the output of said local free-running oscillator, and the slave device is arranged to synchronize the frequency of the slave clock to the frequency of the master clock by adjusting the skew-adjusted free-running counter to take account of the estimated skew and applying the estimated offset to the output of the skew-adjusted free-running counter to produce the master time estimate.

[0106] In some embodiments, the skew-adjusted free-running counter is also used to provide timestamps for the time of receipt and of sending of timing messages at/from the slave device.

[0107] In these embodiments the counter may be initialized on receipt by the slave device of the first timing message from the master device, and the counter may be reset on receipt of the first master time estimate to said first master time estimate.

[0108] The system of the present aspect may include any combination of some, all or none of the above described preferred and optional features.

[0109] The processor of the slave device of the above aspect preferably operates by performing a method according to the second aspect of this invention, as described above, but need not do so.

Proposed Synchronization Solutions

[0110] First a generalized clock offset and skew equation is defined for the synchronization problem. It is assumed that, at any particular time instant, the instantaneous view of the relationship between the master (server) clock with timeline S(t) and the slave (client) clock with timeline C(t), can be described by the well-known simple skew clock model depicted in FIG. 3, and described by the equation,

S(t)=(1+α)C(t)+θ,   (1)

[0111] where θ is the initial time offset and a is the skew (frequency offset) which is a very small quantity in the order of parts-per-million. This snapshot is an instantaneous view of how well the two clocks are (mis)aligned. FIG. 3 illustrates the influence of θ and α on the alignment.

[0112] Equation (1) can further be expressed as

S(t)−C(t)=θ.sub.tot(t)=αC(t)+θ,

[0113] where θ.sub.tot(t)=αC(t)+θ is the total time offset at any particular time t>0. This time varying offset which reflects the true offset between the two clocks consists of two components, one being θ the (fixed) initial offset, and the other αC(t) which is an offset that arises as a result of the non-zero skew between the two clocks. Time synchronization in this sense will require knowing accurately the total offset θ.sub.tot(t) or, equivalently, its constituent components α and θ, when given any C(t) value.

[0114] Considering the network configuration in FIG. 1, it is assumed that synchronization messages (see FIG. 2) are being exchanged between a master 1 in the headend/aggregation point and a slave 3 at the modem/access point end. The above equation can be extended to account for the case where the master clock 4 and slave clock 5 exchange messages over a communication link with delay. It can be assumed the nth Sync message traveling from the master to the slave (downstream direction) experiences a transmission delay of t.sub.ds, a fixed physical link (or propagation) delay of p.sub.ds , plus a random delay w.sub.ds which is due to DSL/GPON line noise and other artifacts.

[0115] Similarly, the nth Delay_Req message sent from the slave to the master (upstream direction) is assumed to experience a transmission delay of t.sub.us, a fixed propagation delay of p.sub.us plus a random delay of w.sub.us . It should be noted that the downstream and upstream end-to-end signal transmission delays of a DSL link are different. It is observed that a DSL link contains the following processing sources that can generate packet “jitters” or line perturbations in the order of a few hundreds of microseconds: [0116] Forward error correction (FEC) encoder/decoder [0117] mapping onto discrete multi-tone (DMT) modulation symbols [0118] symbol transmission/reception [0119] insertion of DSL sync symbols [0120] transmitting user data to higher layer

[0121] In addition, the DSL transceiver consists of digital part and analog part, which result in asymmetrical downstream and upstream end-to-end delays and delay jitters. The delays w.sub.ds and w.sub.us are considered to be the packet jitter in the DSL network.

[0122] An asymmetric path exists when the delay components in the two directions are unequal. It is assumed that the physical link delay (which can consist of wire/fiber delays, and internal device signal path and processing delays (i.e., chip, board, and board-to-board level delays)) is manually calibrated (as described in ITU-T Rec. G.8271 [7]) or known through other means. Current industry practices (see ITU-T Rec. G.8271) involve manual calibration of all of these types of delays.

[0123] The transmission delay, on the other hand, is inversely proportional to the transmission rate (speed). The master to slave (downstream direction) transmission rate can be defined as S.sub.ds∝1/t.sub.ds and the slave to master (upstream direction) transmission rate as S.sub.us∝1/t.sub.us as shown in FIG. 4. From this the following speed relationship can be derived:

[00007]$\begin{array}{cc}\frac{S_{\mathrm{ds}}}{S_{\mathrm{us}}}=\frac{t_{\mathrm{us}}}{t_{\mathrm{ds}}}=\xi ,& \left(2\right)\end{array}$

where ξ>0 is a multiplicative factor (which we call a speed ratio) that relates t.sub.ds and t.sub.us . The speed ratio ξ can easily be computed if the downstream speed S.sub.ds and upstream speed S.sub.us are known or can be estimated. These speeds are the transmission speeds of PTP messages on the communication medium linking the master and slave clocks.

[0124] The master and slave exchange messages using the delay-request delay-response mechanism described in FIG. 2. For the nth Sync message which departs the master with timestamp T.sub.1,n∈S(t) and arrives at the slave with timestamp T.sub.2,n∈C(t) after having experienced delays of t.sub.ds, p.sub.ds and w.sub.ds, the simple skew clock model above can be extended to account for the travel time to obtain the following expression:

(T.sub.1,n+t.sub.ds+p.sub.ds+w.sub.ds)=(1+α)T.sub.2,n+θ  (3)

[0125] From (3), the following expressions can be derived

(T.sub.1,n+t.sub.ds+p.sub.ds)≦(1+α)T.sub.2,n+θ  (4)

T.sub.1,n≦(1+α)T.sub.2,n+θ−t.sub.ds−p.sub.ds   (5)

[0126] A key assumption here is that the message exchanges occur over a period of time so small that the offset θ.sub.tot and skew α can be assumed constant over that period. The effects of the initial offset and skew on the master-slave clock alignment are illustrated in FIG. 3.

[0127] For the nth Delay_Req message which departs the slave with timestamp T.sub.3,n∈C(t) and arrives at the master with timestamp T.sub.4,n∈S(t) after having experienced delays of t.sub.us=ξt.sub.ds, p.sub.us and w.sub.us, the following expression is obtained:

(t.sub.4,n−t.sub.us−p.sub.us−w.sub.us)=(1+α)t.sub.3,n+θ  (6)

[0128] From (6), the following expressions can be obtained

(T.sub.4,n−t.sub.us−p.sub.us)≧(1+α)T.sub.3,n+θ  (7)

T.sub.4,n≧(1+α)T.sub.3,n+θ+ξt.sub.ds+p.sub.us   (8)

[0129] From (5), it is known that

T.sub.1,n≦(1+φ.sub.1)T.sub.2,n+β.sub.1   (9)

[0130] where

φ.sub.1=α  (10)

β.sub.1=θ−t.sub.ds−p.sub.ds   (11)

[0131] From (8), we can write

T.sub.4,n≧(1+φ.sub.2)T.sub.3,n+β.sub.2   (12)

[0132] where

φ.sub.2=α  (13)

β.sub.2=θ+ξt.sub.ds+p.sub.us   (14)

[0133] Adding (10) and (13), the skew is obtained as

[00008]$\begin{array}{cc}\alpha =\frac{{\varphi }_1+{\varphi }_2}{2}& \left(15\right)\end{array}$

[0134] Then adding (11) and (14), the clock offset is obtained as

[00009]$\begin{array}{cc}{\beta }_1+{\beta }_2=2.Math..Math.\theta +\left(\xi -1\right).Math.t_{\mathrm{ds}}+\left(p_{\mathrm{us}}-p_{\mathrm{ds}}\right)& \left(16\right)\\ \theta =\frac{{\beta }_1+{\beta }_2}{2}+\left(1-\xi \right).Math.\frac{t_{\mathrm{ds}}}{2}+\frac{\left(p_{\mathrm{ds}}-p_{\mathrm{us}}\right)}{2}& \left(17\right)\end{array}$

[0135] The link delays can be symmetric (i.e., p.sub.ds−p.sub.us=0) or the level of link delay asymmetry p.sub.ds−p.sub.us≠0 has to be accurately known and used in (17). For symmetric links, we have

[00010]$\begin{array}{cc}\theta =\frac{{\beta }_1+{\beta }_2}{2}+\left(1-\xi \right).Math.\frac{t_{\mathrm{ds}}}{2}& \left(18\right)\end{array}$

[0136] When both the physical links and the transmission rates are symmetric (i.e., p.sub.ds−p.sub.us=0 and ξ=1), then (17) and (18) simplify to the classic clock synchronization solution (where symmetry is usually assumed):

[00011]$\begin{array}{cc}\theta =\frac{{\beta }_1+{\beta }_2}{2}& \left(19\right)\end{array}$

[0137] The downstream transmission delay t.sub.ds can be estimated using a number of methods some of which are as follows: [0138] Use the downstream transmission rate S.sub.ds and the Sync (or Delay_Req) message size P.sub.sync at the slave to estimate t.sub.ds. Note that PTP Sync and Delay_Req messages have the same size:

[00012]$\begin{array}{cc}{t}_{\mathrm{ds}}=\frac{P_{\mathrm{sync}}}{S_{\mathrm{ds}}}& \left(20\right)\end{array}$ [0139] Use the time it takes to receive a Sync message at the slave measured using the slave clock C(t) and the skew α to estimate t.sub.ds. If T.sub.first and T.sub.last denote the receive timestamps (times) of the first and last bits of the message, respectively, then

t.sub.ds=(1+α)(T.sub.last−T.sub.first)   (21)

[0140] The implementation complexity of each method will play a big role in which method to use. The t.sub.ds obtained via any of the above two methods can be filtered before use in the computation of the clock offset θ. Below two linear programming models for computing the offset θ and skew α according to embodiments of the invention are described.

Linear Programming Model 1

[0141] A linear programming model for computing φ.sub.1, β.sub.1, φ.sub.2 , and β.sub.2 according to a first embodiment of the present invention will now be described. First the exchange of Sync messages between master and slave is considered. Given the timestamps T.sub.1,n and T.sub.2,n, let τ.sub.n=T.sub.2,n−T.sub.1,n denote the transport delay between master and slave. If it is assumed that there is a cloud of τ.sub.n points with corresponding T.sub.2,n points maintained at the slave, then the objective is to find a line below the cloud of points with T.sub.2 in abscissa (x-axis) and τ in ordinate (y-axis). The slope of the line gives an estimate of the skew φ.sub.1.

[0142] From (9),

−φ.sub.1T.sub.2,n−β.sub.1≦T.sub.2,n−T.sub.1,n

−φ.sub.1T.sub.2,n−β.sub.1≦τ.sub.n   (22)

[0143] Let a=−φ.sub.1 and b=−β.sub.1. Then (22) is of form

ax+b≦y,   (23)

[0144] where x=T.sub.2,n and y=τ.sub.n . The line bordering the cloud of points is

ax+b=y   (24)

[0145] The unknowns in (24) are a=−φ.sub.1 and b=−β.sub.1. Since the line (24) must lie below the cloud, the linear constraint aT.sub.2,n+b≦τ.sub.n must be satisfied for all n. A possible objective function may then consist of minimizing the area between the cloud and the line as illustrated in FIG. 5.

[0146] Let L>1 denote the number of Sync message exchanges between master and slave over a defined period of time (i.e., the sampling or measurement period). From FIG. 5, the objective function can be expressed as

[00013]$\begin{array}{cc}\begin{array}{c}f\left(a,b\right)=.Math.\frac{1}{2}.Math.\underset{n=1}{\overset{L-1}{.Math.}}.Math..Math.\left[\left({\tau }_n-{\mathrm{aT}}_{2,n}-b\right)+\left({\tau }_{n+1}-{\mathrm{aT}}_{2,n+1}-b\right)\right].Math.\left(T_{2,n+1}-T_{2,n}\right)\\ =.Math.\lambda -\frac{a}{2}.Math.\underset{n=1}{\overset{L-1}{.Math.}}.Math..Math.\left(T_{2,n+1}+T_{2,n}\right).Math.\left(T_{2,n+1}-T_{2,n}\right)-b.Math.\underset{n=1}{\overset{L-1}{.Math.}}.Math..Math.\left(T_{2,n+1}-T_{2,n}\right)\\ =.Math.\lambda -\frac{a}{2}.Math.\underset{n=1}{\overset{L-1}{.Math.}}.Math..Math.\left(T_{2,n+1}^2-T_{2,n}^2\right)-b.Math.\underset{n=1}{\overset{L-1}{.Math.}}.Math..Math.\left(T_{2,n+1}-T_{2,n}\right)\\ =.Math.\lambda -\frac{a}{2}.Math.\left(T_{2,L}^2-T_{2,1}^2\right)-b\left(T_{2,L}-T_{2,1}\right)\\ =.Math.\lambda +\frac{a}{2}.Math.\left(T_{2,1}^2-T_{2,L}^2\right)+b\left(T_{2,1}-T_{2,L}\right)\end{array}& \left(25\right)\\ .Math.\lambda =\frac{1}{2}.Math.\underset{n=1}{\overset{L-1}{.Math.}}.Math..Math.\left({\tau }_n+{\tau }_{n+1}\right).Math.\left(T_{2,n+1}-T_{2,n}\right),& \left(26\right)\end{array}$

[0147] is a quantity that is not dependent on a and/or b. From the above discussion, the following two-dimensional or two-variable linear program can be formulated:

[00014]$\begin{array}{cc}\mathrm{Minimize}.Math.\left\{\frac{a}{2}.Math.\left(T_{2,1}^2-T_{2,L}^2\right)+b\left(T_{2,1}-T_{2,L}\right)\right\}.Math..Math.s.t..Math.{\mathrm{aT}}_{2,n}+b\le {\tau }_n,n\in \left\{1,2,\mathrm{.Math.}.Math.,L\right\}& \left(27\right)\end{array}$

[0148] Linear programming in two-dimensions can be solved using linear-time algorithms that are extremely efficient.

[0149] The analysis above for the Sync message scenario can be extended to Delay_Req message exchanges between slave and master. Here, τ.sub.n=T.sub.4,n−T.sub.3,n denotes the transport delay between slave and master. From (12)

φ.sub.2T.sub.3,n+β.sub.2≦T.sub.4,n−T.sub.3,n

φ.sub.2T.sub.3,n+β.sub.2≦τ.sub.n   (28)

[0150] Let a=φ.sub.2 and b=β.sub.2. Then (28) is of form ax+b≦y where x=T.sub.3,n and y=τ.sub.n. The line bordering the cloud of points is ax+b=y . The unknowns here are a=φ.sub.2 and b=β.sub.2. Here, the linear constraint aT.sub.3,n+b≦τ.sub.n must be satisfied for all n. The objective function (25) can be formulated to solve for a=φ.sub.2 and b=β.sub.2.

[0151] Knowing φ.sub.1, β.sub.1, φ.sub.2, and β.sub.2 from the linear programming solution, the skew α can then be determined from (15) and offset θ can be determined from (17) as discussed earlier. Other linear programming approaches for determining the skew and offset are described in [2][3][4][5][6].

Linear Programming Model 2

[0152] A second linear programming model for computing offset θ and skew α according to a further embodiment of the present invention will now be described. Retaining α in (9), the following expression for the nth Sync (downstream) message flows becomes T.sub.1,n≦(1+α)T.sub.2,n+β.sub.1 from which the boundary of the cloud of downstream timestamps is T.sub.1,n=(1+α)T.sub.2,nβ.sub.1. This is of the form y=(1+α)x+β.sub.1, where y∈T.sub.1,n, T.sub.4,n∈S(t) and x∈T.sub.2,n,T.sub.3,n∈C(t).

[0153] The cloud of downstream timestamps generated as a result of path propagation delay and queuing delays can lie (or spread) below this line but the “true” line relating master and slave clocks must NOT. This means, the line relating the master and slave clocks, must lie ON or ABOVE this boundary (line). This results in the following constraint for the downstream cloud T.sub.1,n≧(1+α)T.sub.2,n+β.sub.1 or y≧(1+α)x+β.sub.1.

[0154] Similarly, retaining α in (12) gives the following expression for the nth Delay_Req (upstream) message flows as T.sub.4,n≧(1+α)T.sub.3,n+β.sub.2, which also produces the boundary of the cloud of upstream timestamps as T.sub.4,n=(1+α)T.sub.3,n+β.sub.2. This is also of the form y=(1+α)xβ.sub.2.

[0155] Here too, the cloud of upstream timestamps generated as a result of path propagation delay and queuing delays can lie above this line but the “true” line relating master and slave clocks must NOT. The line relating the master and slave clocks, must lie ON or BELOW this boundary (line). This results in the following constraint for the upstream cloud T.sub.4,n≦(1+α)T.sub.3,n+β.sub.2 which is also of the form y≦(1+α)x+β.sub.2.

[0156] These two constraints T.sub.1,n≧(1+α)T.sub.2,n+β.sub.1 and T.sub.4,n≦(1+α)T.sub.3,n+β.sub.2 (see FIG. 6) can be interpreted as the constraints of a linear program which suggests a line (dashed line in figure) that separates the downstream cloud of timestamps and upstream cloud of timestamps. The clock offset parameters β.sub.1 and β.sub.2 ideally should be the same or extremely close together since they relate to the same clocks (master and slave). We are therefore trying to find the smallest corridor (defined by the constraints T.sub.1,n≧(1+α)T.sub.2,n+β.sub.1 and T.sub.4,n≦(1+α)T.sub.3,n,+β.sub.2) that gives us the smallest difference between β.sub.1 and β.sub.2.

[0157] The idea here is to estimate parameters that will make the two parallel lines in FIG. 6 as close together as possible, that is, make the lane between these two lines as small as possible. The estimation algorithm strives to identify the two parallel lines y=(1+α)x+β.sub.1 (line bordering the downstream cloud) and y=(1+α)x+β.sub.2 (line bordering upstream cloud) with the condition that β.sub.1−β.sub.2 is minimized but at the same time allow the two lines to fit just at the edge of the two clouds.

[0158] A linear programming formulation that seeks to place these two parallel lines as wide apart as possible is as follows.

[0159] Minimize β.sub.1−β.sub.2

[0160] s.t.

T.sub.1,n≧(1+α)T.sub.2,n+β.sub.1, n∈{1,2, . . . , L},

T.sub.4,n≦(1+α)T.sub.3,n+β.sub.2, n∈{1,2, . . . , L},

β.sub.1−β.sub.2≧0.

[0161] Knowing the skew α and the parameters β.sub.1 and β.sub.2 from the above linear program, the offset θ can be determined from (17) as discussed earlier.

Clock Skew Estimation Using a Timestamp-Driven Digital Phase-Locked Loop

[0162] A further embodiment of the present invention provides a method of estimating clock skew based on a timestamp-driven digital phase-locked loop (DPLL) and a free-running counter (that is driven by the destination oscillator) for clock skew estimation which will now be described. A further embodiment of the present invention provides a method of estimating and monitoring how well the DPLL is frequency synchronized to the source frequency. The DPLL frequency synchronization and clock skew estimation in these embodiments is done using only one-way measurements, for example, via PTP Sync and Follow_Up messages—two-way PTP message exchanges are not required (no need for Delay_Req and Delay_Resp messages).

Frequency Synchronization Using a DPLL

[0163] The transmitter (master or PTP GrandMaster) clock conceptually can be viewed as consisting simply of a high accuracy, high performance oscillator 4 and a (master) counter 40 (FIG. 7). The oscillator 4 issues periodic pulses that constitute the input to the master counter 4-. The oscillator frequency is the inverse of the interval between consecutive pulses (oscillator period). The output of the master counter 4- represents the master clock signal and is incremented by a fixed amount at each pulse (e.g., 8 ns increments for a 125 MHz nominal oscillator frequency). Samples of master clock signals are communicated to the receiver (slave) 3 as timestamps 20. The local clock 4 in the master 1 is free running or possibly synchronized to an external source of time such as the Global Positioning System (GPS) or atomic clock.

[0164] From the flow of timestamp messages arriving at the receiver 3, the receiver DPLL 30 tunes its internal controlled oscillator 33 such that it produces an output clock signal that is identical to the transmitter clock. To do this, the first arriving timestamp at the receiver is used to initialize the master counter 34 and DPLL control is exercised such that the master counter 34 readings coincide with arriving timestamp values. The timestamps used in determining the arrival instants of timestamp messages are based on timestamps generated from the local clock 5 (FIG. 7). The control loop in the receiver DPLL adjusts the clock 5 to agree with the time of its master 4, that is, to make the rate of the local clock equal to that of the master.

[0165] In the frequency synchronization technique according to the present embodiment, each broadcast begins at time T.sub.1 with a Sync message sent by the master to all the slave clocks in the domain. A slave clock receiving this message takes note of the local time T.sub.2 when this message is received. The master may subsequently send a multicast Follow_Up with accurate T.sub.1 timestamp, the reason being not all masters have ability to present an accurate time stamp in the Sync message. It is only after the transmission is complete that they are able to retrieve an accurate time stamp for the Sync transmission from their network hardware. Masters with this limitation use the Follow_Up message to convey T.sub.1 (two-step clock). Masters with PTP capabilities built into their network hardware are able to present an accurate time stamp in the Sync message and do not need to send Follow_Up messages, these are called one-step clocks.

[0166] The controlled oscillator 33 within the DPLL 30 as shown in FIG. 7 and FIG. 8 produces a periodic pulse signal which drives a local DPLL counter 34 whose output enters the phase detector 31. Here the phase of the signals from the DPLL counter 34 and the incoming reference signal in the form of timestamps 20 are compared and a resulting difference or error signal is produced. This error corresponds to the phase difference between the two signals, transmitter and receiver clocks.

[0167] The error signal from the phase detector 31 in the DPLL 30 passes through a low pass filter 32 (loop filter) which governs many of the properties of the loop and removes any high frequency elements on the signal. Once through the filter 32 the error signal is applied to the control terminal of the controlled oscillator 33 as its control or tuning signal. The nature of this control signal is such that it tries to reduce the phase difference and hence the frequency between the two signals. Initially the loop will be out of lock, and the filtered error signal will pull the frequency of the controlled oscillator towards that of the reference, until it cannot reduce the error any further and the loop is locked.

[0168] This frequency synchronization strategy allows multiple slaves, for example in a broadcast or point-to-multipoint communication scenario, to synchronize their clocks to the master. The one-step clock and two-step clock algorithms used by the slave DPLL to synchronize its frequency to the master's are described in a previous patent of the inventors' [8].

[0169] Let S.sub.n=T.sub.1,n denote the timeline (e.g., in clock increments of say 8ns for a 125 MHz clock) of the transmitter and R.sub.n=T.sub.2,n the timeline of the receiver. These two functions correspond to the timestamps of the two clocks at discrete time instants n, n=0,1,2, . . . . We assume that the timelines S.sub.n=T.sub.1,n and R.sub.n=T.sub.2,n are discrete time samples of the master (server) clock S(t) and the tunable (synchronized) slave clock R(t), respectively. The state of the free-running counter 35 is denoted in discrete time and continuous time, respectively, by C.sub.n and C(t).

[0170] In the DPLL 30, only when the phase between the two signals (that is the difference between transmitter timestamp S.sub.n=T.sub.1,n and receiver timestamp R.sub.n=T.sub.2,n) is changing is there a frequency difference. The phase difference decreases towards zero when the loop is in lock, which means that the frequency of the DPLL internal controlled oscillator 33 is exactly the same as the reference frequency.

[0171] The DPLL employs a phase accumulator 37, a loop filter 32, a phase detector 31, and a counter 34 as shown in FIG. 8. In the method of this embodiment, at each phase accumulator overflow (output) pulse, the DPLL counter 34 is incremented by the nominal period of the phase accumulator overflow pulse (e.g., 8 ns for a 125 MHz nominal phase accumulator overflow output frequency). The DPLL 30 is controlled in such a way that the DPLL counter evolution follows the server counter as illustrated in FIG. 7.

[0172] The phase accumulator 37 is a variable-modulus counter that increments the number stored in it each time it receives a clock pulse. When the counter overflows it wraps around, making the phase accumulator's output contiguous as shown in FIG. 9. The larger the added increment φ, the faster the accumulator overflows, which results in a higher output frequency. The output frequency f.sub.ACC of the phase accumulator is a function of the system clock frequency f.sub.o, the number of bits q in the phase accumulator and the phase increment value φ. The phase increment φ is an unsigned value.

[00015]$\begin{array}{cc}{f}_{\mathrm{ACC}}=\frac{f_o}{2^q}.Math.\phi & \left(30\right)\end{array}$

[0173] From this equation it can be seen that the frequency resolution of the phase accumulator is f.sub.res=.sub.o/2.sup.q. The phase accumulator is operating with a control input φ.sub.nom which corresponds to the nominal frequency f.sub.ACC=f.sub.nom. It can be seen from the above discussion that adding a quantity −φ.sub.corr to φ.sub.nom (i.e. φ.sub.ACC=φ.sub.nom−φ.sub.corr) results in a decrease in the output frequency, f.sub.ACC=f.sub.nom−Δf, whereas adding a quantity+φ.sub.corr to φ.sub.nom (i.e., φ.sub.ACC=φ.sub.nom+φ.sub.corr) results in an increase in the output frequency, f.sub.ACC=f.sub.nom+Δf. Thus, by appropriately controlling the quantity φ.sub.corr added to φ.sub.nom, the output frequency of the phase accumulator f.sub.ACC can be controlled accordingly.

[0174] For example, at startup in a system operating in the one-step clock mode, the DPLL 30 waits for the first arriving Sync message timestamp (T.sub.1,0). This first server timestamp is used to initialize the DPLL counter 34 (R.sub.0=T.sub.1,0). From this point onwards and upon the receipt of subsequent Sync message timestamps (T.sub.1,n) at any discrete time instant n, the DPLL 30 starts to operate in a closed-loop fashion. At each Sync message timestamp arrival (T.sub.1,n), the DPLL counter 34 reading is noted by the slave (R.sub.n). Then the difference between the arriving server timestamp) (T.sub.1,n) and the DPLL counter reading (R.sub.n) gives an error signal (e.sub.n=T.sub.1,n−R.sub.n). This error signal (e.sub.n) is sent to the loop filter 32 whose output controls the frequency of the phase accumulator 37. The output (overflow pulses) of the phase accumulator 37 in turn provides the clock frequency of the slave and also drives the DPLL counter 34. After a while the error term is expected to converge to zero which means the DPLL 30 has been locked to the incoming master timeline.

[0175] The control models for the phase detector 31, and digitally controlled oscillator, and given some general structure of the loop filter 32, the DPLL 30 as a whole are described in [8]. The analysis in [8] provides design procedures for determining the parameters of the loop filter 32 that will meet certain pre-specified design and performance requirements.

Clock Skew Estimation using a DPLL

[0176] Next a technique, according to an embodiment of the present invention, for estimating the skew of the free-running local oscillator using the DPLL 30 and free-running counter 35 described above will be set out. The clock skew (a) is estimated by the client 3 after each Sync message broadcast by the server 1 or after multiple periods of the Sync message broadcast. The period between Sync messages could serve as sampling period of the system. FIG. 8 shows the main blocks of the proposed synchronization and skew estimation mechanism at the time client 3. A free running local oscillator 33 and counter 35 are used together with the DPLL 30 to estimate the skew of the local free-running (high-speed) oscillator.

Skew Estimation

[0177] If the DPLL 30 locks onto the master 1 and achieves accurate frequency synchronization (a technique for accuracy analysis described further below), then we can assume that ΔR.sub.n=ΔS.sub.n, meaning the master timeline and the DPLL counter 34 evolve at the same rate.

[0178] If A.sub.cc denotes the level of frequency synchronization accuracy in parts-per million (ppm) or parts-per billion (ppb), then A.sub.c=0 implies perfect (ideal) frequency synchronization and a positive A.sub.cc as the DPLL 30 (specifically the DPLL counter 34) running faster than the master by A.sub.cc. The underlying idea is to make the slope of the slave DPLL timeline R.sub.n equal to that of the master timeline S.sub.n.

[0179] Equation (1) above can be written in discrete time as

S.sub.n=(1+α)C.sub.n+θ  (31)

[0180] From this

ΔS.sub.n=(1+α)ΔC.sub.n,   (32)

[0181] where ΔS.sub.n=S.sub.n−S.sub.n−1=T.sub.1,n−T.sub.1,n−1 and ΔC.sub.n=C.sub.n−C.sub.n−1. If accurate frequency synchronization is achieved, then the evolution of R.sub.n becomes a local (slave) copy of the evolution of the master clock S.sub.n, that is, ΔR.sub.n=ΔS.sub.n. Under this condition,

ΔR.sub.n=(1+α)ΔC.sub.n   (33)

[0182] With this, if incremental changes of both the DPLL counter ΔR.sub.n and the free-running counter ΔC.sub.n are taken at a given time instant, then a one-time estimate of the clock skew can be obtained as

[00016]$\begin{array}{cc}\alpha =\frac{\Delta .Math..Math.R_n}{\Delta .Math..Math.C_n}-1& \left(34\right)\end{array}$

[0183] It is assumed that the two counters are sampled at the same time instant. The sample skew values obtained from the above can be filtered to obtain an estimate of the skew between master clock and slave clock. From (34), it can be inferred that

ΔC.sub.n=R.sub.nα=0

ΔC.sub.n>ΔR.sub.nα<0 (free-running counter is faster)

ΔC.sub.n<ΔR.sub.nα>0 (free-running counter is slower)   (35)

[0184] The relationships in (35) are already depicted in FIG. 3.

Accuracy Analysis

[0185] As discussed above, A.sub.cc denotes the level of frequency synchronization accuracy in ppm or ppb, that is, accuracy of evolution of R.sub.n with respect to S.sub.n. A.sub.free is used to denote the accuracy of the evolution of the free-running clock C.sub.n with respect to the master S.sub.n. For telecommunication applications, A.sub.free is typically in ppm, e.g., 4.6 ppm for a Stratum 3 clock and 32 ppm for a Stratum 4 clock. For mobile applications, for example, A at the air interface should be no more than 50 ppb and 16 ppb at the incoming synchronization interface.

[0186] Using (34) and given an ideal reference interval Δt, a specified A.sub.cc and A.sub.free, it follows that

[00017]$\begin{array}{cc}\alpha =\frac{\left(1\pm A_{\mathrm{cc}}\right).Math.\Delta .Math..Math.t}{\left(1\pm A_{\mathrm{free}}\right).Math.\Delta .Math..Math.t}-1=\frac{\left(1\pm A_{\mathrm{cc}}\right)}{\left(1\pm A_{\mathrm{free}}\right)}-1& \left(36\right)\end{array}$

[0187] Taking for example, A.sub.cc=+16 ppb (i.e., the DPLL counter running faster by 16 ppb and counts in excess over Δt), and A.sub.free=+4 ppm (the free-running clock running faster by 4 ppm and counts in excess over Δt), gives

[00018]$\alpha =\frac{1+16\times {10}^{-9}}{\left(1+4\times {10}^{-6}\right)}-1=\frac{\left(1+0.000000016\right)}{\left(1+0.000004\right)}-1\approx -3.98398\times {10}^{-6}\approx -4.Math..Math.\mathrm{ppm},$

[0188] as expected. Note that by the above definition of α and equation (1), α<0 implies the slave free-running counter C.sub.n (reference 35) is faster than the master clock S.sub.n (see FIG. 3). For A.sub.cc=+50 ppb, α≈−3.94998×10.sup.−6, and for A.sub.cc=+100 ppb, α26 −3.89998×10.sup.−6. For a perfect frequency lock, A.sub.cc=0 ppb, which means

[00019]$\begin{array}{cc}\alpha =\frac{1}{\left(1\pm A_{\mathrm{free}}\right)}-1=\frac{\mp A_{\mathrm{free}}}{\left(1\pm A_{\mathrm{free}}\right)}& \left(37\right)\end{array}$

[0189] But given that for telecom applications A.sub.free is typically a very small quantity (in ppm), it can safely be assumed that α26 ∓A.sub.free under these conditions.

Real-Time Estimation and Monitoring of DPLL Frequency Synchronization Accuracy

[0190] Next a technique for estimating the frequency synchronization accuracy A.sub.cc in real-time according to an embodiment of the present invention will be described. This technique can also be used to monitor the tracking efficiency of the frequency synchronization scheme, i.e., the DPLL in real-time. First, it is assumed that some level of frequency synchronization accuracy A.sub.cc is achieved by the DPLL 30. Next the relationship between the synchronized clock (i.e., DPLL counter) R(t) and the master clock S(t) is modeled by

S(t)=(1+A.sub.cc)R(t)+θ.sub.cc,   (38)

[0191] where θ.sub.cc is a clock offset. In discrete time, this can be expressed as

S.sub.n=(1+A.sub.cc)R.sub.n+θ.sub.c   (39)

[0192] From this

ΔS.sub.n=(1+A.sub.cc)ΔR.sub.n,   (40)

[0193] where ΔR.sub.n=R.sub.n−R.sub.n−1. If the T.sub.1,n timestamps are sent at fixed intervals ΔT (as is allowed in PTP), then ΔS.sub.n=T.sub.1,n−T.sub.1,n−1=ΔT. Summing over N samples, gives

[00020]$\begin{array}{cc}N.Math..Math.\Delta .Math..Math.T=\left(1+A_{\mathrm{cc}}\right).Math.\underset{i=0}{\overset{N-1}{.Math.}}.Math..Math.\Delta .Math..Math.R_{n-i},& \left(41\right)\end{array}$

[0194] from which

[00021]$\begin{array}{cc}{A}_{\mathrm{cc}}=\frac{N.Math..Math.\Delta .Math..Math.T}{\underset{i=0}{\overset{N-1}{.Math.}}.Math..Math.\Delta .Math..Math.R_{n-i}}-1=\frac{\Delta .Math..Math.T}{\stackrel{\_}{\Delta .Math..Math.R_n}}-1,.Math.\mathrm{where}.Math..Math.\stackrel{\_}{\Delta .Math..Math.R_n}=\underset{i=0}{\overset{N-1}{.Math.}}.Math..Math.\Delta .Math..Math.R_{n-i}/N& \left(42\right)\end{array}$

is the average of the ΔR.sub.n samples. ΔR.sub.n can be estimated by several methods one of which is the well-known exponentially weighted moving average (EWMA) technique which can be expressed as

ΔR.sub.n=(1−γ)ΔR.sub.n−1+γΔR.sub.n,   (43)

[0195] where 0<γ<1 is a filtering parameter. This simple technique allows A.sub.cc to be estimated continuously and efficiently in real-time.

Estimating the Clock Offset Given a Known or Estimated Skew

[0196] If the clock skew is known, then using the estimation described above or any other technique, the linear programming techniques can be formulated as follows:

Linear Programming Model 1:

[0197]
Minimize {b(T.sub.2,1−T.sub.2,L)}

s.t.

b≦τ.sub.n−aT.sub.2,n, n∈{1,2, . . . , L}  (44)

[0198] Here α=−φ.sub.1=−α for Sync messages (or a=φ.sub.2=α for Delay_Req) are known or estimated while the corresponding b=−62 .sub.1 (or b=β.sub.2) are unknown.

Linear Programming Model 2:

[0199]
Minimize β.sub.1−β.sub.2

s.t.

β.sub.1≦T.sub.1,n−(1+α)T.sub.2,n, n∈{1,2, . . . , L},

β.sub.2≧4,n−(1+α)T.sub.3,n, n∈{1,2, . . . , L},

β.sub.1−β.sub.2≧0.   (45)

[0200] In this model, α is the known or estimated skew while β.sub.1 and β.sub.2 are unknown.

[0201] Furthermore, when frequency synchronization is achieved using a technique such as Synchronous Ethernet (Sync-E), Network Timing Reference (NTR) or similar techniques, then α≈0. With this the linear programming models can be formulated as follows:

Linear Programming Model 1:

[0202]
Minimize {b(T.sub.2,1−T.sub.2,L)}

s.t.

b≦τ.sub.n, n∈{1,2, . . . , L}

Linear Programming Model 2:

[0203]
Minimize β.sub.1−β.sub.2

s.t.

β.sub.1≦T.sub.1,n−T.sub.2,n, n∈{1,2, . . . , L},

β.sub.2≧T.sub.4,n−T.sub.3,n, n∈{1,2, . . . , L},

β.sub.1−β.sub.2≧0.   (47)

[0204] The systems and methods of the above embodiments may be implemented in a computer system (in particular in computer hardware or in computer software) in addition to the structural components and user interactions described.

[0205] The term “computer system” includes the hardware, software and data storage devices for embodying a system or carrying out a method according to the above described embodiments. For example, a computer system may comprise a central processing unit (CPU), input means, output means and data storage. Preferably the computer system has a monitor to provide a visual output display. The data storage may comprise RAM, disk drives or other computer readable media. The computer system may include a plurality of computing devices connected by a network and able to communicate with each other over that network.

[0206] The methods of the above embodiments may be provided as computer programs or as computer program products or computer readable media carrying a computer program which is arranged, when run on a computer, to perform the method(s) described above.

[0207] The term “computer readable media” includes, without limitation, any non-transitory medium or media which can be read and accessed directly by a computer or computer system. The media can include, but are not limited to, magnetic storage media such as floppy discs, hard disc storage media and magnetic tape; optical storage media such as optical discs or CD-ROMs; electrical storage media such as memory, including RAM, ROM and flash memory; and hybrids and combinations of the above such as magnetic/optical storage media.

[0208] While the invention has been described in conjunction with the exemplary embodiments described above, many equivalent modifications and variations will be apparent to those skilled in the art when given this disclosure. Accordingly, the exemplary embodiments of the invention set forth above are considered to be illustrative and not limiting. Various changes to the described embodiments may be made without departing from the spirit and scope of the invention.

[0209] In particular, although the methods of the above embodiments have been described as being implemented on the systems of the embodiments described, the methods and systems of the present invention need not be implemented in conjunction with each other, but can be implemented on alternative systems or using alternative methods respectively.

REFERENCES

[0210] [1]. IEEE Standard for a Precision Clock Synchronization Protocol for Networked Measurement and Control Systems, IEEE 1588-2008. [0211] [2]. S. B. Moon, P. Skelly and D. Towsley, “Estimation and removal of clock skew from network delay measurements,” in Proc. IEEE INFOCOM, vol. 1, pp. 227-234, New York, N.Y., USA, Mar. 1999. [0212] [3]. P. Skelly, S. B. Moon, D. Towsley, Verizon Laboratories Inc. (2003), Clock skew estimation and removal, U.S. Pat. 6,661,810. [0213] [4]. L. Zhang, Z. Liu and C. H. Xia, “Clock synchronization algorithms for network measurements,” in Proc. IEEE INFOCOM, vol. 1, pp. 160-169, Nov. 2002. [0214] [5]. Z. Liu, C. H. Xia, L. Zhang, International Business Machines Corporation (2005), Clock synchronization with removal of clock skews through network measurements in derivation of a convex hull, U.S. Pat. 6,957,357. [0215] [6]. A. Bletsas, “Evaluation of Kalman filtering for network time keeping,” IEEE Transactions on Ultrasonics, Ferroelectrics and Frequency Control, vol. 52, no. 9, pp. 1452-1460, Sept. 2005. [0216] [7]. ITU-T Recommendation G.8271/Y.1366, Time and Phase Synchronization Aspects of Packet Networks, Feb. 2012. [0217] [8]. James Aweya and Saleh Al-Araji, Method and System for Frequency Synchronization, U.S. Pat. 8,913,632.

[0218] All references referred to above are hereby incorporated by reference.