Method and devices for synchronization using linear programming

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 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 seeks to minimize the expression θf−θr in which θf is the offset of the slave clock compared to the master clock, derived from timing messages sent from the master to the slave and θr is the offset derived from timing messages sent from the slave to the master, subject to the constraints that T1,n≧(1+α)T2,n+θf, T4,n≦(1+α)T3,n+θr and θf−θr≧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;
• 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.

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
• the slave device is arranged to:
• exchange with the master device, timing messages and to 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 seeks to minimize the expression θf−θr in which θf is the offset of the slave clock compared to the master clock, derived from timing messages sent from the master to the slave and θr is the offset derived from timing messages sent from the slave to the master, subject to the constraints that T1,n≧(1+α)T2,n+θf, T4,n≦(1+α)T3,n+θr and θf−θr≧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;
• 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.