VERFAHREN ZUM ERZWINGEN DER FAIL-SILENT EIGENSCHAFT IN EINEM VERTEILTEN COMPUTERSYSTEM UND VERTEILEREINHEIT EINES SOLCHEN SYSTEMS Diese Erfindung betrifft ein Verfahren zum Erzwingen der fail-silent Eigenschaft im Zeitbereich von Knotenrechnern eines fehlertoleranten verteilten Computersystems, in dem eine Vielzahl von Knotenrechnern über eine Verteilereinheit verbunden sind, jeder Knotenrechner über eine auto- nome Kommunikationskontrolleinheit mit den entsprechenden Anschlüssen an die Kommunika- tionskanäle verfügt und der Zugriff auf die Kommunikationskanäle entsprechend einem zykli- schen Zeitscheibenverfahren erfolgt. Ebenso betrifft die Erfindung eine Verteilereinheit mit in- tegriertem Guardian zur Erzwingung der fail-silent Eigenschaft im Zeitbereich von Knotenrech- nern eines fehlertoleranten verteilten Computersystems, über welche eine Vielzahl von Knoten- rechnern miteinander verbunden sind, jeder Knotenrechner über eine autonome Kommunikati- onskontrolleinheit mit zugehörigen Anschlüssen an die Kommunikationskanäle verfügt und der Zugriff auf die Kommunikationskanäle entsprechend einem zyklischen Zeitscheibenverfahren erfolgt.

Sicherheitskritische technische Anwendungen, d. s. insbesondere Anwendungen, bei welchen ein Fehler zu einer Katastrophe fiihren kann, werden zunehmend von verteilten fehlertoleranten Echtzeitcomputersystemen geführt.

In einem verteilten fehlertoleranten Echtzeitcomputersystem, bestehend aus einer Anzahl von Knotenrechnern und einem Echtzeitkommunikationssystem, muss der Ausfall eines Knotenrech- ners toleriert werden. Im Kern einer solchen Computerarchitektur befindet sich ein fehlertoleran- tes Echtzeitkommunikationssystem zum vorhersehbar schnellen und sicheren Austausch von Nachrichten.

Ein Kommunikationsprotokoll, das diese Anforderungen erfüllt, ist in der EP 0 658 257 A (WO 94/06080) beschrieben. Dieses Protokoll ist unter dem Namen"Time-Triggered Protokoll/C (TTP/C)"bekannt geworden. Es basiert auf dem bekannten zyklischen Zeitscheibenverfahren (TDMA-time-division multiple access) mit a priori festgelegten Zeitscheiben. Das Protokoll TTP/C verwendet ein Verfahren zur fehlertoleranten Uhrensynchronisation, das in der US 4,866,606 A geoffenbart ist.

Das Protokoll TTP/C setzt voraus, dass das Kommunikationssystem eine logische Broadcasttopo- logie unterstützt und dass die Knotenrechner ein"fail-silence" (Kopetz, p. 121) Ausfallverhalten zeigen, d. h. entweder die Knotenrechner funktionieren korrekt im Wertebereich und im Zeitbe- reich oder sie sind ruhig Dies ist beschrieben in Kopetz, H. (1997),"Real-Time Systems, Design Principles for Distributed Embedded Applications" ; ISBN : 0-7923-9894-7, Boston, Kluwer Aca- demic Publishers. Die Verhinderung von Fehlern im Zeitbereich, d. s. der sogenannten"Babbling Idiot"Fehler (Kopetz, p. 130), wird in dem Protokoll TTP/C durch eine unabhängige Fehlerer- kennungseinheit, den sogenannten"Guardian", erreicht, der über eine unabhängige Zeitbasis ver- fügt und das Zeitverhalten des Knotenrechners kontinuierlich überprüft. Um die Fehlertoleranz zu realisieren, werden mehrere fail-silent Knotenrechner zu einer fehlertoleranten Einheit (fault- tolerant unit-FTU) zusammengefasst und das Kommunikationssystem repliziert. Solange ein Knotenrechner einer FTU und ein Replikat des Kommunikationssystems funktionieren, werden die Dienste der FTU im Zeit-und Wertebereich rechtzeitig erbracht.

