Die vorliegende Erfindung bezieht sich auf das Gebiet der Verfahren zur Leitwegberechnung (routing methods) für Netzwerksysteme, insbesondere auf vernetzte eingebettete Systeme (networked embedded systems), die eine Datenübertragungsplattform für mehrere Verarbeitungseinheiten bereitstellen.

Die Realisierung elektrischer Steuereinheiten oder Verarbeitungseinheiten befindet sich in ständigem Wachstum innerhalb der Struktur der Automobiltechnologie, der industriellen Fertigungstechnologie sowie der Unterhaltungselektronik oder bei Haushaltsgeräten. In solchen Systemen muss eine Verarbeitungseinheit typischerweise eine bestimmte vorgegebene Funktion erfüllen. Ein aus mehreren solchen Verarbeitungseinheiten bestehendes elektronisches System wird deshalb als ein vernetztes eingebettetes System bezeichnet.

Komplexe elektronische eingebettete Systeme bestehen aus einer großen Anzahl von elektrischen Steuereinheiten, die miteinander Daten austauschen müssen. Da heutzutage in hoch entwickelten Automobilen etwa 70 Verarbeitungseinheiten vorliegen, muss eine leistungsfähige und verlässliche Datenübertragungsplattform bereitgestellt werden. Typischerweise wird sowohl die Verbindung als auch die Datenübertragung unter den Verarbeitungseinheiten mit einer Art von Netzwerk realisiert.

Ein einfaches Netzwerk, das mehrere Verarbeitungseinheiten verbindet, ist mit dem so genannten einfachen oder geraden Busnetzwerk gegeben. In dieser Netzwerktopologie kann ein Bus, der alle Verarbeitungseinheiten verbindet, als eine Gerade dargestellt werden. Der Datenaustausch zwischen den Verarbeitungseinheiten wird von einer Bussteuereinheit, die mit jeder Verarbeitungseinheit verbunden ist, verwaltet. Die Kommunikation und die Datenübertragung zwischen den Verarbeitungseinheiten werden über die Bussteuereinheiten, die Datenübertragungsrechte für den Bus anfordern, reguliert.

Eine andere gebräuchliche Netzwerktopologie ist durch ein Ringnetzwerk gegeben. Dabei kann der Bus, der mehrere Verarbeitungseinheiten verbindet, durch einen geschlossenen Ring dargestellt werden. Der Zugriff auf das Netzwerk oder den Bus wird auf dieselbe Weise gehandhabt wie für das gerade Busnetzwerk, indem Bussteuereinheiten verwendet werden.

Ein üblicher Nachteil des geraden Busnetzwerks und des Ringnetzwerks ist ihre einzelne Fehlerstelle. Falls das Netzwerk oder das Bussystem zwischen zwei beliebigen Verarbeitungseinheiten unterbrochen wird, bricht die gesamte Datenübertragung über das Netz zusammen. Außerdem ist die Bandbreite solcher gerader Bus- oder Ringnetzwerke eingeschränkt, da zu einem bestimmten Zeitpunkt immer nur eine Verarbeitungseinheit auf den Bus zugreifen kann.

In der Sternnetzwerk-Topologie steuert ein zentraler Vermittler den Zugriff auf den Bus. Der Vermittler, der mit allen Verarbeitungseinheiten verbunden ist, handhabt den Zugriff auf ein externes Bussystem sowie den Austausch von Daten unter den einzelnen Verarbeitungseinheiten. Im Gegensatz zum Ringnetzwerk oder dem geraden Busnetzwerk kann der Vermittler mehrere Verbindungen zwischen verschiedenen Verarbeitungseinheiten gleichzeitig einrichten.

Wenn eine einzelne Verarbeitungseinheit ausfällt oder irgendwie vom zentralen Vermittler getrennt wird, bleibt die Funktionalität des Sternnetzwerks erhalten. Gleichwohl umfasst das Sternnetzwerk auch eine einzelne Fehlerstelle in Form des zentralen Vermittlers. Falls der zentrale Vermittler aus irgendeinem Grund defekt ist, bricht die Datenübertragung im gesamten Netzwerk zusammen.

Üblicherweise ist jede Verarbeitungseinheit in einer Fahrzeugumgebung für einen bestimmten Zweck vorgesehen und hat verschiedene Anforderungen in Bezug auf Echtzeit-Verhalten, Datenaustauschrate, Signalübertragung und Signalverarbeitung. Typischerweise sind in einem hoch entwickelten Fahrzeug eine große Anzahl von Verarbeitungseinheiten in mehreren, aber verschiedenen Netzwerksystemen, die oben beschrieben sind, angeordnet.

Da ein Datenaustausch unter zwei Verarbeitungseinheiten, die unterschiedlichen Netzwerksystemen angehören, realisiert werden muss, sind die verschiedenen Netzwerksysteme typischerweise über Gateway-Steuereinheiten verbunden. Die Gateway-Steuereinheiten regeln den Datenaustausch zwischen unterschiedlichen Bussystemen. Die Gesamtarchitektur der Datenübertragungsplattform zwischen den Verarbeitungseinheiten kann als heterogen beschrieben werden.

