Clock synchronization

• US 8,249,049 B2
• Filed: 03/17/2009
• Issued: 08/21/2012
• Est. Priority Date: 03/17/2009
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Silverman, Matthew Aaron, Stager, Paul Jeffrey, Hart, Brian Donald
• Primary Examiner(s): Sheikh, Ayaz
• Assistant Examiner(s): Haliyur, Venkatesh
• Application Number:
  US12/405,383
• Publication Number:
  US 20100238917A1
• Time in Patent Office: 1,253 Days
• Field of Search: 370328-516, 709219-224
• US Class Current: 370/350
• CPC Class Codes: G01S 5/02216 Timing or synchronisation of the receivers
• CPC Class Codes: G01S 5/06 Position of source determined by co-ordinating a plurality of position lines defined by path-difference measurements G01S5/12 takes precedence
• 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: H04W 56/0075 based on arrival time vs. expected arrival time

Abstract

In an example embodiment, a method for synchronizing clocks between a plurality of clocked devices where one of the plurality of clocked devices is not directly synchronized with another of the plurality of clocked devices. Clock offset and a clock drift between a first clock associated with a first device and a second clock associated with a second is directly determined based on signals exchanged between the first and second devices. Clock offset and clock drift between the second clock and a third clock associated with a third device is directly determined based on signals exchanged between the second and third devices. A clock offset and clock drift between the first clock and third clock is determined based on a difference between the clock offset and drift between the first and second clocks and the clock offset and drift between the second and third clocks.

Claims

1. An apparatus, comprising:

an interface configured to receive data from a plurality of clocked devices; and

logic in communication with the communication interface and configured to acquire data representative of clock synchronization data between a first clock associated with a first clocked device and a second clock associated with a second clocked device and via the interface;

wherein the clock synchronization data comprises data representative of clock offset and data representative of clock drift corresponding to a rate of change of the clock offset between the first and second clocks;

wherein the logic is configured to synchronize the first clock and second clock at a future time based on the clock synchronization data;

wherein the logic further receives clock synchronization data for a third clock associated with a third clocking device and the second clock via the interface;

wherein the logic is configured to indirectly synchronize the first clock and the third clock at the future time by translating the clock synchronization data between the first and second clocks and the clock synchronization data between the second and third clocks to a common time frame and determining a difference between translated data;

wherein the clock synchronization data between the first clock and second clock comprises data representative of a time a first signal was transmitted by the first clocked device based on the first clock and data representative of a time the first signal was received by the second clocked device based on the second clock;

wherein the clock synchronization data between the first clock and second clock further comprises data representative of a time a second signal was transmitted by the second clocked device based on the second clock and data representative of a time the second signal was received by the first clocked device based on the first clock; and

wherein the logic is operable to determine a clock offset based on a difference between the time the second signal was received by the first clocked device and the time the first signal was received by the second clocked device and a difference between the time the first signal was sent by first device and the time the second signal was sent by the second device.

2. The apparatus set forth in claim 1, wherein the clock synchronization data between the second clock and third clock comprises a clock offset and a clock drift corresponding to a rate of change for the clock offset between the second and third clocks.

3. The apparatus set forth in claim 2, wherein the logic uses a first order approximation to compute the rate of change for the clock offset between the first and second clocks and the rate of change for the clock offset between the first and second clocks.

4. The apparatus set forth in claim 1, wherein the clock synchronization data between the first clock and second clock comprises data representative of a time a third signal was transmitted by the first clocked device based on the first clock and data representative of a time the third signal was received by the second clocked device based on the second clock;

wherein the clock synchronization data between the first clock and second clock further comprises data representative of a time a fourth signal was transmitted by the second clocked device based on the second clock and data representative of a time the fourth signal was received by the first clocked device based on the first clock;

wherein the logic is operable to determine a second clock offset based on a difference between the time the fourth signal was received by the first clocked device and the time the third signal was received by the second clocked device and a difference the time the third signal was sent by first device and the time the fourth signal was sent by the second device; and

wherein the logic is further operable to compute a rate of change for the clock offset based on the clock offset determined from the first and second signals and the clock offset determined from the third and fourth signals.

