Method for exchanging data packets in a safe multicomputer system and multicomputer system for carrying out the same

The invention relates to a method for the exchange of data packets within a safe multicomputer system. The invention further relates to a secure multicomputer system for implementing the method.

To control and monitor safety-critical systems, such as in The field of railway signaling technology or aviation and space travel, are generally used more computing systems. Such multi-computer systems consist of at least two computers, the upcoming tasks largely parallel and independently execute. The hosts of the most More computer systems share their results an internal system or - external comparator with which entails a majority decision. Of the Comparator ensures that only those results are accepted by the majority of the computers involved have been identified consistently. An unidentified from one computer only result can thus never on the to controlling process to act as a computer in a multiprocessor system may under no circumstances have the majority. Often, such More computer systems as performed 2-of-3-computer systems, in which the Coincidence of results is required at least two computers. Precipitation of one of the three computers can be tolerated by the system because then always two computers can identify matching results.

Since, as already mentioned above, the computer in such a More computer systems upcoming tasks execute largely parallel, it must be ensured that all the hosts also the same data stream is supplied. For example, if one of the computers data packets in the order a → b → c and other computer equipment in the order a → c → b gets so are the hosts usually make their calculations, despite the same Programming lead to different results, although at to operate correctly. A 2-of-2 computer system is controlled by a such an error incapable of outputting a result. The occurrence of other error may already lead to two incorrect results be consistent and thus recognized as "right" from the comparator. Catastrophic consequences such as train crashes and plane crashes are not then excluded.

Known are more computer systems for a solid, unified system Synchronization clock work. The data is in the form of data packets exchanged between the computers of the multicomputer system. Each Data packet received from the sending computer, a clock number by which a receiving computer incoming data packets in the correct can bring order. In this way, one for the entire Multicomputer system of uniform data stream ensured. An own Synchronization network serves the system uniform maintain synchronization clock. About this synchronization network sends a selected computer (called. "master processor") at short intervals Synchronization signals to the other computer. Such solutions however require special hardware, including for the Synchronization network, and are therefore expensive.

It is therefore an object of the invention to provide a low cost method of Exchange of data packets within a safe multicomputer system indicate to which ensure that all computers have the same Stream process. The process should not provide a require own Sychronisationsnetzwerks.

The invention solves this problem by means of defined in claim 1 Characteristics. Further advantageous embodiments of the invention are the Subclaims.

The invention is described with reference to embodiments and the Drawings in detail. Show it:<dl tsize="9"><dt>Fig. 1:</dt><dd>A 2-of-3 system MRS as an example of a Multicomputer system in a schematic view for explaining the The inventive method;</dd><dt>Fig. 2a:</dt><dd>The 2-of-3 system MRS from Fig. 1, wherein the computer R1 Data packets A sends to the other two computers R2 and R3;</dd><dt>Fig. 2b:</dt><dd>The 2-of-3 system MRS from FIG. 1, in which the two Computer R2 and R3 turn data packets B and C to the computer R1 message;</dd><dt>Fig. 3a:</dt><dd>The 2-of-3 system MRS from Fig. 1, wherein the computer R1 ... R3 are provided with status sign S;</dd><dt>Fig. 3b:</dt><dd>The 2-of-3 system MRS from FIG. 1, in which for a Embodiment of the invention, the local views LS_k and the global view of GS computer R1 ... R3 is specified;</dd><dt>Fig. 4:</dt><dd>Schematic diagram for explaining how from local views a global view can be determined;</dd><dt>Fig. 5:</dt><dd>The 2-of-3 system MRS from Fig. 1 for explaining a Embodiment according to claim 5;</dd><dt>Fig. 6:</dt><dd>The 2-of-3 system MRS from FIG. 1, in which the Communication connection KV12 is disturbed;</dd><dt>Fig. 7:</dt><dd>The 2-of-3 system MRS from Fig. 1, wherein the computer R1 is disturbed;</dd><dt>Fig. 8:</dt><dd>Stark schematic representation of a computer in a Multicomputer system according to the invention for explaining the Data exchange within the computer and between computers; </dd><dt>Fig. 9:</dt><dd>Structure of a data packet;</dd><dt>Fig. 10:</dt><dd>3-of-5 computer system with two transmission buses.</dd></dl>