Eine logische Broadcasttopologie der Kommunikation kann physikalisch entweder durch ein verteiltes Bussystem, ein verteiltes Ringsystem, oder durch eine Verteilereinheit, z. B. einen Sternkoppler, mit Punkt-zu-Punkt Verbindungen zu den Knotenrechnern oder durch eine Kombi- nation dieser Topologien aufgebaut werden. Wenn ein verteiltes Bussystem oder ein verteiltes Ringsystem aufgebaut wird, so muss jeder Knotenrechner über seinen eigenen Guardian ver-- gen. Wird hingegen eine Verteilereinheit verwendet, so können alle Guardians in diese Verteiler- einheit integriert werden, die aufgrund der globalen Beobachtung des Verhaltens aller Knoten- rechner ein reguläres Sendeverhalten im Zeitbereich effektiv erzwingen kann. Die vorliegende Erfindung betrifft auch die Integration der Guardians in eine solche Verteilereinheit.

Solche Verteilereinheiten mit integriertem Guardian bringen folgende Vorteile : (i) Die Fault-Containment Region für global kritische Fehler wird um die Punkt-zu- Punkt Verbindungen der Knotenrechner zu der Verteilereinheit reduziert, d. h. Fehler, die z. B. durch EMI (electromagnetic immission) in diese Punkt-zu-Punkt Verbin- dungen eingestreut werden, können eindeutig einem Knotenrechner zugeordnet wer- den und haben keine globale Wirkung.

(ii) Die replizierten global kritischen Verteilereinheiten können räumlich getrennt in ge- schützten Bereichen installiert und physisch kompakt ausgeführt werden. Dadurch wird die Wahrscheinlichkeit, dass eine Fehlerursache alle global kritischen Verteiler- einheiten zerstört, signifikant herabgesetzt.

(iii) Der Guardian der Verteilereinheit ersetzt die dezentralen Guardians in den Knoten- rechnern. Dadurch wird bei den Knotenrechnern Hardware, z. B. die Guardian Oszil- latoren eingespart.

(iv) Physikalische Punkt-zu-Punkt Verbindungen eignen sich gut für die Einführung von Glasfaser und bringen auch bei verdrillten Leitungen Vorteile in der Impedanzanpas- sung.

Es ist eine Aufgabe der Erfindung die Fehlertoleranz eines verteilten zeitgesteuerten Computer- systems zu erhöhen und die Kosten zu senken.

Diese Aufgabe wird mit einem Verfahren der eingangs genannten Art gelöst, bei welchem erfin- dungsgemäß die zumindest eine Verteilereinheit aufgrund des ihr a priori bekannt regulären Sen- deverhaltens der Knotenrechner erzwingt, dass ein Knotenrechner nur innerhalb seiner statisch zugewiesenen Zeitscheibe an die anderen Knotenrechner zu senden vermag.

Durch die Integration eines"Guardian"in die intelligente Verteilereinheit können"Babbling Idiot"-Fehler, d. h. Aussendung von Nachrichten zu falschen Zeitpunkten, der Knotenrechner verhindert werden.

Ebenso wird die Aufgabe mit einer Verteilereinheit der oben erwähnten Art gelöst, bei welcher erfindungsgemäß die zumindest eine Verteilereinheit dazu eingerichtet ist, aufgrund des ihr a priori bekannten regulären Sendeverhaltens der Knotenrechner zu erzwingen, dass ein Knoten- rechner nur innerhalb seiner statisch zugewiesenen Zeitscheibe an die anderen Knotenrechner zu senden vermag.

Die Funktion der Verteilereinheit basiert auf der Auswertung einer Kombination von statischen a priori Informationen über die zeitliche Sendeberechtigung der einzelnen Knotenrechner mit einer dynamischen Synchronisation der Verteilereinheit durch die Nachrichten eines zeitgesteuerten Kommunikationssystems.

