Clock Synchronization Using Correlation Events

• US 20090319819A1
• Filed: 06/19/2008
• Published: 12/24/2009
• Est. Priority Date: 06/19/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Haba, Erez
• Granted Patent: US 8,630,316 B2
• Time in Patent Office: Days
• US Class Current: 713/503
• CPC Class Codes: G06F 1/12 Synchronisation of different clock signals provided by a plurality of clock generators
• CPC Class Codes: H04J 3/0661 using timestamps
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 43/106 using time related information in packets, e.g. by adding timestamps
• CPC Class Codes: H04N 21/242 Synchronization processes, e.g. processing of PCR [Program Clock References] arrangements for synchronising broadcast or distribution via plural systems in broadcast distribution systems H04H20/18

Abstract

Two clocks may be synchronized by calculating skew and offset values that may be determined from several correlation events. A correlation event may be the passing of messages in both directions between the two devices. The skew and offset values may be used to determine the time of non-correlated events. The clock synchronization may be performed on a real time basis or may be performed on a post processing basis. One method for calculating the skew and offset may use inequalities within a solution space to refine a solution set with multiple sets of correlation events.

Claims

1. A method comprising:

identifying a plurality of correlation events having an initiating timestamp and a receiving timestamp, said correlation events occurring between a first device having a first clock and a second device having a second clock, said plurality of correlation events comprising a first correlation event having said initiating timestamp correlated to said first clock and a second correlation event having said initiating timestamp correlated to said second clock;

calculating a set of linear correlation constants using at least a subset of said plurality of correlation events comprising said first correlation event and said second correlation event, said set of linear correlation constants defining a linear relationship between said first clock and said second clock;

identifying a first event not being one of said correlation events, said first event having a third timestamp being defined by said second clock; and

determining a fourth timestamp from said third timestamp by using said set of linear correlation constants, said fourth timestamp being with respect to said first clock.

2. The method of claim 1, said set of linear correlation constants comprising a skew constant and an offset constant.

3. The method of claim 1, at least one of said initiating timestamp and said receiving timestamp being determined by a transport layer service.

4. The method of claim 1, at least one of said initiating timestamp and said receiving timestamp being determined by an application layer service.

5. The method of claim 4, at least one of said initiating timestamp and said receiving timestamp being determined by a transport layer service.

6. The method of claim 1, at least one of said initiating timestamp and said receiving timestamp being determined by a message passing interface.

7. The method of claim 1, said calculating being done in a real time mode.

8. The method of claim 1, said calculating being done by post processing.

9. The method of claim 8, said post processing comprising analyzing a log file.

10. The method of claim 8, said post processing comprising comparing a first log file from said first device and a second log file from said second device to identify at least one of said plurality of correlation events.

11. The method of claim 1, said calculating being performed at least in part by a calculation method comprising:

for each of said correlation events, determining an inequality representing said correlation event and mapping said inequality to a solution space to form a bounded area within said solution space.

12. The method of claim 11, said calculating further comprising:

determining a point within said bounded area to represent said set of linear correlation constants.

13. The method of claim 12, said point being determined based on a centroid of said bounded area.

14. The method of claim 12 further comprising:

determining an accuracy factor based on an area calculation of said bounded area.

15. A system comprising:

a first clock;

a first communication mechanism configured to send and receive messages and include a timestamp on each of said messages using said first clock;

a clock synchronization mechanism configured to synchronize a second clock from a second device with said first clock by a method comprising;

identifying a plurality of said messages transmitted to said second device and received from said second device, said plurality of messages having a timestamp from a second clock on said second device; and

calculating a set of linear correlation constants using at least a subset of said plurality of said messages, said set of linear correlation constants defining a linear relationship between said first clock and said second clock.

16. The system of claim 15, said clock synchronization mechanism further configured to calculate said set of linear correlation constants in real time.

17. The system of claim 15, said clock synchronization mechanism further configured to perform said calculating by a calculation method comprising:

for each of said plurality of messages, determining an inequality representing said correlation event and mapping said inequality to a solution space to form a bounded area within said solution space.

18. The system of claim 17, said clock synchronization mechanism further configured to:

determine a point within said bounded area to represent said set of linear correlation constants.

19. A computer readable medium comprising computer executable instructions configured to perform a method comprising:

reading a log file to identify a plurality of correlation events having an initiating timestamp and a receiving timestamp, said correlation events occurring between a first device having a first clock and a second device having a second clock, said plurality of correlation events comprising a first correlation event having said initiating timestamp created by said first device and a second correlation event having said initiating timestamp created by a second device;

calculating a set of linear correlation constants using at least a subset of said plurality of correlation events comprising said first correlation event and said second correlation event, said set of linear correlation constants defining a linear relationship between said first clock and said second clock, said calculating being performed by a method comprising;

for each of said correlation events, determining an inequality representing said correlation event and mapping said inequality to a solution space to form a bounded area within said solution space; and

determining a point within said bounded area to represent said set of linear correlation constants.

20. The computer readable medium of claim 19, said point being determined based on a centroid for said bounded area.