Solche heterogenen Netzwerke ergeben sich aus der fortwährend lernfähigen Umsetzung unterschiedlicher Datenübertragungstechnologien in vorhandene elektronische eingebettete Systeme. Die Gateway-Steuereinheit in einem derartigen heterogenen Netzwerksystem bringt zwei Hauptnachteile mit sich. Erstens stellt sie einen Engpass für den Datenaustausch innerhalb des Netzwerks dar, und zweitens repräsentiert sie eine einzelne Fehlerstelle. Falls eine Gateway-Steuereinheit ausfällt, kann das gesamte heterogene Netzwerk zusammenbrechen.

Des Weiteren erlaubt ein heterogenes Netzwerk nur eine eingeschränkte Leitwegberechnung (routing) von Nachrichten. Das Leiten bzw. Führen eine Nachricht zwischen verschiedenen zum heterogenen Netzwerk gehörenden Bussystemen, welche z.B. verschiedene Datenübertragungsraten haben, erfordert einen erheblichen Aufwand an Neuberechnung. Die Gateway-Steuereinheiten verlangen deshalb eine beträchtliche Leistungsfähigkeit, um ein schnelles und verlässliches Berechnen des Leitweges von Nachrichten innerhalb des heterogenen Netzwerks einzurichten.

Den üblichen Nachteilen der oben beschriebenen Sternbus- und Ringbustopologie sowie der heterogenen Netzwerktopologie kann im Allgemeinen mit einem neuronalen Netzwerk begegnet werden. Solche neuronalen Netzwerke zeichnen sich durch ein autonomes Lernverhalten aus. Wenn beispielsweise eine einzelne Verarbeitungseinheit ausfällt, kann ihre allgemeine Funktionalität von den verbleibenden Verarbeitungseinheiten übernommen werden. Neuronale Netzwerke haben deshalb keine einzelne Fehlerstelle oder einen Engpass in der Leitwegstruktur von Nachrichten. Der Nachteil von neuronalen Netzwerken ist ihr enormer Bedarf an Verarbeitungsleistung sowohl an die einzelnen Verarbeitungseinheiten als auch an die große Menge der Verbindungen zwischen den einzelnen Verarbeitungseinheiten, was deshalb zu einer sehr komplizierten Netzwerkarchitektur führt. Es ist deshalb unwahrscheinlich, dass sie in naher Zukunft für kostenbeschränkte eingebettete Verarbeitungssysteme anwendbar sind.

1 zeigt schematisch ein gerades Busnetzwerksystem. Eine Verarbeitungseinheit 100 ist an eine Bussteuereinheit 102 angeschlossen, die mit dem Bus 104 verbunden ist. Der Datenaustausch zwischen verschiedenen Verarbeitungseinheiten 100 wird über die Bussteuereinheiten 102 mit dem geraden Bus 104 als Datenübertragungsplattform gesteuert. Um eine Nachricht über den Bus 104 zu übertragen, muss jede Verarbeitungseinheit 100 über die Bussteuereinheit 102 eine Berechtigung für den Bus anfordern.

1b zeigt eine ähnliche Netzwerkarchitektur in Form eines Ringbussystems. Die Verarbeitungseinheiten 110 sind an die Bussteuereinheiten 112 angeschlossen, die mit dem Ringbus 114 verbunden sind. Der Datenaustausch zwischen verschiedenen Verarbeitungseinheiten wird durch den Ringbus 114 bereitgestellt und von den Bussteuereinheiten 112 gesteuert.

1c veranschaulicht ein Blockschaltbild einer Sternnetzwerk-Topologie. Dabei sind die einzelnen Verarbeitungseinheiten 120 auch mit den Bussteuereinheiten 122 verbunden, die an einen zentralen Vermittler 124 angeschlossen sind. Abhängig von den von der Bussteuereinheit 122 ausgesendeten Anforderungen richtet der zentrale Vermittler 124 Verbindungen zwischen einzelnen Verarbeitungseinheiten ein. Diese Topologie erlaubt z.B. eine gleichzeitige Übertragung von Daten zwischen mehreren Paaren von Verarbeitungseinheiten.

1d veranschaulicht ein Blockschaltbild einer heterogenen Netzwerkstruktur. Das heterogene Netzwerk besteht aus mehreren Teilnetzwerken, die unterschiedliche Topologien aufweisen. In diesem Beispiel werden ein gerader Bus 104, ein Ringbus 144 und der zentrale Vermittler 124 eines Sternnetzwerks mit zwei Gateway-Steuereinheiten 130 und 140 miteinander verknüpft.

Falls die Verarbeitungseinheit 110, die einem Ringbus-Teilnetzwerk 114 angehört, eine Nachricht an eine Verarbeitungseinheit 100 senden möchte, die einem Teilnetzwerk 104 mit geradem Bus angehört, muss die Gateway-Steuereinheit 130 die Verbindung zwischen den beiden Teilnetzwerken einrichten sowie schließlich die Unterschiede der abweichenden Datenübertragungsprotokolle zwischen den unterschiedlichen Teilnetzwerken 104 und 114 übersetzen.

Auf dieselbe Weise stellt die Gateway-Steuereinheit 140 die Übertragung von Daten zwischen dem zentralen Vermittler 124 des Stern-Teilnetzwerks und dem Ringbusnetzwerk 114 bereit. Die Kommunikation unter den Verarbeitungseinheiten 120, die dem Sternnetzwerk angehören, und den Verarbeitungseinheiten 100, die dem geraden Busnetzwerk angehören, muss mit den beiden Gateway-Steuereinheiten 130 und 140 eingerichtet werden. Ein Austausch von Daten zwischen der Verarbeitungseinheit 100 und der Verarbeitungseinheit 120 stellt deshalb hohe Anforderungen an die Rechnerressourcen der Gateway-Steuereinheiten 130 und 140.