Embodiment 1:

As an example of a multi-computer system shown in FIG. 1 is a schematic Display a 2-of-3 system MRS, which and the computer R1, R2 R3 includes. The three computers are connected via communication links KV12, KV13 and KV32 fully meshed with each other. The Communication links KV12, KV13 and KV32 permit bi-directional communication between the computers. Will be realized these communication links, for example, as physical Point-to-point links or via a local area network ( "local area network ", LAN), that ensures the free addressability of computer is. The computer R1 is not shown on Communication links a message a fed. In the same way the computer receives a message R2 b and R3 computer a message c. The news sources that supply the computers, the messages can For example, other more computer systems or a single computer to be, the not part of the multicomputer system MRS. It is also possible that the Messages can not be supplied from external news sources, but in the computers themselves thence running application programs to be generated.

After receiving the message, the computer set according to an agreed Protocol messages a, b, c into the corresponding data packets A, B and C around. If bear no news at one or more computers, so Data packets are created, the user data area is empty. It is also possible, several messages fitting together in a data packet to arrange. In FIG. 2 it is illustrated how one of the computer, here the computer R1, with the transmission of the data packet A provided by him to the two adjacent computer R2 and R3 starts. Which of the computer in this Moment takes the initiative is explained in more detail later will. After receiving the data packet A Send the other two Computer R2 and R3 turn the data packets they create B or C out. This is illustrated in Fig. 2b by the solid arrows. The the Computer R2 adjacent computer R1 and R3 obtained in this way each a data packet B that the computer R3 adjacent computer R1 and R2 each data packet C. After the transfer has now each of the computer R1, R2 and R3 from any other computer in the multicomputer system exactly receive data packet. In Fig. 2b, this is evident in that the share of each Computer exactly two arrows (solid or broken) directed. The applied in the individual computers message a, b and c are thus after performing the process of the invention as the computer been distributed so that all the computers of all supplied to the overall system can have messages. The following is the just described Process referred to as "transmission round". Decisive for the Establishment of such transmission round is the fact that the two computers R2 and R3 after receipt of transmitted from the computer R1 own data packet A in turn within a predetermined time period Data packets to all other computers transmit.

In order to ensure a uniform flow of data in all computers must Now the data packets are placed in a single order. there can be exploited for the fact. B. that each computer on receipt a data packet may identify the transmitter. An investigation of the transmitter both physical point-to-point connections as well as Networks possible and requires no special measures. by virtue of the transmitter can determine the received data packets to the Assigning sending computer clearly. In an agreement can then are set so that the data packets are to be sorted so that the first from computer R1 derived data packet A, then the computer from R2 derived data packet B and finally originating from the computer R3 Data packet C the running in the computers application processes is supplied. In the example shown above, this would mean a sequence A → B → C result. In this way, however, the the computer R1 supplied message preferably processed. Therefore, it may be useful, determine the order in a different way. So z. B. is conceivable that Direction of transmission round to round transmission cyclically permute. In a Round 1 is then about the sequence A → B → C, in the subsequent round 2 the sequence B '→ C' → A 'and then in Round 3 is selected, the sequence C "→ A" → B "etc. In this procedure, All computers on an equal footing when determining the order.

By carrying out the process according to the invention thus is all Computers in the multicomputer system, a single data stream available posed. A private Sychronisationsnetzwerk is this to the contrary known solutions is not required. Another advantage of the Method of the invention is that due to the temporal Sequence of transmission and reception, the computers are capable of certain errors in the transmission to identify and localize. Receives example in above with reference to FIG. 2b illustrated example the computer R1 <i>not</i> from computer R2 the data packet B, so the computer can out R1 fact that one of the following faults is present:<ul><li>the computer R2 has not received the data package A;</li><li>the computer R2 has received the data packet A, but due to a computer internal fault no data packet sent B;</li><li>the computer R2 has sent a data packet B, this could, however, returned due to a broken communication link will.</li></ul>

The computer R1 due to this diagnosis z. B. communication with Set the computer R2 and continue only with the computer R3 communicate.

