ALMOST PEER-TO-PEER CLOCK SYNCHRONIZATION

• US 20080170592A1
• Filed: 01/11/2007
• Published: 07/17/2008
• Est. Priority Date: 01/11/2007
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Liu, Zhen, Zhang, Li, Hack, Michel H.T., Sobeih, Ahmed A.
• Application Number:
  US11/622,177
• Publication Number:
  US 20080170592A1
• Time in Patent Office: Days
• US Class Current: 370/503
• CPC Class Codes: H04J 3/0641 Change of the master or reference, e.g. take-over or failure of the master
• CPC Class Codes: H04J 3/0664 unidirectional timestamps
• CPC Class Codes: H04J 3/0676 Mutual

Abstract

Disclosed are a method of and a system for synchronizing clocks in a coordinated network of computers including a multitude of processing nodes, each of the nodes having a clock and one or more neighbor nodes. The method comprises the steps of electing one of the nodes as a correct leader node; and each of the non-leader nodes adjusting its clock rate, based on messages exchanged with neighbor nodes, to remain synchronized with the clock of said correct leader node. In a preferred embodiment, the adjusting step includes the step of each of the non-correct leader nodes using a weight assignment mechanism that gives neighbor nodes that are closer to the leader node more effect on the clock adjustment than those nodes that are further away from the correct leader node.

Claims

1. A method of synchronizing clocks in a coordinated network of computers including a multitude of processing nodes, each of the nodes having a clock and one or more neighbor nodes, the method comprising the steps of:

electing one of the nodes as a correct leader node; and

each of the non-leader nodes adjusting its clock rate, based on messages exchanged with neighbor nodes, to remain synchronized with the clock of said correct leader node.

2. A method according to claim 1, wherein said adjusting step includes the step of each of the non leader nodes using a weight assignment mechanism that gives neighbor nodes that are closer to the correct leader node more effect on the clock adjustment than those nodes that are further away from the correct leader node.

3. A method according to claim 1, wherein the electing step includes the steps of:

each of the nodes identifying one of the nodes as the correct leader node;

passing messages with leader identification information between the nodes; and

one or more of the nodes changing their identification of the correct leader node based on said messages passing between the nodes, until all of the nodes agree on one of the nodes as the correct leader node.

4. A method according to claim 3, wherein:

the identifying step includes the step of each node of at least some of the nodes identifying itself as a correct leader node;

the passing step includes the step of each of the nodes that identifies itself as a correct leader node, broadcasting a leader packet that identifies itself as a correct leader node; and

the changing step includes the step of the nodes using the leader packets to converge to an agreement on one of the nodes as the correct leader node.

5. A method according to claim 1, wherein the electing step includes the steps of:

assigning each of the nodes a sequence number; and

electing one of the nodes as the leader node based on the sequence numbers assigned to the nodes.

6. A method according to claim 1, comprising the further steps of:

under steady state conditions, the correct leader node broadcasting a packet at defined times identifying itself as the correct leader node; and

if the non-leader nodes do not receive said packet within a defined period of time, the non-leader nodes electing a new correct leader node.

7. A method according to claim 6, wherein the step of electing a new correct leader node includes the steps of:

each of the nodes maintaining a time stamp, and each node refreshing its time stamp each time the node receives said packet; and

if the time stamp of one of the nodes is not refreshed within said defined period of time, said one of the nodes identifying the current leader node as failed.

8. A method according to claim 7, wherein the step of electing a new correct leader node includes the step of, if the time stamp of one of the nodes is not refreshed within said defined period of time, said one of the nodes identifying itself as the new correct leader.

9. A system for synchronizing clocks in a coordinated network of computers, the system comprising:

a multitude of processing nodes, each of the processing nodes having a clock; and

said processing nodes configured for

electing one of the nodes as a correct leader node; and

each of the non-leader nodes adjusting its clock rate, based on messages exchanged with neighbor nodes, to remain synchronized with the clock of said correct leader node.

10. A system according to claim 9, wherein said processing nodes are further configured for, each of the non-leader nodes using a weight assignment mechanism that gives neighbor nodes that are closer to the correct leader node more effect on the clock adjustment than those nodes that are further away from the correct leader node.

11. A system according to claim 9, wherein the nodes are configured so that the electing is done by:

each of the nodes identifying one of the nodes as the correct leader node;

passing messages with leader identification information between the nodes; and

one or more of the nodes changing their identification of the correct leader node based on said messages passing between the nodes, until all of the nodes agree on one of the nodes as the correct leader node.

12. A system according to claim 11, wherein the nodes are configured so that:

the identifying is accomplished as a result of each node, of at least some of the nodes, identifying itself as a correct leader node;

the passing is accomplished as a result of each of the nodes that identifies itself as a correct leader node, broadcasting a leader packet that identifies itself as a correct leader node; and

the changing is done by using the leader packets to converge to an agreement on one of the nodes as the correct leader node.

13. A system according to claim 9, wherein the nodes are configured so that the electing is done by:

assigning each of the nodes a sequence number; and

electing one of the nodes as the leader node based on the sequence numbers assigned to the nodes.

14. A method according to claim 9, wherein the processing node are further configured for:

under steady state conditions, the correct leader node broadcasting a packet at defined times identifying itself as the correct leader node; and

if the non-leader nodes do not receive said packet within a defined period of time, the non-leader nodes electing a new correct leader node.

18. A program storage device according to claim 14, wherein the method comprises the further steps of:

under steady state conditions, a correct leader node broadcasting a packet at defined times identifying itself as a correct leader node; and

if the non-leader nodes do not receive said packet within a defined period of time, the non-leader nodes electing a new correct leader node; and

wherein

the step of electing a new correct leader node includes the steps of;

i) each of the nodes maintaining a time stamp and sequence number, and each node refreshing its time stamp and sequence number each time the node receives said packet; and

ii) if the time stamp of one of the nodes is not refreshed within said defined period of time, said one of the nodes identifying the current leader node as failed.

15. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform a method of synchronizing clocks in a coordinated network of computers including a multitude of processing nodes, each of the processing nodes having a clock, the method comprising the steps of:

electing one of the nodes as a correct leader node; and

each of the non-leader nodes adjusting its clock rate, based on messages exchanged with neighbor nodes, to remain synchronized with the clock of said correct leader node.

16. A program storage device according to claim 15, wherein said adjusting step includes the step of each of the non-leader nodes using a weight assignment mechanism that gives neighbor nodes that are closer to the correct leader node more effect on the clock adjustment than those nodes that are further away from the correct leader node.

17. A program storage device according to claim 15, wherein;

the electing step includes the steps of

i) each of the nodes identifying one of the nodes as the correct leader node,

ii) passing messages with leader identification information between the nodes, and

iii) one or more of the nodes changing their identification of the leader node and sequence number based on said messages passing between the nodes, until all of the nodes agree on one of the nodes as the leader node;

iv) the identifying step includes the step of each node of at least some of the nodes identifying itself as a correct leader node;

v) the passing step includes the step of each of the nodes that identifies itself as a correct leader node, broadcasting a leader packet that identifies itself as a correct leader node; and

vi) the changing step includes the step of the nodes using the leader packets to converge to an agreement on one of the nodes as the correct leader node.