Die in 1a bis d dargestellten Blockschaltbilder stellen gewöhnliche Netzwerktopologien für Datenübertragungszwecke dar. Ein üblicher Nachteil dieser Netzwerke ist durch einzelne Fehlerstellen und Engpässe gegeben. Falls das Bussystem 104 bzw. 114 in 1a oder 1b unterbrochen wird, bricht die Datenübertragung des gesamten Netzwerks völlig zusammen. Wenn in 1c der zentrale Vermittler 124 ausfällt, fällt gleichermaßen das gesamte Netzwerk aus.

Wenn in 1d der gerade Bus 104 oder der Ringbus 114 oder der zentrale Vermittler 124 ausfallen, kann das betreffende Teilnetzwerk zusammenbrechen, aber der verbleibende Teil des heterogenen Netzwerks arbeitet weiterhin. Gleichwohl begrenzen auch hier die Gateway-Steuereinheiten 130 und 140 die Bandbreite der gesamten Datenübertragung im Netz und stellen Engpässe oder einzelne Fehlerstellen des heterogenen Netzwerks dar.

Die US-Patentanmeldung 2001/0036183 beschreibt ein Verfahren zum Führen von Daten über ein Netzwerk, wobei Kontakt mit einem Heimnetzwerk geschlossen wird, um die gemeldete Geoposition zu ermitteln, und wobei diese Geoposition zur Datenübertragung an die Einheit auf einem Pfad über einen Knoten verwendet wird, wobei der Knoten in dem Pfad die Geoposition liest, auf eine Liste möglicher Empfänger und deren Geopositionen zugreift, seine Lage mit den Positionen vergleicht, einen Empfänger zumindest teilweise basierend auf der Nähe des Empfängers zu der Einheit auswählt und die Daten über den besten Pfad überträgt. Schließlich wird die Einheit zum Empfänger. Eine Geoposition kann als Teil einer IP-Adresse gesendet werden. Die Geopositions-Daten können von einem GPS-Empfänger erzeugt werden. Dieses Verfahren und/oder die IP-Adresse kann in einem Verfahren des Wirtschaftslebens eingesetzt werden, in dem die Geoposition zum Identifizieren der Quelle und des Standortes zur Belieferung verwendet wird. Diese Informationen können in eine Bestellung oder in eine Empfangsbestätigung eingebettet sein.

Die vorliegende Erfindung stellt eine Netzwerktopologie und ein neues Verfahren zum Führen von Nachrichten für ein vernetztes eingebettetes Computersystem bereit. Jeder Verarbeitungseinheit wird eine virtuelle Adresse zugewiesen. Die virtuelle Adresse bezieht sich typischerweise auf ein räumliches Koordinatensystem. Das Koordinatensystem kann ein-, zwei-, drei- oder mehrdimensional sein. Gemäß der Wahl des Koordinatensystems ist jede Verarbeitungseinheit mit mehreren benachbarten Verarbeitungseinheiten verbunden.

In einem idealen zweidimensionalen Koordinatensystem ist jede Verarbeitungseinheit an vier benachbarte Verarbeitungseinheiten angeschlossen, und in einem idealen dreidimensionalen Koordinatensystem ist jede Verarbeitungseinheit an sechs benachbarte Verarbeitungseinheiten angeschlossen. Die Anzahl der benachbarten Verarbeitungseinheiten in einem zwei- oder dreidimensionalen Koordinatensystem kann jedoch auch geringer als die oben erwähnten Zahlen sein. In diesem Fall muss nicht jede unter Umständen redundante Verbindung zwischen Verarbeitungseinheiten eingerichtet sein. Ferner umfasst eine Verarbeitungseinheit einen Berechnungsalgorithmus für das Führen von Nachrichten. Eine Nachricht, die an eine bestimmte Zielverarbeitungseinheit übertragen werden muss, umfasst die virtuelle Adresse der betreffenden Zielverarbeitungseinheit.

Gemäß einer bevorzugten Ausführungsform der Erfindung wird eine Nachricht zuerst von einer Verarbeitungseinheit empfangen. In einem nächsten Schritt vergleicht die Verarbeitungseinheit die virtuelle Zieladresse der Nachricht mit ihrer eigenen virtuellen Adresse. Abhängig von ihrem gespeicherten Algorithmus ermittelt die Verarbeitungseinheit eine ihrer benachbarten Verarbeitungseinheiten, die direkt an sie angeschlossen sind.

Die Ermittlung einer benachbarten Verarbeitungseinheit erfolgt anhand des räumlichen Koordinatensystems und der virtuellen Zieladresse der Nachricht, sodass die Entfernung zwischen der virtuellen Zieladresse und der virtuellen Adresse einer benachbarten Verarbeitungseinheit so klein wie möglich wird. Wenn eine benachbarte Verarbeitungseinheit ermittelt wurde, wird die Nachricht an die benachbarte Verarbeitungseinheit gesendet. Diese Prozedur wiederholt sich, solange die virtuelle Zieladresse der Nachricht nicht mit der virtuellen Adresse einer Verarbeitungseinheit übereinstimmt. Wenn schließlich die virtuelle Zieladresse der Nachricht mit der virtuellen Adresse einer Verarbeitungseinheit übereinstimmt, wird die Nachricht von der Verarbeitungseinheit bearbeitet.