Embodiment 2

:

It is u. U. Depending on the configuration of the inventive method is not excluded (see below for more details), that in addition to the Computer R1 almost simultaneously a different computer, a transmission round abuts. Thus for example the computer R2 after the initiation of a Transmission round by the computer R1, but before receiving the A data packet, another transfer round sending his Data packet B trigger. In this case, the computer would R2 after receiving the data packet A from computer R1 its data packet B retransmit, although with this data packet B just before a transmission round has initiated. The computer R1 and R3 would therefore the data packet B received twice. Moreover, there is the danger that it of a kind "Ping-pong effect" occurs, wherein the computer data packets identical in endless succession shall provide each other.

To rule this out, is in one embodiment according to the invention Claim 2 provides that a computer in one transmission round not upon receipt of a data packet by transmitting an own Data packet to do when it on in this broadcast round already own own initiative sent a packet to all other computers. This assumes that the data packets to identify the data RN include transmission round, so that each computer data packets received may assign at any time a particular transmission round. If For example, a transmission round is finished and the two i Computer R1 and R2 are independently a transmission round 1 + 1 initiate by sending data packets A and B, so the computer sends R2 in this transmission round yet again its data packet B as the other computers have received this already once or soon received. He also does not react with the sending of another internally generated data packet B ', so that the above-mentioned "ping-pong effect" is avoided. The same applies to the computer R1.

Embodiment 3

:

In the inventive method, the communication takes place between the computers instead of in the form of transfer rounds. At the end of such Transmission round any machine at least one data packet from all get other computers. This form of data packet exchange particularly advantageous when the data packets status information to the individual computers contain. It can in this way each individual Hosts for the last transmission round a global view of System Status detect. What this means in detail, hereinafter fully described.

Fig. 3a shows the multiprocessor system of FIG. 1 and in addition, for each Computer status S_k, The two computers R1 and R2 Own Example shown without error and are therefore fully fledged "members" in Multicomputer system. Therefore, they are the status symbol "m" in. It is understood that only the data processed or evaluated (about in a comparator), which by a computer the "members" - state submitted. The computer R3 is defective in this example and is therefore called a "non-member". He is for this reason the Status symbol "n" assigned From this computer R3 derived data are therefore rejected.

After performing a transmission round each computer determines its custom local view LS_k the system state by the received Evaluates data packets. Should, for instance, the computer R1 from computer R2 no or only an erroneous data packet, so he considered this calculator in its local view LS₁ as ,, non-member ". Depending on the type of error may quite possible that the view from the computer R1 faulty computer R2 itself, however. As error-free and therefore regarded as "Member" In the local view LS₂ of the computer R2 are thus possibly all computers "Members". The local views LS_k the system status can be so differ.

However, for certain purposes it is advantageous, also a global, for all Computer unified view GS to determine the system status. The global view The system status is particularly needed<ul><li>thus given at the system level a uniform basis for decision is to assist in the error-free computers ( "members"), the same to carry out processing steps in the same order,</li><li>thus recognize a central error handling instance errors and where appropriate measures can take to remedy,</li><li>to defective computer reenter in the multiprocessor system</li></ul>

The determination of the global view is the subject of the following sections.

After completion of a transmission round i of each computer determines its local Overview LS_k the system status. The following transmission round 1 + 1 transmitted each computer its local viewpoint LS_k the system status in Transmission round i the other computers. After completion of the Transmission round i + 1 thus has every computer from any PC in the Multicomputer system which local views of the preceding Transmission round i. From these local views can now each computer after an agreed rule a global view of the system status in Transmission round i determine. Such a rule may, for. Example, the following include steps:<ul><li>Use the local views LS_k the system state in transmission round i those machines that at the global view of the system status in this Transmission round i the status "member" had;</li><li>Make these local views LS_k a majority decision by;</li><li>Accept a by majority vote as a "member" certain Calculator only as such when this themselves running in the Transmission round has been reported as "Member".</li></ul>