Die Erfindung samt ihrer weiteren Vorteile wird im folgenden an Hand von Ausführungsbeispie- len näher erläutert, die in der Zeichnung veranschaulicht wird. In dieser zeigen : > Fig. 1 die Struktur eines verteilten Computersystems mit vier Knotenrechnern, die über zwei replizierte Verteilereinheiten verbunden sind, Fig. 2 die Struktur eines Knotenrechners, bestehend aus einer Kommunikations-Kontroll- einheit und einem Hostcomputer, die über ein Communication Network Interface (CNI) kommunizieren, > Fig. 3 die Struktur einer Verteilereinheit mit integriertem Guardian, Fig. Fig. 4 die Datenstruktur der Information, welche die Verteilereinheit a priori enthält, > Fig. 5 die Struktur einer Initialisierungsnachricht, und Fig. Fig. 6 die inneren Zustände der Verteilereinheit.

Im folgenden Abschnitt wird eine Realisierung der Erfindung an einem Beispiel mit vier Knoten- rechnem, die über zwei replizierte Verteilereinheiten verbunden sind, gezeigt. Die Objekte in den Abbildungen sind so nummeriert, dass sich die erste der dreistelligen Bezugsziffem immer auf die Bildnummer bezieht.

Fig. 1 zeigt ein System von vier Knotenrechnem 111,112,113 und 114, wobei jeder Knoten- rechner eine austauschbare Einheit bildet und über je eine Punkt-zu-Punkt Verbindung 121 mit zwei replizierten Verteilereinheiten 101 und 102 verbunden ist. Von der ersten Verteilereinheit 101 führt ein unidirektionaler Kommunikationskanal 151 zu der anderen zweiten Verteilereinheit 102. Umgekehrt führt von der Verteilereinheit 102 ein unidirektionaler Kommunikationskanal 152 zu der Verteilereinheit 101. Über diese unidirektionalen Kommunikationskanäle kann die erste Verteilereinheit 101 den Verkehr auf der zweiten Verteilereinheit 102 und umgekehrt beo- bachten und den Kaltstart oder die Uhrensynchronisation auch vomehmen, wenn es an den eige- nen Verbindungen 121 keinen Nachrichtenverkehr gibt. Angedeutete Verbindungen 141 und 142 sind dedizierte Kommunikationskanäle ; sie führen zu einem auf der Zeichnung nicht ersichtli- chen Wartungscomputer, der die Parameter der Verteilereinheiten festlegen kann und die korrek- te Funktion der Verteilereinheiten kontinuierlich überwacht.

Fig. 2 zeigt den inneren Aufbau eines Knotenrechners 111. Er besteht aus zwei Subsystemen, nämlich einem Kommunikationskontroller 210, der mit den replizierten Kommunikationskanälen 201 und 202 verbunden ist (entspricht 121 in Fig. 1), und einem Hostcomputer 220, auf dem die Anwendungsprogramme des Knotenrechners ausgeführt werden. Diese beiden Subsysteme sind miteinander über ein Communication Network Interface (CNI) 241 und eine Signalleitung 242 verbunden. Das Interface 241 enthält einen Speicher (Dual Ported RAM = DPRAM), auf den beide Subsysteme zugreifen können. Die beiden Subsysteme tauschen über diesen gemeinsamen Speicher bzw. Interface 241 die Kommunikationsdaten aus. Die Signalleitung 242 dient zur Ü- bertragung der synchronisierten Zeitsignale. Diese Signalleitung ist in der angeführten US 4,866,606 A genau beschrieben. Der Kommunikationskontroller 210, der autonom arbeitet, ver- fugt über eine Kommunikationskontrolleinheit 211 und eine Datenstruktur 212, die angibt, zu welchen Zeitpunkten Nachrichten gesendet und empfangen werden müssen. Die Datenstruktur 212 wird als Message Descriptor List (MEDL) bezeichnet.

Fig. 3 zeigt die Struktur einer Verteilereinheit mit integriertem Guardian. Eine solche Verteiler- einheit besteht aus Eingangsports 311, Ausgangsports 312, einem Datenverteiler 330 und einem Steuercomputer 340. Die Datenverbindungen 309 von dem Knotenrechner (entspricht 121 in Fig.

1), werden zu einem Eingangsport 311 und einem Ausgangsport 312 der Verteilereinheit geführt.

