Netzwerk-Know-how (tecCHANNEL COMPACT) Kapitel 2: Rechner-zu-Rechner-Verbindung
Veröffentlicht: 22. Jun 2005
Von PROF. DR. STEPHAN EULER
Die einfachste Form
eines Netzwerks ist die direkte Verbindung zwischen zwei Computern. Sie eignet sich gut, um die grundlegenden Standards und Anforderungen bei der Datenübertragung zu erläutern.
Auf dieser Seite |
In diesem Beitrag |
|---|---|
|
|
.png "Dn151195.ACDCF196BC98A92A7E35715F19C8C405(de-de,TechNet.10).png")
Übertragung von BitsÜbertragung von Bits
Das einfachste Modell für eine Übertragung ist eine Leitung, auf der ein Signal zwei Zustände annehmen kann. Dieses Signal bewegt sich mit der Ausbreitungsgeschwindigkeit vom Sender zum Empfänger. Die Dauer eines einzelnen Zustandes bestimmt die erreichbare Übertragungsrate. Bei einer Dauer dt kann man pro Sekunde 1/dt Zustände übermitteln.
.png "Dn151195.474A051C84BBB1F86514567AC7903D18(de-de,TechNet.10).png")
Bild 1: Folge von Bits mit den Werten 0 und 1.
Bei einer elektrischen Leitung werden die beiden Zustände beispielsweise durch zwei verschiedene Spannungen realisiert. Die beiden Zustände seien als low und high bezeichnet. Über diese Leitung sollen Daten übertragen werden. Dazu muss eine Zuordnung der Bits zu den Zuständen getroffen werden - die Kodierung. Die nahe liegende Vereinbarung ist, für den Wert 1 das Signal high und für 0 low zu übertragen. Bild 1 zeigt für eine Folge von 0-1-Werten die Zustände in zeitlicher Folge. Aus den im Folgenden genannten Gründen nennt man diese Art der Kodierung Non-Return to Zero (NRZ).
.png "Dn151195.590B5404BFEA7F06684DB47B00539355(de-de,TechNet.10).png")
Zum Seitenanfang
Probleme bei der Übertragung
Einen etwas allgemeineren Fall zeigt Bild 2. Folgen mehrere gleiche Werte aufeinander, bleibt das Signal auf einem festen Pegel und es findet kein Wechsel mehr statt. Wenn beispielsweise der Sender eine lange Folge von Nullen schickt, sieht der Empfänger für die entsprechende Zeitdauer einen konstanten Pegel. Dann kann es schwierig werden, exakt zu zählen, wie viele Nullen geschickt wurden.
Falls Sender und Empfänger keine gemeinsame Zeitbasis haben, können kleine Abweichungen in der Zeitmessung zwischen beiden dazu führen, dass der Empfänger zu wenige oder zu viele Nullen zählt. Im Normalfall - das heißt, wenn keine zu langen Folgen mit konstanten Werten auftreten - kann der Empfänger kleine Abweichungen kompensieren, indem er die Signalwechsel nutzt, um sich immer wieder auf den Sender zu synchronisieren (Taktregenerierung).
.png "Dn151195.FEBEE8A9A9EEE89E8D85EED1FDC902CE(de-de,TechNet.10).png")
Bild 2: Allgemeine Folge von Bits.
Andererseits können Taktfehler weit reichende Folgen haben, wenn man zum Beispiel die Übertragung eines Stroms von Bytes betrachtet. Sobald ein Bit verloren geht, verschiebt sich für alle nachfolgenden Werte die Zuordnung der Bits zu den Bytes, so dass sich komplett andere Byte-Werte ergeben.
Zum Seitenanfang
Kodierung als Lösung
Es ist daher sinnvoll dafür zu sorgen, dass auch bei konstanten Werten Signalwechsel stattfinden. Ein Ansatz dazu ist die Kodierung Non-Return to Zero Inverted (NRZI). Dabei gilt die Regel, dass bei einer 1 der Pegel sich ändert, das heißt von low auf high oder von high auf low springt. Dadurch wird aus der Folge 0 1 1 1 1 die Signalfolge low high low high low. NRZI löst das Problem von vielen aufeinander folgenden Einsen, hilft aber nicht bei langen Folgen von Nullen.
Ein weitergehender Ansatz ist die Manchester-Kodierung. Man kann sich dabei die Übertragung mit doppelter Rate vorstellen, das heißt für jeden Wert stehen zwei Zeiteinheiten zur Verfügung. Dann überträgt man die Folge low-high für 0 und high-low für 1. So ist gewährleistet, dass für jeden übertragenen Wert mindestens ein Signalwechsel stattfindet. Nachteil ist, dass jetzt für jeden Wert zwei Zeiteinheiten gebraucht werden oder, umgekehrt, in der gleichen Zeit nur halb so viele Werte übertragen werden können. Von den vier möglichen Signalfolgen werden nur noch zwei verwendet.
Es gibt eine ganze Reihe weiterer Schemata für die Kodierung, die auf diesen Ideen beruhen. Der verbreitete 4B5B-Code überträgt 4 Bit mit 5 Signalwerten. Die Zuordnung ist dabei so gewählt, dass nie mehr als 3 Nullen hintereinander kommen. Zusammen mit einer NRZI-Kodierung ermöglicht der Code bei nur geringem Mehraufwand (20 %) eine deutliche Verbesserung der Taktregenerierung.
In diesem Zusammenhang wird oft das Maß Baud (Bd) benutzt. Die Einheit ist benannt nach dem französischen Ingenieur Baudot 1 ,der den Baudot-Code - den Vorläufer des ASCII-Codes - entwickelte. Die Anzahl der pro Sekunde erfolgten Übertragungen bezeichnet man als Baudrate. Wenn mit jeder Übertragung genau ein Bit dargestellt wird, entspricht die Baudrate dem Maß Bit/s. Anderseits sind bei der Manchester-Kodierung zwei Übertragungen pro Bit notwendig. Damit ist die Baudrate doppelt so hoch wie die Anzahl der Bits pro Sekunde. Können bei der Übertragung mehr als nur zwei Zustände unterschieden werden, ist umgekehrt die Baudrate kleiner als die Zahl der Bits pro Sekunde.
Zum Seitenanfang
Rahmenerstellung
Die Übertragung von Bits ist stets auch bis zu einem gewissen Grad fehleranfällig. Neben den bereits besprochenen Synchronisationsfehlern können einzelne Bits falsch dekodiert werden. Solche Fehler sind in einem kontinuierlichen Datenstrom nicht zu erkennen. Es ist daher wichtig, den Datenstrom zu strukturieren und durch Zusatzinformationen unempfindlich gegen Störungen zu machen. Weiterhin ist bei Rechnernetzen die kontinuierliche Übertragung eher die Ausnahme. Bei typischen Anwendungen (zum Beispiel Surfen im Internet) wechseln sich Phasen von Datenübertragungen - aus Sicht des Kommunikationskanals - mit Ruhephasen ab. Daher muss der Beginn einer neuen Übertragung kenntlich gemacht werden.
Aus diesen Gründen werden mehrere Bits oder Bytes zusammengefasst, um entsprechende Informationen ergänzt und als Einheit übertragen. Man spricht dann von Rahmen oder Frames. Dabei ist zwischen Byte-orientierten und Bit-orientierten Protokollen zu unterscheiden, je nach dem, ob Bytes oder Bits als kleinste Bausteine für einen Frame zum Einsatz kommen.
Bei klassischen Kommunikationsanwendungen wie Telefonie ist die Übertragungsrate fest, so dass sich der Datenstrom gut in eine Reihe gleich großer Rahmen aufteilen lässt. Wenn eventuell am Ende der Übertragung ein Rahmen nicht mehr komplett gefüllt wird, kann man problemlos mit Nullen auffüllen. Die dadurch entstehende kleine Pause stört nicht. Demgegenüber ist die Rechnerkommunikation durch starke Schwankungen in der Übertragungsrate gekennzeichnet. Außerdem ist das Auffüllen des letzten Rahmens beispielsweise beim Kopieren einer Datei nicht akzeptabel. Daher werden in der Regel Rahmenformate für eine variable Anzahl von Daten eingesetzt. Hierzu muss der Sender dem Empfänger mitteilen, wie viele Daten im aktuellen Rahmen enthalten sind. Zwei Verfahren werden dazu benutzt: Verwendung einer Endmarkierung oder explizite Angabe der Anzahl der Daten. Zusammengefasst lassen sich daher folgende Methoden der Rahmenbildung unterscheiden:
- Feste Anzahl von Nutzdaten
- Variable Anzahl von Nutzdaten
- Markierung des Endes der Nutzdaten
- Angabe der Anzahl der Nutzdaten im aktuellen Frame
Im Folgenden diskutieren wir am Beispiel von Byte-orientierten Protokollen die beiden Verfahren zur Erstellung von Rahmen mit einer variablen Anzahl von Daten-Bytes.
Zum Seitenanfang
Markierungszeichen
Bei der Übertragung von Texten verwendet man die im ASCII-Standard definierten Steuerzeichen zum Aufbau von Rahmen. Ein einfacher Rahmen könnte dann folgende Form haben (Beispiel nach [1]):
[DLE] [STX] [Daten] [DLE] [ETX]
Die zeitliche Abfolge ist bei dieser Darstellung von links nach rechts, das heißt, das am weitesten links stehende Element wird zuerst gesendet. Das Zeichen DLE (Data Link Escape, ASCII Code 127) markiert den Beginn einer Steuersequenz. Anfang und Ende werden durch STX (Start of TeXt, ASCII Code 2) beziehungsweise ETX (End of TeXt, ASCII Code 3) gekennzeichnet. Eingebettet zwischen diesen beiden Steuersequenzen liegen die Nutzdaten.
Dieses Verfahren funktioniert bei der Übertragung von Textdaten problemlos. Bei beliebigen Binärdaten - Gleitkommazahlen, Bilder oder Ähnliches - besteht allerdings die Möglichkeit, dass die Endsequenz DLE ETX auch in den Nutzdaten auftritt:
[DLE] [STX] [...] [DLE] [ETX] [...] [DLE] [ETX]
Der Empfänger würde dann vorzeitig das Ende des Rahmens erkennen. Ein ähnliches Problem ist bei der Programmierung in C und verwandten Sprachen die Darstellung des Zeichens " als Teil einer Zeichenkette. Eine Lösung besteht in der Einfügung eines zusätzlichen Zeichens. Man kann etwa in den Daten vor jedem DLE ein zweites DLE einfügen:
[DLE] [STX] [...] [DLE] [DLE] [ETX] [...] [DLE] [ETX]
Durch dieses so genannte Zeichenstopfen (engl. character stuffing) wird sichergestellt, dass innerhalb des Datenfeldes nie ein einzelnes DLE erscheint. Vielmehr folgen stets zwei oder - allgemein betrachtet - eine gerade Anzahl von DLE-Zeichen aufeinander. Der Empfänger muss dann nur aus jedem Paar von DLE-Zeichen eines entfernen, um die gesendete Byte-Folge zu rekonstruieren.
Zum Seitenanfang
Zeichenzähler
Die zweite Methode zur Rahmenerzeugung beruht auf der Angabe der Anzahl der nachfolgenden Daten. Im einfachsten Fall wird ein Feld mit einem Zähler vor den Daten eingefügt:
[DLE] [STX] [Anzahl] [Daten]
In dem Anzahlfeld steht, wie viele Bytes Daten in diesem Rahmen noch kommen werden. Die Größe des Nutzfeldes ist dann durch die Größe des Anzahlfeldes beschränkt. Steht nur ein Byte für die Größenangabe zur Verfügung, so kann das Nutzfeld maximal 256 Bytes lang sein. In dieser einfachsten Form ist die Übertragung recht fehleranfällig. Tritt ein Fehler im Anzahlfeld auf, berechnet der Empfänger die Rahmengröße falsch. Es kann unter Umständen lange dauern, bis der Empfänger sich wieder auf einen korrekten Rahmenanfang synchronisiert. Man verwendet daher in der Regel den Zeichenzähler nur in Kombination mit anderen Methoden.
Zum Seitenanfang
Fehlererkennung
Im Allgemeinen ist die Übertragung über einen Kanal nicht fehlerfrei. Ein Rahmen kann daher fehlerhafte Daten enthalten. Wie im Artikel „Rechner-zu-Rechner-Verbindung, Teil 1“ beschrieben, können Fehler im Extremfall sogar dazu führen, dass das Rahmenende nicht richtig erkannt und damit auch der Empfang der nachfolgenden Rahmen gestört wird. Deshalb ist es wichtig, dass der Empfänger durch Analyse des Rahmens feststellen kann, ob Übertragungsfehler auftraten.
Bei optimaler Ausnutzung der Übertragungskapazität entspricht jedem Bitmuster ein gültiges Zeichen. Durch Übertragungsfehler werden dann aus gültigen Zeichen auch wieder „gültige" Zeichen. Der Empfänger kann dann nicht erkennen, ob Übertragungsfehler vorliegen. Um eine Fehlererkennung zu ermöglichen, muss die Übertragung so erweitert werden, dass Fehler zu ungültigen Zeichen (oder Rahmen) führen. Dazu fügt der Sender zusätzliche Informationen (Redundanz) in den Rahmen ein.
Eine Anwendung dieses Prinzips sind die Prüfzeichen bei wichtigen oder leicht zu verwechselnden Informationen wie Konto- und Kreditkartennummern oder die Internationale Standard Buchnummer (ISBN). Diese Nummern enthalten ein zusätzliches Zeichen, das nach einem vorgegebenen Algorithmus aus den anderen Stellen berechnet wird.
Auch in der sprachlichen Kommunikation setzen wir in schwierigen Fällen Redundanz ein. Ein Beispiel ist das Buchstabieren bei der Übermittlung von Namen. Noch mehr Redundanz kann man durch die Verwendung von Buchstabieralphabeten wie A wie Anton, B wie Berta ... erreichen. Die Eigennamen sind als längere Einheiten besser zu erkennen als die einzelnen Buchstaben.
Oft lassen sich nicht erkannte Fehler in der unteren Schicht auf einer höheren Schicht noch feststellen. Bei der Übermittlung einer Textdatei führen Übertragungsfehler mit einiger Wahrscheinlichkeit dazu, dass erkennbar falsche Wörter daraus resultieren. Diese Fehlererkennung ist aber nur auf Grund der Redundanz der Sprache möglich. Nicht jede Buchstabenfolge ergibt ein Wort in der jeweiligen Sprache, so dass Sprache auch ein Maß an Redundanz enthält.
Die Zusatzinformation als Sicherung gegen Fehler verringert die Nettoübertra-gungsrate. Daraus ergibt sich die Herausforderung, mit möglichst wenig Zusatzinformation eine zuverlässige Fehlererkennung zu ermöglichen.
Man unterscheidet dabei:
- Fehlererkennung: Der Empfänger kann erkennen, dass ein Rahmen fehlerhaft übertragen wurde.
- Fehlerkorrektur: Der Empfänger kann bis zu einem gewissen Grad erkannte Übertragungsfehler auch korrigieren.
Kommt nur eine Fehlererkennung zum Einsatz, muss der Empfänger im Fehlerfall den Sender auffordern, den Rahmen erneut zu schicken. Will man eine Fehlerkorrektur realisieren, muss mehr Sicherheitsinformation in den Rahmen eingebaut werden. Trotzdem ist auch damit nur ein Teil der Fehler zu reparieren. Enthält ein Rahmen zu viele Fehler, dann lässt sich die ursprüngliche Information nicht wieder herstellen.
Welches Verfahren effizienter in Hinblick auf die Sicherheit und die insgesamt erreichbare Nettodatenrate ist, hängt von dem Übertragungskanal ab. Dabei spielen sowohl die Auftrittswahrscheinlichkeit für einen Bitfehler als auch die statistische Verteilung der Fehler eine Rolle. Bei vielen Kanälen treten Fehler nicht gleichmäßig verteilt auf, sondern in Gruppen (Bursts). Wenn der Kanal in einem schlechten Zustand ist - zum Beispiel bei einer Funkverbindung in einem „Schatten" hinter einem Hochhaus - kommt es zu sehr viel mehr Fehlern als im Normalzustand. Dann scheitert die Fehlerkorrektur, und die entsprechenden Rahmen müssen verworfen werden.
Insgesamt ist die Fehlererkennung eine komplexe Aufgabe. Die eingesetzten Methoden erfordern ein tiefes Verständnis von Statistik und Informationstheorie. Letztere erlaubt auch Aussagen zu den theoretischen Grenzen für die Nachrichtenübertragung über einen gegebenen Kanal.
Im Folgenden werden ohne Anspruch auf mathematische Tiefe anhand von zwei wichtigen Beispielen einige grundsätzliche Prinzipien der Fehlererkennung dargestellt. Bei diesen beiden Verfahren bleiben die Daten unverändert und werden um zusätzliche Sicherungsdaten ergänzt.
Zum Seitenanfang
Parität
Eine weit verbreitete Methode zur Fehlererkennung ist das Einfügen von Paritätsbits. Dazu zählt man die Bits mit Wert 1 in dem Datenwort und fügt dann ein weiteres Bit hinzu, so dass bei der so genannten geraden Parität (even parity) insgesamt eine gerade Anzahl von Einsen entsteht. Bei ungerader Parität (odd parity) ist die Anzahl der gesetzten Bits ungerade. Das folgende Beispiel zeigt, was man für das ASCII-Zeichen C bei gerader Parität erhält.
.png "Dn151195.244CB637102ACE4A6EADFF1823B8DE38(de-de,TechNet.10).png")
Das zusätzliche Paritätsbit eignet sich sehr gut für ASCII-Zeichen. Wenn man sich auf den 7-Bit-Zeichensatz beschränkt, dann kann das achte Bit als Paritätsbit verwendet werden. Die Parität hat weiterhin den Vorteil, dass sich die Prüfung auch in Hardware ohne großen Aufwand mit hintereinander geschalteten XOR-Ele-menten realisieren lässt.
Von den mit acht Bit möglichen 256 Zeichen bleiben nach der Paritätsprüfung nur noch 128 gültige Zeichen übrig. Dabei gilt, dass sich zwei gültige Zeichen in mindestens zwei Bitpositionen unterscheiden. Ändert man nur ein Bit, so resultiert daraus ein ungültiges Zeichen. Man sagt, der Hamming2 -Abstand beträgt 2. Allgemein bedeutet ein Hamming-Abstand n, dass sich zwei Zeichen in mindestens n Positionen voneinander unterscheiden.
Mit einem Paritätsbit wird ein Fehler (oder allgemein eine ungerade Anzahl von Fehlern) innerhalb eines Bytes erkannt. Zwei Fehler kompensieren sich aber gegenseitig und führen wieder zu einem korrekten Paritätsbit. Betrachtet man einen Block - das heißt eine Anzahl aufeinander folgender Zeichen - gemeinsam, lässt sich die Sicherheit deutlich erhöhen. Dazu wird zu der beschriebenen Parität pro Zeichen eine zweite Parität pro Position in Zeitrichtung eingeführt. Zur Unterscheidung zur einfachen (eindimensionalen) Parität spricht man auch von zweidi-mensionaler Parität. Die Tabelle zeigt die zweidimensionale Parität am Beispiel der Zeichenfolge HALLO. Die Parität in Zeilen- und Spaltenrichtung heißt Quer-und Längsparität.
.png "Dn151195.515EF04E7A77770B2E7A49039B2C8344(de-de,TechNet.10).png")
Ein einzelner Fehler macht sich sowohl in einer Zeile als auch Spalte bemerkbar und ist damit korrigierbar. Zwei Fehler - selbst in unterschiedlichen Zeilen und Spalten - sind aber nicht mehr auszubessern. Allerdings lassen sich die Fehler relativ gut lokalisieren, und es gibt nur zwei Möglichkeiten, wo sie sich befinden können. Liegen die beiden Fehler zusätzlich in einer Zeile, stimmen alle Querparitäten. Die Fehler werden zwar durch die Längsparität detektiert, können aber nicht mehr korrigiert werden. Allgemein lassen sich alle 3-Bit-Fehler und auch die meisten 4-Bit-Fehler erkennen. Nur wenn die vier Fehler genau an den passenden Kreuzungspunkten liegen, stimmen wieder alle Quer- und Längsparitäten.
Die Paritätsprüfung zählt die vorkommenden Einsen und prüft, ob sich in Summe eine gerade Anzahl ergibt. Die Übertragung umfasst einen Block Daten und eine Anzahl von Paritätsinformationen:
[Datenbits] [Paritätsbits]
Der Empfänger kann dann durch die Prüf Operation auf dem Gesamtblock die Integrität testen. Dieses allgemeine Schema „Daten - Prüfinformation - Prüfoperation" lässt sich leicht verallgemeinern, indem man andere Prüfoperationen nutzt.
In Internet-Protokollen wird ein Verfahren mit einer Prüfsumme angewandt. Die Prüfoperation ist dabei eine Addition im Einerkomplement. Als Prüfinformation wird das Ergebnis dieser Addition an die Daten angehängt. Der Empfänger führt dann ebenfalls die Addition aus und vergleicht das Ergebnis mit der Prüfsumme. Dieses Verfahren ist einfach zu realisieren, bietet aber nicht sehr viel Schutz. Wesentlich mächtiger ist das Verfahren der zyklischen Redundanzprüfung.
Zum Seitenanfang
Zyklische Redundanzprüfung
Bei dem Verfahren der zyklischen Redundanzprüfung (Cyclic Redundancy Check CRC) ist die Prüfoperation im Prinzip eine Division. Betrachten wir zunächst ein Beispiel mit Dezimalzahlen. Übertragen werden soll eine große Dezimalzahl wie etwa 35628828297292. Weiterhin wählt man einen Divisor D aus. Nimmt man dafür beispielsweise den Wert 17 und führt die Division aus, so erhält man bei ganzzahliger Division (Modulo-Operator % in C) einen Rest von 8. Der Sender kann damit zu der großen Zahl als Prüfwert die 8 senden. Der Empfänger rechnet dann zur Kontrolle (35628828297292-8)%17. Bleibt bei der Division ein Rest übrig, so liegt ein Übertragungsfehler vor.
Schon an diesem einfachen Beispiel werden einige Grundeigenschaften deutlich. Zunächst einmal sind nicht alle Divisoren gleich gut geeignet für diesen Zweck. Beispielsweise wäre 10 ein schlechter Divisor, da sich dann nur Fehler an der letzten Stelle auswirken würden. Weiterhin wird ein größerer Divisor einen besseren Schutz bieten. Allerdings muss dann entsprechend mehr Platz für den Rest vorgehalten werden. Der Rest kann maximal den Wert D-l annehmen. Der Divisor selbst hat sinnvollerweise einen festen Wert und braucht dann nicht mehr übertragen zu werden.
Die Übertragung dieses Ansatzes auf Binärdaten beruht auf der Interpretation von Bitfolgen als Polynomen. Für eine Bitfolge abcdef schreibt man
.png "Dn151195.3FA3ABF5B6FE6726C4BC457D9B2BEE95(de-de,TechNet.10).png")
Dabei genügt es, die Terme mit Einsen anzugeben. Für die Bitfolge 100101 erhält man dann zum Beispiel
.png "Dn151195.D0F23C438DD7099B539F885BA3562B3A(de-de,TechNet.10).png")
Die Prüfbits werden durch eine Division von solchen Polynomen bestimmt. CRC benutzt eine polynomiale Modulo-2-Arithmetik. In dieser Arithmetik reduziert sich die Subtraktion auf eine XOR-Operation. Die Division lässt sich - wie bei der üblichen Division - durch fortgesetzte Subtraktion ausführen.
Es sei als Beispiel x3+x+l das Divisorpolynom und damit 1011 das zugehörige Bitmuster. Die Nachricht 110101101 ist zu übertragen. Zunächst wird sie entsprechend der höchsten Potenz im Divisor um drei Bits erweitert: 110101101000. Genau in diese zusätzlichen Bits kommen später die Prüfbits.
Der erste Schritt in der Division ist dann:
.png "Dn151195.F55CAF820F1C10F514AA49FC05D6BCFB(de-de,TechNet.10).png")
Das Ergebnis der Division wird nicht benötigt und daher nicht notiert. Dann wird die nächste Stelle von oben übernommen und der Divisor erneut subtrahiert:
.png "Dn151195.A2C34B242B47AA04F773F98DA5625FEA(de-de,TechNet.10).png")
Insgesamt ergibt sich
.png "Dn151195.B58413133CFAA8B7CB005F30C0BD4C73(de-de,TechNet.10).png")
Bei der Division bleibt ein Rest von 110. Zieht man diesen von der erweiterten Zahl ab, so ist die neue Zahl ohne Rest durch den Divisor teilbar. Da Subtraktion einer XOR-Operation entspricht, erhält man 110101101110. Diese um die drei Prüfbits erweiterte Bitfolge wird gesendet. Der Empfänger führt ebenfalls die Division durch. Falls dabei ein Rest übrig bleibt, liegt ein Übertragungsfehler vor.
Wie bei dem Beispiel mit den Dezimalzahlen gibt es auch für die Polynomdivision mehr oder weniger gut geeignete Divisorpolynome. In der Fachliteratur - beziehungsweise in den entsprechenden Spezifikationen - findet man jedoch schnell geeignete Polynome.
Man bezeichnet die Polynome in diesem Zusammenhang oft auch als Generatorpolynome. Einige davon sind unten in Tabelle 3.3 aufgelistet. Die Zahl nach dem Namen gibt an, wie viele Prüfbits jeweils genutzt werden. Details der Implementierung zusammen mit einer Realisierung in der Programmiersprache C findet man beispielsweise in [1].
.png "Dn151195.D0129B887C93C04BCED1EDD072755A13(de-de,TechNet.10).png")
Die Prüfverfahren schützen in allen Fällen, in denen die Anzahl der Bitfehler kleiner ist als die Anzahl der Prüfbits. Darüber hinaus werden auch die „meisten" anderen Fehler erkannt.
Im dritten und letzten Teil der Serie „Rechner-zu-Rechner-Verbindung“ widmen wir uns der sicheren Übertragung von Rahmen sowie dem Stop-and-Wait- und dem Sliding-Windows-Algorithmus.
Zum Seitenanfang
Sichere Übertragung von Rahmen
Wenn der Sender einen Rahmen abgeschickt hat, dauert es eine Weile, bis ihn der Empfänger erhalten und anschließend die Korrektheit festgestellt beziehungsweise wieder hergestellt hat.
Der Empfänger kann dann den Empfang quittieren, indem er dem Sender eine Bestätigung schickt. Insgesamt ergibt sich folgender Ablauf:
- Sender schickt Rahmen
- Empfänger wartet, bis der Rahmen vollständig angekommen ist
- Empfänger prüft Korrektheit
- Empfänger schickt Bestätigung
- Sender erhält Bestätigung
Dieser Zusammenhang ist in Bild 3 mit einem Zeitstrahl grafisch dargestellt. Rl bezeichnet den ersten Rahmen und ACK die Bestätigung (Acknowledgement). In dieser Darstellung ist beim Empfänger eine kleine Zeitspanne nach Erhalt des Rahmens zur Prüfung eingetragen. Diese Zeit wird zwar im Prinzip immer benötigt, im Folgenden wird sie aber zur Vereinfachung der Darstellung nicht mehr explizit eingetragen.
.png "Dn151195.1C424904F3108EA9B36044B362B54DE7(de-de,TechNet.10).png")
Bild 3: Zeitlicher Ablauf bei Bestätigung eines Rahmens R1
Zum Seitenanfang
Stop-and-Wait-Algorithmus
Eine direkte Implementierung des beschriebenen Verfahrens ist der Stop-and-Wait-Algorithmus. Der Sender schickt einen Rahmen und wartet auf die Bestätigung. Erhält er innerhalb einer gewissen Wartezeit keine Bestätigung, so geht er davon aus, dass der Rahmen verloren gegangen ist und schickt ihn erneut. Die Wartezeit bezeichnet man als Timeout. Damit ergibt sich Bild 4
.png "Dn151195.81A255AE00A42770F5BD40A4D9BCF430(de-de,TechNet.10).png")
Bild 4: Zeitlicher Ablauf beim Stop-and-Wait-Algorithmus.
Der Timeout soll dem Empfänger genügend Zeit zur Bestätigung lassen. Andererseits soll er aber so kurz wie möglich sein, um die Wartezeit bei einem verloren gegangenen Rahmen zu minimieren. Ein Problem tritt auf, wenn die Bestätigung zu spät oder gar nicht ankommt. Beim Sender ist mittlerweile der Timeout abgelaufen, und in der Annahme, dass der Rahmen nicht korrekt empfangen wurde, schickt der Sender ihn erneut. Der Empfänger hat andererseits den Rahmen bestätigt und erwartet nun bereits den nächsten. Ohne weitere Maßnahmen würde er den zum zweiten Mal geschickten Rahmen bereits als nächsten interpretieren.
Es ist daher eine Kennung für die einzelnen Rahmen nötig. Beim Stop-and-Wait-Algorithmus verwendet man in der Regel die einfachste Nummerierung mit 0 und 1. Falls ein Rahmen fälschlicherweise erneut geschickt wird, erkennt dies der Sender an seiner Nummer. Er kann daher den Rahmen ignorieren, muss aber natürlich eine Bestätigung schicken. Den vollständigen Ablauf zeigt Bild 5 In diesem Beispiel geht die Bestätigung für den Rahmen 0 verloren. Der Sender schickt ihn daher nochmals. Diesmal wird die Bestätigung ordnungsgemäß zugestellt, und der Sender geht zum nächsten Rahmen, der die Kennung 1 erhält.
.png "Dn151195.1A2180C1F433DA4105246EB2DA674801(de-de,TechNet.10).png")
Bild 5: Stop-and-Wait-Algorithmus mit Rahmennummer, Verlust einer Bestätigung
Zum Seitenanfang
Sliding-Window-Algorithmus
Im Stop-and-Wait-Algorithmus gibt es lange Pausen, in denen der Sender auf eine Bestätigung wartet. Daher wird der Kanal nur schlecht ausgenutzt. Eine bessere Auslastung lässt sich aber erreichen, indem der Empfänger bereits während der Wartezeit weitere Rahmen schickt. Zu jedem Zeitpunkt sind dann mehrere Rahmen auf der Leitung unterwegs, und der Sender wartet auf entsprechend viele ausstehende Bestätigungen.
.png "Dn151195.3140DE3002C42022DADB7211E64E4550(de-de,TechNet.10).png")
Bild 6: Sliding-Window-Algorithmus.
Der Sender nummeriert die Rahmen, so dass sie individuell bestätigt werden können. Die maximale Anzahl von gleichzeitig auf dem Weg befindlichen Frames -das Sendefenster (Send Window Size, SWS) - kann bei bekannter Leitungscharakteristik an die RTT der Leitung angepasst werden. Im Idealfall wird das Fenster dann so gewählt, dass der Timeout für den ersten Rahmen unmittelbar nach Abschicken des letzten Frames im Sendefenster abläuft. Der Sender muss alle Frames im Sendefenster vorrätig halten, um sie bei Bedarf nochmals senden zu können. Kommt die Bestätigung für den ersten Rahmen an, dann kann der Empfänger diesen löschen und das Sendefenster weiterschieben. Anderenfalls sendet er diesen Rahmen erneut.
Im Allgemeinen kommt es vor, dass zwar ein Rahmen verloren geht, aber die nachfolgenden Frames trotzdem ankommen. Eine gute Kanalauslastung erreicht man, wenn jeder angekommene Rahmen bestätigt wird (selektive Bestätigung, Englisch: selective acknowledgements). Allerdings ist dann der Aufwand in der Verwaltung des Sendefensters und des Empfangsfensters kompliziert. Geht beispielsweise ein bestimmter Rahmen mehrfach verloren, muss der Empfänger sehr viele neue Frames speichern, um diesen alten Rahmen an der richtigen Stelle einfügen zu können. Wenn erforderlich, kann der Empfänger den Sender bremsen, indem er Frames, die zu weit vor dem letzten fehlenden Rahmen liegen, nicht bestätigt oder zumindest die Bestätigung verzögert.
Die Arbeit des Senders wird wesentlich vereinfacht, wenn der Empfänger die aus der Reihe angekommenen Rahmen nicht bestätigt. Angenommen Rahmen 4 geht verloren oder wird stark verzögert. Der Empfänger erhält stattdessen bereits die folgenden Rahmen 5 und 6. Er bestätigt diese Rahmen aber nicht, sondern wartet auf den Rahmen 4 - entweder das verspätete Original oder die wieder gesendete zweite Version. Sobald Rahmen 4 ankommt, bestätigt der Empfänger den Frame 6. Bei entsprechendem Protokoll erkennt der Sender daraus, dass alle Rahmen bis zur Nummer 6 gut angekommen sind (kumulative Bestätigung). Er kann dann das Sendefenster auf die Position 7 weiterschieben.
Wenn tatsächlich Frames verloren gehen, wird bei diesem Verfahren der Kanal nicht optimal ausgenutzt. Der Sender schickt während des Wartens nach dem wiederholten Rahmen unnötigerweise auch die nachfolgenden Frames zum zweiten Mal. Andererseits ist in dieser Form die Verwaltung der Rahmen in Sende- und Empfangsfenster recht einfach. Die Nummer eines Rahmens (Sequenznummer) ist eine zusätzlich zu übertragende Information. Aus Effizienzgründen sollten möglichst wenige Bits für diese Nummer verbraucht werden. Die Sequenznummer ist daher auf einen relativ kleinen Bereich beschränkt. Sobald das Maximum erreicht ist, springt der Zähler wieder auf 0 zurück. Es muss allerdings gewährleistet sein, dass die Rahmen noch eindeutig identifiziert werden können.
Zum Seitenanfang
Literatur
[1] Andrew S. Tannenbaum. Computernetzwerke. Prentice Hall, 2000
[2] W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery. Numerical Recipes on C. Cambridge University Press 1992
Zum Seitenanfang