Back to results
US 10,097,339 B1Granted
Time synchronization using timestamp exchanges
AssigneeAmazon Technologies, Inc.
InventorMichael Alan Pogue
Life of this patent
Estimating the term…
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.
Claims20
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.
7 more elements
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.
5 more elements
A device, comprising:
- at least one processor;
- a memory device including instructions operable to be executed by the at least one processor to configure the device to:
- determine 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;
- determine 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;
- determine 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;
- determine 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;
- determine 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
- determine, 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.
7 more elements
Dependencies are inferred from the claim text.