Das gleiche gilt für Datenverbindungen 302,303 und 304. Bei einer unidirektionalen Kommuni- kationsleitung können diese beiden Ports 311 und 312 auch getrennt mit entsprechenden Ports des Knotenrechners mit der Datenverbindung 301 verbunden werden. In jedem Eingangsport 311 befindet sich-neben den üblichen Filtem und, falls erforderlich, einer Potenzialtrennung-ein Schalter 313, der vom Steuercomputer 340 der Verteilereinheit über eine Signalleitung 314 ange- steuert werden kann und der dem Steuercomputer 340 mitteilt, wann auf diesem Port empfangen wird. Die Daten, die am Eingangsport 311 eintreffen, werden über den Datenverteiler 330 an die Ausgangsports 312, an den Steuercomputer 340 (über die Datenleitung 331) und an andere Ver- teilereinheiten (über den Kanal 351) weitergeleitet. Der Steuercomputer 340 verfügt auch über einen seriellen I/O Kanal 341, über den die statische Datenstruktur entsprechend Fig. 4 geladen werden kann und der periodisch Diagnosemeldung über den Zustand des Steuercomputers 340 an einen Wartungscomputer gibt. Falls erforderlich, können die Daten auf den Leitungen 312 vor dem Ausgang verstärkt werden. Solche, dem Stand der Technik entsprechenden Verstärker sind in der Fig. 3 nicht eingetragen.

Fig. 4 zeigt die Datenstruktur, die dem Steuercomputer 340 a priori, d. h. vor der Laufzeit, zur Verfügung gestellt wird. Diese Datenstruktur enthält für jeden Port bzw. Knotenrechner 111, 112,113,114 der Verteilereinheit einen eigenen Datensatz 411,412,413,414. In einem ersten Feld dieses Datensatzes 401 steht die Portnummer, auf die sich dieser Datensatz bezieht. In ei- nem zweiten Feld 402 steht die Sendedauer des mit dem Port verbundenen Knotens entsprechend der Eintragung in der Liste MEDL 212. In einem dritten Feld 403 steht die Dauer des Zeitinter- valls zwischen dem Ende des aktuellen Sendens bis zum Beginn des nächsten Sendens des mit dem Port verbundenen Knotens. In einem vierten Feld 404 steht die Nummer des zeitlich nächs- ten Ports. In einem fünften Feld 405 steht die Dauer des Zeitintervalls zwischen dem Ende des aktuellen Sendens bis zum Beginn des Sendens des Knotens am zeitlich nächsten Port. Im Feld 406 steht die Länge einer Initialisierungsnachricht, die auf dem aktuellen Port empfangen werden kann. Der Inhalt der Datenstruktur von Fig. 4 wird von einem Entwicklungstool in Abstimmung mit den Message Descriptor Lists 212 erstellt und vor der Laufzeit über den Kanal 341 in den Steuercomputer 340 geladen.

Fig. 5 zeigt die Struktur einer Initialisierungsnachricht. Die Initialisierungsnachricht muss in Header 501 ein ausgezeichnetes Bit 510 enthalten, das die Nachricht als Initialisierungsnachricht kennzeichnet. Im Datenfeld 502 der Initialisierungsnachricht stehen weitere Informationen, die für die Funktion einer einfachen Verteilereinheit ohne Bedeutung sind. Am Ende der Initialisie- rungsnachricht befindet sich das CRC Feld 503. Entsprechend leistungsfähige Verteilereinheiten können die Informationen im Datenfeld 502 einer Initialisierungsnachricht zusätzlich zur Erhö- hung der Fehlererkennungswahrscheinlichkeit auswerten. Zum Beispiel können solche leistungs- fähigere Verteilereinheiten das Zeitfeld einer TTP/C Initialisierungsnachricht auswerten, um den Uhrenstand des Senders mit der eigenen Uhr vergleichen zu können.

