ARQ-Protokoll

ARQ-Protokolle (englisch Automatic Repeat reQuest, deutsch: „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 sogenannter ACK/NAK-Signale (Acknowledgement bzw. Negative Acknowledgement, d. h. korrekter Empfang bestätigt bzw. Wiederholungsanfrage). Gegebenenfalls wird eine gestörte Nachricht so lange erneut übertragen, bis sie den Empfänger ohne Fehler erreicht hat.

Folgende Protokolle, die sich hauptsächlich im erzielbaren Datendurchsatz unterscheiden, werden als grundlegend betrachtet:

• Stop-and-Wait
• Go-Back-N
• Selective Repeat

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 der Sender einen Datenblock (z. B. ein Paket) gesendet hat, muss er auf die Quittung (ACK) des Empfängers warten, bevor er den nächsten Datenblock senden kann. Falls er innerhalb einer bestimmten Zeitdauer (Timeout) keine Quittung empfängt, muss er den Datenblock noch einmal senden. Dazu werden für die Datenblocks und die Quittungen Sequenznummern verwendet. Der Sender vergibt dem ersten Datenblock mit einer Sequenznummer, der Empfänger quittiert den erfolgreichen Empfang eines Datenblocks mit einem ACK mit der Sequenznummer des nächsten erwarteten Datenblocks. Stop-and-Wait ist demnach ein Sonderfall des Sliding-Window-Verfahrens mit der Fenstergröße 1.

Beispielablauf (siehe Abbildung):

Ablauf eines Stop-and-Wait-Protokolls

1. Sender sendet ersten Datenblock mit der Sequenznummer 0
2. Empfänger bestätigt erfolgreichen Empfang mit einem ACK mit der Sequenznummer 1
3. Sender sendet nächsten Datenblock mit der Sequenznummer 1
4. Empfänger bestätigt erfolgreichen Empfang mit einem ACK mit der Sequenznummer 0
5. Sender sendet nächsten Datenblock mit der Sequenznummer 0
6. usw.

Ablauf bei Übertragungsfehlern

Empfängt der Sender innerhalb des Timeout keine positive (ACK) oder eine negative Quittierung (NAK), sendet er den Datenblock noch einmal.

Mögliche Fehlerfälle sind:

• Datenblock geht auf dem Weg zum Empfänger verloren (Paketverlust). Abbildung „Stop-and-Wait bei Datenblockverlust“.
• Quittierung geht auf dem Weg zum Sender verloren. Abbildung „Stop-and-Wait bei Verlust des ACK“.
• Quittierung kommt zu spät (nach Ablauf des Timeout) beim Sender an. Abbildung „Stop-and-Wait bei verspätetem ACK“.
• Empfänger sendet ein NAK, weil der Datenblock fehlerhaft ist. Abbildung „Stop-and-Wait bei NAK“.

• 
  Stop-and-Wait bei Datenblockverlust
• 
  Stop-and-Wait bei Verlust des ACK
• 
  Stop-and-Wait bei verspätetem ACK
• 
  Stop-and-Wait bei NAK

Datendurchsatz

Zeitdiagramm

Der Datendurchsatz lässt sich allgemein berechnen mit der Formel:

$\eta _{SW}={\frac {t_{Block}}{t_{AV}}}\cdot R_{C}$

mit $t_{AV}={\frac {t_{RTT}}{1-P_{ed}}}$ ergibt sich

$\eta _{SW}={\frac {t_{Block}}{t_{RTT}}}\cdot (1-P_{ed})\cdot R_{C}$

und weiter mit $t_{RTT}=t_{Block}+{\tau _{1}}+{t_{ACK}}+{\tau _{2}}$ und ${\tau _{1}}+{t_{ACK}}+{\tau _{2}}=t_{BB}$ ergibt sich

$\eta _{SW}={\frac {1-P_{ed}}{1+{\frac {t_{BB}}{t_{Block}}}}}\cdot R_{C}$

$\eta _{SW}$: Datendurchsatz

$R_{C}$: Informationsrate des verwendeten fehlererkennenden Codes

$t_{Block}$: Datenblockdauer

$t_{AV}$: Mittlere Übertragungsdauer eines Datenblocks

$t_{BB}$: Zeitdauer zwischen zwei Datenblöcken

$t_{ACK}$: Dauer der ACK-Nachricht

$t_{RTT}$: Round Trip Time

$\tau _{1}$: Laufzeit des Datenblocks durchs Netz

$\tau _{2}$: Laufzeit der ACK-Nachricht durchs Netz

${P_{ed}}$: Auftrittswahrscheinlichkeit eines vom Empfänger erkennbaren Fehlers im Datenblock

Beispielrechnung

Ein Sender sendet Datenblocks mit einer Größe von 1000 Byte über eine Übertragungsstrecke mit einer maximal möglichen Datenübertragungsrate von 2 Mbit/s. Dabei wird ein fehlererkennender Code mit einer Informationsrate von 7/8 verwendet. Die mittlere Round Trip Time beträgt 18 ms und die Datenblockverlustrate beträgt 1 %.

$\eta _{SW}={\frac {t_{Block}}{t_{RTT}}}\cdot (1-P_{ed})\cdot R_{C}$

mit $t_{Block}={\frac {IP-Paketgroesse}{Datenuebertragungsrate}}={\frac {1000Byte\cdot 8{\frac {bit}{Byte}}}{2Mbit/s}}=4ms$

$\eta _{SW}={\frac {4ms}{18ms}}\cdot (1-0,01)\cdot 7/8=0,1925$

Der Datendurchsatz entspricht 19,25 % der maximal möglichen Datenübertragungsrate: $0,1925\cdot 2Mbit/s=440kbit/s$.

Anwendungsbeispiel

Ein Beispiel für ein Stop-and-Wait-Protokoll ist das Trivial File Transfer Protocol (TFTP).

Go-Back-N

Go-Back-N (engl. für Gehe zu N zurück) ist ein Sliding-Window-Verfahren, das gegenüber Stop-and-Wait einen deutlich größeren Datendurchsatz ermöglicht.

Der Sender kann dabei mehrere Datenblocks senden, ohne zunächst auf Quittungen vom Empfänger warten zu müssen. Wie viele Datenblocks hintereinander ohne Bestätigung versendet werden, hängt von der sogenannten „Fenstergröße“ des Sliding Window ab, die vorab von einem Flusskontrollverfahren bestimmt wird. Beträgt die Fenstergröße n, kann der Sender noch n-1 weitere Datenblocks absenden, bevor die Bestätigung für den ersten Datenblock durch den Empfänger erfolgt sein muss. Es können vom Empfänger auch mehrere Datenblocks 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 und sendet diesen und auch alle nach diesem gesendete Datenblocks erneut. Da es der Fall sein kann, dass lediglich ein Datenblock nicht ordnungsgemäß übertragen wurde und dennoch auch alle danach gesendeten erneut übertragen werden, wird an dieser Stelle Übertragungskapazität verschwendet. Beim Sender wird zum Zwischenspeichern der gesendeten und noch nicht quittierten Datenblocks Speicher benötigt. Die erforderliche Größe dieses Pufferspeichers hängt von der Datenblock- und der Fenstergröße ab.

Ein Beispiel für ein Go-Back-N-Protokoll ist das Transmission Control Protocol (TCP).

Selective Repeat

Selective Repeat (engl. für Selektive Wiederholung) ist eine weitere Fehlerbehandlungsstrategie auf Basis des Sliding-Window-Verfahrens. 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 übergeben. 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.

Ein Beispiel für ein Selectiv-Repeat-Protokoll ist die Erweiterung „SACK“ für das Transmission Control Protocol (TCP).

Literatur

• Tanenbaum, Feamster, Wetherall: Computer Networks. Sixth Edition., Pearson Global Edition, 2021, ISBN 978-1-292-37406-2.
• Badach, Hoffmann: Technik der IP-Netze. 4. Auflage. Hanser, ISBN 978-3-446-46210-6.
• Harald Orlamünder: Paket-basierte Kommunikationsprotokolle. 1. Auflage. Hüthig, Bonn 2005, ISBN 3-8266-5046-8.

Weblinks

• Simulation von Selective-Repeat und Go-Back-N als Website. tkn.tu-berlin.de
• Simulation von Go-Back-N als Java-Applet. pearsoncmg.com
• Simulation von Selective-Repeat als Java-Applet. pearsoncmg.com