DE3785211T2

DE3785211T2 - Mittel für Datenintegritätssicherung.

Info

Publication number: DE3785211T2
Application number: DE87480017T
Authority: DE
Inventors: Jean Calvignac; Michel Dauphin; Raymond Lenoir; Jean-Louis Picard
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1987-10-30
Filing date: 1987-10-30
Publication date: 1993-10-07
Anticipated expiration: 2007-10-31
Also published as: EP0313707A1; JPH01149631A; DE3785211D1; EP0313707B1; JPH0671244B2; US5046069A

Description

Gebiet der Erfindung

Die vorliegende Erfindung betrifft allgemein Nachrichtennetzwerke und im besonderen Mittel für die Datenintegritätssicherung in diesen Netzwerken.

Hintergrund der Erfindung

Die Datenintegrität bildet ein Hauptaugenmerk in Nachrichtennetzwerken, in denen Daten von einer Abgangssendstelle zu einer Zielendstelle durch ein Netzwerk, das mehrere zwischenliegende Knotenstellen umfaßt, über Signalwege, die verschiedene physikalische Verbindungen beinhalten, übertragen werden. Die Datenintegrität wird im Rahmen der Verbindungen von Knoten zu Knoten mittels einer Blockprüfzeichenfolge (FCS) gesichert. Diese Prüffolge wird am Sendepunkt nach einem vorgegebenen funktionellen Zusammenhang datenabhängig erzeugt. Die generierte Sende-FCS (d. h. FCSt wobei t für Senden - transmit - steht) wird an die gesendeten Daten angehängt. Die Datenintegrität wird dann an der empfangenden Endstelle dadurch überprüft, daß aus den empfangenen Daten eine Empfangs-Blockprüfzeichenfolge (FCSr wobei r für Empfangen - receive - steht) abgeleitet und FCSr mit FCSt verglichen wird, um die Identität zu prüfen, oder es werden komplette Datenblöcke nach einem ähnlichen Verfahren, wie es zur Erzeugung der FCSt angewandt wird, bearbeitet, und das Ergebnis wird dann mit einem vorbestimmten Wert auf Identität verglichen. Jede Fehlererkennung führt zum Verwerfen des empfangenen Datenblockes, und es wird ein Programm gestartet, das eine erneute Übertragung desselben Datenblockes bewirkt, bis dessen Gültigkeit gesichert ist.
Die FCS-Bildung ist ein komplexer Vorgang, der Polynomdivisionen mit allen Daten des Datenblocks enthält. Diese Operationen beanspruchen sehr viel Rechenleistung, die zusätzlich zur normalen Verarbeitungskapazität des Übertragungssystems bereitgestellt werden muß. Somit wird jedes Verfahren zur Vereinfachung der FCS-Bildung bei der nachrichtentechnischen Industrie willkommen sein.
Bei einer Anzahl von Anwendungen enthalten die übertragenen Nachrichtenblöcke zusätzliche Informationen und sogenannte Kopfzeilen, die angewandt werden, damit für den speziellen Block die Übertragungswege innerhalb des Netzwerkes von Knoten zu Knoten zur Zielendstelle leichter gefunden werden können. Diese Leitwegdaten werden an jedem Knoten beispielsweise durch Einfügen der Adresse des nachfolgenden Netzwerkknotens in die zu übertragende Nachricht modifiziert. Alle diese Operationen beeinflussen deshalb den Nachrichtenblock, und somit muß die FCS in jedem Knoten neu gebildet werden. Das bedeutet, daß der Prozeß der FCS-Bildung während jeder Datenblockübertragung innerhalb eines Nachrichtennetzes mehrmals durchgeführt werden muß, was obige Anmerkungen über den Nutzen einer Vereinfachung des FCS- Bildungsschemas unterstreicht.
Schließlich wird bei einigen Anwendungen wie beispielsweise in Übertragungssteuereinrichtungen die empfangene Nachricht bitweise zusammengesetzt und einige Zeit in einer zwischenliegenden Übertragungssteuereinrichtung abgespeichert, bevor sie zum nächsten Knoten (z. B. zur nächsten Steuereinrichtung) weitergegeben wird, und dies wiederholt sich bis zur Zieldatenstation. Konventionelle Übertragungssteuereinrichtungen verwerfen in diesem Prozeß die empfangene FCSr nach Überprüfung der Gültigkeit des empfangenen Datenblocks und speichern nur die Daten ab. Danach wird, wenn die Daten weiter übertragen werden sollen, eine neue FCS, d. h. eine FCSt, gebildet und an die Daten angehängt. Wenn irgend eine Veränderung die Daten während der Zeit der Speicherung beeinflußt hat, kann dies nicht durch die Zieldatenendstelle oder den Knoten bemerkt werden, weil die neu gebildete FCS mit den veränderten Daten berechnet wird.
Das Dokument WO-A-8002611 beschreibt eine Anordnung zur Datenübertragung zwischen einem Sendecomputer und einem Empfangscomputer, die Mittel zur Bildung und Überprüfung zweier Prüfsummen, die sich wechselseitig ergänzen, enthält; eine innere Prüfsumme zur Überwachung der Hardware, die zu Computern oder Zwischenstationen auf einem Übertragungsweg gehört, sowie eine äußere Prüfsumme zur Überwachung der Übertragungsleitungen. Eine Schaltung zur Prüfsummenbildung ist dem Sendecomputer zugeordnet und enthält eine Additionsschaltung und ein Register, die durch Addition aller Nachrichtenworte in einem vollständigen Signalwort die innere Prüfsumme erzeugen. Eine Schaltung für die Bildung der äußeren Prüfsumme erzeugt die äußere Prüfsumme durch Addition der Adreßsteuersignale der Nachricht und der inneren Prüfsumme. Auch hier wird wieder deutlich, daß der Prozeß der Prüfsummenbildung, der in den offenbarten Verfahren und Anordnungen gemäß der vorliegenden Erfindung behandelt wird, bei jeder Datenübertragung mehrmals ausgeführt werden muß, und damit zusätzliche Verarbeitungskapazität benötigt.
Eine Aufgabe der vorliegenden Erfindung ist es, ein Verfahren zur Überprüfung der Datenintegrität der in einem Zwischenknoten eines Nachrichtennetzes abgespeicherten Daten gemäß Anspruch 1 bereitzustellen.
Eine andere Aufgabe der vorliegenden Erfindung ist es, ein Verfahren zur FCS-Bildung bereitzustellen, das die Rechnerbelastung, die zur Aktualisierung einer FCS verbunden mit einem gegebenen Datenblock, z. B. zur Aktualisierung einer FCS in Zwischenknoten eines Datennetzes, benötigt wird, minimiert und zusätzlich Mittel zur Überprüfung der Datenintegrität bereitstellt.
Eine andere Aufgabe der vorliegenden Erfindung ist es, ein Verfahren bereitzustellen, mit dem die Datenintegrität der in einem Zwischenknoten oder in einer Übertragungssteuereinrichtung eines Nachrichtennetzes abgespeicherten Daten überprüft werden kann, bevor die Daten weiter übertragen werden.
Diese und andere Aufgaben, Merkmale und Vorteile der vorliegenden Erfindung werden im folgenden mit Bezug auf die beigefügten Zeichnungen erläutert werden.

