-
Die Erfindung bezieht sich auf
Mehrfachknoten-Datenverarbeitungssysteme.
-
US-Patent Nr. 4 562 539 beschreibt ein
Datenverarbeitungssystem mit einer Mehrzahl von Datenverarbeitungsknoten, die
miteinander über eine Datenübertragungsverbindung verbunden
sind. Jeder Knoten weist seinen eigenen Datenspeicher auf,
der Datenausdrücke speichert, die speziell diesem Knoten
zugeordnet sind, und der auch Kopien von gemeinsam benutzten
Datenausdrücken aufnimmt, die allen Knoten gemeinsam sind.
Wenn ein Knoten einen der gemeinsam benutzten Datenausdrücke
fortschaltet, überträgt er eine Fortschalt-Nachricht über die
Verbindung an alle anderen Knoten, damit sie ebenfalls ihre
Kopien des Datenausdruckes fortschalten können. Auf diese
Weise werden alle Kopien in der richtigen Reihenfolge
gehalten. Um sicherzustellen, daß die richtige Chronologie
der Fortschaltung aufrecht erhalten wird, ist es notwendig,
daß jeder Knoten alle Fortschalt-Nachrichten in der gleichen
Folge empfängt.
-
Ferner tragen bei Nahbereichsnetzwerken Folgezahlen dazu bei,
die Reihenfolge von Paketen während des Datenflusses zwischen
zwei Knoten einwandfrei beizubehalten. Pakete mit einer
Folgezahl, die aus der Reihe fällt, werden ignoriert (siehe
Hopper et al "LOCAL AREA NETWORK DESIGN" Addison-Wesley
Publishing Co. 1986, Seiten 11-12, 97-102).
-
Für Hochleistungssysteme kann eine einzige
Datenübertragungsverbindung nicht ausreichend sein, um alle Nachrichten
zwischen den Knoten zu verarbeiten. Es wird deshalb
vorgeschlagen, eine Vielzahl von Übertragungsverbindungen zwischen
den Knoten vorzusehen. Ein hierbei auftretendes Problem
besteht jedoch darin, daß die Nachrichten dann nicht mehr an
jedem Knoten in der gleichen Reihenfolge ankommen.
-
Aufgabe der Erfindung ist es, dieses Problem zu lösen.
Kurzfassung der Erfindung
-
Gemäß der beanspruchten Erfindung wird ein
Datenverarbeitungssystem mit einer Mehrzahl von Datenverarbeitungsknoten
(10) und einer Mehrzahl von Datenübertragungsverbindungen
(11) zum Übertragen von Nachrichten zwischen den Knoten
vorgeschlagen, das gekennzeichnet ist durch
Übertragungsfolge-Numerierungsvorrichtungen (12, 20-25) zum Definieren
einer Folge von Übertragungsfolgezahlen, wobei die Folge
allen Knoten gemeinsam ist, eine Vorrichtung in jedem Knoten,
die die nächste Übertragungsfolgezahl aus der
Übertragungsfolge-Numerierungsvorrichtung erfaßt, wenn der Knoten eine
Nachricht zu senden hat, und die diese Zahl der Nachricht
zuordnet, wenn die Nachricht gesendet wird, und eine
Vorrichtung (46-51) in jedem Knoten zum Empfangen von Nachrichten
aus einer Mehrzahl der Verbindungen und zum Organisieren
dieser Nachrichten in der Rangfolge ihrer
Übertragungsfolgezahl.
Kurze Beschreibung der Zeichnungen
-
Ein Datenverarbeitungssystem nach der Erfindung wird
nachstehend anhand eines Ausführungsbeispieles in Verbindung mit den
Zeichnungen erläutert.
-
Fig. 1 ist ein Gesamtblockdiagramm des Systems.
-
Fig. 2 zeigt eine
Übertragungsfolgezahl-Handhabungsvorrichtung im Detail.
-
Fig. 3 zeigt eine Datenübertragungsschaltung im Detail.
-
Fig. 4 zeigt eine Datenempfangsschaltung im Detail.
Beschreibung einer Ausführungsform der Erfindung
-
Fig. 1 zeigt ein Mehrknoten-Datenverarbeitungssystem mit
einer Mehrzahl von Verarbeitungsknoten 10 (NODE 1- NODE 4,
die mittels vier Datenübertragungsverbindungen 11 (LINK 1 -
LINK 4) miteinander verbunden sind. Jeder Knoten weist eine
Datenverarbeitungseinheit und einen lokalen Speicher auf, die
von herkömmlicher Ausführung sind und hier nicht näher
beschrieben werden brauchen. Jeder Knoten enthält ferner
Schaltungen zur Steuerung der Übertragung von
Datennachrichten über die Verbindungen, wie nachstehend im einzelnen
beschrieben wird.
-
Jede der Datenübertragungsverbindungen 11 kann eine
herkömmliche Nachrichten-Sammelleitung sein. Andererseits kann jede
dieser Verbindungen eine Sternkopplungsvorrichtung aufweisen,
wie z. B. in der EP-Anmeldung Nr. 84 30 26 28 (EP-A-123 507)
beschrieben.
-
Jedem Knoten 10 werden die alleinigen Übertragungsrechte auf
einer der Verbindungen zugeordnet. So ist beispielsweise nur
NODE 1 berechtigt, auf LINK 1 zu übertragen, usw.
-
Jeder Knoten kann Datennachrichten aus allen Verbindungen
einschließlich der Verbindung, für die er die
Übertragungsrechte hat, empfangen.
-
Zusätzlich zu den obigen Datenverbindungen sind die Knoten
auch miteinander so verbunden, daß sie einen geschlossenen
Ring 12 bilden. Dieser Ring führt keine Daten, jedoch einen
numerischen Wert, der als Übertragungsfolgezahl (TSN)
bezeichnet wird, die zur Steuerung der Übertragens und
Aufnehmens von Datennachrichten auf den Datenverbindungen 11
verwendet wird, wie nachstehend beschrieben wird.
-
Wenn keiner der Knoten 10 eine Nachricht übertragen will,
wird die TSN einfach im Ring 11 von einem Knoten zum anderen
ohne jede Änderung geführt. Wenn ein Knoten eine Nachricht
übertragen will, wartet er, bis er die TSN empfängt. Ist die
TSN empfangen, schaltet der Knoten sie um Eins weiter und
gibt sie anschließend an den nächsten Knoten im Ring.
-
Wenn der Knoten auf diese Weise eine TSN erhalten hat, ist er
berechtigt, seine Nachricht über die zugeordnete
Übertragungsverbindung 11 zu übertragen. Die TSN wird der Nachricht
als Überschrift beigegeben. Da nur ein Knoten berechtigt
ist, auf jeder Datenverbindung 11 zu übertragen, sind keine
anderen Zugriffs- oder Kontentions-Auflösungsprotokolle für
die Verbindungen erforderlich; jeder Knoten kann seine
Nachricht über seine Verbindung senden, sobald er eine TSN
erfaßt hat.
-
Alle Knoten empfangen alle Nachrichten, die auf einer der
Verbindungen 11 übertragen worden sind. Jeder Knoten
speichert die Nachrichten, die von jeder Verbindung empfangen
worden sind, in einer getrennten Reihe zusammen mit ihren
TSNs und liest dann die Nachricht von allen Reihen in der
genauen TSN-Reihenfolge aus. Da jede über die Verbindungen
übertragene Nachricht eine eindeutige TSN besitzt, lesen
somit alle Knoten die Nachrichten aus den Reihen in der
gleichen Folge aus.
-
Die TSN wird im Ring 12 in Serienform übertragen. Jede TSN
besteht aus acht Bits und wird mit dem Bit niedrigster
Bedeutung zuerst und dem Bit höchster Bedeutung zuletzt
übertragen. Jeder TSN geht ein Markierbit mit dem Wert "1"
voraus, um den Beginn der TSN anzuzeigen, und zwischen den
TSNs wird eine Serie von Null-Bits übertragen. Die TSN auf
dem Ring 12 wird mit Hilfe eines Manchester-Codes codiert.
-
Fig. 2 zeigt eine TSN-Verarbeitungsschaltung, die in jedem
Knoten vorgesehen ist, um die TSN im Ring herum zu führen und
erforderlichenfalls weiterzuschalten.
-
Die Schaltung weist einen Empfänger 20 auf, der die
ankommende TSN aus dem vorausgehenden Knoten im Ring 12 empfängt. Der
Ausgang des Empfängers 20 wird einem Decodierer 21 zugeführt,
der das Manchester codierte Signal decodiert, um ein
Taktsignal CLK und ein Datensignal D zu erzeugen. Das Datensignal
wird einem Flip-Flop 22 zugeführt, dessen Ausgang in einen
Eingang eines Exklusiv-ODER-Gatters 23 gegeben wird. Der
Ausgang des Exklusiv-ODER-Gatters wird mit Hilfe eines
Manchester-Codierers 24 codiert und dann an einen Übertrager
25 geführt, damit er auf den nächsten Knoten im Ring
übertragen wird. Sowohl der Flip-Flop 22 als auch der Codierer 24
werden durch das Taktsignal CLK getaktet.
-
Das Exklusiv-ODER-Gatter 23 wird durch ein Signal INV
gesteuert. Normalerweise wird dieses Signal auf dem Wert "0"
gehalten, so daß das Gatter die Daten unverändert durchläßt.
-
Wie vorstehend beschrieben, ist dann, wenn der Knoten eine
Nachricht zu übertragen hat, erforderlich, die TSN um Eins
weiterzuschalten. Dies geschieht durch selektives Pulsen des
Signals INV nach "1", so daß ausgewählte Bits des TSN nach
folgendem Algorithmus invertiert werden:
-
(a) Invertieren des ersten Bits (niedrigster Bedeutung).
-
(b) Invertieren des nächsten Bits, wenn es eine "1" ist, und
wenn das vorausgehende Bit invertiert worden ist.
-
(c) Wiederholen des Schrittes (b), bis alle TSN-Bits
empfangen worden sind.
-
Diese Technik zur Fortschaltung der TSN kann auf eine Zahl
beliebiger Länge angewandt werden, und die Fortschaltung wird
nur mit einer einzigen Taktverzögerung durchgeführt, die von
dem Flip-Flop 22 eingeführt wird.
-
Die TSN-Verarbeitungsschaltung speist auch die folgenden
Ausgangssignale zur Verwendung ein, wie nachstehend
beschrieben wird:
-
ALTE TSN: der Ausgang des Flip-Flops 22.
-
NEUE TSN: der Ausgang des Exklusiv-ODER-Gatters.
-
Fig. 3 zeigt eine Datenübertragungsschaltung, die in jedem
Knoten 10 vorgesehene ist, um die Übertragung von Daten auf
die zugeordnete Verbindung 11 für diesen Knoten zu steuern.
-
Zu übertragende Daten werden in einem Schieberegister 30
gehalten und können serienweise über einen Multiplexer 31,
einen Manchester-Codierer 32 und eine Übertragerschaltung 33
auf die Verbindung 11 übertragen werden.
-
Wenn der Knoten keine Nachricht zu senden hat, wird der
Inhalt des Registers 30 auf Null gesetzt, und damit wird eine
Folge von Null-Bits über die Verbindung übertragen.
-
Hat der Knoten eine Nachricht zu senden, wartet er, bis kein
TSN empfangen wird, d. h. bis ein Strom von Nullen über den
TSN-Ring 12 empfangen wird. Dann erzeugt er ein Signal TxREQ,
und führt gleichzeitig die Nachricht in das Schieberegister
30 ein.
-
TxREQ setzt einen Flip-Flop 34, und dieser gibt ein UND-
Gatter 35 frei, wodurch ein Signal SEND TSN erzeugt wird.
Dieses Signal wird in einem Gatter 36 invertiert, das die
Verschiebung des Schieberegisters 30 unwirksam macht. Das
Signal SEND TSN schaltet ferner den Multiplexer 31 auf seinen
anderen Eingang, so daß er nunmehr das Signal NEW TSN zur
Abgabe an die Verbindung 11 auswählt. In diesem Zustand wird
angenommen, daß die TSN noch nicht angekommen ist und somit
NEW TSN Null ist. Somit werden Nullen weiter auf die
Verbindung 11 ausgegeben.
-
Wenn die TSN ankommt, wird sie in der vorbeschriebenen Weise
fortgeschaltet. Die fortgeschaltete TSN wird dem Multiplexer
31 als NEW TSN zugeführt und wird auf die
Datenübertragungsverbindung 11 mit einer Taktverzögerung (im Flip-Flop 22 der
Fig. 2) ausgegeben.
-
Das Markierbit der TSN setzt ein Flip-Flop 37 und erzeugt
einen START-Impuls. Dieser triggert einen Zähler 38, der
durch Acht teilt, und der die nächsten acht Takte
entsprechend
den acht Bits der TSN zählt. Am Ende der acht Takte
erzeugt der Zähler 38 ein Rücksetzsignal R, das den Flip-Flop
34 rücksetzt. Dies macht das UND-Gatter 35 unwirksam, wodurch
SEND TSN falsch gemacht wird, so daß der Multiplexer 31 in
seinen ersten Eingang zurückgeschaltet und damit nunmehr der
Ausgang des Schieberegisters 30 ausgewählt wird. Der falsche
Wert von SEND TSN macht ferner das Schieberegister 30 in der
Weise wirksam, daß erneut die Verschiebung begonnen wird, so
daß der Inhalt des Schieberegisters nunmehr serienweise zur
Übertragung über die Verbindung 11 ausgeschoben wird.
-
Zusammenfassend ergibt sich, daß der Knoten dann, wenn er
eine Nachricht zu übertragen hat, wartet, bis er eine TSN
aufnimmt. Dann schaltet er die TSN weiter und gibt sie auf
die Verbindung 11, worauf die Nachrichtendaten folgen.
-
Wie vorstehend erwähnt, empfängt jeder Knoten Daten aus allen
vier Datenübertragungsverbindungen 11.
-
Nach Fig. 4 enthält jeder Knoten vier
Datenempfangsschaltungen 40 zum Empfangen von Daten aus den entsprechenden
Verbindungen 11. Nur eine dieser Schaltungen ist in Fig. 4
dargestellt; die anderen drei sind entsprechend ausgelegt.
Die Ausgänge aller Schaltungen 40 werden mit einer
Datensammelleitung 41 verbunden, die der Datenverarbeitungseinheit
(nicht dargestellt) des Knotens zugeführt wird.
-
Eingangsdaten aus der Verbindung 11 werden über eine
Empfängerschaltung 42 und einen Manchester-Codierer 43 an den
Serieneingang eines acht Bits umfassenden Schieberegisters 44
zugeführt. Der Decodierer 43 entnimmt ein Datentaktsignal
DCLK aus den Daten, und dieses wird als Schiebetakt für das
Register 44 verwendet.
-
Der Takt DCLK wird ferner einem Zähler 45, der durch Acht
teilt, zugeführt, um ein Taktsignal IPCLK nach jedem achten
Taktschlg von DCLK zu erzeugen. Dies bewirkt, daß der Inhalt
des Schieberegisters 44 parallel in einen Pufferspeicher 46
im Schiebebetrieb (FIFO) eingeführt wird. Aufeinanderfolgende
Bytes der eingehenden Nachricht, beginnend mit der der
Nachricht zugeordneten TSN, werden in aufeinanderfolgende
Speicherplätze des FIFO-Pufferspeichers 46 eingeführt. Die
korrekte Bildeinstellung von Byte-Grenzen ist dadurch
gewährleistet, daß das TSN-Startbit zum Synchronisieren des
Zählers 45 verwendet wird.
-
Die TSN der ersten (d. h. ältesten) Nachricht im FIFO-Puffer
46 wird mit Hilfe einer Vergleichsschaltung 47 mit dem Inhalt
eines Zählers 48 verglichen, der den Wert der nächsten
erwarteten TSN hält, die auf die Datensammelleitung 41
ausgelesen werden kann. Wenn die Vergleichsschaltung 47
Gleichheit anzeigt, setzt sie einen Flip-Flop 49, der ein
ENABLE-Signal erzeugt.
-
Das ENABLE-Signal wird in einem UND-Gatter 50 mit dem IP
CLK-Signal kombiniert und erzeugt ein Ausgangstaktsignal
OPCLK, das Daten aus dem FIFO-Pufferspeicher taktet. Das
ENABLE-Signal macht auch eine
Sammelleitungs-Antriebsschaltung 51 wirksam, die jedes Bytes aus dem Ausgang des FIFO-
Pufferspeichers in die Datensammelleitung 41 speist.
-
Der Ausgang des FIFO-Pufferspeichers 46 wird ferner mit Hilfe
einer Vergleichsschaltung 52 mit einem festen Schema 53
verglichen, das das das Ende der Nachricht bildende Byte EOM
darstellt, welches das letzte Byte einer jeden Nachricht ist.
Wenn eine Übereinstimmung angezeigt wird, wird der Flip-Flop
49 rückgesetzt und entfernt das ENABLE Signal. Gleichzeitig
wird der nächste TSN-Zähler 48 weitergeschaltet.
-
Der TSN-Zähler 48, der nur als Teil einer
Datenempfangsschaltung 40 dargestellt ist, wird in Wirklichkeit zwischen allen
vier Datenempfangsschaltungen im Knoten geteilt und
weitergeschaltet, wenn eine der vier Schaltungen das das Ende der
Nachricht angebende Byte EOM anzeigt.
-
Zusammenfassend ergibt sich, daß Nachrichten aus den vier
Datenübertragungsverbindungen in den FIFO-Pufferspeichern der
entsprechenden Datenempfangsschaltungen aufgereiht werden.
-
Sie werden dann aus den Pufferspeichern auf die
Datensammelleitungen in exakter TSN-Folge unter Steuerung des nächsten
TSN- Zählers ausgesehen.
Einige mögliche Modifikationen
-
Bei der vorbeschriebenen Anordnung werden TSNs an die Knoten
mit Hilfe einer Ringverbindung gegeben. Die TNSs können
jedoch auch mit Hilfe einer speziellen TSN-Ausgabeeinheit,
die mit allen Knoten in einer Sternanordnung verbunden ist,
ausgegeben werden. Wenn ein Knoten eine Nachricht senden
will, muß er zuerst eine Anfrage an die die TSN abgebende
Einheit senden und dann warten, bis er eine TSN als Antwort
erhält. Wenn ein Knoten auf diese Weise eine TSN erhalten
hat, kann er seine Nachricht auf eine der Datenverbindungen
wie vorher senden, wobei die TSN der Nachricht zugeordnet
ist. Die TSN-Ausgabeeinheit ist für die Auflösung der
Kontention zwischen gleichzeitigen Anfragen von zwei oder
mehr Knoten und für das Weiterschalten der TSN
verantwortlich.
-
Bei der vorbeschriebenen Grundanordnung besitzt jeder Knoten
eine zweckbestimmte Datenübertragungsverbindung, für die er
die alleinigen Übertragungsrechte hat. Es ist auch möglich,
jeden Knoten mit mehr als einer zugehörigen Verbindung zu
versehen, um die Datenverarbeitungskapazität zu erhöhen und
eine Form von Qualitätsverschlechterung ohne nachteilige
Folgen im Falle von auftretenden Fehlern zu erzielen.
Beispielsweise kann jeder Knoten mit L Verbindungen versehen
sein, an denen er alleine die Übertragungsrechte hat, wodurch
eine Gesamtzahl von LN Verbindungen erzielt wird, wenn N die
Anzahl von Knoten ist.
-
Ein dabei auftretendes Problem besteht darin, daß eine
direkte Beziehung zwischen der Anzahl von Knoten und der
Anzahl von Verbindungen erforderlich ist, und dies ist nicht
notwendigerweise auf die Erfordernisse der
Gesamtdatenbandbreite abgestellt. Darüberhinaus kann kein Knoten eine
größere Bandbreite erfassen als auf seiner eigenen, ihm
zugeordneten Verbindung oder Verbindungen zur Verfügung
steht, selbst wenn die anderen Knoten vorübergehend leer
sind.
-
Alternativ können die zweckbestimmten Verbindungen durch einen
Satz von anteiligen Verbindungen ersetzt werden, wobei jeder
Knoten auf einer beliebigen der Verbindungen übertragen kann.
Jede anteilige Verbindung kann beispielsweise eine
Markierungs-Sternanordnung sein, wie sie in der oben bezeichneten
europ. Patentanmeldung beschrieben ist. Die Anzahl von
Verbindungen kann dann so gewählt sein, daß die erforderliche
Gesamtdatenbandbreite verarbeitet wird, wodurch das
vorbezeichnete Problem gelöst wird. In diesem Fall werden
Übertragungsrechte durch Erfassen einer TSN entweder aus einer
Ringverbindung oder aus einer speziellen TSN-Ausgabeeinheit
erhalten. Ist eine TSN erfaßt worden, kann ein Knoten auf der
Verbindung übertragen, deren Markierung als nächstes ankommt.
Alle Knoten hören dauernd auf alle Verbindungen, nehmen
Nachrichten in ihre FIFO-Pufferspeicher auf und verarbeiten
sie in der exakten TSN-Reihenfolge, wie im Grundschema.
-
Bei einer anderen möglichen Ausführungsform werden die
zweckbestimmten Verbindungen durch einen Satz von anteiligen
Verbindungen ersetzt, und das Recht zur Übertragung wird
wiederum durch Erfassung einer TSN erhalten. In diesem Fall
werden die L Bits niedrigster Bedeutung der TSN (L ist die
Anzahl von Verbindungen, die laufend verfügbar oder in
Betrieb sind) verwendet, um festzulegen, auf welcher
Verbindung die Übertragung erfolgen soll. Damit entfällt die
Notwendigkeit einer Markierung oder anderer
Kontentionsauflösungsprotokolle, da nur ein Knoten die Möglichkeit hat, auf
jeder Verbindung zu einer bestimmten Zeit zu übertragen.
-
Diese Modifikation ist nur direkt auf ein Nachrichtenschema
fester Länge anwendbar, bei dem die
Nachrichtenübertragungsdauer garantiert kleiner ist als die Zeitdauer, während der
die weitergeschaltete/zirkulierende TSN die
Übertragungsrechte auf einer gegebenen Verbindung erneut anrufen kann. Diese
Beschränkung kann jedoch dadurch behoben werden, daß ein
Reservierungs/Freigabemechanismus für die
Übertragungsverbindung zum TSN-Erfassungsmechanismus vorgesehen wird.
-
Wenn zweckbestimmte Übertragungsverbindungen verwendet
werden, gibt es keinen Grund, warum ein Knoten nicht mit der
Übertragung einer Nachricht auf einer Verbindung beginnen
soll, für die er die alleinigen Übertragungsrechte hat,
sobald die Nachricht für die Übertragung gelesen wird, ohne
daß er auf die Erfassung einer TSN warten muß. Wird die TSN
verfügbar, kann der Knoten diese TSN im Anschluß an die
Nachricht übertragen, anstatt einer Überschrift für die
Nachricht, wie bei dem oben beschriebenen System. In diesem
Fall ist es notwendig, sicherzustellen, daß jeder Knoten die
Verarbeitung einer empfangenen Nachricht solange aussetzt,
bis die TSN für diese Nachricht angekommen ist, und dann nur
in der genauen TSN-Folge.