5. The apparatus set forth in claim 1, wherein the clock synchronization data comprises data representative of a packet exchange between the first device and second device comprising data representative of a time a first packet was sent by the first clocked device according to the first clock and a time the first packet was received by the second clocked device according to the second clock and a time a second packet was sent by the second clocked device according to the second clock and a time the second packet was received by the first clocked device according to the first clock;

wherein the logic is configured to synchronize the first clock and second clock responsive to determining the packet exchange occurred within a predefined time period.

6. An apparatus, comprising:

an interface configured to communicate with a plurality of wireless access points;

logic in communication with the communication interface;

wherein the logic is configured to acquire data representative of clock synchronization data between a first clock associated with a first wireless access point and a second clock associated with a second wireless access point and data representative of clock synchronization data between the second clock and a third clock associated with a third wireless access point via the communication interface;

wherein the logic is configured to acquire data representative of a time a signal is received by the first access point time stamped by the first clock, the time the signal is received by the second access point time stamped by the second clock, and a time the signal is received by the third access point time stamped by the third clock;

wherein the logic is configured to directly synchronize the time the signal was received relative to the second clock with the time the signal was received relative to the third clock based on clock synchronization data between the second and third clocks; and

wherein the logic is configured to indirectly synchronize the time the signal was received relative to the first clock with the time the signal was received relative to the third clock by determining a difference between the clock synchronization data between the first and second clocks and the clock synchronization data between the second and third clocks.

7. The apparatus set forth in claim 6, wherein the logic is operable to determine a position of a transmitter of the signal based on a time difference of arrival of the time the signal was received relative to the first clock translated to the third clock, the time the signal was received by the second clock translated to the third clock and the time the signal was received relative to the third clock.

8. The apparatus set forth in claim 7, wherein the clock synchronization data between the first clock and second clock comprises a clock offset and a rate of change for the clock offset between the first and second clocks.

9. The apparatus set forth in claim 8, wherein the clock synchronization data between the second clock and third clock comprises a clock offset and a rate of change for the clock offset between the first and second clocks.

10. The apparatus set forth in claim 9, wherein the logic uses a first order approximation to compute the rate of change for the clock offset between the first and second clocks and the rate of change for the clock offset between the first and second clocks.

11. The apparatus set forth in claim 7, wherein the clock synchronization data between the first clock and second clock comprises data representative of a time a first signal was transmitted by the first clocked device based on the first clock and data representative of a time the first signal was received by the second clocked device based on the second clock;

wherein the clock synchronization data between the first clock and second clock further comprises data representative of a time a second signal was transmitted by the second clocked device based on the second clock and data representative of a time the second signal was received by the first clocked device based on the first clock; and

wherein the logic is operable to determine a clock offset based on a difference between the time the second signal was received by the first clocked device and the time the first signal was received by the second clocked device and a difference the time the first signal was sent by first device and the time the second signal was sent by the second device.

12. The apparatus set forth in claim 11, wherein the clock synchronization data between the first clock and second clock comprises data representative of a time a third signal was transmitted by the first clocked device based on the first clock and data representative of a time the third signal was received by the second clocked device based on the second clock;

wherein the clock synchronization data between the first clock and second clock further comprises data representative of a time a fourth signal was transmitted by the second clocked device based on the second clock and data representative of a time the fourth signal was received by the first clocked device based on the first clock;

wherein the logic is operable to determine a second clock offset based on a difference between the time the fourth signal was received by the first clocked device and the time the third signal was received by the second clocked device and a difference the time the third signal was sent by first device and the time the fourth signal was sent by the second device; and

wherein the logic is further operable to compute a rate of change for the clock offset based on the clock offset determined from the first and second signals and the clock offset determined from the third and fourth signals.

13. The apparatus set forth in claim 6, wherein the clock synchronization data comprises data representative of a packet exchange between the first device and second device comprising data representative of a time a first packet was sent by the first wireless access point according to the first clock and a time the first packet was received by the second wireless access point according to the second clock and a time a second packet was sent by the second wireless access point according to the second clock and a time the second packet was received by the first wireless access point according to the first clock;

wherein the logic is configured to discard the clock synchronization data responsive to determining the packet exchange occurred in a time period longer than a predefined time period.

14. The apparatus set forth in claim 6, wherein the plurality of wireless access points further comprises a fourth wireless access point and a fifth wireless access point;

