# US 2017/0288801 A1 · Methods and systems for estimating offset and skew using linear programming

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2017/0288801 A1
- Document ID: US20170288801A1
- Status: Published application
- Kind: A1
- Application number: 15/088,468
- Filed: 2016-04-01
- Published: 2017-10-05
- Earliest claimed: 2016-04-01
- Assignees: Khalifa University of Science, Technology, and Research; British Telecommunications pic; Emirates Telecommunications Corporation
- Applicants: Khalifa University of Science, Technology and Research; British Telecommunications PIc; Emirates Telecommunications Corporation
- Inventors: James Aweya
- Web page: https://patentgrep.com/patent/US20170288801A1

## CPC

- H04J 3/0661: {using timestamps}
- H04L 7/04: Speed or phase control by synchronisation signals {(H04L7/0075 takes precedence)}
- H04W 56/001: {Synchronization between nodes}
- H04W 56/005: {compensating for timing error by adjustment in the receiver}
- H04J: MULTIPLEX COMMUNICATION (transmission in general H04B; peculiar to transmission of digital information H04L5/00; systems for the simultaneous or sequential transmission of more than one television signal H04N7/08; in exchanges H04Q11/00; stereophonic systems H04S)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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
a
2

(
T
2
,
1
2
-
T
2
,
L
2
)
+
b
1

(
T
2
,
1
-
T
2
,
L
)
subject to the constraint that aT2,n+b1≦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, b1 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=T2,n−T1,n is the transport delay between the master and the slave with T1,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 aT4,n+b≦τn, n∈{1,2, . . . , L} wherein a is the negative of the skew of the slave clock relative to the master clock, T4,n is the time of receipt of the nth timing message from the slave device according to the master clock, b2 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=T4,n−T3,n is the transport delay between the master and the slave with T3,n being the time of sending of the nth timing message from the slave device according to the slave clock.

### Claim 3 (depends on 2)

A slave device according to claim 2 wherein b1=θ+tds+pds and b2=−θ−ξtds−pus wherein θ is the offset of the slave clock compared to the master clock, tds is the transmission delay in the downstream direction, pds is the physical link delay in the downstream direction, pus 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.

### Claim 4 (depends on 1)

A 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 T1,n≧(1+α)T2,n+β1, T4,n≦(1+α)T3,nβ2 and β1−β2≧0 wherein: α is the skew of the slave clock compared to master clock; T1,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; T3,n is the time of sending of the nth timing message from the slave device according to the slave clock; and T4,n is the time of receipt of the nth timing message from the slave device according to the master clock.

### Claim 5 (depends on 4)

A slave device according to claim 4 wherein β1=θ−tds−pds and β2=θ+ξtds+pus wherein θ is the offset of the slave clock compared to the master clock, tds is the transmission delay in the downstream direction, pds is the physical link delay in the downstream direction, pus 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.

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 6)

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.

### Claim 8 (depends on 7)

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.

### Claim 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.

### Claim 10 (depends on 9)

A method according to claim 9 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 aT2,n+b1≦τ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, b1 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=T2,n−T1,n is the transport delay between the master and the slave with T1,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 aT4,n+b≦τn, n∈{1,2, . . . , L} wherein a is the negative of the skew of the slave clock relative to the master clock, T4,n is the time of receipt of the nth timing message from the slave device according to the master clock, b2 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=T4,n−T3,n is the transport delay between the master and the slave with T3,n being the time of sending of the nth timing message from the slave device according to the slave clock.

### Claim 11 (depends on 10)

A method according to claim 10 wherein b1=−θ+tds+pds and b2=−θ−ξtds−pus wherein θ is the offset of the slave clock compared to the master clock, tds is the transmission delay in the downstream direction, pds is the physical link delay in the downstream direction, pus 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.

### Claim 12 (depends on 9)

A method according to claim 9 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 T1,n≧(1+α)T2,n+β1, T4,n≦(1+α)T3,n+β2 and β1−β2≧0 wherein: α is the skew of the slave clock compared to master clock; T1,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; T3,n is the time of sending of the nth timing message from the slave device according to the slave clock; and T4,n is the time of receipt of the nth timing message from the slave device according to the master clock.

### Claim 13 (depends on 12)

A method according to claim 12 wherein β1=θ−tds−pds and β2=θ+ξtds+pus wherein θ is the offset of the slave clock compared to the master clock, tds is the transmission delay in the downstream direction, pds is the physical link delay in the downstream direction, pus 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.

### Claim 14 (depends on 9)

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.

### Claim 15 (depends on 14)

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.

### Claim 16 (depends on 15)

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.

### Claim 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.

### Claim 18 (depends on 17)

A system according to claim 17 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 aT2,n+b1≦τ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, b1 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=T2,n−T1,n is the transport delay between the master and the slave with T1,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 aT4,n+b≦τn, n∈{1,2, . . . , L} wherein a is the negative of the skew of the slave clock relative to the master clock, T4,n is the time of receipt of the nth timing message from the slave device according to the master clock, b2 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=T4,n−T3,n is the transport delay between the master and the slave with T3,n being the time of sending of the nth timing message from the slave device according to the slave clock.

### Claim 19 (depends on 18)

A system according to claim 18 wherein b1=−θ+tds+pds and b2=−θ−ξtds−pus wherein θ is the offset of the slave clock compared to the master clock, tds is the transmission delay in the downstream direction, pds is the physical link delay in the downstream direction, pus 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.

### Claim 20 (depends on 17)

A system according to claim 17 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 T1,n≧(1+α)T2,n+β1, T4,n≦(1+α)T3,n+β2 and β1−β2≧0 wherein: α is the skew of the slave clock compared to master clock; T1,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; T3,n is the time of sending of the nth timing message from the slave device according to the slave clock; and T4,n is the time of receipt of the nth timing message from the slave device according to the master clock.

### Claim 21 (depends on 20)

A system according to claim 20 wherein β1=θ−tds−pds and β2=θ+ξtds+pus wherein θ is the offset of the slave clock compared to the master clock, tds is the transmission delay in the downstream direction, pds is the physical link delay in the downstream direction, pus 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.

### Claim 22 (depends on 17)

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.

### Claim 23 (depends on 22)

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.

### Claim 24 (depends on 23)

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.
