US5689688A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Probabilistic anonymous clock synchronization method and apparatus for synchronizing a local time scale with a reference time scale
Assignee: International Business Machines Corp
•
Filing: 1993-11-16
•
Granted: 1997-11-18
•
Expires: 2013-11-16
Abstract
Abstract A method is provided for synchronizing local times, maintained at nodes within a network architecture, with a reference time. A node according to the invention can synchronize its local time with the reference time source either actively or in a passive, or eavesdropping, manner. Which of the two manners is to be used preferably depends on whether the node's error exceeds a threshold, and whether the node receives an unsolicited burst of synchronization messages. The active manner is preferably a handshaking scheme, such as probabilistic clock synchronization, in which synchronization is initiated by a request from a node requiring synchronization, and a handshaking exchange of messages between the node and the reference time source establishes a temporal relationship, from which the node produces a synchronized time and a maximum error. The passive manner is preferably a manner in which the reference time source broadcasts a burst of reference-time-stamped synchronization messages, and the node eavesdrops on the messages. The receiving node establishes temporal relationships between certain ones of the local and reference time stamps. Using the temporal relationships, the receiving node updates its local time and its maximum error.
Inventors
- 👤 Hovey Raymond Strong
- 👤 Edward Leo Wimmers
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 12:32
CPC Classifications
H; H04; H04J; H04J3/00; H04J3/02; H04J3/06; H04J3/0635; H04J3/0638; H04J3/0658; H04J3/0661; H04J3/0667; G; G06; G06F; G06F1/00; G06F1/04; G06F1/14; H04L; H04L9/00; H04L9/40; H04L69/00; H04L69/28
Claims Analysis
Total Claims: 40
Claim 1
Independent Claim
113 words
For use with a communication network including a plurality of nodes which maintain respective local time scales and a reference time source which maintains a reference time scale, a method for synchronizing a local time scale of one of the nodes with the reference time scale comprising the steps of: synchronizing based on a first procedure responsive to a first event, the first procedure including synchronizing according to a protocol in which the node is known to the reference time source; and synchronizing based on a second procedure responsive to a second event the second procedure including synchronizing according to a protocol in which the node is anonymous to the reference time source.
Claim 2
Dependent Claim
113 words
For use with a communication network including a plurality of nodes which maintain respective local time scales and a reference time source which maintains a reference time scale, a method for synchronizing a local time scale of one of the nodes with the reference time scale comprising the steps of: synchronizing based on a first procedure responsive to a first event, the first procedure including synchronizing according to a protocol in which the node is known to the reference time source; and synchronizing based on a second procedure responsive to a second event the second procedure including synchronizing according to a protocol in which the node is anonymous to the reference time source.
Claim 3
Dependent Claim
40 words
A method as recited in claim 1, wherein: the method further comprises the step of maintaining a synchronization error value; and the first event includes detection, by the node, that the synchronization error value has exceeded a threshold error value.
Claim 4
Dependent Claim
82 words
A method as recited in claim 1, wherein the step of synchronizing based on the first procedure includes: transmitting a first synchronization request message to the reference time source; receiving a first synchronization message from the reference time source, in response to the first request message; transmitting a second synchronization request message to the reference time source following receipt of the first synchronization message; and receiving a second synchronization message from the reference time source, in response to the second request message.
Claim 5
Dependent Claim
119 words
A method as recited in claim 3 wherein: the first and second synchronization messages each contain a respective reference time stamp giving a time, according to the reference time scale, related to the time of creation and broadcast of the respective synchronization message; and the step of synchronizing based on the first procedure further includes synchronizing using a probabilistic clock synchronization technique based on temporal relationships between times including at least some of (i) a local time at which one of the synchronization request messages was sent, (ii) a reference time given in one of the reference time stamps, and (iii) a time of reception of one of the synchronization message broadcast responsive to the one synchronization request message.
Claim 6
Dependent Claim
31 words
A method as recited in claim 1, wherein the second event includes receipt of a message which is part of a synchronization procedure between the reference time source and another node.
Claim 7
Dependent Claim
35 words
A method as recited in claim 5, wherein the second event includes receipt of one of: a broadcast synchronization request message from the other node, and a broadcast synchronization message from the reference time source.
Claim 8
Dependent Claim
55 words
A method as recited in claim 5, wherein the step of synchronizing based on the second procedure includes the steps of: establishing a temporal relationship between a time according to the reference time scale and a time according to the local time scale; and adjusting the local time scale in accordance with the temporal relationship.
Claim 9
Dependent Claim
163 words
A method as recited in claim 7, wherein the step of establishing includes: marking received messages with local time stamp marks related to times, according to the local time scale, at which the messages were received; extracting reference time stamps from received synchronization messages, the reference time stamps giving times, according to the reference time scale, related to times at which the synchronization messages were created and broadcast; and determining, based on a predetermined protocol which limits the number of messages in transit through the network at any given time, one of the following temporal relationships: (i) that a given time, defined by a given one of the reference time stamps, falls between first and second times defined by first and second ones of the local time stamp marks; and (ii) that a given time, defined by a given one of the local time stamp marks, falls between first and second times defined by first and second ones of the reference time stamps.
Claim 10
Dependent Claim
55 words
A method as recited in claim 8, wherein the step or adjusting includes: determining a difference between the given time and a time related to the first and second 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 11
Dependent Claim
124 words
A communication and processing node, for use as a node with a communication network including a plurality of nodes which maintain respective local time scales and a reference time source which maintains a reference time scale, the node comprising: means for synchronizing its local time scale with the reference time scale based on a first procedure responsive to a first event, the first procedure including synchronizing according to a protocol in which the node is known to the reference time source; and means for synchronizing its local time scale with the reference time scale based on a second procedure responsive to a second event, the second procedure including synchronizing according to a protocol in which the node is anonymous to the reference time source.
Claim 12
Dependent Claim
124 words
A communication and processing node, for use as a node with a communication network including a plurality of nodes which maintain respective local time scales and a reference time source which maintains a reference time scale, the node comprising: means for synchronizing its local time scale with the reference time scale based on a first procedure responsive to a first event, the first procedure including synchronizing according to a protocol in which the node is known to the reference time source; and means for synchronizing its local time scale with the reference time scale based on a second procedure responsive to a second event, the second procedure including synchronizing according to a protocol in which the node is anonymous to the reference time source.
Claim 13
Dependent Claim
39 words
A node as recited in claim 10, wherein: the node further comprises means for maintaining a synchronization error value; and the first event includes detection, by the node, that the synchronization error value has exceeded a threshold error value.
Claim 14
Dependent Claim
90 words
A node as recited in claim 10, wherein the means for synchronizing based on the first procedure includes: means for transmitting a first synchronization request message to the reference time source; means for receiving a first synchronization message from the reference time source, in response to the first request message; means for transmitting a second synchronization request message to the reference time source following receipt of the first synchronization message; and means for receiving a second synchronization message from the reference time source, in response to the second request message.
Claim 15
Dependent Claim
121 words
A node as recited in claim 12 wherein: the first and second synchronization messages each contain a respective reference time stamp giving a time, according to the reference time scale, related to the time of creation and broadcast of the respective synchronization message; and the means for synchronizing based on the first procedure further includes means for synchronizing using a probabilistic clock synchronization technique based on temporal relationships between times including at least some of (i) a local time at which one of the synchronization request messages was sent, (ii) a reference time given in one of the reference time stamps, and (iii) a time of reception of one of the synchronization message broadcast responsive to the one synchronization request message.
Claim 16
Dependent Claim
31 words
A node as recited in claim 10, wherein the second event includes receipt of a message which is part of a synchronization procedure between the reference time source and another node.
Claim 17
Dependent Claim
35 words
A node as recited in claim 14, wherein the second event includes receipt of one of: a broadcast synchronization request message from the other node, and a broadcast synchronization message from the reference time source.
Claim 18
Dependent Claim
56 words
A node as recited in claim 14, wherein the means for synchronizing based on the second procedure includes: means for establishing a temporal relationship between a time according to the reference time scale and a time according to the local time scale; and means for adjusting the local time scale in accordance with the temporal relationship.
Claim 19
Dependent Claim
169 words
A node as recited in claim 16, wherein the means for establishing includes: means for marking received messages with local time stamp marks related to times, according to the local time scale, at which the messages were received; means for extracting reference time stamps from received synchronization messages, the reference time stamps giving times, according to the reference time scale, related to times at which the synchronization messages were created and broadcast; and means for determining, based on a predetermined protocol which limits the number of messages in transit through the network at any given time, one of the following temporal relationships: (i) that a given time, defined by a given one of the reference time stamps, falls between first and second times defined by first and second ones of the local time stamp marks; and (ii) that a given time, defined by a given one of the local time stamp marks, falls between first and second times defined by first and second ones of the reference time stamps.
Claim 20
Dependent Claim
59 words
A node as recited in claim 17, wherein the means for adjusting includes: means for determining a difference between the given time and a time related to the first and second times; and means for 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 21
Dependent Claim
131 words
A communication network comprising: a reference time source including means for maintaining a reference time scale and means for communicating through a communication medium; and a node including: (i) means for communicating through the communication medium; (ii) means for maintaining a local time scale, (iii) means for synchronizing its local time scale with the reference time scale based on a first procedure responsive to a first event, the first procedure including synchronizing according to a protocol in which the node is known to the reference time source; and (iv) means for synchronizing its local time scale with the reference time scale based on a second procedure responsive to a second event, the second procedure including synchronizing according to a protocol in which the node is anonymous to the reference time source.
Claim 22
Dependent Claim
131 words
A communication network comprising: a reference time source including means for maintaining a reference time scale and means for communicating through a communication medium; and a node including: (i) means for communicating through the communication medium; (ii) means for maintaining a local time scale, (iii) means for synchronizing its local time scale with the reference time scale based on a first procedure responsive to a first event, the first procedure including synchronizing according to a protocol in which the node is known to the reference time source; and (iv) means for synchronizing its local time scale with the reference time scale based on a second procedure responsive to a second event, the second procedure including synchronizing according to a protocol in which the node is anonymous to the reference time source.
Claim 23
Dependent Claim
39 words
A network as recited in claim 19, wherein: the node further includes means for maintaining a synchronization error value; and the first event includes detection, by the node, that the synchronization error value has exceeded a threshold error value.
Claim 24
Dependent Claim
90 words
A network as recited in claim 19, wherein the means for synchronizing based on the first procedure includes: means for transmitting a first synchronization request message to the reference time source; means for receiving a first synchronization message from the reference time source, in response to the first request message; means for transmitting a second synchronization request message to the reference time source following receipt of the first synchronization message; and means for receiving a second synchronization message from the reference time source, in response to the second request message.
Claim 25
Dependent Claim
121 words
A network as recited in claim 19 wherein: the first and second synchronization messages each contain a respective reference time stamp giving a time, according to the reference time scale, related to the time of creation and broadcast of the respective synchronization message; and the means for synchronizing based on the first procedure further includes means for synchronizing using a probabilistic clock synchronization technique based on temporal relationships between times including at least some of (i) a local time at which one of the synchronization request messages was sent, (ii) a reference time given in one of the reference time stamps, and (iii) a time of reception of one of the synchronization message broadcast responsive to the one synchronization request message.
Claim 26
Dependent Claim
31 words
A network as recited in claim 19, wherein the second event includes receipt of a message which is part of a synchronization procedure between the reference time source and another node.
Claim 27
Dependent Claim
35 words
A network as recited in claim 23, wherein the second event includes receipt of one of: a broadcast synchronization request message from the other node, and a broadcast synchronization message from the reference time source.
Claim 28
Dependent Claim
56 words
A network as recited in claim 23, wherein the means for synchronizing based on the second procedure includes: means for establishing a temporal relationship between a time according to the reference time scale and a time according to the local time scale; and means for adjusting the local time scale in accordance with the temporal relationship.
Claim 29
Dependent Claim
169 words
A network as recited in claim 25, wherein the means for establishing includes: means for marking received messages with local time stamp marks related to times, according to the local time scale, at which the messages were received; means for extracting reference time stamps from received synchronization messages, the reference time stamps giving times, according to the reference time scale, related to times at which the synchronization messages were created and broadcast; and means for determining, based on a predetermined protocol which limits the number of messages in transit through the network at any given time, one of the following temporal relationships: (i) that a given time, defined by a given one of the reference time stamps, falls between first and second times defined by first and second ones of the local time stamp marks; and (ii) that a given time, defined by a given one of the local time stamp marks, falls between first and second times defined by first and second ones of the reference time stamps.
Claim 30
Dependent Claim
59 words
A network as recited in claim 26, wherein the means for adjusting includes: means for determining a difference between the given time and a time related to the first and second times; and means for 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 31
Dependent Claim
147 words
A computer program product, for use with a node of a communication network including a plurality of nodes which maintain respective local time scales and a reference time source which maintains a reference time scale, to facilitate the synchronization of a local time scale of the node with the reference time scale, the computer program product comprising: a recording medium; means, recorded on the recording medium, for directing the node to synchronize based on a first procedure responsive to a first event, the first procedure including synchronizing according to a protocol in which the one node is known to the reference time source; and means, recorded on the recording medium, for directing the node to synchronize based on a second procedure responsive to a second event, the second procedure including synchronizing according to a protocol in which the one node is anonymous to the reference time source.
Claim 32
Dependent Claim
147 words
A computer program product, for use with a node of a communication network including a plurality of nodes which maintain respective local time scales and a reference time source which maintains a reference time scale, to facilitate the synchronization of a local time scale of the node with the reference time scale, the computer program product comprising: a recording medium; means, recorded on the recording medium, for directing the node to synchronize based on a first procedure responsive to a first event, the first procedure including synchronizing according to a protocol in which the one node is known to the reference time source; and means, recorded on the recording medium, for directing the node to synchronize based on a second procedure responsive to a second event, the second procedure including synchronizing according to a protocol in which the one node is anonymous to the reference time source.
Claim 33
Dependent Claim
53 words
A computer program product as recited in claim 28, wherein: the computer program product further comprises means, recorded on the recording medium, for directing the node to maintain a synchronization error value; and the first event includes detection, by the one node, that the synchronization error value has exceeded a threshold error value.
Claim 34
Dependent Claim
130 words
A computer program product as recited in claim 28, wherein the means for directing to synchronize based on the first procedure includes: means, recorded on the recording medium, for directing the node to transmit a first synchronization request message to the reference time source; means, recorded on the recording medium, for directing the node to receive a first synchronization message from the reference time source, in response to the first request message; means, recorded on the recording medium, for directing the node to transmit a second synchronization request message to the reference time source following receipt of the first synchronization message; and means, recorded on the recording medium, for directing the node to receive a second synchronization message from the reference time source, in response to the second request message.
Claim 35
Dependent Claim
134 words
A computer program product as recited in claim 30 wherein: the first and second synchronization messages each contain a respective reference time stamp giving a time, according to the reference time scale, related to the time of creation and broadcast of the respective synchronization message; and the means for directing to synchronize based on the first procedure further includes means, recorded on the recording medium, for directing the node to synchronize using a probabilistic clock synchronization technique based on temporal relationships between times including at least some of (i) a local time at which one of the synchronization request messages was sent, (ii) a reference time given in one of the reference time stamps, and (iii) a time of reception of one of the synchronization message broadcast responsive to the one synchronization request message.
Claim 36
Dependent Claim
33 words
A computer program product as recited in claim 28, wherein the second event includes receipt of a message which is part of a synchronization procedure between the reference time source and another node.
Claim 37
Dependent Claim
37 words
A computer program product as recited in claim 32, wherein the second event includes receipt of one of: a broadcast synchronization request message from the other node, and a broadcast synchronization message from the reference time source.
Claim 38
Dependent Claim
78 words
A computer program product as recited in claim 32, wherein the means for directing to synchronize based on the second procedure includes: means, recorded on the recording medium, for directing the node to establish a temporal relationship between a time according to the reference time scale and a time according to the local time scale; and means, recorded on the recording medium, for directing the node to adjust the local time scale in accordance with the temporal relationship.
Claim 39
Dependent Claim
201 words
A computer program product as recited in claim 34, wherein the means for directing to establish includes: means, recorded on the recording medium, for directing the node to mark a received messages with local time stamp marks related to times, according to the local time scale, at which the messages were received; means, recorded on the recording medium, for directing the node to extract reference time stamps from received synchronization messages, the reference time stamps giving times, according to the reference time scale, related to times at which the synchronization messages were created and broadcast; and means, recorded on the recording medium, for directing the node to determine, based on a predetermined protocol which limits the number of messages in transit through the network at any given time, one of the following temporal relationships: (i) that a given time, defined by a given one of the reference time stamps, falls between first and second times defined by first and second ones of the local time stamp marks; and (ii) that a given time, defined by a given one of the local time stamp marks, falls between first and second times defined by first and second ones of the reference time stamps.
Claim 40
Dependent Claim
81 words
A computer program product as recited in claim 35, wherein the means for directing to adjust includes: means, recorded on the recording medium, for directing the node to determine a difference between the given time and a time related to the first and second times; and means, recorded on the recording medium, for directing the node to update the local time scale to compensate for the difference between the first time and the time related to the second and third times.
References Cited (Backward Citations)
US2986723A
Cited
US3940558A
Cited
US4142069A
Cited
US4305045A
Cited
US4677614A
Cited
US4584643A
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
US5327468A
Cited
US5550873A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-11-17 | 2001-05-19 | 2001-11-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-11-17 | 2005-05-19 | 2005-11-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-11-17 | 2009-05-19 | 2009-11-18 | $7700.00 | Window Closed / Lapsed |