Dieses Nachrichten-Leitwegberechnungsverfahren, das auf der beschriebenen Netzwerktopologie der Erfindung beruht, hat mehrere Vorteile im Vergleich zu herkömmlichen Nachrichten-Leitwegberechnungsverfahren, die auf geraden Bus-, Ringbus- oder Sternbus-Netzwerktopologien beruhen. Das Netzwerk der vorliegenden Erfindung weist weder Engpässe noch einzelne Fehlerstellen auf. Wenn in einem zwei- oder dreidimensionalen Netzwerk beispielsweise eine einzelne Verarbeitungseinheit ausfällt, kann ihre Funktionalität, Nachrichten zu leiten, von den verbleibenden Verarbeitungseinheiten bereitgestellt werden.

Gemäß einer weiteren bevorzugten Ausführungsform der Erfindung prüft die sendende Verarbeitungseinheit, ob die empfangende Verarbeitungseinheit eine Nachricht empfangen kann. Die Nachricht wird dann von der sendenden Verarbeitungseinheit an die empfangende Verarbeitungseinheit nur übertragen, falls Letztere in der Lage ist, die Nachricht zu empfangen und zu verarbeiten.

Eine empfangende Verarbeitungseinheit kann aus mehreren Gründen gegebenenfalls nicht in der Lage sein, eine Nachricht zu empfangen oder zu verarbeiten. Sie könnte ausgelastet sein, während sie eine Nachricht verarbeitet oder eine andere Nachricht weiterleitet, oder sie könnte einfach defekt sein. In letzterem Fall antwortet sie nicht auf die Anforderung der sendenden Verarbeitungseinheit. Die Nachricht wird deshalb von der sendenden Verarbeitungseinheit nicht an diese empfangende, sondern an eine andere Verarbeitungseinheit gesendet.

Deshalb bringen sowohl die Netzwerktopologie als auch das Leitwegberechnungsverfahren der Erfindung ein autonomes Verhalten mit sich. Der Ausfall einer bestimmten Systemkomponente hat nur eine untergeordnete Auswirkung auf das gesamte Netzwerksystem. Außerdem kann der Ausfall automatisch kompensiert werden, ohne dass ein Eingriff des Teilnehmers erforderlich ist. Vor allem dieses autonome Verhalten stellt eine hohe Verlässlichkeit und eine Langzeitstabilität des gesamten Netzwerks bereit.

Die Erfindung stellt ein Verfahren zum Leiten von Nachrichten ohne eine Berechnung des vollständigen Leitweges zwischen zwei beliebigen Verarbeitungseinheiten bereit. Das gesamte Leiten von Nachrichten wird in kleine Schritte unterteilt, die von den einzelnen Verarbeitungseinheiten gehandhabt werden. Die einzelnen Verarbeitungseinheiten befassen sich nicht mit dem Gesamtablauf des Leitens von Nachrichten, sondern nur mit dem Leiten zu einem nächsten Nachbarn.

Ein weiterer Vorteil der vorliegenden Erfindung besteht darin, dass die einzelnen Verarbeitungseinheiten keine Informationen über die Adressen der anderen Verarbeitungseinheiten des vernetzten eingebetteten Systems benötigen. Stattdessen benötigt eine einzelne Verarbeitungseinheit nur ihre eigene Adresse und die Adresse ihrer nächsten Nachbarn, an die sie direkt angeschlossen ist. Insbesondere erfordert das Verfahren der räumlich verknüpften Datenübertragung keinerlei Nachschlagetabelle, indem es eine Abbildung zwischen dem physischen Adressraum der einzelnen Verarbeitungseinheiten und dem auf dem ein-, zwei- oder dreidimensionalen Koordinatensystem beruhenden Adressraum bereit stellt. Die Rechnerressourcen für die Berechnung der Leitung von Nachrichten sind daher von relativ einfacher Art.

Gemäß einer weiteren bevorzugten Ausführungsform der Erfindung können das kombinierte Leitwegberechnungsverfahren und die Netzwerktopologie der vorliegenden Erfindung universell auf eine Vielfalt von Netzwerksystemen und Datenübertragungsprotokollen angewendet werden. Den Nachrichten, die zwischen den verschiedenen Verarbeitungseinheiten transferiert werden, ist eine virtuellen Adresse für das Datenübertragungsnetzwerk zugewiesen, und sie umfassen beliebige Datenfolgen wie z.B. Nachrichten, die einem unterschiedlichen Datenübertragungsprotokoll entsprechen.

Insbesondere diese Universalität der Nachrichten macht es sehr attraktiv, Gateway-Steuereinheiten in einem heterogenen Netzwerk durch Verarbeitungseinheiten der Erfindung zu ersetzen. In einer solchen Umsetzung stellt jede Verarbeitungseinheit der Erfindung ein Teilnetzwerk dar. Ein Nachrichtenaustausch zwischen verschiedenen Teilnetzwerken wird dann verwirklicht, indem die Nachrichten der Teilnetzwerke in die Nachrichten der vorliegenden Erfindung gekapselt werden.