The global view GS for Übertragunsrunde is exemplified by in Figure 3b the symbols "MMN" marked. This means that the computer R1 and R2 are globally recognized as members, while the computer as R3 Not a member is considered. Also shown are the local views LS_kthe computer R1 ... R3 of the system status of the preceding Transmission round. In this simple example, all computer R1 ... R3 the same local view of the system status of the preceding Transmission round, namely "mmn". This means that all the computers the Computer R1 and R2 as members and the computer R3 as "Non-Member" have view.

The determination of a global perspective is in Fig. 4 based on a simple Example explained again. The global view of the GS in Transmission round i was "MMN", ie the two computers R1 and R2 are as recognized members while the computer R3 is regarded as defective. According to the rule above are therefore in the following Transmission round i + 1, only the local views of the computers R1 and R2 when Majority vote ME considered. In the example shown are wrong local views coincide, so that the majority decision ME earnings "Mmn" delivers. The local view of the defective computer R3 is u. U. nonsensical faulty or incomplete, which in FIG. 4 by the symbols "???" is pictured. Since the two specified members as computers R1 and R2 see themselves in their local view LS as members, is the global view the system status equal to the result of majority rule, therefore ,, MMN ".

The concept, the data packets accompanied by status information, can ever be extended on the requirements of the overall system. Thus, In addition to the listed status options "Member" and ,, non-member " also intermediate states as "Provisional Member" or "Anwärfer on Member "to be defined. This is about useful if defective computer without the intervention of an operator again in the multiprocessor system should be involved. With such integration, it is for reasons security appropriate to the function of or the einzubindenden to let computer first watch of the non-defective computers. A global recognition as a member only takes place when the integrate is Hosts a kind of "trial period" has passed successfully.

In a further advantageous embodiment, contain Data packets data from which a local time of the data packet is sending computer determined. Under local time, the time will be understood, the sending computer the data packet at the time of creation of a computer internal or external clock taps. After completion of a Transmission round, each computer in the multiprocessor system capable of a global time to determine this information. This may for example by simple formation of the median value (= median) of each local Times happen. A global time often need the from Multicomputer system running application programs or certain external modules such as the already mentioned above Comparator which a the results of the individual computers Majority decision subjects.

Furthermore it can be provided to the data packets accompanied by checksums, serve to check whether all or part of the data packet Data contained have been correctly received. By such, per se known measures can ensure that only data packets are evaluated - as for determining a global view of System Status - which have actually been transmitted without errors.

Embodiment 4:

guided in a particularly advantageous embodiment according to claim 6 the computer R1 ... R3 received data packets so adjacent to the Computer further in that each computer each circumferential data package faultless case receives at least twice. This is with reference FIG. 5 explained. The computer R1 sends in this example, a data packet A made. The two computers R2 and R3 receive this data packet A and submit it to the computer R3 or R2 on. In this manner, receives the Computer R2 the data packet A again directly from the computer R1 and once indirectly via the computer R3. The same applies to the computer R3. Of the computers R2 and R3 transmitted data packets B and C also passed in the manner described. The twofold Reception is the tolerance of the multicomputer system to errors and Precipitation improved significantly. Further, it is possible to use a larger class to locate faults precisely, especially if the data packets Control data may include, as described above. Subsequently representative two in multicomputer system possible failure scenarios discussed, to demonstrate the advantages of this embodiment of the invention.

Fig. Figure 6 shows the multiprocessor system of FIG. 1, in which the Communication connection KV12 between the computers R1 and R2 in both directions of transmission is interrupted. The computer R2 can Data packets thus not directly from the computer R1, but only indirectly received via the computer R3. The same applies to data packets of the Computer R2 to the computer R1 sends. Due to the invention Handoff of the data packets so is the interruption of the Communication connection KV12 tolerated. In an advantageous variant of the Invention contain data packets data that characterize the way the data packets are taken by the multicomputer system. In order it possible for each machine, to locate the error precisely because of Computer R1 then know for example, that he the only one data packet calculator received R2, which has taken the route via the computer R3. The Cause of it can only be a break in the communication link be KV12. Analogously, the other computers R2 and R3 may determine on the basis of the transmission path of the received data packets to where in the multicomputer system a communication link is interrupted. This determined locally individual at any computer Status information is preferably by transferring rounds exchanged between the computers and this - as described above - used to determine a global view of the system status. A central Error handling instance then performs appropriate actions. In which in Fig. 6 example shown, a possible measure z. B. therein could exist, sending and receiving this communication link KV12 permanently discontinue or completely for a predetermined time.

