Fault tolerant data exchange unit

• US 5,349,654 A
• Filed: 02/20/1992
• Issued: 09/20/1994
• Est. Priority Date: 02/20/1992
• Status: Expired due to Term

• Current Assignee: Yakisami Capital Co LLC (Intellectual Ventures LLC)
• Original Assignee: The Boeing Co.
• Inventors: Kirkland, David T., Hill, Todd, Raftery, Michael L., Bond, David G., VanAlen, Derek J., Caluori, Vincent A.
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): Decady, Albert
• Application Number:
  US07/839,208
• Time in Patent Office: 943 Days
• Field of Search: 371/36, 371/8.1, 371/9.1, 395/575, 364/269.1, 364/269.2, 364/268.3, 364/268.8
• US Class Current: 714/45
• CPC Class Codes: G06F 11/08 Error detection or correction by redundancy in data representation, e.g. by using checking codes
• CPC Class Codes: G06F 11/1679 at clock signal level
• CPC Class Codes: G06F 11/18 using passive fault-masking of the redundant circuits error detection by comparing the output of redundant processing systems with continued operation after detection of the error G06F11/165
• CPC Class Codes: G06F 11/185 and the voting is itself performed redundantly
• CPC Class Codes: G06F 11/187 Voting techniques
• CPC Class Codes: G06F 11/2007 using redundant communication media

Abstract

A data exchange system for use in a system that includes a plurality of redundant channels (12). A data exchange unit (30) is provided to process data, ensuring that consistent data are used by each of the channels. The data exchange unit votes the data so that an output is provided that is identical in non-faulty channels. The data exchange units communicate over an inter-channel net that includes a consistency port (160), which serves as a separate second fault containment region for each channel, enabling the data exchange system to be Byzantine resilient. If input data are provided by a single one of the redundant channels, the data are distributed to each of the data exchange units for all channels in the system using two rounds of communication. However, if nominally identical data are input to each of the data exchange units in the redundant channels, a single round of communication and a simple voting process are used to determine a consistent output for each channel. A multiplexer (112) is used to select the data source for distribution to the consistency ports of each of the data exchange units. A 16-bit voter circuit (130) in each data exchange unit votes on the data received by the data exchange unit from the consistency ports for all of the channels to determine the output that is used by each channel.

Claims

1. A data exchange unit for use in a fault tolerant system having redundant channels, each channel being associated with a different data exchange unit, the data exchange units being used for transferring data from at least one source to a recipient so as to detect and compensate a fault in at least one channel of the redundant channels, each data exchange unit comprising:

(a) a transmitter connected to receive the data from the source over a local bus for one channel with which the data exchange unit is associated, the transmitter distributing that data to the other data exchange units associated with each of the channels over an inter-channel communications link;

(b) a multiplexer having plural inputs connected to the inter-channel communications link to receive the data distributed by the transmitter of each data exchange unit for the other channels, and an output;

(c) receiver means for receiving data conveyed over the inter-channel communications link from the output of the multiplexer in each data exchange unit associated with each channel so that a separate data input and data output for the receiver means are provided for each of the channels;

(d) initialization means for initializing the data exchange unit to synchronize it with the data exchange units for the other channels of the fault tolerant system; and

(e) a voter that selects the data output of the receiver means for transmission to the recipient based on predefined logic, so as to insure that at least one fault in the data input to the receiver means is compensated.

2. The data exchange unit of claim 1, the initialization means comprising:

second receiver means, having plural inputs connected to the inter-channel communications link for separately receiving the data distributed by the transmitter in the data exchange unit associated with each channel, and separate outputs over which the data are conveyed; and

a plurality of buffers, each connected to one of the separate outputs of the second receiver means, providing temporary storage of the data output from the second receiver means until used to initiate the data exchange unit.

3. The data exchange unit of claim 2, further comprising control means for determining the type of data to be conveyed through the data exchange unit and for controlling data transfer within the data exchange unit.

4. The data exchange unit of claim 3, wherein the control means determine whether the data distributed by the transmitter in the data exchange unit for each channel nominally comprise single source data or identical data, and in response to a control signal provided to the multiplexer by the control means indicative thereof, the multiplexer selects an appropriate one of its inputs to provide the data that appears on the multiplexer'"'"'s output.

5. The data exchange unit of claim 4, wherein for single source data, the control means cause the multiplexer to select its input that is connected to receive the data distributed by the transmitter comprising the same data exchange unit as the multiplexer, to provide the data for its output.

6. The data exchange unit of claim 2, further comprising a plurality of buffers connected between outputs of the receiver means and the voter, in which sufficient data are stored to accommodate a maximum skew in a rate at which data are transferred, for each of the channels.

7. The data exchange unit of claim 2, further comprising error logging means, connected to the voter, for logging errors detected in the data input to the voter from the receiver means.