Gemäß einer bevorzugten Ausführungsform der Erfindung zieht das Leitverfahren für Nachrichten verschiedene Nachrichteneigenschaften in Betracht wie beispielsweise eine Nachrichtenpriorität oder eine Nachrichtendringlichkeit und unterschiedliche Anforderungen an Übertragungsarten wie z.B. synchron, asynchron oder isochron. Das Verfahren erlaubt ferner eine datenpaketvermittelte sowie eine leitungsvermittelte Übertragung von Nachrichten. In der Leitungsvermittlungs-Betriebsart wird ein Leitpfad einer Nachricht, der verschiedene Verarbeitungseinheiten verbindet, eingerichtet und aufrechterhalten, bis eine ganze Nachricht zwischen einer Quellverarbeitungseinheit und einer Zielverarbeitungseinheit übertragen wurde.

Gemäß einer anderen bevorzugten Ausführungsform der Erfindung wird das autonome Verhalten des Netzwerks verbessert. Ein möglicher Ausfall einer bestimmten Verarbeitungseinheit wird von den umgebenden, benachbarten Verarbeitungseinheiten erkannt. Als eine Folge davon reagieren die umgebenden Verarbeitungseinheiten auf diesen Ausfall und senden keine Nachrichten mehr an die bestimmte defekte Verarbeitungseinheit.

Gemäß einer weiteren bevorzugten Ausführungsform der Erfindung kann eine Nachricht auch in eine der Zielverarbeitungseinheit entgegengesetzte Richtung geleitet werden. Dies geschieht in einer Situation, wenn eine Verarbeitungseinheit eine Nachricht an eine Zielverarbeitungseinheit senden möchte, und die Verarbeitungseinheit von vier benachbarten Verarbeitungseinheiten umgeben ist, von denen drei aus irgendeinem Grund nicht in der Lage sind, die Nachricht zu verarbeiten oder zu empfangen. Des Weiteren verläuft der kürzeste Nachrichtenpfad, um eine Zielverarbeitungseinheit zu erreichen, über eine der benachbarten Verarbeitungseinheiten, die momentan nicht verfügbar sind. In einer solchen kritischen Situation führt das Verfahren zur Ermittlung der von den benachbarten Verarbeitungseinheiten verbleibenden Einheit. Auf diese Weise ist es gewährleistet, dass die Nachricht weiter durch das Netzwerk übertragen wird, falls der kürzeste Pfad blockiert ist. Das vorliegende Leitwegberechnungsverfahren findet nicht notwendigerweise den kürzesten Weg für die Nachricht, aber abhängig von der Auslastung des Netzwerks kann eine Nachricht über eine enorme Vielfalt von alternativen, für Nachrichten geeignete Pfade geleitet werden. Je nach der vorgegebenen Situation wählt das Leitwegberechnungsverfahren automatisch den besten Pfad in Hinblick auf die momentanen allgemeinen Umstände wie z.B. Systemauslastung, Ausfall bestimmter Verarbeitungseinheiten, die Priorität von Nachrichten und die gegebene Netzwerktopologie.

Im Folgenden werden bevorzugte Ausführungsformen der Erfindung ausführlicher beschrieben, indem Bezug auf die Zeichnung genommen wird, in denen

1a ein Blockschaltbild eines Netzwerkes vom Typ des geraden Bus zeigt,

1b ein Blockschaltbild eines Netzwerksystems mit einer Ringbustopologie zeigt,

1c ein Blockschaltbild einer Sternnetzwerk-Topologie zeigt,

1d ein Blockschaltbild eines heterogenen Netzwerksystems zeigt,

2a ein Blockschaltbild einer zweidimensionalen Ausführungsform der Erfindung zeigt,

2b ein Blockschaltbild einer bevorzugten Ausführungsform der Erfindung im Datenpaket-Vermittlungsmodus zeigt,

2c ein Blockschaltbild einer bevorzugten Ausführungsform der Erfindung im Leitungsvermittlungs-Modus zeigt,

3 ein Flussdiagramm des Leitwegberechnungsverfahrens für Nachrichten der Erfindung veranschaulicht,

4 ein Blockschaltbild einer von der Erfindung verarbeiteten Nachricht zeigt,

5 ein Blockschaltbild einer Verarbeitungseinheit der Erfindung zeigt,

6 ein Blockschaltbild einer Zentraleinheit einer Verarbeitungseinheit der Erfindung zeigt.

2a zeigt eine zweidimensionale Ausführungsform der Erfindung. Die Figur veranschaulicht sechs Verarbeitungseinheiten 200, 210, 220, 230, 240 und 250, die feldartig angeordnet sind. Jede der Verarbeitungseinheiten ist Idealerweise an vier benachbarten Verarbeitungseinheiten über horizontale Verbindungen 202 und vertikale Verbindungen 204 angeschlossen. Außerdem wird jeder Verarbeitungseinheit eine virtuelle Adresse zugeteilt, die der Position der Verarbeitungseinheit in dem zweidimensionalen Feld entspricht. Die von diesen Verarbeitungseinheiten abgewickelten Nachrichten umfassen eine zweidimensionale virtuelle Adresse, die der Zielverarbeitungseinheit, an die die Nachricht übertragen werden muss, entspricht.

