ARQ-Protokoll

ARQ-Protokolle (englisch Automatic Repeat reQuest, dt. Automatische Wiederholungsanfrage) werden bei Computernetzen eingesetzt, um eine zuverlässige Datenübertragung durch Sendewiederholungen zu gewährleisten.

Durch die Möglichkeit der Fehlererkennung kann ein Empfänger aufgetretene Übertragungsfehler feststellen. Über einen Rückkanal kann dieser dem Sender der Nachricht das Resultat der Fehlererkennung mitteilen. Gewöhnlicherweise geschieht dies durch Übertragung so genannter ACK/NAK Signale (Acknowledgement bzw. Negative Acknowledgement, d.h. korrekter Empfang bestätigt bzw. Wiederholungsanfrage). Gegebenenfalls wird eine gestörte Nachricht solange erneut übertragen, bis sie den Empfänger ohne Fehler erreicht hat.

Folgende Protokolle, welche sich hauptsächlich im erzielbaren Durchsatz unterscheiden, werden als grundlegend betrachtet:

Stop-and-Wait

Stop-and-Wait (engl. für Halte an und Warte, auch als Send-and-Wait bezeichnet) stellt das einfachste Verfahren dar: Nachdem er eine Dateneinheit gesendet hat, muss der Sender auf die Quittung warten, bevor er das nächste Paket senden kann. Falls er keine Quittung innerhalb eines bestimmten Zeitrahmens (Timeout) empfängt, muss er die Dateneinheit noch einmal senden.

$\eta_\text{SW} = \frac{k}{(n+\Gamma)\theta}= \frac{\eta_\text{max}}{1+\frac{\Gamma}{n}}$ mit $\eta_\text{max} = \frac{k}{n\theta}$ ; $\theta = \frac{1}{1-P_R}$

η_max: maximaler Durchsatz

k: Anzahl Informations-Bits

Γ: Anzahl an Bits während auf Acknowledge gewartet wird

θ: mittlere Anzahl an Übertragungsversuchen

P_R: Wahrscheinlichkeit für Übertragungswiederholung bei Fehler

Beispiel: TFTP, das Trivial File Transfer Protocol.

Go-Back-N

Go-Back-N (engl. für Gehe zu N zurück) stellt ein Verfahren dar, das im Gegensatz zu Stop-and-Wait einen deutlich größeren Durchsatz ermöglicht.

Der Sender kann dabei mehrere Dateneinheiten senden, ohne auf eine Quittung warten zu müssen. Wie viele das sind, hängt von der so genannten Fenstergröße ab. Beträgt diese n, kann der Sender noch n-1 weitere Dateneinheiten absenden, bevor die Bestätigung für die erste Einheit durch den Empfänger erfolgt sein muss. Es können vom Empfänger auch mehrere Dateneinheiten auf einmal (kumulativ) bestätigt werden, so zeigt eine Quittung für n+i an, dass alle Einheiten von n bis n+i korrekt empfangen wurden. Kommt es beim Warten auf die Bestätigungen zu einem Timeout, so übermittelt der Sender alle Dateneinheiten in dem Fenster neu. Er geht also zurück zur letzten unbestätigten Sequenznummer N. Da es der Fall sein kann, dass lediglich eine Dateneinheit nicht ordnungsgemäß übertragen wurde und dennoch auch alle danach gesendeten erneut übertragen werden, wird an dieser Stelle Übertragungskapazität verschwendet.

Die Zahl der Dateneinheiten, die ohne Bestätigung verschickt werden dürfen (also die Fenstergröße), wird von einem Flusskontrollverfahren bestimmt.

Beispiel: TCP, das Transmission Control Protocol.

Selective Repeat

(engl. für Selektive Wiederholung) Die andere allgemeine Fehlerbehandlungsstrategie bei ARQ-Protokollen ist Selektive Wiederholung. Hier wird ein fehlerhafter Rahmen verworfen, aber die danach erhaltenen Rahmen werden im Empfänger in einem Puffer abgelegt und bestätigt. Wenn beim Sender die Zeit abgelaufen ist, wird nur der älteste nicht bestätigte Rahmen erneut übertragen. Wenn dieser Rahmen korrekt ankommt, kann der Empfänger in der Folge alle im Puffer gespeicherten Rahmen an die Vermittlungsschicht übertragen. Die selektive Wiederholung wird oft mit dem Senden einer negativen Bestätigung (NAK, Negative Acknowledgement) durch den Empfänger kombiniert, wenn dieser einen Fehler wie einen Prüfsummenfehler oder einen Rahmen außerhalb der Reihenfolge entdeckt. NAKs stoßen die erneute Übertragung an, bevor der entsprechende Timer abläuft und verbessern daher die Leistung. Geht das NAK verloren, wartet der Sender auf den Timeout für den Rahmen und sendet ihn (und zwar nur ihn) auf eigene Veranlassung noch einmal. Die selektive Wiederholung entspricht einem Empfangsfenster größer 1.

Werden diese Protokolle mit den Methoden der Kanalkodierung kombiniert, so spricht man von den hybriden ARQ-Protokollen.

Beispiel: TCP SACK

Weblinks

• Simulation von Go-Back-N als Java-Applet
• Simulation von Selective-Repeat als Java-Applet
• Flash-Simulation Go-Back-N (mehrere Fehlersituationen)