Methods and systems for estimating offset and skew using linear programming

Patent metadata

Field	Value
Publication number	US-9973292-B2
Application number	US-201615088468-A
Country	US
Kind code	B2
Filing date	Apr 1, 2016
Priority date	Apr 1, 2016
Publication date	May 15, 2018
Grant date	May 15, 2018

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.

First claim

The invention claimed is:

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. The slave device according to claim 1 wherein the linear programming problem comprises two problems, in which:
the first problem seeks to minimize the expression

a
2

⁢

(

T

2
,
1

2

-

T

2
,
L

2

)

+

b
1

⁡

(

T

2
,
1

-

T

2
,
L

)

 subject to the constraint that aT 2,n +b 1 ≤τ n , n∈{1, 2, . . . , L} wherein a is the negative of the skew of the slave clock relative to the master clock, T 2,n is the time of receipt of the nth timing message from the master device according to the slave clock, b 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 τ n =T 2,n −T 1,n is the transport delay between the master and the slave with T 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

a
2

⁢

(

T

4
,
1

2

-

T

4
,
L

2

)

+

b
2

⁡

(

T

4
,
1

-

T

4
,
L

)

 subject to the constraint that aT 4,n +b≤τ n , n∈{1, 2 , . . . , L} wherein a is the negative of the skew of the slave clock relative to the master clock, T 4,n is the time of receipt of the nth timing message from the slave device according to the master clock, b 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 τ n =T 4,n −T 3,n is the transport delay between the master and the slave with T 3,n being the time of sending of the nth timing message from the slave device according to the slave clock.

3. The slave device according to claim 2 wherein b 1 =−θ+t ds +p ds and b 2 =−θ−ξt ds −p us wherein θ is the offset of the slave clock compared to the master clock, t ds is the transmission delay in the downstream direction, p ds is the physical link delay in the downstream direction, p 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. The slave device according to claim 1 wherein the linear programming problem seeks to minimize the expression β 1 −β 2 in which β 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 β 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 1,n ≥(1+α)T 2,n +β 1 , T 4,n ≤(1+α)T 3,n +β 2 and β 1 −β 2 ≥0 wherein: α is the skew of the slave clock compared to master clock; T 1,n is the time of sending of the nth timing message from the master device according to the master clock; T 2,n is the time of receipt of the nth timing message from the master device according to the slave clock; T 3,n is the time of sending of the nth timing message from the slave device according to the slave clock; and T 4,n is the time of receipt of the nth timing message from the slave device according to the master clock.

5. The slave device according to claim 4 wherein β 1 =θ−t ds −p ds and β 2 =θ+ξt ds +p us wherein θ is the offset of the slave clock compared to the master clock, t ds is the transmission delay in the downstream direction, p ds is the physical link delay in the downstream direction, p 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. The slave device according to claim 1 wherein the slave clock includes a local fre

Assignees

• Khalifa Univ Of Science Technology And Research
• British Telecomm
• Emirates Telecommunications Corp

Inventors

• Aweya James

Classifications

• H04L7/04

  Speed or phase control by synchronisation signals {(H04L7/0075 takes precedence)} · CPC title

• H04W56/001 Primary

  Synchronization between nodes · CPC title

• H04J3/0661 Primary

  using timestamps · CPC title

• H04W56/005

  compensating for timing error by adjustment in the receiver · CPC title