Kurze Beschreibung der Figuren

Fig. 1 zeigt die Struktur eines SDLC/HDLC-Blockes.
Fig. 2 ist ein Blockschaltbild eines Gerätes zur Realisierung der vorliegenden Erfindung.
Die Fig. 3a und 3b zeigen Datenblockstrukturen, mit denen im Rahmen der Erfindung gearbeitet wird.
Die Fig. 4 und 5 sind Geräte zur Realisierung der Erfindung.
Fig. 6 zeigt eine Anwendung der vorliegenden Erfindung.

Beschreibung der bevorzugten Ausführungsform

In Fig. 1 ist ein SDLC Block dargestellt, der mehrere Felder umfaßt, die mit F, A, C, Daten, FCS bzw. F gekennzeichnet sind.
Die F-Felder werden als Blockbegrenzer benutzt um in konventioneller Art Markierungszeichen einzufügen, die durch das hexadezimale Byte "7E" repräsentiert werden.
A ist ein Adreßfeld, das die Station kennzeichnet, die den Datenblock sendet (oder die ihn empfangen soll).
C ist ein Steuerfeld, das den Zweck des betreffenden Datenblokkes spezifiziert. Es ist normalerweise ein Byte lang und kann in einem der drei folgenden Formate vorliegen: unnumeriertes Format, Überwachungsformat oder Informationsübertragungsformat. Datenblöcke im unnumerierten Format werden für solche Funktionen wie Initialisierung einer sekundären Zielstation, Steuerung des Antwortverhaltens von Sekundärstationen oder Berichte über bestimmte Ablauffehler verwendet. Das Überwachungsformat wird bei Datenblöcken verwendet, die für die Informationsübertragung Hilfsfunktionen ausüben, derart daß vorhergehende Datenblöcke, die Informationen tragen, bestätigt werden. Die Datenblöcke des Überwachungsformats führen keine reinen Informationen. Diese Blöcke werden benutzt, um empfangene Blöcke zu bestätigen, Bereitschafts- oder Besetzt-Bedingungen weiterzugeben und Blocknumerierungsfehler zu protokollieren (anzuzeigen, daß ein numerierter Informationsblock außerhalb der zugehörigen Folge empfangen wurde). Blöcke im Informationsübertragungsformat transportieren im SDLC-Protokoll die Nutzinformationen. Das Steuerfeld enthält neben der Formatanzeige Sende- und Empfangszählerstände (Ns und Ne), die verwendet werden, um zu sichern, daß diese Datenblöcke in der richtigen Reihenfolge (Ns) empfangen werden und um angenommene Informationsblöcke zu bestätigen (Ne). Der Ns-Zählerstand zeigt die Nummer des Informationsblokkes innerhalb der Folge der gesendeten Informationsblöcke an.
Das Feld mit den Informationsdaten hat eine variable Länge (in Vielfachen von 8-Bit-Bytes) und ist dazu da, die Informationsdaten aufzunehmen, die manchmal als reine Informationsdaten bezeichnet werden (I).
Im Anschluß an das Informationsfeld folgt das Feld mit der Blockprüfzeichenfolge (FCS), dessen Zweck darin besteht, eine Überprüfung des Inhalts des SDLC-Blockes auf Fehler zu ermöglichen, die durch den Übertragungskanal oder an irgend einer Stelle entlang des Übertragungsweges aufgetreten sind, z. B. im Speicher eines Zwischenknotens entlang des Übertragungsweges. Dieses Feld enthält eine 16-Bit-Prüffolge, die an den Block angehängt wird und das Ergebnis einer Berechnung mit den Inhalten der Felder A, C und I ist, die vor der Übertragung bzw. dem Senden jedes SDLC-Blockes ausgeführt wird.
Das, was im Zusammenhang mit der vorliegenden Erfindung verstanden werden muß, ist allgemein ausgedrückt die Tatsache, daß jeder übertragene Datenblock einen Teil enthält, der als informationstragender Teil bezeichnet wird und der sich normalerweise entlang des Übertragungsweges nicht ändern sollte und einen anderen Teil, als "Kopfzeile" bezeichnet, der sich entlang des Übertragungsweges ändert. Jede Veränderung im Bereich des Informationsteils würde einen Fehler kennzeichnen und sollte durch Nutzung des FCS-Bereiches innerhalb des Blockes an jedem Prüfort festellbar sein.
Es sollte beachtet werden, daß im folgenden der Ausdruck "Kopfzeile" den sich verändernden Teil des Datenblockes bezeichnet, auch wenn sich dieser an einer beliebigen Stelle innerhalb des Datenblockes befinden kann.
Die FCS-Bildung wird, wie unten beschrieben, konventionell über eine Polynomdivision durchgeführt.
Wir nehmen an, daß der zu übertragende Datenblock, d. h. das Adreßfeld A, das Steuerfeld C und das (möglicherweise leere) Dateninformationsfeld, k Bits enthält, und wir bezeichnen diese k Bits durch die Koeffizienten ak-1, . . ., a&sub0;, die als Elemente des Galoisfeldes der Ordnung 2 (GF2) definiert werden, wobei jeder Koeffizient den Wert 0 oder 1 annehmen kann, und daß der Datenblock durch ein Polynom Pk-1(x) repräsentiert wird.
Pk-1(x) = ak-1xk-1 + ak-2xk-2 + . . . + a&sub1;x + a&sub0;
Die FCS enthält konventionell die Berechnung der Reste einer Polynomdivision Modulo 2 von x¹·Pk(x) durch ein sogenanntes erzeugendes Polynom G(x) des Grades 1, wobei 1 ein vorher festgelegter ganzzahliger ist. Das erzeugende Polynom ist vorbestimmt, beispielsweise durch das CCITT ausgewählt.
Das erzeugende Polynom, wie es durch das CCITT definiert wurde, lautet
G(x) = x¹&sup6; + x¹² + x&sup5; + 1 mit dem Grad 1 = 16
Im folgenden kennzeichnet die Bezeichnung Rest(A(x),G(x)) den Rest der Polynomdivision (Modulo 2) des Polynoms A(x) durch das Polynom G(x).
Die FCS kann dann als Summe (Modulo 2) dreier Terme betrachtet werden
FCS(x) = T1(x) + T2(x) + F15(x)
wobei
F15(x) = x¹&sup5; + x¹&sup4; + x¹³ + . . . + x³ + x² + x + 1
T1(x) = Rest (xk·F15(x), G(x))
T2(x) = Rest (x¹&sup6;·Pk-1(x), G(x))
sind.
Diese FCS(x) repräsentiert eine 16-Bit lange Folge, an deren Anfang die Koeffizienten höherer Ordnung stehen. Das Polynom, das schließlich als SDLC-Block zwischen den Markierungszeichen übertragen wird, ist
Mt(x) = x¹&sup6;·Pk-1(x) + FCS(x)
Konventionell wird im Empfänger die Summe (Modulo 2) folgender zwei Terme berechnet, wobei Mr(x) den empfangenen Datenblock zwischen den Markierungszeichen bezeichnet.
1. Rest (xk+16·F15, G(x))
wobei k+16 die Anzahl der Bit in Mr(x) ist.
2. Rest (x¹&sup6;·Mr, G(x))
Diese Summe liefert das konstante Polynom x¹² + x¹¹ + x&sup8; + x³ + x² + x + 1 dann und nur dann, wenn kein erkennbarer Fehler aufgetreten ist.
Wir wollen jetzt annehmen, daß Mr(x) ein SDLC/HDLC-Datenblock ist, der an einem Knoten eines Nachrichtennetzes empfangen wurde. Er kann dann in folgender Form beschrieben werden:
Mr(x) = (Hr(x) + I(x))·x¹&sup6; + FCSr(x)
wobei
Hr(x) das Polynom ist, das ein modifizierbares Variablenfeld, hier als Kopfzeile bezeichnet, repräsentiert und die Leitweginformation enthält, die normalerweise von einem Knoten zum andern verändert wird, oder allgemeiner ausgedrückt, die sich innerhalb des Nachrichtennetzes ändert.
I(x) ist das Polynom, das das Informationsfeld repräsentiert, das ohne jede Modifikation übertragen werden soll.
FCSr ist das Polynom, das die empfangene FCS repräsentiert.
Bei der Änderung des Inhaltes der Kopfzeile von Hr(x) zu Ht(x) (t steht für Senden - transmit) zu Zwecken der Datenblockorientierung an dem gegebenen Knoten, der Addition der neuen Kopfzeile zu I(x) und der Neuberechnung der zugehörigen FCSt(x) kann der neue Datenblock Mt(x) folgendermaßen beschrieben werden.
Mt(x) = (Hr(x) + I(x))·x¹&sup6; + FCSt(x)
Anstatt der Ausführung der FCS-Bildung über Ht(x) + I(x), werden gemäß der vorliegenden Erfindung folgende Operationen ausgeführt:
- Berechnung eines Variationspolynoms D(x)
D(x) = Ht(x)-Hr(x)
- Berechnung eines dFCS-Terms
dFCS = Rest (D(x)·x¹&sup6;, G(x)) (1)
- Berechnung von FCSt(x)
FCSt(x) = FCSr(x) + dFCS
Einen Vorteil des vorgeschlagenen Verfahrens kann man aus der Tatsache ableiten, daß I(x) nicht direkt in die Operationen einbezogen wird. Deshalb können unerwartete Änderungen, die innerhalb dieses Feldes stattgefunden haben, von dem angenommen wird, daß es unverändert bleibt, am Empfangsende des Nachrichtennetzes erkannt werden.
Ein Beispiel für die Realisierung eines Übertragungsadapters, in dem ein Gerät eingesetzt wird, daß auf dem vorgeschlagenen Verfahren beruht, ist in Fig. 2 dargestellt. Es dient dazu, einen SDLC-Datenblock zu aktualisieren, d. h. dessen FCS zu aktualisieren, wenn sich die Kopfzeile von Hr(x) auf Ht(x) zum Zweck der Blockleitung geändert hat.
Die Logik enthält zwei Parallel-Serien-Wandler. Der Parallel-Serien-Wandler 10 wird benutzt, um den gesamten empfangenen Datenblock Mr(x), so wie er empfangen wurde, in eine Folge umzusetzen. Der Parallel-Serien-Wandler 12 wird benutzt, um die neue Kopfzeile Ht(x), die vorher in dem Pufferregister 14 gespeichert war, in eine Folge umzusetzen.
Die Verschiebeoperationen der Parallel-Serien-Wandler werden durch einen Takt (nicht dargestellt) gesteuert, der mit der Bitrate arbeitet.
Ein Logiksignal KOPF TOR wird so erzeugt, daß es während der Zeit, während der die Bits von Hr(x) durch den Parallel-Serien- Wandler 10 ausgegeben werden, HIGH ist. Dieses Logiksignal steuert sowohl die Funktion des Parallel-Serien-Wandlers 12 als auch die des UND-Gatters A1.
Hr(x) und Ht(x) werden durch die Schaltung 13 antivalent verknüpft, wobei die obigen Operationen ausgeführt werden und damit D(x) abgeleitet wird, weil die Subtraktions- und Additionsoperationen im GF2-Feld mit einer Antivalenzverknüpfung (Exklusiv- ODER, XOR) gleichwertig sind.
Ein FCS-Generator 14, der ursprünglich komplett auf Null gesetzt ist, wird verwendet, um das Polynom D(x), das über A1 geleitet wird, durch das vorgewählte Polynom G(x) zu dividieren und den Rest dFCS auszugeben. Der FCS-Generator wird konventionell aus Schieberegistern aufgebaut und ist dem Stand der Technik entsprechend wohlbekannt. Für weitere Details kann auf das Dokument "IBM Synchronous Data Link Control General Information" GA27 - 3093 - 2 verwiesen werden.
Das Signal FCS TOR wird während der Zeit aktiviert, während der das FCS-Feld übertragen wird, wobei es das dFCS-Signal über das UND-Gatter A2 und das ODER-Gatter 01 auf einen Eingang der Antivalenzschaltung 15 legt.
Die Ausgänge der Parallel-Serien-Wandler 10 und 12 werden über die Gatter A3 bzw. A4 weitergeleitet, wobei die Freigabe der Signale über das Logiksignal KOPF TOR gesteuert wird, das direkt A4 oder über einen Inverter I A3 öffnet.
Der Ausgang von A4 wird auf die ODER-Schaltung O1 gegeben, während der Ausgang von A3 auf den zweiten Eingang der Antivalenzschaltung 15 gelegt wird.
Das Zeichenmuster, das durch den FCS-Generator 14 berechnet wird, wird dann Modulo 2 zu der alten FCS im XOR-Gatter 15 addiert und in den SDLC-Block an der richtigen Position eingefügt, so daß man am Schaltungsausgang Mt(x) erhält.
Wie unten noch gezeigt werden soll, führt das Verfahren der vorliegenden Erfindung zu besonders interessanten Ausführungsformen, wenn zusätzliche spezifische Merkmale wie beispielsweise Größe und/oder Platz des zu verändernden Kopfzeilenbereiches in Betracht gezogen und Größen-, Geschwindigkeits- oder Kostenparameter hervorgehoben werden. Spezifische Beispiele werden weiter unten betrachtet.
Wir wollen zuerst annehmen, daß der Datenblock zwischen den Bits "n" (n einschließlich) und "p-1" (0< n< p< k) modifiziert wird, d. h. die niedrigen "n" Bits und die oberen "k-p" Bits des Datenblockes bleiben unverändert, und die "p-n" Bits in der Mitte werden modifiziert (siehe Fig. 3a).
Wir nehmen an, daß die k Bits des Datenblockes Pk-1(x) vor der Modifikation noch durch die Koeffizienten ak-1, . . ., a&sub0; repräsentiert werden. Das Problem besteht dann darin, den Einfluß der Modifikation auf die ursprüngliche FCS herauszufinden. Der Datenblock kann durch die Summe zweier Polynome, I(x) (welches unverändert bleibt) plus Hr(x) (zu verändernder Teil) repräsentiert werden:
Pk-1(x) = I(x) + Hr(x) wobei:
I(x) = ak-1·xk-1 + ak-2·xk-2+ . . . + ap+1·xp+1 + ap·xp
+ an-1·xn-1 + an-2·xn-2+ . . . a&sub1;x + a&sub0;
Hr(x) = ap-1·xp-1 + ap-2·xp-2 + . . . + an+1·xn+1 + an·nn
Es sollen die neuen Bitwerte zwischen dem Bit p-1 und dem Bit n mit bp-1, bp-2, . . ., bn bezeichnet werden, und Ht(x) soll den modifizierten Teil des- Datenblockes repräsentieren:
Ht(x) = bp-1·xp-1 + bp-2·xp-2 + . . . + bn·xn
Der modifizierte Datenblock P'k-1(x) wird dann durch folgenden Term repräsentiert:
P'k-1(x) = I(x) + Ht(x)
Gemäß dem Ergebnis (1), ergibt sich die Differenz zwischen der alten FCS, bezeichnet als FCSr und der neuen FCS, bezeichnet als FCSt dann zu
dFCS = Rest ((Ht(x)-Hr(x))·x¹&sup6;, G(x))
oder wieder zu
dFCS(x) repräsentiert den Anteil, der zu FCSr addiert werden muß, um FCSt zu erhalten.
Als Beispiel wollen wir annehmen, daß der Datenblock 80 Byte (k = 640 Bits) enthält und daß die ersten 20 Bytes (n = 480 Bits, p = 640 Bits) modifiziert werden. dFCS ergibt sich dann zu
und kann wie folgt berechnet werden:
1) Berechnung (durch Antivalenz) der Bitkette
b&sub6;&sub3;&sub9;-a&sub6;&sub3;&sub9;, . . ., b&sub4;&sub8;&sub0;-a&sub4;&sub8;&sub0;
2) Berechnung von dFCS, d. h. Berechnung der partiellen FCS dieser Bitkette wie jeder anderen FCS auch,
3) Addition (durch Antivalenz) dieser dFCS zur ursprünglichen FCSr, um FCSt zu erhalten.
Es ist erkennbar, daß dieselben Verfahren auch dann angewendet werden können, wenn der modifizierte Bereich aus mehreren Teilabschnitten besteht, die sich an beliebigen Stellen innerhalb des Datenblockes Pk-1(x) befinden können.
Ein Gerät zur Ausführung der oben beschriebenen Verarbeitungsoperationen ist in Fig. 4 dargestellt.
Die alten und die neuen Datenblöcke werden in den Speichern 20 bzw. 22 gespeichert. Beide Speicher werden mit den Informationsdaten (d. h. I(x)), die während des Prozesses normalerweise keinen Veränderungen unterliegen, und mit den variablen Teilen der Datenblöcke, d. h. Hr(x) bzw. Ht(x), geladen.
Drei ein Byte breite Register K, N und P werden verwendet, um die letzte Byteadresse von I(x) plus 1, die erste Byteadresse von H (d. h. Hr(x) und Ht(x)) bzw. die letzte Byteadresse von H(x) plus 1 zu speichern.
Ein Bytezähler 23, der durch einen Takt gesteuert wird, wird inkrementiert. Beginnend nach einem Startkommando für die Aktualisierung wird er von Null bis K Bytes, entsprechend eines K Byte langen Datenblocks, hochgezählt. Der Byte-Zählerstand des Zählers 23 wird über die Komparatoren 24, 25 und 26 ständig mit K, N und P verglichen. Wenn die modifizierten Bytes mit dem nten Byte beginnen und am (p-1)-ten Byte enden, werden die Ausgänge der Komparatoren 25 bzw. 26 dazu verwendet, einen Zwischenspeicher 27 zu setzen und rückzusetzen, dessen Ausgangssignal die H-Feldlänge repräsentiert. Während der modifizierten H- Feld-Periode (H-Feld-Signal = 1), werden die abgetasteten Bytes in die Parallel-Serien-Wandler SERWAN 28 und 29 übertragen, mit einer Byterate, die durch eine Detektorschaltung 30 bestimmt wird, welche eine Änderung des Zählerstandes im Zähler 23 erkennt und deren Ausgangssignal über das UND-Gatter A31, gesteuert durch das H-Feld-Signal, weitergeleitet wird.
Wenn ein Byte in jeden SERWAN 28 und 29 übertragen wurde, werden deren Inhalte mit der Bittaktrate in die Antivalenz-Schaltung geschoben, die die (bi-ai)-Operationen ausführt. Das Ergebnis bi-ai wird über das UND-Gatter A33, gesteuert durch das H-Feld-Signal, in ein FCS-Berechnungs-Glied 32 eingespeist. Die FCS-Bits werden dann auf einen 16-Bit breiten Serien-Parallel-Wandler SERWAN 33 gegeben.
Da der Bytezähler 23 von Null bis zum (n-1)-ten Byte und von P bis zum K-ten Byte zählt, werden die Nullen der H-Feld-Periode während der H-Feld-Null-Periode (H-Feld-Signal = 0) in das bitweise arbeitende FCS-Berechnungs-Glied gegeben.
Ein sechzehn Bit breiter Puffer 37 speichert die alte FCS (d. h. FCSr), damit sie aktualisiert werden kann. Die Blockprüfzeichenfolge FCSr wird in einer sechzehn Bit breiten Antivalenz-Schaltung 34 auch mit dem Parallelausgang des Serien-Parallel-Wandlers SERWAN 33 antivalent verknüpft.
Wenn einmal das K-te Byte von der Vergleichsschaltung 24 festgestellt wird, wird die Aktualisierung der FCS gestoppt und die neue FCS über das 16 Bits breite UND-Gatter 36 in einen 16-Bit- Puffer 35 geführt.
Eine andere besonders interessante Ausführungsform der vorliegenden Erfindung kann dann erhalten werden, wenn man annimmt, daß sich beispielsweise eine zwei Byte lange Kopfzeile an einer vorbestimmten Position innerhalb des Datenblockes befindet. Wir halten fest, daß das Verfahren auf eine ein Byte lange Kopfzeile angewandt werden kann, indem das hochwertige Byte der zwei Bytes langen Kopfzeile mit Nullen aufgefüllt wird.
In Fig. 3b ist ein Datenblock dargestellt, der ohne FCS K Bits lang ist. Man kann sich den Datenblock in drei Teile zerlegt vorstellen, wobei die zwei zu modifizierenden Bytes (Kopfzeile) an n-ter Byteposition in den Block eingebettet sind und die FCS mit eingeschlossen wird. Wir nehmen an, daß der alte Wert der Kopfzeile durch das Polynom O(x) und deren neuer Wert durch das Polynom N(x) repräsentiert werden, wobei beide Polynome O(x) und N(x) den Polynomgrad von höchstens 15 besitzen, und wie oben wird das Differenzpolynom gebildet:
D'(x) = N(x)-O(x)
Die zugehörige Modifikation der gesamten FCS wird dann
dFCS(x) = Rest (D'(x)·x8n, G(x))
oder
dFCS(x) = {Rest (D'(x)·x8n, G(x))
multipliziert mit Rest (x8n, G(x)) } modulo G(x)
Wenn man zwei Polynome
P&sub1;(x) = Q&sub1;(x)·G(x) + R1(x)
und P&sub2;(x) = Q&sub2;(x)·G(x) + R2(x) voraussetzt,
dann gilt:
Rest (P&sub1;(x)·P&sub2;(x), G(x)) =
Rest (R&sub1;(x)·R&sub2;(x), G(x))
Es sollte erwähnt werden, daß D'(x) sein eigener Rest ist, wenn die Kopfzeile zwei Byte lang ist. D'(x) enthält höchstens 16 signifikante Bits. Deshalb erfordert die Berechnung der Bestimmungsgleichung von dFCS(x) nur die Berechnung des Restes von x8n, der als Rb(x) bezeichnet wird.
Alle möglichen Werte dieses letzten Restes müssen für Werte von "n" zwischen 1 und 16.000 berechnet werden, weil Datenblöcke, wie sie im Nachrichtennetz via Satellit auftreten können, bis zu 16.000 Bytes umfassen können.
Wir halten fest; daß n in binärer Form wie folgt geschrieben werden kann:
wobei m die höchstwertige Bitposition von n ist
und n = 0 oder 1 ist.
Dann folgt:
Rb = Rest (x8n, G(x)) =
Deshalb kann für Rb geschrieben werden:
Wobei Ri(x) als Bit-Rest bezeichnet werden kann:
und Π für "Produkt von . . ." steht.
Es folgt dann
Zum Beispiel wollen wir annehmen, daß die zu modifizierenden Bytes innerhalb des betrachteten Datenblockes an n=245-ter Position stehen.
Dann gilt: n = 245 = 128+64+32+16+4+1
= 2&sup7;+2&sup6;+2&sup5;+2&sup4;+2²+2&sup0;
oder n = n&sub7;·2&sup7;+n&sub6;·2&sup6;+n&sub5;·2&sup5;+n&sub4;·2&sup4;+n&sub3;·2³+n&sub2;·2²+n&sub1;·2¹+n&sub0;·2&sup0;
mit ni = 0 für i=1 und 3
und ni = 1 für i=0,2,4,5,6 und 7.
In diesem Fall wird:
Die Reste, die auch als Bitreste Rb bezeichnet werden, können vorher gespeichert werden.
Wir nehmen an, daß die zu modifizierenden Bytes innerhalb des betrachteten Datenblockes an jeder beliebigen Stelle bis zur n=255-ten Position stehen können. Die höchste Anzahl an Resten, die betrachtet werden soll, soll gleich acht sein. Wenn n dann Werte bis n=16383 annehmen kann, würde lediglich ein Maximum von bis zu 15 Resten betrachtet werden müssen. Diese Reste werden in der folgenden TABELLE der RESTE dargestellt. TABELLE der RESTE Restpolynom Restbits
Diese Reste können in einem Speicher mit wahlfreiem Zugriff (RAM) gespeichert werden, wobei der gesamte Wiederberechnungsprozeß der FCS folgende Schritte umfassen würde:
- Berechnung von D'(x) = N(x)-O(x), wobei N(x) und O(x) die neue bzw. die alte Kopfzeile repräsentieren,
- Laden des effektiven
in ein Adreßregister,
- Aktivieren der RAM-Adressen, für die ni = 1 gilt,
- Berechnung des Produktes Rb der geladenen Reste,
- Multiplikation von Rb mit D(x), um daraus dFCS abzuleiten und
- Addition von dFCS zur alten FCS.
Dargestellt in Fig. 5 ist eine Geräteausführungsform, bei der die Aktualisierung der FCS unter Verwendung vorher gespeicherter Reste entsprechend der obigen Tabelle durchgeführt wird.
Diese Ausführungsform wird verwendet, um die FCS in den Fällen zu aktualisieren, in denen die Bytes innerhalb der betrachteten Datenblöcke zwischen der Byteposition n und der Byteposition (p-1) modifiziert werden, wobei n < p-1 gilt.
Die Werte von n und p sind in den 16 Bits breiten Registern Reg 1 bzw. Reg 2 gespeichert. Der alte Teil des Datenblockes zwischen den Bytes n und p-1 wird in einem Speicher Hr und der modifizierte Teil oder der neue Bereich zwischen den Bytes n und p-1 wird in Ht gespeichert. Die alte FCS wird in einem Register Reg 3 gespeichert.
Der Vorgang startet mit dem Signal "Anfangsladen", bei dem n aus dem Register Reg 1 in ein Register Reg 4 sowie die alte FCS von Reg 3 in ein Register Reg 19 ("Schritt/Schritt FCS") übertragen und der Zähler 50 auf Null gesetzt wird. Dieser Zähler 50 arbeitet modulo 16, d. h. wenn er über 15 inkrementiert wird, wird er auf Null zurückgesetzt. Ein Decoder 52, der "Wert i = 0" erkennt, überträgt die ersten zwei Byte von Hr und Ht in die Register Reg 6 bzw. Reg 7. Diese zwei Zwei-Byte-Worte werden antivalent verknüpft und in das Register Reg 8 übertragen, das dann D'(x)=N(x)-O(x) enthält. Der Inhalt von Register Reg 8 wird in ein "Zwischen-FCS" Register Reg 12 über das UND-Gatter 54, gesteuert durch das Signal "Wert i=0", übertragen.
Bei i=0 wird der Inhalt von Register Reg 4 über das UND-Gatter 56 in den Parallel-Serien-Wandler (SERWAN) 58 geladen, dessen Ausgang das UND-Gatter 60 ansteuert. Die Verschiebeoperationen in SERWAN 58 werden durch das "I-TAKT"-Signal , das die i-Rate definiert, gesteuert. Das Signal I-TAKT steuert sowohl das Inkrementieren des Zählers 50 als auch den zweiten Eingang des UND-Gatters 60. Die Koinzidenz eines Taktimpulses von "I-TAKT" mit einem binärem 1-Wert am Ausgang von SERWAN 58 erzeugt ein HIGH-Niveau (d. h. "i GÜLTIG") im Ausgangssignal des Gatters 60.
Der Inhalt des Zählers 50 wird zur Adressierung des Speichers (RAM) 62 benutzt, der die Reste enthält, wie sie in der TABELLE der RESTE für i = 0 bis 15 definiert sind. Diese Tabelle wird somit zyklisch überstrichen, und der adressierte Inhalt wird zyklisch in ein Ausgabe-Register 64 übertragen. Gleichzeitig wird der Inhalt der Register 64 und Reg 12 mit der i-Taktrate in einem Multiplizierer 66 miteinander multipliziert (Polynommultiplikation). Der Multipliziererausgang , d. h. ein 32 Bits breites Polynom, wird auf das Glied 68 gegeben, das ein 16 Bits breites Polynom liefert, das den Rest der Polynomdivision von besagtem Multipliziererausgang durch G(x) darstellt. Der Rest wird über ein UND-Gatter 70 in das Zwischen-FCS-Reg 12 übertragen, dann und nur dann, wenn das Signal "i GÜLTIG" HIGH ist. Wenn i den Wert 15 erreicht hat, enthält Register Reg 12 den dFCS-Wert.
Der Inhalt von Reg 12 und Reg 19 wird über eine 16 Bit breite XOR-Schaltung 70 antivalent verknüpft, und das Ergebnis dessen wird, wenn i = 15 durch den DECODER 72 erkannt wird, wieder auf Reg 19 zurückgeführt.
Das Signal i-WERT = 15, das durch den DECODER 72 bereitgestellt wird, triggert ein Inkrementierglied 74, das den Inhalt des Registers Reg 4 um 2 hochzählt. Ein Komparator 76 vergleicht den neuen Wert von Reg 4 mit dem Inhalt von Reg 2 und erzeugt bei Gleichheit einen Impuls "n INKREMENT STOPP", der über ein UND- Gatter 78 die Übergabe des neuen FCS-Blockes von Reg 19 in Reg 24 triggert.
Sollte die Variation der Kopfzeile länger als zwei Byte sein, wird der Vorgang wiederholt. Es sollte erwähnt werden, daß für n und p angenommen wurde, daß diese Vielfache von 2 Bytes seien. Wenn n und p Vielfache von einem Byte sind, wird ein Null-Muster in die entsprechenden 8 Bitpositionen der Hr- und Ht-Register geladen.
Die oben beschriebene Erfindung ist besonders gut für Anwendungen in Übertragungssteuereinrichtungen geeignet, bei denen jede empfangene Nachricht konventionell erst zusammengesetzt wird, dann auf Gültigkeit überprüft (FCSr) und schließlich ohne FCSr solange gespeichert wird, bis sie an ihr Ziel, möglicherweise über weitere Übertragungssteuereinrichtungen weitergesendet wird. Vor dem Weitersenden muß eine neue FCS (d. h. FCSt) berechnet und mit dem abzusendenden Datenblock verbunden werden. Wie aus der folgenden Beschreibung einer Ausführungsform klar wird, reduziert die Erfindung nicht nur die erforderliche Rechnerkapazität, sondern ermöglicht auch an der Empfangsstation die Überprüfung der Gültigkeit des gesamten empfangenen Datenblockes und somit die Erkennung jeder Änderung der Daten, die auf ihrem Weg in den Übertragungssteuereinrichtungen zwischengespeichert waren.
In Fig. 6 ist ein Blockschaltbild der vorliegenden Erfindung dargestellt, wie sie in einer Übertragungssteuereinrichtung implementiert ist. Die Elemente der Steuereinrichtung, die innerhalb der vorliegenden Erfindung enthalten sind, umfassen eine Abtasteinrichtung 80, einen Übertragungssteuereinrichtungs- (USE)-Speicher 82 und einen Verarbeitungsrechner 84. Die eingehenden und herauslaufenden Nachrichtenverbindungen sind an die Abtasteinrichtung 80 angeschlossen, die die eingehenden Verbindungen abtastet, um die empfangenen Bits zu erkennen und diese in SDLC/HDLC-Datenblöcke zusammenzusetzen. Die empfangene Nachricht enthält Daten, die Kopfzeile O(x), FCSr und Markierungszeichen, wobei Kopfzeile hier den Teil der SDLC/HDLC-Nachricht bezeichnet, der zur Steuerung des Leitweges des Datenblockes zu modifizieren ist. Die Markierungszeichen, die sobald der Datenblock zusammengesetzt ist, entfernt werden, sind in der Figur nicht mit dargestellt worden. Jeder empfangene Datenblock wird, bevor er unter Steuerung des Verarbeitungsrechners über die entsprechende herausgehende Verbindung weitergesendet wird, in einem Speicher 82 durch den Verarbeitungsrechner 84 an einer bestimmten Position gespeichert, die der entsprechenden Verbindung zugeordnet ist. Der Verarbeitungsrechner muß nicht nur die herausgehende Verbindung zuweisen, sondern auch den SDLC/HDLC-Block mit Markierungszeichen, Daten, der neuen Kopfzeile (N(x)) und der neuen FCS (FCSt) rekonstruieren. Die neue Kopfzeile wird durch den Verarbeitungsrechner bestimmt, um die neue Leitweginformation, d. h. die Identifikation des nächsten Knotens im Nachrichtennetz, einzufügen. Die neue FCS wird im Verarbeitungsrechner berechnet. Der Verarbeitungsrechner berücksichtigt die Stelle (n) der Kopfzeilenbyte, die zu modifizieren sind sowie deren neuen Inhalt N(x). Er kennt ebenfalls den betreffenden USE-Speicherplatz und holt von dort FCSr und O(x), um daraus die neue FCS (d. h. FCSt) zu erzeugen, die dem herausgehenden Datenblock zugeordnet werden muß. Die Bildung der neuen FCSt wird mit einer Geräterealisierung, wie sie in den Fig. 4 oder 5 dargestellt ist, durchgeführt.
Es ist klar, daß das Verfahren auf Kopfzeilen beliebiger Länge erweitert werden kann, indem der beschriebene Prozeß mehrmals wiederholt wird.

Claims

1. Verfahren zum Aktualisieren der Blockparitätssequenz (FCS) eines Datenblocks Mr(x), der einen Polynominformationsabschnitt I(x), der ungeändert gehalten werden soll, einen Polynomanfangsabschnitt Hr(x), der in Ht(x) geändert werden soll, wobei die FCS dem Rest der Polynomdivision von I(x) + Hr (x) durch einen vorher vorgegebenen Polynomgenerator G(x) des Grades 1 entspricht, die Operationen in dem Galoisfeld durchgeführt werden und das Verfahren aufweist

- Berechnen eines Differenz- oder Variationspolynoms

D(x) = Ht(x)-Hr(x)

- Berechnen einer Differential-FCS

dFCS(x) = Rest (D(x)·X¹, G(x))

- Hinzuaddieren der Differential-FCS zu der Original- FCSr(x), um die aktualisierte FCS, d. h. FCSt, zu erzeugen.

2. Verfahren nach Anspruch 1, bei welchem die Differential-FCS bitweise über das Differentialpolynom (D(x) berechnet wird.

3. Verfahren nach Anspruch 1, bei welchem der Polynomanfangsabschnitt ein zwei Bit langes Wort ist, das bei der n-ten Bitposition des Datenblocks (einschließlich der FCS) beginnt, und das Verfahren dadurch gekennzeichnet ist, daß die Berechnungsoperation für die Differential-FCS aufweist:

- Berechnen des Restes R(x) der Polynomdivision von X8n durch G(x), und

- Multiplizieren des Restes R(x) mit D'(x), wobei D'(x) das Polynom ist, so daß D(x) = D'(x) das Polynom ist, so daß

D(x) = D' (x)·x8n-16.

4. Verfahren nach Anspruch 3, bei welchem die genannte n-te Bitstelle in ihrer Binärform ausgedrückt ist:

mit n&sub1;=0 oder 1 und m das höchste Bitgewicht von n ist,

und die Berechnungsoperation für die Differential-FCS aufweist:

- Berechnen von "Bitresten" der Polynomdivision von x8·2i durch G(x) für jeden Wert von i = 0 bis m für den n&sub1;= 1,

- miteinander Multiplizieren der Bitreste, und

- Multiplizieren der Bitreste mit D'(x).

5. Verfahren nach Anspruch 4, bei welchem die "Bitreste" vorberechnet und gespeichert werden.

6. Einrichtung zum Aktualisieren der Blockparitätssequenz (FCS) eines Blocks Mr(x) mit einem Anfangsabschnitt Hr(X), der in einen neuen Anfangsabschnitt Ht(x) geändert werden soll, wobei die Einrichtung dadurch gekennzeichnet ist, daß sie aufweist:

- ein erstes Puffermittel zum Speichern von Mr(x)

- ein zweites Puffermittel (14) zum Speichern von Ht(x)

- ein erstes exklusives-ODER (XOR)-Mittel (13),

- Mittel, um ,dem ersten XOR-Mittel die Hr und H, zuzuführen und um daraus D(x) = Hr(x) OHt(x) zu gewinnen,

- ein FCS-Berechnungsmittel (16), das an den Ausgang des XOR-Mittels angeschlossen ist, um eine Differentialblockparitätssequenz (dFCS) zu berechnen:

dFCS(x) = Rest (D(x)·x¹, G(x)), und

ein zweites XOR-Mittel (15), das an das erste Puffermittel und an das FCS-Berechnungsmittel angeschlossen ist und die aktualisierte Blockparitätssequenz (FCSt) liefert.

7. Einrichtung zum Aktualisieren der Blockparitätssequenz (FCSr) eines Datenblockes auf FCSt, wobei der Datenblock einen variablen Anfang besitzt, der von einem O(x)-Polynom in ein N(x)-Polynom geändert werden soll, und der an der n-ten Bitposition des Blockes gelegen ist, wobei zum Aktualisieren ein Polynomgenerator (G(x) verwendet wird und die Einrichtung aufweist:

- erste XOR-Mittel (REG 6, REG 7, XOR) zur Durchführung von D'(x) = N(x) 0(x),

- ein Speichermittel (62), welches sogenannte Bitreste speichert, welche die Reste vorbestimmter Werte von x8·2i durch G(x) darstellen,

- ein Adressiermittel (50) zum Adressieren des Speichermittels,

- ein Mittel, um in das Adressiermittel einen binären Ausdruck

zu laden und um sequentiell zunächst die Bitreste für jeden Speicherplatz, der ni = 1 entspricht, auszulesen,

- ein mit dem Speichermittel (66) verbundenes erstes Multipliziermittel zum Multiplizieren der ausgelesenen Bitreste miteinander,

- ein zweiten Multipliziermittel, das an das erste Multipliziermittel und an das XOR-Mittel angeschlossen ist und D'(x) liefert, und

- ein Addiermittel (REG19), das an das zweite Multipliziermittel angeschlossen ist, um den Ausgang des zweiten Multiplizierers zu FCSr zu addieren und daraus FCSt zu erhalten.

8. Nachrichtennetz mit einer Übertragungssteuerung, wobei Nachrichtenblöcke Mr(x), einem variablen Anfang Hr(x) und einer Blockparitätssequenz FCSr(x) bestehen, umgesteuert werden sollen, wobei Hr(x) in Ht(x) umgewandelt und die Blockparitätssequenz entsprechend gesetzt wird, und dieses Nachrichtennetz dadurch gekennzeichnet ist, daß es Mittel zum Berechnen und zum Setzen der aktualisierten Blockparitätssequenz unter Verwendung eines Verfahrens nach einem der Ansprüche 1 bis 5 besitzt.