wherein the logic is configured to acquire data representative of clock synchronization data between the third clock associated with the third wireless access point and a fourth clock associated with a fourth second wireless access point and data representative of clock synchronization data between the third clock and a fifth clock associated with a fifth wireless access point via the communication interface;

wherein the logic is configured to acquire data representative of a time a second signal is received by the third access point time stamped by the third clock, the time the second signal is received by the fourth access point time stamped by the fourth clock, and a time the second signal is received by the fifth access point time stamped by the fifth clock;

wherein the logic is configured to directly synchronize the time the second signal was received relative to the fourth clock with the time the signal was received relative to the fifth clock based on clock synchronization data between the fourth and fifth clocks; and

wherein the logic is configured to indirectly synchronize the time the second signal was received relative to the third clock with the time the signal was received relative to the fifth clock by determining a difference between the clock synchronization data between the third and fourth clocks and the clock synchronization data between the fourth and fifth clocks.

15. A method, comprising:

determining a clock offset and a clock drift between a first clock and a second clock;

determining a clock offset and a clock drift between the second clock and a third clock;

determining a clock offset and clock drift between the first clock and third clock based on a difference between the clock offset and clock drift between the first and second clocks and the clock offset and clock drift between the second and third clocks;

synchronizing the second clock with the first clock by translating the second clock to the first clock based on the clock drift and clock offset determined between the first clock and the second clock;

synchronizing the third clock with the first clock by translating the third clock to the first clock based on the clock drift and clock offset determined between the first clock and the third clock;

obtaining data representative of a time a signal was received by a first device associated with the first clock relative to the first clock;

obtaining data representative of a time a signal was received by a second device associated with the second clock relative to the second clock;

obtaining data representative of a time a signal was received by a third device associated with the third clock relative to the third clock;

translating the time the signal was received relative to the second clock to a time relative to the third clock based on the clock offset and drift between the second clock and the third clock; and

translating the time the signal was received relative to the first clock to a time relative to the third clock based on the difference between clock offset and drift between the first and second clocks and clock offset and drift between the second and third clocks.

16. The method according to claim 15, further comprising:

acquiring data representative of a time a first signal is sent from a first device associated with the first clock to a second device associated with the second clock relative to the first clock;

acquiring data representative of a time the first signal is received by the second device relative to the second clock;

acquiring data representative of a time a second signal is sent from the second device to the first device relative to the second clock;

acquiring data representative of a time the second signal is received by the first device relative to the first clock; and

determining a clock offset based on the difference between the time the first signal was sent by the first device relative to the first clock and the time the second signal was sent by the second device relative to the second clock and the difference between the time the second signal was received by the first device relative to the first clock and the time the first signal was received by the second device relative to the second clock.

17. The method according to claim 16, further comprising:

acquiring data representative of a time a third signal is sent from a first device associated with the first clock to a second device associated with the second clock relative to the first clock;

acquiring data representative of a time the third signal is received by the second device relative to the second clock;

acquiring data representative of a time a fourth signal is sent from the second device to the first device relative to the second clock;

acquiring data representative of a time the fourth signal is received by the first device relative to the first clock;

determining a second clock offset based on the difference between the time the third signal was sent by the first device relative to the first clock and the time the fourth signal was sent by the second device relative to the second clock and the difference between the time the fourth signal was received by the first device relative is to the first clock and the time the third signal was received by the second device relative to the second clock; and

determining a clock drift based on the difference between the first clock offset and the second clock offset.

18. Logic encoded in a non-transitory tangible computer readable media for execution and said logic when executed by a processor operable to:

determining a clock offset and a clock drift between a first clock associated with a first device and a second clock associated with a second device;

determining a clock offset and a clock drift between the second clock and a third clock associated with a third device;

determining a clock offset and clock drift between the first clock and third clock based on a difference between the clock offset and clock drift between the first and second clocks and the clock offset and clock drift between the second and third clocks;

acquiring data representative of a time a signal was received by the first device according to the first clock;

acquiring data representative of a time the signal was received by the second device according to the second clock;

acquiring data representative of a time a signal was received by the third device according to the third clock;

synchronizing the time the signal was received by the second device with the first device by translating the time the signal was received according to the second clock to the first clock based on the clock drift and clock offset determined between the first clock and the second clock; and

synchronizing the time the signal was received by the third device with the first device by translating the time the signal was received according to the third clock to the first clock based on the clock drift and clock offset determined between the first clock and the third clock.