2b veranschaulicht dasselbe Netzwerk wie in 2a für den Fall, in dem die Verarbeitungseinheit 230 mit den räumlichen Koordinaten (0, 0) eine Nachricht an die Verarbeitungseinheit 220 mit den räumlichen Koordinaten (1, 2) senden möchte. Abhängig von der virtuellen Zieladresse der Nachricht (1, 2) und der eigenen Adresse der Verarbeitungseinheit 230 sowie abhängig von einem Berechnungsalgorithmus ermittelt die Verarbeitungseinheit 230 eine ihrer benachbarten Verarbeitungseinheiten 240 oder 200, an die die Nachricht gesendet werden muss. Vor dem Verschicken der Nachricht an eine der benachbarten Verarbeitungseinheiten 200 oder 240 prüft die Verarbeitungseinheit 230, ob die benachbarten Verarbeitungseinheiten 200 oder 240 in der Lage sind, die Nachricht zu empfangen. Angenommen, die Verarbeitungseinheit 200 ist nicht in der Lage, die Nachricht von der Verarbeitungseinheit 230 zu empfangen, und die Verarbeitungseinheit 240 kann die Nachricht von der Verarbeitungseinheit 200 empfangen, so wird die Nachricht über eine Verbindung 220 von der Verarbeitungseinheit 230 an die Verarbeitungseinheit 240 übertragen.

Nachdem die Nachricht bei der Verarbeitungseinheit 240 angekommen ist, verfährt die Verarbeitungseinheit 240 auf dieselbe Weise wie die Verarbeitungseinheit 230 im vorherigen Schritt. Abhängig von dem Berechnungsalgorithmus und der Verfügbarkeit der Verarbeitungseinheiten 210 und 250 wird die Nachricht entweder an die Verarbeitungseinheit 250 oder die Verarbeitungseinheit 210 übertragen. Die Verarbeitungseinheit 250 oder 210 verfährt auf dieselbe Weise und überträgt die Nachricht an die Zielverarbeitungseinheit 220.

Gemäß der in 2b dargestellten idealen Konfiguration sind drei verschiedene Pfade vorhanden, auf denen die Nachricht die Zielverarbeitungseinheit über zwei zwischenliegende Verarbeitungseinheiten erreicht. Bereits in dieser einfachen Konfiguration stellt das Netzwerk mehrere alternative Pfade für eine Nachricht zur Verfügung, falls eine bestimmte Verarbeitungseinheit ausgelastet oder defekt ist, oder eine Verbindung zwischen zwei beliebigen Verarbeitungseinheiten unterbrochen wird.

In einer bevorzugten Ausführungsform der Erfindung erfolgt die Ermittlung einer benachbarten Verarbeitungseinheit, an die die Nachricht übertragen werden muss, so, dass die Entfernung zur Zielverarbeitungseinheit so klein wie möglich wird.

Angenommen, die Verarbeitungseinheit 230 möchte die Nachricht an die Verarbeitungseinheit 240 senden, die die Nachricht aber nicht empfangen kann, so wählt die Verarbeitungseinheit 230 die Verarbeitungseinheit 200 als Empfänger der Nachricht aus.

Falls nun aus einem der oben genannten Gründe die Verarbeitungseinheit 200 ebenfalls nicht in der Lage ist, die Nachricht von der Verarbeitungseinheit 230 zu empfangen, ermittelt die Verarbeitungseinheit 230 eine andere ihrer vier benachbarten Verarbeitungseinheiten, an die die Nachricht gesendet werden kann. In einem solchen Fall würde die Nachricht in einer zur Zielverarbeitungseinheit 220 entgegengesetzten Richtung übertragen. So ist es sichergestellt, dass das Führen der Nachricht nicht endet, bevor die Nachricht ihre Zielverarbeitungseinheit erreicht hat.

Gemäß einer weiteren Ausführungsform der Erfindung kann die Nachricht, die zwischen der Verarbeitungseinheit 230 und der Verarbeitungseinheit 220 übertragen werden muss, einen Prioritätsbezeichner umfassen, der der Nachricht eine höchste oder Echtzeit-Priorität zuweist. Angenommen, die Verarbeitungseinheit 230 möchte die Nachricht für die Übertragung an ihre virtuelle Zieladresse an die Verarbeitungseinheit 240 senden, die momentan eine andere Nachricht mit einer geringeren Priorität von der Verarbeitungseinheit 210 empfängt. In einem solchen Fall würde die Übermittlung der Nachricht mit geringerer Priorität zugunsten der Nachricht mit höherer Priorität unterbrochen werden. Auf diese Weise stellt das Netzwerk ein Echtzeitverhalten zur Verfügung und hält die für die Leitwegberechnungsprozedur nötige Zeitdauer so gering wie möglich.

2c zeigt ein Blockschaltbild einer weiteren bevorzugten Ausführungsform der Erfindung, das einen Leitungsvermittler aufweist. Gemäß dieser idealen Ausführungsform wird ein Nachrichtenpfad eingerichtet, der mehrere Verarbeitungseinheiten zwischen der Quellverarbeitungseinheit und der Zielverarbeitungseinheit verbindet. Das Leiten der Nachricht von der Verarbeitungseinheit 230 an die Verarbeitungseinheit 220 wird mit einem Nachrichtenpfad realisiert, der die Verarbeitungseinheit 230 mit der Verarbeitungseinheit 240, die Verarbeitungseinheit 240 mit der Verarbeitungseinheit 250 und die Verarbeitungseinheit 250 mit der Verarbeitungseinheit 220 verbindet.