8. The data exchange unit of claim 1, wherein the inter-channel communications link comprises a plurality of consistency ports, each consistency port having an input and a plurality of outputs, the output of the multiplexer in each data exchange unit being connected to the input of a different one of the plurality of consistency ports, each of the plurality of outputs of each consistency port being connected to a different data input of the receiver means in each of the data exchange units, so that each of the consistency ports comprises a fault containment region that prevents at least a single fault in the distribution of data by the transmitter from being propagated to the receiver means.

9. A fault tolerant data exchange system for use in conveying data in a redundant computer system having a plurality of channels, comprising:

(a) a plurality of data exchange units, each associated with a different channel of the redundant computer system and each including;

(i) a local data bus connected to the channel with which the data exchange unit is associated;

(ii) a transmitter, connected to receive data from the local data bus that is distributed to each of the data exchange units;

(iii) a multiplexer having an output and a plurality of inputs, each input connected to receive the data distributed from a different transmitter of the data exchange units for propagation through the output when selected by the multiplexer;

(iv) means for initializing the data exchange unit so that it is synchronized with the other data exchange units;

(v) receiver means, having a plurality of receiver inputs and a plurality of receiver outputs, for receiving the data selected for output by the multiplexer in each data exchange unit on a different receiver input and producing a corresponding output of the data thereby received; and

(vi) voter means, connected to the receiver outputs, for selecting data from the receiver means for output from the data exchange unit according to predefined logic rules, so as to provide consistent data for all of the data exchange units, for said output, even when differences in the data input to the receiver means from each of the multiplexers are not the same;

(b) first communication means for connecting the transmitter of each data exchange unit to a different one of the inputs of each multiplexer in the data exchange units;

(c) second communication means for connecting the output of each multiplexer to a different receiver input of the receiver means of each data exchange unit; and

(d) the second communication means including a plurality of consistency ports, each consistency port being associated with one of the data exchange units and having an input connected to receive the data selected for output from the multiplexer comprising said one data exchange unit, and a plurality of outputs, each connected to the receiver means in a different data exchange unit, the consistency ports each comprising a fault containment region that blocks propagation of faults within the data exchange system.

10. The dam exchange system of claim 9, wherein each data exchange unit further comprises error logging means for monitoring and detecting errors in the data input to the voter means, based upon unexpected differences in said data, the error logging means identifying the data and channel in which each such error occurred, the error logging means being connected to the local bus by at least one buffer in which said errors are temporarily stored.

11. The data exchange system of claim 9, wherein the initialization means comprise a plurality of serial receivers, each having an output and an input connected via the first communication means to one of the transmitters on a different one of the data exchange units;

and a plurality of buffers that connect the outputs of the serial receivers to the local bus and temporarily store data output from one of the serial receivers.

12. The data exchange system of claim 11, wherein the transmitters on each data exchange unit repetitively transmit a channel initialization status vector that includes a timer status indicator that is received by the serial receivers in each of the data exchange units and is used in forming a node initialization status vector that is voted by the voter means until a consensus vote determines which of the channels are not faulty and can comprise a voting set, said voting set then synchronizing by voting on a sync interval transmitted by each of the channels comprising the voting set.

13. The data exchange system of claim 9, wherein each data exchange unit further comprises control means for controlling the multiplexer so as to determine which of its inputs is selected for propagation to its output, based upon the type of data that is input from the local bus to the transmitter, including nominal single source data and nominal identical data from different sources.

14. A method for transferring data from at least one source, so as to detect and compensate a fault in at least one channel of a fault tolerant system having redundant channels for communicating and processing data, the method comprising the steps of:

(a) for each channel, distributing data produced by the at least one source over a local bus;

(b) transmitting said data to the other channels over an inter-channel communications link;

(c) selectively receiving the data distributed from each of the channels over the inter-channel communications link, in turn, for transmission to a consistency port associated with each channel that retransmits the data to all of the channels over separate communication lines; and

(d) voting the data retransmitted from each of the consistency ports to select data that are output, the data thus selected compensating for at least one fault in the communication of data within the fault tolerant system.

15. The method of claim 14, further comprising the step of synchronizing the channels prior to transmitting said data over the inter-channel communications link.

16. The method of claim 14, further comprising the steps of determining whether the data comprise single source data or identical dam, and if the data comprise identical data, transmitting said data directly to the consistency ports of each of the other channels, instead of initially distributing the data between the channels over the inter-channel communications link.

17. The method of claim 14, further comprising the step of storing the data transmitted over the inter-channel communications link for a time longer than a maximum skew interval during which the data are transferred, to compensate for lack of synchronization between the channels.

18. The method of claim 14, further comprising the step of storing the data from the consistency ports before said data are voted sufficiently long to compensate for skew between the channels.

19. The method of claim 14, further comprising the steps of detecting errors in the data voted and logging those errors.

20. The method of claim 19, wherein three types of errors are detected, including:

(a) orphan errors, wherein voting is attempted on one channel, but not on the others;

(b) no-show errors, wherein at the time of voting, data have not been received from one channel; and

(c) disagreement errors, wherein the data from the plurality of channels do not agree when voted.