imported>PerfektesChaos: tk k

2023-07-06T19:12:25Z

tk k

Neue Seite

'''ARQ-Protokolle''' ({{enS|Automatic Repeat reQuest}},<ref>{{RFC-Internet |RFC=3366 |Titel=Advice to link designers on link Automatic Repeat reQuest (ARQ) |Datum=2002-08}}</ref> deutsch: „Automatische Wiederholungsanfrage“) werden bei [[Rechnernetz|Computernetzen]] eingesetzt, um eine zuverlässige [[Datenübertragung]] durch Sendewiederholungen zu gewährleisten.

Durch die Möglichkeit der [[Fehlerkorrekturverfahren|Fehlererkennung]] kann ein [[Empfänger (Information)|Empfänger]] aufgetretene Übertragungsfehler feststellen. Über einen Rückkanal kann dieser dem [[Absender|Sender]] der Nachricht das Resultat der Fehlererkennung mitteilen. Gewöhnlicherweise geschieht dies durch Übertragung sogenannter ''[[ACK (Signal)|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 [[Netzwerkprotokoll|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<ref>[https://datatracker.ietf.org/doc/html/draft-li-rtgwg-protocol-assisted-protocol-02 ''Protocol Assisted Protocol (PAP)''.] [[Internet Engineering Task Force|IETF]] Internet-Draft, März 2020</ref>) stellt das einfachste Verfahren dar: Nachdem der Sender einen [[Datenblock]] (z. B. ein [[Datenpaket|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 [[Zeitintervall|Zeitdauer]] ([[Timeout (Netzwerktechnik)|Timeout]]) keine Quittung empfängt, muss er den Datenblock noch einmal senden. Dazu werden für die Datenblocks und die Quittungen [[Sequenznummer]]n 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|Sliding-Window-Verfahrens]] mit der Fenstergröße 1.

Beispielablauf (siehe Abbildung):
[[Datei:Stop-and-Wait-Normal.svg|mini|Ablauf eines Stop-and-Wait-Protokolls]]
# Sender sendet ersten Datenblock mit der Sequenznummer 0
# Empfänger bestätigt erfolgreichen Empfang mit einem ACK mit der Sequenznummer 1
# Sender sendet nächsten Datenblock mit der Sequenznummer 1
# Empfänger bestätigt erfolgreichen Empfang mit einem ACK mit der Sequenznummer 0
# Sender sendet nächsten Datenblock mit der Sequenznummer 0
# 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“.
<gallery>
Stop-and-Wait-Datenblockverlust.svg|Stop-and-Wait bei Datenblockverlust
Stop-and-Wait-ACK-Verlust.svg|Stop-and-Wait bei Verlust des ACK
Stop-and-Wait-ACK-zuspaet.svg|Stop-and-Wait bei verspätetem ACK
Stop-and-Wait-NAK.svg|Stop-and-Wait bei NAK
</gallery>

=== Datendurchsatz ===
[[Datei:Stop-and-Wait-Zeiten.svg|mini|Zeitdiagramm]]
Der Datendurchsatz lässt sich allgemein berechnen mit der Formel:
: <math>\eta_{SW} = \frac{t_{Block}}{t_{AV}} \cdot R_C </math>
:: mit <math>t_{AV} = \frac{t_{RTT}}{1-P_{ed}} </math> ergibt sich
: <math>\eta_{SW} = \frac{t_{Block}}{t_{RTT}} \cdot (1-P_{ed}) \cdot R_C </math>
:: und weiter mit <math>t_{RTT} = t_{Block}+{\tau_1}+{t_{ACK}}+{\tau_2}</math> und <math>{\tau_1}+{t_{ACK}}+{\tau_2}=t_{BB}</math> ergibt sich
: <math>\eta_{SW} = \frac{1-P_{ed}}{1+\frac{t_{BB}}{t_{Block}}} \cdot R_C </math>

:<math>\eta_{SW}</math>: Datendurchsatz
:<math>R_C </math>: [[Informationsrate]] des verwendeten fehlererkennenden [[Code]]s
:<math>t_{Block} </math>: Datenblockdauer
:<math>t_{AV} </math>: Mittlere Übertragungsdauer eines Datenblocks
:<math>t_{BB} </math>: Zeitdauer zwischen zwei Datenblöcken
:<math>t_{ACK} </math>: Dauer der ACK-Nachricht
:<math>t_{RTT} </math>: [[Paketumlaufzeit|Round Trip Time]]
:<math>\tau_1 </math>: [[Verzögerung (Telekommunikation)|Laufzeit]] des Datenblocks durchs Netz
:<math>\tau_2 </math>: Laufzeit der ACK-Nachricht durchs Netz
:<math>{P_{ed}} </math>: 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 %.
: <math>\eta_{SW} = \frac{t_{Block}}{t_{RTT}} \cdot (1-P_{ed}) \cdot R_C </math>
:: mit <math>t_{Block} = \frac{IP-Paketgroesse}{Datenuebertragungsrate} = \frac{1000 Byte \cdot 8 \frac{bit}{Byte}}{2 Mbit/s} = 4 ms</math>
: <math>\eta_{SW} = \frac{4ms}{18ms} \cdot (1-0,01) \cdot 7/8 = 0,1925</math>
Der Datendurchsatz entspricht 19,25 % der maximal möglichen Datenübertragungsrate: <math>0,1925 \cdot 2 Mbit/s = 440 kbit/s</math>.

=== 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|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 [[Datenflusssteuerung|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 [[Puffer (Informatik)|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 [[hybrid]]en ARQ-Protokollen.

Ein Beispiel für ein Selectiv-Repeat-Protokoll ist die Erweiterung „[[SACK]]“ für das [[Transmission Control Protocol]] (TCP).<ref>{{RFC-Internet |RFC=2018 |Titel=TCP Selective Acknowledgment Options |Datum=1996-10}}</ref>

== 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 ==
* [https://www2.tkn.tu-berlin.de/teaching/rn/animations/gbn_sr/ Simulation von Selective-Repeat und Go-Back-N als Website.] tkn.tu-berlin.de
* [https://media.pearsoncmg.com/aw/aw_kurose_network_2/applets/go-back-n/go-back-n.html Simulation von Go-Back-N als Java-Applet.] pearsoncmg.com
* [https://media.pearsoncmg.com/aw/aw_kurose_network_3/applets/SelectRepeat/SR.html Simulation von Selective-Repeat als Java-Applet.] pearsoncmg.com

== Einzelnachweise ==
<references />

[[Kategorie:Netzwerkprotokoll]]
[[Kategorie:Übertragungstechnik]]

ARQ-Protokoll - Versionsgeschichte

imported>PerfektesChaos: tk k