Der so eingerichtete Datenübertragungspfad wird durch die dicken Pfeile 260, 262 und 264 angegeben. In diesem Modus der Leitungsvermittlung wird die Verbindung 260 zwischen den Verarbeitungseinheiten 230 und 240 eingerichtet, bis die Verarbeitungseinheit 230 einen Freigabebezeichner von der Zielverarbeitungseinheit 220 empfängt. Dasselbe gilt für die Verarbeitungseinheiten 240 und 250.

Die Zeichnungen in den Fig. (a) bis (c) stellen ideale Umsetzungen eines zweidimensionalen Netzwerks nach der vorliegenden Erfindung dar. Andere Umsetzungen, in denen nicht jede Verbindung zwischen benachbarten Verarbeitungseinheiten besteht, sind alternativ ausführbar, um Kosten zu senken und die Wirtschaftlichkeit des Herstellungsprozesses zu steigern.

3 stellt ein Flussdiagramm für den von einer einzelnen Verarbeitungseinheit ausgeführten Leitwegberechnungsalgorithmus dar. In einem ersten Schritt 300 wird die Nachricht von der Verarbeitungseinheit analysiert. Im Schritt 300 wird zumindest der Ursprung der Nachricht, das Ziel der Nachricht und schließlich ein bestimmter Nachrichtentyp aus dem Nachrichtenvorsatz erzeugt. In Schritt 302 wird die virtuelle Zieladresse der Nachricht mit der virtuellen Adresse der Verarbeitungseinheit verglichen. Falls in Schritt 302 die virtuelle Adresse der Nachricht mit der virtuellen Adresse der Verarbeitungseinheit übereinstimmt, wird die Nachricht von der Verarbeitungseinheit in Schritt 304 verarbeitet.

Falls in Schritt 302 eine virtuelle Zieladresse der Nachricht nicht mit der virtuellen Adresse der Verarbeitungseinheit der Nachricht übereinstimmt, wird die Nachricht in Schritt 306 weiterverarbeitet. In Schritt 306 werden die Nachrichtenpriorität und der Nachrichtentyp ermittelt. Dann fährt das Verfahren mit Schritt 308 fort, in dem eine Nachrichtenübertragung berechnet wird. Gemäß der berechneten Übertragung der Nachricht wird im folgenden Schritt 310 eine benachbarte Verarbeitungseinheit ermittelt. Das Verfahren fährt dann mit Schritt 312 fort. In Schritt 312 prüft das Verfahren, ob die ermittelte benachbarte Verarbeitungseinheit aus Schritt 310 die Nachricht empfangen kann.

Falls in Schritt 312 die ermittelte benachbarte Verarbeitungseinheit die Nachricht empfangen kann, wird die Nachricht anschließend in Schritt 314 an sie gesendet. Falls in Schritt 312 die benachbarte Verarbeitungseinheit keine Nachricht empfangen kann, so kehrt das Verfahren zu Schritt 310 zurück und ermittelt eine andere benachbarte Verarbeitungseinheit.

4 stellt ein Blockschaltbild der Nachricht 400 dar, die durch die Verarbeitungseinheit der vorliegenden Erfindung übertragen und verarbeitet wird. Die Nachricht 400 besteht aus drei verschiedenen Teilen: ein Nachrichtenvorsatz 402, ein Datenpaket 404 und ein Nachrichtenanhang 406. Der Nachrichtenvorsatz 402 umfasst eine virtuelle Zieladresse, eine virtuelle Quelladresse, einen Prioritätsbezeichner und einen Bezeichner der Übertragungsart, der angibt, ob die Nachricht synchron, asynchron oder isochron übertragen wird, und ob die Nachricht in einem paketvermittelten oder leitungsvermittelten Modus übertragen werden soll. Weiterhin definiert der Nachrichtenvorsatz auch eine maximal zulässige Latenzzeit, die ein Zeitintervall definiert, innerhalb dessen eine benachbarte Verarbeitungseinheit eine Anforderung einer Verarbeitungseinheit beantworten muss, um als zum Empfangen einer Nachricht fähig identifiziert zu werden.

Das Datenpaket 404 umfasst eine beliebige Datenfolge. Diese beliebige Datenfolge kann einer gekapselten Originalnachricht entsprechen, die zu einem anderen Teilnetzwerk mit einem abweichenden Datenübertragungsprotokoll gehört. Schließlich gibt der Anhang der Nachricht 406 das Ende der Nachricht an.

5 zeigt ein Blockschaltbild einer Verarbeitungseinheit in der zweidimensionalen Ausführungsform, wie sie in 2a dargestellt ist. Die Verarbeitungseinheit 500 besteht Idealerweise aus vier verschiedenen Anschlüssen 502, einer Zentraleinheit 506 sowie vier Verbindungen 508 zwischen der Zentraleinheit 506 und jeder der vier Anschlüsse 502. Jeder Anschluss 502 hat eine Verbindung 504 zu einer benachbarten Verarbeitungseinheit. Zwar stellt eine solche Konfiguration einen Idealfall dar, es sind jedoch auch alternative Ausführungsformen möglich, in denen nicht zu jedem nächsten Nachbarn eine Verbindung vorhanden ist. In einem solchen Fall umfasst die Verarbeitungseinheit 500 eine Anzahl von Anschlüssen 502, die der Anzahl der nächsten Nachbarn entspricht, an die die Verarbeitungseinheit 500 direkte angeschlossen ist.

