Electrical computers and digital processing systems: multicomput – Multicomputer synchronizing
Reexamination Certificate
2000-10-02
2004-10-05
Follansbee, John (Department: 2154)
Electrical computers and digital processing systems: multicomput
Multicomputer synchronizing
C713S400000
Reexamination Certificate
active
06801951
ABSTRACT:
FIELD OF INVENTION
The present invention relates to the field of computer synchronization and in particular to a system and method for synchronizing multiple nodes on a network that utilizes a convergence technique.
BACKGROUND OF INVENTION
For any network system, synchronization of each node within the network is important to ensure that the network functions smoothly. Nodes that are not synchronized can cause disturbances within the network as miscommunication can occur between the nodes.
Any synchronization implementation needs to be as reliable as possible. However, the more reliable that a synchronization implementation is, usually the more complicated the implementation of that technique tends to be as well.
For example, prior synchronization algorithms have been based on the concept of interactive convergence through local timestamping of broadcasted messages. The synchronization algorithm had to infer the value of the remote node's clock to arrive at a voted and globally consistent clock. This approach, while proven to be fault-tolerant, is inherently complex and resource intensive.
In addition, implementing a synchronization algorithm mainly through software on the node's processor imposes requirements on the hardware of the node itself. The node could be required to have high quality hardware to implement the synchronization software to be able to maintain high reliability of the synchronization procedure. This high quality requirement greatly increases the cost of the implementation overall and sometimes is unnecessary to perform the intended functions of the network.
As such, there exists a need for a synchronization method to effect synchronization of the nodes of a network that will have sufficient features to ensure reliable synchronization while reducing the complexity of the implementation and lowering the high quality standards for hardware.
SUMMARY OF THE INVENTION
This invention utilizes a hardware implementation separate from the network node to synchronize each network node. Synchronization of the network is implemented in a Redundancy Management System (RMS) that can interface with common communication techniques within the network in conjunction with a Field Programmable Gate Array (FPGA) to implement the synchronization algorithm. The invention also exploits the ability of some communication protocols, such as IEEE 1394, to periodically broadcast their local clocks, forming a distributed global database and simplifying the synchronization process. The algorithm uses interactive convergence techniques to arrive at a globally consistent clock.
In accordance with one embodiment of the invention, a method for synchronizing nodes in a network is described that comprises the steps of broadcasting the clock value of each node on the network; determining a voted clock value based on a set of the clock values that were broadcast; comparing the clock value of each node to determine which nodes are synchronized with each other; resetting each node's clock to the voted clock value; and setting flags to indicate which nodes are synchronized.
In accordance with another embodiment of the invention, a system to synchronize nodes in a network is described that comprises a clock broadcaster to broadcast the clock values of each node in the network to all other nodes in the network; a clock voter to determine a voted clock value based on a set of the clock values that were broadcast; a clock setter to set the clock values of each node in the network to the voted clock value; an array of clock timers to store each of the clock values that have been broadcast; a clock comparer to determine which nodes are synchronized based on the clock values stored in the array; and a synchronization indicator to designate the nodes that are synchronized.
In accordance with another embodiment of the invention, an apparatus to synchronize nodes in a network is described that comprises a communication interface associated with each node in the network, the interface capable of broadcasting a clock value of the associated node and receiving the clock values that have been broadcast; a plurality of logic gates associated with each node; the logic gates arranged to be able to determine a voted clock value based on a set of the clock values that have been broadcast and arranged to be able to determine which nodes are synchronized by comparing the clock values; and a memory register associated with each node to store flags indicating the synchronization status of each node.
REFERENCES:
patent: 5146585 (1992-09-01), Smith, III
patent: 5327468 (1994-07-01), Edblad et al.
patent: 5537583 (1996-07-01), Truong
patent: 5768282 (1998-06-01), Ohara et al.
patent: 5875320 (1999-02-01), Gu
patent: 5903717 (1999-05-01), Wardrop
patent: 6104770 (2000-08-01), Yama
patent: 6665316 (2003-12-01), Eidson
patent: WO 88 08161 (1988-10-01), None
patent: WO 99 38287 (1999-07-01), None
D.L. Mills, “Improved Algorithms for Synchronizing Computer Network Clocks”, Computer Communications Review, US, Association for Computing Machinery, New York, vol. 24, No. 4, Oct. 1, 1994, pps. 317-327, XP000477058, ISSN: 0146-4833, Abstract, Chapter 3.
Falk James W.
Follansbee John
Honeywell International , Inc.
Lin Kenny
Luxton Matthew
LandOfFree
System and method for fault-tolerant clock synchronization... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for fault-tolerant clock synchronization..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for fault-tolerant clock synchronization... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3332296