Distributed robust clock synchronization

• US 8,539,108 B2
• Filed: 09/14/2012
• Issued: 09/17/2013
• Est. Priority Date: 12/17/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Liu, Shao, Bar-Zeev, Avi, Kipman, Alex Aben-Athar
• Primary Examiner(s): Tran, Philip B
• Application Number:
  US13/618,852
• Publication Number:
  US 20130013811A1
• Time in Patent Office: 368 Days
• Field of Search: 709/248, 709223-224
• US Class Current: 709/248
• CPC Class Codes: G06F 1/12 Synchronisation of different clock signals provided by a plurality of clock generators
• CPC Class Codes: G06F 1/14 Time supervision arrangements, e.g. real time clock
• CPC Class Codes: H04J 3/0667 Bidirectional timestamps, e.g. NTP or PTP for compensation of clock drift and for compensation of propagation delays arrangements for monitoring round trip delays in packet switching networks H04L43/0864
• CPC Class Codes: H04L 69/02 Protocol performance
• CPC Class Codes: H04L 69/28 Timers or timing mechanisms used in protocols

Abstract

Technology is provided for synchronization of clock information between networked devices. One or more of the devices may include one or more applications needed access to data and a common time reference between devices. In one embodiment, the devices have applications utilizing data shared in a network environment with other devices, as well as having a reference to a local clock signal on each device. A device may have a layer of code between the operating system and software applications that processes the data and maintains a remote clock reference for one or more of the other devices on the network.

Claims

1. A method providing a common time reference for at least a first and a second processing device coupled by a network, comprising:

sending a plurality of time-stamped samples between the first processing device and the second processing device;

calculating a timing reference offset between the devices for each sample;

calculating a predicted drift of the offset after acquiring a defined number of samples; and

responsive to a request for a common time reference at a future time between the first processing device and the second processing device, calculating the offset at the future time from the predicted drift.

2. The method of claim 1 further including the step of filtering the samples to define one or more filtered samples each providing an offset and the defined number of samples includes a defined number of filtered samples.

3. The method of claim 2 wherein the step of calculating comprises performing a regression analysis of the offsets of the filtered samples to determine a predicted drift of the offset.

4. The method of claim 2 wherein said filtering comprises discarding samples over a threshold duration and discarding negative samples.

5. The method of claim 1 further including the steps of grouping the samples, temporally separating groups of samples, determining a group offset value for a group of samples, and wherein the step of calculating performing a regression analysis of a group value.

6. The method of claim 5 further including the step of taking a median sample of each group of samples to define a lead sample.

7. The method of claim 1 further including providing common time reference for at least the first processing device and a third processing device by repeating said sending, calculating, filtering, taking and calculating steps relative to said first processing device and the third processing device.

8. The method of claim 1 wherein each said sample comprises a request from the first processing device to the second processing device, and a reply from the second processing device to the first processing device, including four time stamps used to calculate the timing offset between the devices.

9. A computer readable device including code for instructing a processor to provide a common time reference between a local device and a target device coupled by a network, comprising:

initiating a plurality of groups of samples testing a timing reference offset between a local device and a target device;

calculating the offset for each sample;

for each group, filtering the samples to define one or more group offset values for the group;

when a defined number of samples have been acquired, calculating a predicted drift of the offset; and

responsive to a request for a common time reference at a future time between the local device and the target device, calculating the offset at the future time.

10. The computer readable device of claim 9 wherein each said sample comprises a request from the local device to the target device, and a reply from the target device to the local device, including four time stamps used to calculate the timing offset between the devices.

11. The computer readable device of claim 10 further including establishing common time reference for at least the local device and a third device by repeating said initiating, calculating, filtering, taking and calculating steps relative to said local device and the third device.

12. The computer readable device of claim 9 further including temporally separating each of the plurality of groups of samples, determining a group offset value for a group of samples, and wherein the step of performing a regression analysis includes taking a linear regression of a group value.

13. The computer readable device of claim 9 further including the step of taking a median sample of the group of samples to define a lead sample.

14. A processing device coupled to a network, the processing device including code instructing a processor to provide a common reference between the processing device and another processing device coupled to a network, comprising:

sending a plurality of temporally separated groups of samples to determine a timing reference offset between a local device and a target device;

calculating a timing reference offset for each sample;

for each group, filtering the samples to define one or more group offset values of the group;

when a defined number of samples have been acquired, calculating a predicted drift of the offset; and

responsive to a request for a common time reference at a future time between the local device and the target device, calculating the offset at the future time.

15. The processing device of claim 14 wherein each said sample comprises a request from the local device to the target device, and a reply from the target device to the local device, including four time stamps used to calculate the timing offset between the devices.

16. The processing device of claim 15 further including the step of taking a median sample of the group of samples to define a lead sample.

17. The processing device of claim 14 further including further including temporally separating each of the plurality of groups of samples, determining a group offset value for a group of samples, and wherein the step of performing a regression analysis includes taking a linear regression of a group value.

18. The processing device of claim 17 further including establishing common time reference for at least the local device and a second target device by repeating said determining, calculating, filtering, taking and calculating steps relative to said local device and the second target device.

19. The processing device of claim 18 wherein said filtering comprises discarding samples over a threshold duration and discarding negative samples.

20. The processing device of claim 19 wherein the step of calculating comprises taking a linear regression of the one or more group offset values to determine a predicted drift of the offset.