In the multicomputer system MRS shown in Fig. 7, the computer sends R1 not, as originally planned, on both computers R2 and R3 identical Data packets A, but different data packets A and A '. The cause such as "Byzantine" denoted error scenarios can for example, be that the transmitter unit for a Communication link is disrupted. Without forwarding the data packets according to claim 6, the computer R2 and R3 would not be able to determine that they have received different data packets. An error is therefore not occurred in their view. They would, therefore, the data packets A and A 'further process, but here - because the data packets from each other differ - may lead to different results. Since at least one of the results must be wrong, the case could occur that precisely this false result from the defective computer R1 determined result matches. A single error, namely the failure of the Computer R1, could therefore already two in a match wrong Results and thus lead to a dangerous condition.

Conversely, if the data packets are forwarded according to claim 6, so can the computers R2 and R3 in this case, two data packets from Computer R1 (one directly and one indirectly), but from one another differ. If the data packets contain control data, so can the R2 and R3 computer to determine whether the data packets on the transmission path have been corrupted. Is not a falsification occurred, can the Computer R2 and R3 reliably determine that the computer R1 has different data packets A and A 'sent. As for the computer R2 and R3, however, it is not clear which of the two data packets that right is, discard both computers by the computer R1 directly or indirectly received data packets. In the local view of the computer R2 and R3 and also in the global view of the computer R1 is therefore as "Non-member" considered.

The following statements deal with the already mentioned above Question of which computers in the multicomputer system transferring rounds be initiated. According to the invention are here filters provided that enter individually or combined for use can:<sl><li>a) That from a computer running application program even provides Command to send a data packet and thus a transmission round abut. Since mostly the same in multiprocessor systems, all computers Application program execute in parallel, it may happen that all computers simultaneously or within, ie short in very intervals, received orders to transfer Round nudge. It then comes to the scenario that up to Embodiment has been described of claim 2.</li><li>b) Any computer in the multicomputer system encounters regularly in advance or specified during the operation time intervals a Transmission lap. In this way, in particular ensuring that Status information between computers regularly exchanged be such that any encountered malfunction of computers or Transmission paths be discovered quickly. However, if only one Host is responsible for initiating, then in case of failure just this computer triggered no transfer rounds. Therefore it will be more convenient, as a rule, all the computers at different times in to let initiate periodic transmission rounds. If bear no messages to be exchanged with a computer, so the computer sends a data packet in question from whose is user data area empty.</li><li>c) A computer meets at least each time a transmission round by Sending of a data packet, if the in his message buffer (For details see below) stored message set a pre exceeds specified limit. This reduces the exchange of empty Data packets. In place of the measurable in bytes message set can enter the number of messages. So can specify that a computer initiates a transmission round once, for example, 5 Messages are stored in its buffer messages.</li><li>d) For safety-critical computer systems more it makes sense, News be provided with a priority value of a measure of the importance Payload is. In a variant of the invention, the Priority value in the data packets together with the user data, and possibly to transmit more data. A transmission round, in this launched variant, if the priority value of a communication over an is pre-determined threshold. This ensures that important Messages are exchanged immediately.</li></sl>

Preferably, the criteria a) to d) are combined so that a portable Compromise between high safety requirements on the one hand and the Requiring a low transmission volume on the Communication connections on the other hand achieved. As already mentioned, it may in combination of criteria quite happen that several Computers simultaneously or within a transmission round nudge.

Embodiment 5

:

In FIG. 8 is illustrated schematically in a highly simplified model, such as according to another embodiment of the method according to the invention Messages and data packets processed and within a computer Multicomputer system to be replaced. The belonging to a computer R Modules are surrounded by a dashed line. A from any Computer R executed in multiprocessor system application process AP indicates the computer R news from NA. These messages are in a NA Incoming message buffer ENP buffered. notify the arrival of an email this is the input message buffer ENP an exchange rules module ATVM examining communications with MA. are in the exchange rules module ATVM the basic exchange rules stored, after which the Exchange of data between computers in the multicomputer system make is. In the exchange rules is defined, for example, by What criteria will be the triggering of transmission rounds. Further, the exchange rules module ATVM the task, the message stream in Incoming message buffer ENP (and also in the output message buffer ANP, see below) to control.

