US5428645A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Anonymous time synchronization method
Assignee: International Business Machines Corp
•
Filing: 1992-11-03
•
Granted: 1995-06-27
•
Expires: 2012-11-03
Abstract
Abstract A method is provided for synchronizing a local time maintained at a node within a network architecture with a reference time. Bursts of synchronization messages containing reference time stamps are transmitted over a network or communication link according to a predetermined protocol. A node to be synchronized receives and time stamps the messages. Thus, times according to a first time scale and a second time scale are obtained, and the protocol defines temporal relationships between certain ones of the times. In accordance with the predetermined protocol, the node determines a difference between a first time according to one of the time scales and a time related to second and third times according to the other time scale. The node then updates its local time based on the difference between the first time and the related time. This synchronization method provides a well-defined upper bound of synchronization error, and allows the nodes receiving the messages to synchronize their internal times based only on information contained in the received messages and their internally, generated local time stamp marks. Therefore, no "round trip" or handshaking messages are necessary to define the needed temporal relationships between the times according to the first and second scales. Thus, it is not necessary that the reference time source know the identities of the nodes which synchronize themselves based on the messages. The node also maintains a global precision value, which estimates its time synchronization error, by resetting the value when the node is synchronized, and updating the value as the node operates. Responsive to the global precision exceeding various thresholds, the node requests resynchronization or sends synchronization messages based on its internal time.
Inventors
- 👤 Danny Dolev
- 👤 Rudiger K. Reischuk
- 👤 Hovey R. Strong
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 04:48
CPC Classifications
G; G06; G06F; G06F1/00; G06F1/04; G06F1/14; H; H04; H04J; H04J3/00; H04J3/02; H04J3/06; H04J3/0635; H04J3/0638; H04J3/0658; H04J3/0661; H04J3/0664
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
281 words
For use with a communication network including a node which maintains a local time scale and a reference time source which maintains a reference time scale, a method for synchronizing the local time scale with the reference time scale comprising the steps of: receiving synchronization messages broadcast from the reference time source according to a predetermined protocol, at least two of the synchronization messages containing a reference time stamp denoting a time of a respective event according to the reference time scale; associating local time stamp marks with the received synchronization messages, the local time stamp marks denoting respective events of reception of the synchronization messages according to the local time scale, the step of associating being performed in accordance with the predetermined protocol, thereby defining temporal relationships between certain ones of the reference time stamps of the synchronization messages and certain ones of the local time stamp marks; identifying a first time, which is one of a local time stamp mark and a reference time stamp from one of the synchronization messages, and second and third times, which are the other of local time stamp marks and reference time stamps from two of the synchronization messages, the first, second, and third times being identified in accordance with the defined temporal relationships between the events denoted by the times, such that the event denoted by the first time falls between the events denoted by the second and third times; determining a difference between the first time and a time related to the second and third times; and updating the local time scale to compensate for the difference between the first time and the time related to the second and third times.
Claim 2
Dependent Claim
281 words
For use with a communication network including a node which maintains a local time scale and a reference time source which maintains a reference time scale, a method for synchronizing the local time scale with the reference time scale comprising the steps of: receiving synchronization messages broadcast from the reference time source according to a predetermined protocol, at least two of the synchronization messages containing a reference time stamp denoting a time of a respective event according to the reference time scale; associating local time stamp marks with the received synchronization messages, the local time stamp marks denoting respective events of reception of the synchronization messages according to the local time scale, the step of associating being performed in accordance with the predetermined protocol, thereby defining temporal relationships between certain ones of the reference time stamps of the synchronization messages and certain ones of the local time stamp marks; identifying a first time, which is one of a local time stamp mark and a reference time stamp from one of the synchronization messages, and second and third times, which are the other of local time stamp marks and reference time stamps from two of the synchronization messages, the first, second, and third times being identified in accordance with the defined temporal relationships between the events denoted by the times, such that the event denoted by the first time falls between the events denoted by the second and third times; determining a difference between the first time and a time related to the second and third times; and updating the local time scale to compensate for the difference between the first time and the time related to the second and third times.
Claim 3
Dependent Claim
28 words
A method as recited in claim 1 wherein, in the step of determining a difference, the related time is a time halfway between the second and third times.
Claim 4
Dependent Claim
118 words
A method as recited in claim 1, wherein: according to the predetermined protocol, there is a limit of k synchronization messages which can, at any given time, be in transit through the network; and the step of identifying includes: (a) extracting a reference time stamp from one of the synchronization messages as the first time, (b) identifying a local time stamp mark associated with a synchronization message received subsequent to receipt of the synchronization message containing the extracted reference time stamp as being the third time, and (c) identifying a local time stamp mark associated with a synchronization message received at least k+1 messages prior to receipt of the subsequently received synchronization message as being the second time.
Claim 5
Dependent Claim
123 words
A method as recited in claim 1, wherein: according to the predetermined protocol, there is a limit of k synchronization messages which can, at any given time, be in transit through the network; and the step of identifying includes: (a) selecting a local time stamp mark associated with one of the synchronization messages as the first time; (b) identifying a reference time stamp contained within a synchronization message received prior to the synchronization message associated with the selected local time stamp mark as being the second time, and (c) identifying a reference time stamp contained within a synchronization message received at least k+1 synchronization messages subsequent to the synchronization message associated with the selected local time stamp mark as being the third time.
Claim 6
Dependent Claim
148 words
A method as recited in claim 1, wherein: according to the predetermined protocol, each synchronization message sent by the reference time source must be acknowledged with an acknowledgement message sent by a designated acknowledger before a subsequent synchronization message may be placed in transit; and the step of identifying includes: (a) extracting a reference time stamp from one of the synchronization messages as the first time, (b) identifying a local time stamp mark associated with a synchronization message received at least two synchronization messages prior to the synchronization message containing the extracted reference time stamp as being the second time, and (c) identifying a local time stamp mark associated with one of (i) a synchronization message which contains the extracted reference time stamp and (ii) a synchronization message received subsequently to receipt of the synchronization message which contains the extracted reference time stamp as being the third time.
Claim 7
Dependent Claim
151 words
A method as recited in claim 1, wherein: according to the predetermined protocol, each synchronization message sent by the reference time source must be acknowledged with an acknowledgement message sent by a designated acknowledger before a subsequent synchronization message may be placed in transit; and the step of identifying includes: (a) selecting a local time stamp mark associated with one of the synchronization messages as the first time; (b) identifying a reference time stamp contained within one of (i) the synchronization message associated with the selected local time stamp mark and (ii) a synchronization message received prior to receipt of the synchronization message which contains the extracted reference time stamp as being the second time, and (c) identifying a reference time stamp contained within a synchronization message received at least two synchronization messages subsequent to the synchronization message associated with the selected local time stamp mark as being the third time.
Claim 8
Dependent Claim
34 words
A method as recited in claim 1, further comprising the step of: maintaining global precision information representing an upper bound of precision of synchronization between the local time scale and the reference time scale.
Claim 9
Dependent Claim
51 words
A method as recited in claim 7 wherein the step of maintaining includes: resetting the global precision information to an initial value responsive to the step of updating; and changing the global precision information at a rate corresponding with a worst case clock drift of a clock employed by the node.
Claim 10
Dependent Claim
25 words
A method as recited in claim 7, further comprising the step of sending a synchronization request if the global precision information exceeds a first threshold.
Claim 11
Dependent Claim
45 words
A method as recited in claim 9, wherein: the node is coupled to a plurality of networks; and the method further comprises the step of sending a synchronization request over each of the plurality of networks if the global precision information exceeds a second threshold.
Claim 12
Dependent Claim
42 words
A method as recited in claim 10, further comprising the steps of: waiting a second predetermined time interval responsive to the global precision information exceeding a third threshold; and sending synchronization messages if no synchronization messages are received during the second interval.
Claim 13
Dependent Claim
40 words
A method as recited in claim 7, further comprising the steps of: waiting, responsive to receipt of a synchronization request, for a predetermined time interval; and if no synchronization messages was received during the predetermined time interval, sending synchronization messages.
Claim 14
Dependent Claim
78 words
A method as recited in claim 7, wherein: each synchronization message contains a rank associated with a reference time source; and the method further comprises the steps of: maintaining a record of the rank contained within the last synchronization message which was successfully used for performing the step of updating; and performing the step of updating in response to receipt of a synchronization message containing a rank which is at least equal to that in the record maintained.
Claim 15
Dependent Claim
90 words
A method as recited in claim 7, wherein: each message contains information relating to an upper bound of accuracy associated with a device which sent the message; and the method further comprises the steps of: maintaining a record of the upper bound of accuracy contained within the last synchronization message which was successfully used for performing the step of updating; and performing the step of updating in response to receipt of a message containing an upper bound of accuracy which is at least equal to that in the record maintained.
References Cited (Backward Citations)
US2986723A
Cited
US3940558A
Cited
US4142069A
Cited
US4305045A
Cited
US4677614A
Cited
US4709347A
Cited
US4736393A
Cited
JPS6384228A
Cited
US4918652A
Cited
US4860285A
Cited
US4988989A
Cited
US4893318A
Cited
JPH02118868A
Cited
US5001730A
Cited
US4982185A
Cited
US4939752A
Cited
US5052029A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-06-26 | 1998-12-26 | 1999-06-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-06-26 | 2002-12-26 | 2003-06-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-06-26 | 2006-12-26 | 2007-06-27 | $7700.00 | Window Closed / Lapsed |