Processing system for use as a network node for performing anonymous time synchronization in a network

• US 5,550,873 A
• Filed: 02/01/1995
• Issued: 08/27/1996
• Est. Priority Date: 11/03/1992
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Reischuk, R udiger K., Dolev, Danny, Strong, Hovey R.
• Primary Examiner(s): Chin, Stephen
• Assistant Examiner(s): PHAN, HAI
• Application Number:
  US08/382,479
• Time in Patent Office: 573 Days
• Field of Search: 375/354, 375/356, 375/359-361, 375/364, 375/365, 370/100.1, 370/103, 370/105, 370/105.1, 340/825.14
• US Class Current: 375/354
• CPC Class Codes: G06F 1/14 Time supervision arrangements, e.g. real time clock
• CPC Class Codes: H04J 3/0664 unidirectional timestamps

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. A network node as recited in claim 7 further comprising means for requesting synchronization if the global precision information exceeds a first threshold.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.