6 zeigt ein Blockschaltbild einer Zentraleinheit. Die Zentraleinheit 600 umfasst eine Steuereinheit 602, einen Vermittler 604, mehrere Verbindungen zu den Anschlüssen 606, einen Nachrichtenumformer 608, ein Steuerungsspeicher-Modul 610, eine Nachschlagetabelle 612 sowie ein Parameterregister-Modul 614 und ein Register 616. Die Verbindungen zu den Anschlüssen 606, welche die Zentraleinheit 600 mit den Anschlüssen der Verarbeitungseinheiten verbinden, sind an den Vermittler 604 angeschlossen. Der Vermittler 604 ist an den Nachrichtenumformer 608 über eine bidirektionale Verbindung angeschlossen. Der Nachrichtenumformer 608 ist an die Steuereinheit 602 über eine bidirektionale Verbindung und die Steuereinheit 602 an den Vermittler 604 über eine unidirektionale Verbindung angeschlossen. Die Steuereinheit 602 ist ferner über eine bidirektionale Verbindung an das Parameterregister-Modul 614 angeschlossen. Die Nachschlagetabelle 612 ist bidirektional mit der Steuereinheit 602 verbunden, und die Steuereinheit 610 ist unidirektional mit der Steuereinheit 602 verbunden. Wenn eine Nachricht in der Zentraleinheit 600 durch den Vermittler 604 empfangen wurde, wird sie an den Nachrichtenumformer 608 geleitet. Der Nachrichtenumformer 608 decodiert die virtuelle Adresse der Nachricht und leitet die decodierten Daten weiter an die Steuereinheit 602.

Die Steuereinheit 602 führt eine Entscheidungsprozedur zum Führen der Nachricht mit Hilfe eines Berechnungsalgorithmus aus, der im Steuerspeicher-Modul 610 gespeichert vorliegt. Abhängig von der virtuellen Adresse der Verarbeitungseinheit, die im Register 616 gespeichert ist, ermittelt die Steuereinheit 602 eine benachbarte Verarbeitungseinheit, an die die Nachricht gesendet werden muss. Gemäß dieser Ermittlung weist die Steuereinheit 602 den Vermittler 604 an, die entsprechende Verbindung zu dem zugehörigen Anschluss zu einzurichten. Die Nachricht wird dann über den Nachrichtenumformer 608 übertragen, und der Vermittler 604 richtet eine Verbindung mit dem zugehörigen Anschluss und schließlich mit der zugehörigen benachbarten Verarbeitungseinheit ein.

Die Nachschlagetabelle 612 ist ein optionales Ausstattungsmerkmal, wenn die Verarbeitungseinheit zusätzlich an ein anderes nicht räumlich verknüpftes Teilnetzwerk angeschlossen ist, das z.B. auf einem CAN-Bus oder LIN-Bus beruht. Die Nachschlagetabelle 612 zur Zuordnung von früheren Adressen, die an die Steuereinheit 602 angeschlossen ist, speichert eine Tabelle zur Adressübersetzung für die Konvertierung der virtuellen Adressen und den möglicherweise beteiligten, nicht räumlich verknüpften physischen Adressen der einzelnen Verarbeitungseinheiten sowie von Verarbeitungseinheiten, die zu einem Teilnetzwerk gehören.

Das Register 616 ist im Gegensatz dazu ein wesentliches Ausstattungsmerkmal der Zentraleinheit 600, da es die mit dem virtuellen Raum verknüpften Adressen der Verarbeitungseinheit speichert, was zum Leiten der Nachrichten erforderlich ist. Vorzugsweise ist das Register 616 als nichtflüchtiger Speicher ausgeführt.

Das Parameterregister-Modul 614, das bidirektional an die Steuereinheit 602 angeschlossen ist, speichert die Parameter des Nachrichtenzustands und des Nachrichtentyps, die für den von der Steuereinheit 602 zum Führen der Nachricht ausgeführten Algorithmus erforderlich sind.

100

Verarbeitungseinheit

102

Bussteuereinheit

104

Netzwerk

110

Verarbeitungseinheit

112

Bussteuereinheit

114

Ringnetzwerk

120

Verarbeitungseinheit

122

Bussteuereinheit

124

zentraler Vermittler

130

Gateway-Steuereinheit

140

Gateway-Steuereinheit

200

Verarbeitungseinheit

202

Verbindung

204

Verbindung

210

Verarbeitungseinheit

220

Verarbeitungseinheit

230

Verarbeitungseinheit

240

Verarbeitungseinheit

250

Verarbeitungseinheit

260

Verbindung

262

Verbindung

264

Verbindung

400

Nachricht

402

Nachrichtenvorsatz

404

Datenpaket

406

Anhang der Nachricht

500

Verarbeitungseinheit

502

Port

504

Verbindung

506

Zentraleinheit

508

Verbindung

600

Zentraleinheit

602

Steuereinheit

604

Vermittler

606

Verbindung

608

Nachrichtenumformer

610

Steuerspeicher-Modul

612

Nachschlagetabelle

614

Parameterregister-Modul

616

Register