The messages MA from the input message buffer ENP to the Exchange rules module ATVM included in this embodiment, Information, what is the priority value has the last received message. The exchange regulations module ATVM compares this priority value with a predetermined threshold is exceeded, causing the Threshold above commands B, that the input message buffer ENP of the buffered messages NA a data packet DP and created this Data packet to the replacement module AM ​​for initiating a Transmission round emits. The data packet DP has a header which include the sender and includes recipient address, and a core in which the to be transmitted User data are stored.

The replacement module AM ​​fulfilled in this embodiment, among others, the Functions of the network and transport layers in the OSI model. The overlying layers thus remain the physical realization of the communication links, the transmission method used and the number of computers in the multicomputer system hidden. Further, the Exchange module AM, the task of the head of the data packets among other things to expand the following information:<ul><li>a number to designate the transmission round;</li><li>the newly determined local view of the system status;</li><li>the local time;</li><li>an identification of the computer on which operates the replacement module AM.</li></ul>

From replacement module, the data packet DP reaches the driver layer T that the Link layer in the OSI layer model and provided that the Data packets to a physical bit stream mapping. The driver layer ensures that the data packet within a limited period of time at other, is transmitted in Fig. 8, not shown computer. The driver layer should ensure that data packets are not reordered in the transmission is, as otherwise u. U. can not be guaranteed that all computers in the Multicomputer system can process a single data stream. Around To ensure an unambiguous assignment error, should also apply for the Transmission will not distort the data packets or regenerated. For the overlying layers is the driver layer transparent.

In the receive direction pass data packets DP on the driver layer to T Exchange module AM, in the particular in the head of the data packets Information contained (local view of the system status, local time, Number of transmission round etc.) are evaluated. The Exchange module creates error messages FM and outputs them together with the data packets DP to an output message buffer ANP on. Of the Output message buffer ANP extracted from the data packets, the News NA and makes this an application process AP 'available.

Fig. 9 shows a summary of the structure of a data packet DP, which in a preferred embodiment of the invention the exchange of Data is used between the computers. The core of the data packet DP consists of the useful data ND. The head H of the data packet contains, inter alia,<ul><li>Data W to identify which way the data packet through the Multicomputer system has taken,</li><li>Data (LS), the local view of the sending computer from the System Status featuring in the preceding transmission round,</li><li>Data LZ, from which the local time of the packet data transmitted is computer determined,</li><li>Data RN to identify the current transmission round,</li><li>Control data K for checking whether all or part of the above Data referred to have been correctly received.</li></ul>

The previously described embodiments of the invention relate all on a 2-from-3-computer system, because there the invention is particularly applicable method advantageous. The process can, however, without modifications also for multiprocessor systems with other Redundancy levels are used to advantage. The described above Embodiments can be, for example, on a 2-out-2 computer system transfer. Likewise, in a 3- of-5 computer system the communication between the computers according to the invention Processes are carried out. Instead of a single addressing the computers it may then be advantageous to communicate in "Broadcasting" mode perform, ie data packets either to all or no computer transmits. Fig. 10 shows an example of such a 3-of-5-computer system. Five computer R1 ... R5 communicate in "Broaclcasting" mode via a first bus B1 and a second bus B2 one another. Of the second bus B2 is optional and is used to ensure the availability of increase multicomputer system.

A transmission round comprises in this embodiment the following steps:<ul><li>a computer such as computer R1, sends a data packet to all A Computer R2 ... R5;</li><li>the computer R2 ... R5 set then from its own data packets B, C, D and E, which are received by all other computers.</li></ul>

An additional redundancy can be made in this arrangement, if after the first round of transmission through the first bus B1, a second performed transmission round via the bus B1 and / or via the bus B2 becomes. The possibilities of error localization are the broadcast mode However, not as diverse as the above-described Embodiments.