Time synchronization using timestamp exchanges

Patent metadata

Field	Value
Publication number	US-10097339-B1
Application number	US-201615388258-A
Country	US
Kind code	B1
Filing date	Dec 22, 2016
Priority date	Dec 22, 2016
Publication date	Oct 9, 2018
Grant date	Oct 9, 2018

Abstract

A system capable of synchronizing clocks on separate devices despite variable delays between the separate devices. The system may compensate for skew (e.g., difference between clocks) and drift (e.g., frequency offset between clocks). The system may determine the skew and drift based on differences between timestamps when packets are sent from a first device to a second device and vice versa. For example, the system may estimate a first line corresponding to the fastest packets from the first device to the second device and may estimate a second line corresponding to the fastest packets from the second device to the first device. The system may determine the skew based on a midpoint between the first line and the second line, and the drift based on a slope of the first line or the second line.

First claim

What is claimed is:

1. A computer-implemented method for determining a time offset and a frequency offset between a first clock of a first device and a second clock of a second device, the method comprising, by the first device:
determining a first difference between a first timestamp generated using the first clock of the first device and a second timestamp generated using the second clock of the second device, the first timestamp corresponding to a first packet being sent by the first device and the second timestamp corresponding to the first packet being received by the second device;
determining a second difference between a third timestamp generated by the second clock and a fourth timestamp generated by the first clock, the third timestamp corresponding to a second packet being sent by the second device and the fourth timestamp corresponding to the second packet being received by the first device;
determining first data points including a first data point corresponding to the first difference at a first time, the first data points corresponding to transit times that are below a first time threshold;
determining second data points including a second data point corresponding to the second difference at a second time and a third data point corresponding to a third difference at a third time, the second data points corresponding to transit times that are below the first time threshold;
determining a first vector between the first data point and the second data point, a first component of the first vector corresponding to a first time difference between the first time and the second time and a second component of the first vector corresponding to a second time difference between the first difference and the second difference;
determining a second vector between the second data point and the third data point, a first component of the second vector corresponding to a third time difference between the second time and the third time and a second component of the second vector corresponding to a fourth time difference between the second difference and the third difference;
determining a fourth data point that corresponds to a midpoint of the first vector, wherein the time offset is equal to a value of the first component of the fourth data point at a fourth time and the fourth time is equal to a value of the second component of the fourth data point; and
determining a value of a slope of the second vector, wherein
the frequency offset is equal to the value of the slope at the fourth time.

2. The computer-implemented method of claim 1 , further comprising:
determining that a fixed duration of time has not elapsed since a wireless communication session between the first device and the second device was initiated;
determining that an absolute value of the slope exceeds a second threshold corresponding to a maximum frequency offset;
setting the frequency offset equal to a value of zero;
receiving an instruction to output audio data at a first clock value associated with the second clock;
determining, using the first clock value and the time offset, a second clock value associated with the first clock; and
outputting audio, using the audio data, at the second clock value.

3. The computer-implemented method of claim 1 , further comprising:
determining that a fixed duration of time has not elapsed since a first wireless communication session between the first device and the second device was initiated;
determining a previous frequency offset between the first clock and the second clock, the previous frequency offset corresponding to a second wireless communication session between the first device and the second device prior to the first wireless communication session; and
determining a second time offset based on the time offset and the previous frequency offset;
receiving an instruction to output audio data at a first clock value associated with the second clock;
determining, using the first clock value and the second time offset, a second clock value associated with the first clock; and
outputting audio using the audio data at the second clock value.

4. The computer-implemented method of claim 1 , further comprising:
determining that an absolute value of the slope is greater than a second time threshold corresponding to a maximum frequency offset;
discarding the first and the second plurality of data points;
determining third data points corresponding to transit times that are below the first time threshold;
determining fourth data points corresponding to transit times that are below the first time threshold; and
determining a second frequency offset between the first clock and the second clock using the third data points and the fourth data points.

5. A computer-implemented method, comprising:
determining a first data point having a first component corresponding to a first time and a second component equal to a first difference between a first timestamp associated with a first clock of a first device and a second timestamp associated with a second clock of a second device, the first timestamp corresponding to a first packet being sent by the first device and the second timestamp corresponding to the first packet being received by the second device;
determining a second data point having a first component corresponding to a second time and a second component equal to a second difference between a third timestamp associated with the second clock and a fourth timestamp associated with the first clock, the third timestamp corresponding to a second packet being sent by the second device and the fourth timestamp corresponding to the second packet being received by the first device;
determining that the first difference corresponds to a first transit time from the first device to the second device that is below a first time threshold;
determining that the second difference corresponds to a second transit time from the second device to the first device that is below the first time threshold;
determining a first vector between the first data point and the second data point, a first component of the first vector corresponding to a first time difference between the first time and the second time and a second component of the first vector corresponding to a second time difference between the first difference and the second difference; determining a midpoint of the first vector, a first component of the midpoint corresponding to a third time and a second component of the midpoint corresponding to an average of the first difference and the second difference, wherein a first time offset is equal to the second component of the midpoint; and
determining, based on the first time offset, a first clock value associated with the first clock that corresponds to a second clock value associated with the second clock, the second clock value corresponding to a fourth time after the third time.

6. The computer-implemented method of claim 5 , further comprising:
determining first data points corresponding to packets sent from the first device to the second device, the first data points including the first data point;
determining a first convex hull enclosing the first data points;
determining that the first data point is along the first convex hull;
determining second data points corresponding to packets sent from the second device to the first device, the second data points including the second data point;
determining a second convex hull enclosing the second data points;
determining that the second data point is along the second convex hull;
receiving an instruction to output audio data at the second clock value associated with the second clock; and
outputting, using the audio data, audio at the first clock value.

7. The computer-implemented method of claim 6 ,

Assignees

• Amazon Tech Inc

Inventors

• Pogue Michael Alan

Classifications

• H04W56/001 Primary

  Synchronization between nodes · CPC title

• H04J3/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 title

• H04L7/0037

  Delay of clock signal · CPC title

• H04L7/0054 Primary

  Detection of the synchronisation error by features other than the received signal transition (by means of signal transition H04L7/033) · CPC title