US5550873A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Processing system for use as a network node for performing anonymous time synchronization in a network
Assignee: International Business Machines Corp
•
Filing: 1995-02-01
•
Granted: 1996-08-27
•
Expires: 2015-02-01
Abstract
Abstract A network node, such as a computer or processing system, is provided, for use within a network, the node including program code for synchronizing a local time maintained at the node with a reference time. Bursts of synchronization messages containing reference time stamps are transmitted over the network, or over a communication link, according to a predetermined protocol. The node receives and time stamps the messages. Thus, times according to a first time scale and a second time scale are obtained. The protocol defines temporal relationships between certain ones of the times. In accordance with the 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. This synchronization method provides a well-defined upper bound of synchronization error, and allows the node to synchronize its internal time based only on information contained in the received messages and the internally generated local time stamp marks. 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 identity of the node which is synchronizing itself. 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
- 👤 R udiger K. Reischuk
- 👤 Hovey R. Strong
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 21:46
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
240 words
A network node comprising: means for maintaining an internal time scale; means for receiving synchronization messages containing reference time stamps which denote times of respective events according to a reference time scale, the synchronization messages having been sent according to a predetermined protocol; means for marking received synchronization messages with local time stamp marks which denote respective events of receipt of the synchronization messages according to the internal time scale, in accordance with the predetermined protocol, thereby defining temporal relationships between certain ones of the reference time stamps and certain ones of the local time stamp marks; means for identifying a first time according to a first scale and second and third times according to a second time scale, the first time scale being one of the internal time scale and the reference time scale, the second time scale being the other of the internal time scale and the reference time scale, 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; means for determining a difference between the first time and a time related to the second and third times; and means for updating the internal 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
240 words
A network node comprising: means for maintaining an internal time scale; means for receiving synchronization messages containing reference time stamps which denote times of respective events according to a reference time scale, the synchronization messages having been sent according to a predetermined protocol; means for marking received synchronization messages with local time stamp marks which denote respective events of receipt of the synchronization messages according to the internal time scale, in accordance with the predetermined protocol, thereby defining temporal relationships between certain ones of the reference time stamps and certain ones of the local time stamp marks; means for identifying a first time according to a first scale and second and third times according to a second time scale, the first time scale being one of the internal time scale and the reference time scale, the second time scale being the other of the internal time scale and the reference time scale, 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; means for determining a difference between the first time and a time related to the second and third times; and means for updating the internal 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
32 words
A network node as recited in claim 1 wherein the means for determining a difference includes means for selecting the related time as a time halfway between the second and third times.
Claim 4
Dependent Claim
124 words
A network node as recited in claim 1, wherein: k is an upper limit of the number of the synchronization messages which can, at any given time, be in transit through the network; and the means for identifying includes: means for selecting a local time stamp mark associated with a first one of the messages as the first time; means for identifying a reference time stamp contained within one of (i) the message associated with the selected local time stamp mark and (ii) a message received prior thereto as the second time; and means for identifying a reference time stamp contained within a message received at least (k+1) messages subsequent to the message associated with the selected local time stamp as the third time.
Claim 5
Dependent Claim
127 words
A network node as recited in claim 1, wherein: k is an upper limit of the number of the synchronization messages which can, at any given time, be in transit through the network; and the means for identifying includes: means for selecting one of the synchronization messages, which contains a first reference time stamp, wherein the first reference time stamp is to be the first time; means for selecting a local time stamp mark associated with a synchronization message received at least (k+1) synchronization messages prior to the selected synchronization message as being the second time; and means for selecting a local time stamp mark associated with one of (i) the selected synchronization message and (ii) a synchronization message received subsequent thereto as being the third time.
Claim 6
Dependent Claim
104 words
A network node as recited in claim 1, wherein: each synchronization message must be acknowledged before a subsequent synchronization message may be placed in transit; and the means for identifying includes: means for selecting a local time stamp mark associated with a first one of the synchronization messages as the first time; means for identifying a reference time stamp contained within a synchronization message received at least two synchronization messages prior to the first synchronization message as the second time; and means for identifying a reference time stamp contained within a synchronization message received subsequent to the first synchronization message as the third time.
Claim 7
Dependent Claim
119 words
A network node as recited in claim 1, wherein: each synchronization message must be acknowledged before a subsequent synchronization message may be placed in transit; and the means for identifying includes: means for selecting a first reference time stamp contained within a first one of the synchronization messages as being the first time; means for identifying a local time stamp mark associated with a synchronization message received before the synchronization message associated with the selected local time stamp mark as the second time; and means for identifying a local time stamp mark associated with a synchronization message received at least two synchronization messages subsequent to the synchronization message associated with the selected local time stamp as the third time.
Claim 8
Dependent Claim
35 words
A network node as recited in claim 1 further comprising means for maintaining global precision information representing an upper bound of inaccuracy of synchronization between the node's internal time scale and the reference time scale.
Claim 9
Dependent Claim
63 words
A network node as recited in claim 7 wherein the means for maintaining includes: means for resetting the global precision information to an initial value responsive to updating of the internal time scale by the means for updating; means for changing the global precision information at a rate corresponding with a worst case clock drift of the internal time scale of the node.
Claim 10
Dependent Claim
23 words
A network node as recited in claim 7 further comprising means for requesting synchronization if the global precision information exceeds a first threshold.
Claim 11
Dependent Claim
28 words
A network node as recited in claim 9 further comprising means for requesting synchronization over a plurality of networks if the global precision information exceeds a second threshold.
Claim 12
Dependent Claim
35 words
A network node as recited in claim 10 further comprising means for sending synchronization messages if no messages are received during a first selected time interval after the global precision information exceeds a third threshold.
Claim 13
Dependent Claim
32 words
A network node as recited in claim 11 further comprising means for sending synchronization messages if, after reception of a synchronization request, no message is received during a second selected time interval.
Claim 14
Dependent Claim
84 words
A network node as recited in claim 7 further comprising: means for maintaining a record of a rank of a reference time source from which the node previously received a synchronization message based on which the node synchronized its time; and means for synchronizing responsive to receipt of a synchronization message containing rank information indicating that the reference time source of the received synchronization message has a rank greater than the rank of the source maintained in the record by the means for maintaining.
Claim 15
Dependent Claim
84 words
A network node as recited in claim 7 further comprising: means for maintaining a record of a global precision of a source from which the node previously received a synchronization message based on which the node synchronized its time; and means for synchronizing responsive to receipt of a synchronization message containing global precision information indicating that the source of the received synchronization message has a global precision greater than the global precision of the source maintained in the record by the means for maintaining.
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) | 1999-08-27 | 2000-02-26 | 2000-08-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-08-27 | 2004-02-26 | 2004-08-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-08-27 | 2008-02-26 | 2008-08-27 | $7700.00 | Window Closed / Lapsed |