Fehlererkennung

Die Suche nach den verlorenen Rahmen

Mit den vorher beschriebenen Methoden können wir jetzt nach einer Übertragungsstörung feststellen wo ein Frame beginnt und aufhört.

Normalerweise kann man eine zuverlässige Übertragung gewährleisten, indem der Empfänger dem Sender eine Bestätigung über empfangene Rahmen sendet. Fernschreiber benutzten dafür zum Beispiel die ASCII-Zeichen ACK wie acknowledged für »Okay, schick mir den Nächsten.« und NACK wie not acknowledged für »Das war wohl nichts, noch mal bitte.«.

Gehen allerdings ganze Rahmen verloren, dann wartet der Empfänger bis in alle Ewigkeit auf den nächsten Frame, den der Sender nicht schickt, weil er auf eine Bestätigung wartet. Um das zu verhindern sind auf beiden Seiten Zeitnehmer notwendig, die nach einer bestimmten Leerlaufzeit nachfragen, was eigentlich los ist. In diesem Fall wird der Frame nochmals übertragen und wir stehen vor dem nächsten Problem..

Geht die Bestätigung verloren, dann wird der Frame mehrmals übertragen. Um das zu verhindern, werden die Rahmen durchnummeriert, so das der Empfänger statt einfach eine Neuübertragung anzufordern, gezielt nach einigen Rahmen fragen kann.

Das letzte Ärgernis das uns hier begegnen kann sind schnelle Sender. Sendet nämlich ein Sender schneller als der Empfänger die Daten verarbeiten kann, dann gehen Rahmen beim Empfänger verloren, während er versucht die Daten zu verarbeiten.

Die Lösung für dieses Problem heißt Flow-Control. Dafür gibt es verschiedene Methoden, aber meistens laufen sie darauf hinaus, das der Empfänger dem Sender sagt: »Schick mir die nächsten n Rahmen und dann warte bis ich mehr will.«

Man spricht in diesem Zusammenhang von einem Schiebefensterprotokoll (Sliding Windows Protocol). Die Fenstergröße entspricht dabei der maximalen Anzahl unbestätigter  Rahmen. Die Rahmen besitzen dabei Folgenummern von 0 - Fenstergröße -1. Läuft das Sendefenster voll, so muss der  Sender die Sendung auf der Sicherungsschicht blockieren, bis wieder Platz im Sendefenster ist, also bis mindestens ein Rahmen bestätigt worden ist.

Fehlererkennungsmethoden

Um einen fehlerhaft übertragenen Block noch einmal anfordern zu können, muss er zuerst einmal erkannt werden, aber woran soll der Empfänger erkennen, ob eine Gruppe von 0-en und 1-en bei ihm genauso angekommen ist, wie der Sender sie abgeschickt hat?

Die einfachste Methode ist die Übertragung mit

Parity

Dabei vereinbart man, das jede Gruppe von Bits eine gerade (even) oder eine ungerade (odd) Anzahl von 1-Bits enthält. Jetzt zählt man in jeder Gruppe von n (z.B. 8 ) Bits die 1-Bits und hängt je nachdem ob man eine gerade oder eine ungerade Anzahl von 1-Bits erhält eine 1, oder eine 0 an.

Kommt jetzt zum Beispiel bei vereinbarter gerader Parität ein Block von Bytes an, der eine ungerade Parität hat, dann wird er als fehlerhaft verworfen, und neu angefordert.

Auf diese Art können alle Fehler entdeckt werden, die eine ungerade Anzahl von Bits kippen, und vor allem die häufigsten, die Einbitfehler.

Gegen Fehler die eine gerade Anzahl von Bits kippen hilft ein einzelnes Paritybit natürlich nicht. Mit 2 Paritybits lassen sich auch alle Fälle von 2 gekippten Bits erkennen. 

Wesentlich verbreiteter sind Prüfsummenverfahren, insbesondere der

Cyclic Redundancy Check (CRC)

Der CRC ist ein Polynomcode. Er basiert darauf, das man Bitfolgen als Polynome mit den Koeffizienten 0 und 1 schreiben kann. Ein Frame mit k Bits wird als Polynom vom Grad k-1 betrachtet. Das werthöchste Bit ist der Koeffizient von x^k-1, das nächste Bit der Koeffizient für x^k-2, und so weiter.

Zum Beispiel wird die Bitkette 100101 dargestellt als

Die Grundidee dahinter ist, eine Prüfsumme an das Ende des zu übertragenden Rahmens anzuhängen, so das das Polynom das durch den geprüften Frame dargestellt wird, durch das Prüfpolynom teilbar ist. Erhält der Empfänger den geprüften Rahmen, so teilt er ihn durch das Prüfpolynom. Bleibt ein Rest so ist ein Übertragungsfehler aufgetreten.

Damit das Verfahren funktioniert müssen sich Sender und Empfänger auf ein Prüfpolynom, das auch das Generatorpolynom für die Prüfsumme genannt wird einigen. Dabei müssen sowohl das höchstwertige als auch das niederstwertige Bit 1 sein.

Der Algorithmus zur Berechnung der Prüfsumme sieht wie folgt aus:

1. Sei r der Grad des Generatorpolynoms G(x), sei m die Anzahl der Bits im Rahmen, sei M(x) das durch den Frame dargestellte Polynom. Hänge r Nullbits an der niederwertigen Seite des Frames an, so daß er nun m + r Bits enthält und dem Polynom x^rM(x) entspricht.
2. Teile die Bitkette die x^rM(x) entspricht anhand der Modulo-2-Division durch die Bitkette, die G(x) entspricht.
3. Ziehe den Rest (immer r Bit oder weniger ) mittels Modulo-2-Subtraktion (das entspricht einem bitweisen XOR ) von der Bitkette ab, die x^rM(x) entspricht. Das Ergebnis des summengeprüften Rahmens wird übertragen.