Fig. 6 zeigt die beiden wichtigsten inneren Zustände des Steuercomputers 340, einer Verteiler- einheit 101, unsynchronisiert 601 und synchronisiert 602. Nach Power-up 610 geht der Steuer- computer 340 in den Zustand"unsynchronisiert". In diesem Zustand sind alle Eingangports 311 mit dem Datenverteiler 330 verbunden. Sobald auf einem Eingangsport über die Datenleitung 331 (oder über den Kanal 352) vom Steuercomputer 340 eine korrekte Nachricht empfangen wird, stellt der Steuercomputer 340 über die Signalleitung 314 fest, über welchen Port empfangen wurde, speichert den Empfangszeitpunkt, überprüft die Länge der Nachricht durch Vergleich mit der im Feld 406 gespeicherten Länge und geht, bei positivem Ausgang der Prüfung, in den Zu- stand"synchronisiert"602, wobei der gespeicherte Empfangszeitpunkt der Initialisierungsnach- richt das Synchronisationsereignis darstellt. Im Zustand"synchronisiert"602 stellt der Steuer- computer 340 nur während der Zeitdauer 403 eine Verbindung am entsprechenden Eingangsport her. Wenn zum ungefähr richtigen Zeitpunkt eine beliebige Nachricht eintrifft, die den Codie- rungsvorschriften des gewählten Codierungssystems entspricht, dann verwendet der Steuercom- puter die gemessene Zeitdifferenz zwischen dem beobachteten und erwarteten Ankunftszeitpunkt der Nachricht, um seine Uhr über einen bekannten fehlertoleranten Algorithmus (z. B. Kopetz 1997, p. 61) nachzusynchronisieren. Wenn während eines a priori festgelegten Zeitintervalls dfauit-i keine korrekte Nachricht an irgendeinem der Kanäle 301 bis 304 oder 352 eintrifft, wech- selt die Verteilereinheit bzw. ihr Steuercomputer 340 in den Zustand"unsynchronisiert"601. Im synchronisierten Zustand 602 ist eine Nachricht korrekt, wenn sie mindestens die folgenden Kri- terien erfüllt : Sie trifft am Eingangsport ungefähr zum erwarteten Zeitpunkt ein, verfügt über ein korrektes CRC Feld 503 und hat die richtige Länge entsprechend dem Feld 406.

Der Steuercomputer 340 kommuniziert über die I/O Leitung 341 (dies sind die Leitungen 141 und 142 in Fig. 1) mit einem Wartungscomputer, der die Parametrisierung des Steuercomputers 340 vornimmt und die Funktion des Steuercomputers während des Betriebes überwacht.

Um zu verhindern, dass ein Einzelfehler im Taktgeber eines Knotenrechners, z. B. 111, der zu einer marginal falschen Kodierung der physikalischen Signale auf beiden Kanälen 201 und 202 des Knotenrechners 111 führen kann, über beide Verteilereinheiten an die Empfänger der Nach- richt durchschlägt, wird das eintreffende physikalische Signal in jeder Verteilereinheit unmittel- bar nach dem Empfangen unter Verwendung des lokalen Taktgebers der Verteilereinheit in ein Digitalsignal umgewandelt und unmittelbar vor dem Senden von der Verteilereinheit erneut in die physikalische Form umgewandelt (Signal Reshaping durch die Verteilereinheit). Damit wird ein marginal falsche Kodierung entweder in eine konsistent richtige Kodierung oder in eine kon- sistent falsche Kodierung abgebildet. Unter der Annahme, dass innerhalb einer TDMA Runde nur eine Fehlerursache auftritt, kann durch diese Maßnahme verhindert werden, dass ein Einzel- fehler im Zeitbereich oder im Wertebereich die Kodierung auf beiden Kanälen derart stört, dass im System Inkonsistenzen auftreten können.

Es ist eine wichtige Eigenschaft dieser Erfindung, dass der Steuercomputer 340 nur das Öffnen und Schließen der Schalter 313 bewirken kann, jedoch die vermittelten Nachrichten inhaltlich weder verändert, noch neue Nachrichten einfügt. Die einzige Ausfallart der Verteilereinheit ist daher ein fail-silent Ausfall eines Kommunikationskanals. In einer fehlertoleranten Konfiguration ist aber stets ein zweiter unabhängiger Kommunikationskanal vorhanden.

Abschließend sei festgehalten, dass sich die Erfindung nicht auf die beschriebene Realisierung mit vier Knotenrechnern und zwei Verteilereinheiten beschränkt, sondern beliebig erweiterbar ist. Sie ist nicht nur beim TTP/C Protokoll, sondern auch bei anderen zeitgesteuerten Protokollen anwendbar.